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:
“... today we round out the first century of a professed republic,—with woman figuratively representing freedom—and yet all free, save woman.”
—Phoebe W. Couzins (1845–1913)
“Nobody is so constituted as to be able to live everywhere and anywhere; and he who has great duties to perform, which lay claim to all his strength, has, in this respect, a very limited choice. The influence of climate upon the bodily functions ... extends so far, that a blunder in the choice of locality and climate is able not only to alienate a man from his actual duty, but also to withhold it from him altogether, so that he never even comes face to face with it.”
—Friedrich Nietzsche (1844–1900)