Power Set - Representing Subsets As Functions

Representing Subsets As Functions

In set theory, XY is the set of all functions from Y to X. As "2" can be defined as {0,1} (see natural number), 2S (i.e., {0,1}S) is the set of all functions from S to {0,1}. By identifying a function in 2S with the corresponding preimage of 1, we see that there is a bijection between 2S and, where each function is the characteristic function of the subset in with which it is identified. Hence 2S and could be considered identical set-theoretically. (Thus there are two distinct notational motivations for denoting the power set by 2S: the fact that this function-representation of subsets makes it a special case of the XY notation and the property, mentioned above, that |2S| = 2|S|.)

This notion can be applied to the example above in which to see the isomorphism with the binary numbers from 0 to 2n−1 with n being the number of elements in the set. In S, a 1 in the position corresponding to the location in the set indicates the presence of the element. So {x, y} = 110.

For the whole power set of S we get:

  • { } = 000 (Binary) = 0 (Decimal)
  • {x} = 100 = 4
  • {y} = 010 = 2
  • {z} = 001 = 1
  • {x, y} = 110 = 6
  • {x, z} = 101 = 5
  • {y, z} = 011 = 3
  • {x, y, z} = 111 = 7

Read more about this topic:  Power Set

Famous quotes containing the words representing and/or functions:

    There are people who are so presumptuous that they know no other way to praise a greatness that they publicly admire than by representing it as a preliminary stage and bridge leading to themselves.
    Friedrich Nietzsche (1844–1900)

    In today’s world parents find themselves at the mercy of a society which imposes pressures and priorities that allow neither time nor place for meaningful activities and relations between children and adults, which downgrade the role of parents and the functions of parenthood, and which prevent the parent from doing things he wants to do as a guide, friend, and companion to his children.
    Urie Bronfenbrenner (b. 1917)