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)
“When Western people train the mind, the focus is generally on the left hemisphere of the cortex, which is the portion of the brain that is concerned with words and numbers. We enhance the logical, bounded, linear functions of the mind. In the East, exercises of this sort are for the purpose of getting in tune with the unconscious—to get rid of boundaries, not to create them.”
—Edward T. Hall (b. 1914)