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:
“He who has learned what is commonly considered the whole art of painting, that is, the art of representing any natural object faithfully, has as yet only learned the language by which his thoughts are to be expressed.”
—John Ruskin (1819–1900)
“One of the most highly valued functions of used parents these days is to be the villains of their children’s lives, the people the child blames for any shortcomings or disappointments. But if your identity comes from your parents’ failings, then you remain forever a member of the child generation, stuck and unable to move on to an adulthood in which you identify yourself in terms of what you do, not what has been done to you.”
—Frank Pittman (20th century)