Power set
Representing subsets as functions

In set theory, X is the notation representing the set of all functions from Y to X. As " 2 " can be defined as {0, 1} (see, for example, von Neumann ordinals), 2 (i.e., {0, 1}) is the set of all functions from S to {0, 1}. As shown above, 2 and the power set of S, P (S), are considered identical set-theoretically.

This equivalence can be applied to the example above, in which S = { x, y, z }, to get the isomorphism with the binary representations of numbers from 0 to 2 − 1, with n being the number of elements in the set S or | S | = n. First, the enumerated set { (x, 1), (y, 2), (z, 3) } is defined in which the number in each ordered pair represents the position of the paired element of S in a sequence of binary digits such as { x, y } = 011; x of S is located at the first from the right of this sequence and y is at the second from the right, and 1 in the sequence means the element of S corresponding to the position of it in the sequence exists in the subset of S for the sequence while 0 means it does not.

For the whole power set of S, we get:

Such an injective mapping from P (S) to integers is arbitrary, so this representation of all the subsets of S is not unique, but the sort order of the enumerated set does not change its cardinality. (E.g., { (y, 1), (z, 2), (x, 3) } can be used to construct another injective mapping from P (S) to the integers without changing the number of one-to-one correspondences.)

However, such finite binary representation is only possible if S can be enumerated. (In this example, x, y, and z are enumerated with 1, 2, and 3 respectively as the position of binary digit sequences.) The enumeration is possible even if S has an infinite cardinality (i.e., the number of elements in S is infinite), such as the set of integers or rationals, but not possible for example if S is the set of real numbers, in which case we cannot enumerate all irrational numbers.
oulipo:avoid_letter[e]