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)
“Mark the babe
Not long accustomed to this breathing world;
One that hath barely learned to shape a smile,
Though yet irrational of soul, to grasp
With tiny finger—to let fall a tear;
And, as the heavy cloud of sleep dissolves,
To stretch his limbs, bemocking, as might seem,
The outward functions of intelligent man.”
—William Wordsworth (1770–1850)