Power Sets come in Small, Infinite and Even Larger Sizes

By

Home / Power Sets come in Small, Infinite and Even Larger Sizes

Last Updated on

What is a power set?

The definition of a power set is, “The power set of a given set S is the set of all subsets of S.” The power set of S is shown as P  (S), or 2S. Let’s save a thousand words and just refer to the image.

Chart Listing Small Power Sets: Image by Mike DeHaan

A Refresher about Sets

A “set” is simply a collection of elements. These elements may be physical objects, such as the people in your family; or abstractions, such as numbers. The elements in a set may themselves be sets.

The special case is the empty set, Ø = {}, which has no elements at all.

Sets, Subsets, and the Power Set

A subset of a set contains zero, one, or more elements from the original set. It could even be identical to the original set.

For example, let’s say that A = {a, b, c}. There is no need to order subsets, but let’s do so anyway in this situation. The subsets of A are A[0] = {Ø} (the set containing the empty set); A[1] = {a}; A[2] = {b}; A[3] = {c}; A[4] = {a, b}; A[5] = {a, c}; A[6] = {b, c}; and A[7] = A = {a, b, c}. Thus, there are 8 subsets of A.

Having listed these subsets of A, we just say that the power set of A is P  (A) = {A[0], A[1], A[2], A[3], A[4], A[5], A[6], A} = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }.

German mathematician Ernst Zermelo: Image by Konrad Jacobs

The Fifth Zermelo-Fraenkel Axiom is a Formality

Ernst Zermelo (1871-1953) was a German mathematician who wrote extensively at the start of the modern analysis of games theory, particularly chess. He proposed a group of axioms for sets, but did not completely prove them.

Adolf Fraenkel (1891-1965), another German mathematician, began his career in ring theory but became best known for his contributions to set theory. He and Thoralf Skolem proved and extended Zermelo’s axioms.

The fifth of eight Zermelo-Fraenkel Axioms is known as the “Axiom of the Power Set”. It states that, for any set X, there exists a set Y such that, for all elements ‘e’ in Y, ‘e’ is also a subset of X.

Adolf Fraenkel: Image via David B. Keidan Collection of Digital Images from the Central Zionist Archives via Harvard University

The Z-F Axioms provide the formal basis for Z-F Set Theory. They can be extended to Z-F-C by including the Axiom of Choice.

Introducing “Cardinality”

For a set with a finite number of elements, the “cardinality” simply means “the number of elements” in that set. For the above sets, the cardinality of A is |A| = 3, and |P  (A)| = 8.

The cardinality of two sets is the same if one can construct a one-to-one relationship between the sets. This is the way to determine whether one infinite set has the same, or larger, cardinality than another.

The starting point for infinite sets is usually the positive Natural numbers, {1, 2, 3…}. Any infinite set that has the same cardinality as the Natural numbers is said to be “countable”.

We can make a sparse but infinite set, the squares of the positive Natural numbers, for example. Let S = {1^2 = 1, 2^2 = 4, 3^2 = 9, 16, 25, 36…}. Although there are huge gaps in S compared to Natural numbers, clearly we can set the one-to-one correspondence from the Natural numbers to their squares. Therefore both sets have the same cardinality.

Georg Cantor proved that the cardinality of the Real numbers is greater than that of the Natural numbers.

The Cardinality of Finite Power Sets

We might see a pattern with a few power sets. Let’s set up a set of pairs of numbers, the cardinalities of sets and their power sets. Let’s call this set C = { ( |A|, |P  (A)| ) } for some small sets. |Ø| = zero, but P  (Ø) = { {} }, so |P  (Ø)| = 1. The first pair is (0, 1).

If A = {a}, then |A| = 1; P  (A) = { {}, {a} }; so |P  (A)| = 2. For B = {a, b}, |B| = 2; P  (B) = { {}, {a}, {b}, {a, b} }; so |P  (B)| = 4. We had already determined that when |A| = 3, then |P  (A)| = 8.

So the set C = { (0, 1), (1, 2), (2, 4), (3, 8)… }. This looks like the formula p = 2^m for m = {0, 1, 2…}.

We can prove this by mathematical induction. We already have demonstrated this is true for a starting point, from |A| = m = 0, 1, 2 or 3.

Next we assume it is true for an arbitrary m = |A| for a set A with a larger number of elements. Then we see whether it would still be true for “m + 1”, the next larger set.

We are using ‘p’ as the cardinality of the power set of A. We assume that, when |A[m]| = m, p[m] = |P  (A[m])| = 2^m. Now we test whether, if |A| = m + 1, then |P  (A)| = p = 2^(m+1).

When we add the new member to A[m] to form set A, what happens to the power set? P  (A) has all the members found in P  (A[m]), plus other new sets. In fact, for each member of P  (A[m]), we create one new member that includes the new member of A, effectively doubling the size of the set. Therefore p = |P  (A)| = |P  (A[m])| * 2 = p[m] * 2.

However, p = p[m] * 2 by the above counting argument, and p[m] = 2^m according to the induction assumption. So p = 2^m * 2 = 2^(m+1) by the rules governing exponentiation and multiplication. This confirms that |P  (A)| = 2^(m+1). By induction, the general case is proven.

The Cardinality of Power Sets of  Countably-Infinite Power Sets

Georg Cantor proved Cantor’s Theorem, stating that the cardinality of any power set is greater than its starting set: |P  (A)| > |A|.

Let’s examine the special case for Natural numbers, N = {0, 1, 2…}. Then P  (N) = { {}, {0}, {1}, {2}… {0, 1}, {0, 2}… {1, 1}, {1, 2}… {0, 1, 2}… {0, 1, 2, 3}…}. P  (N) also contains infinite sets: all even numbers; odd numbers; multiples of three; powers of two; and so on.

Intuitively, we could place N in a one-to-one correspondence with the single-element members of its power set. That leaves all the pairs, triples and so on with no corresponding Natural numbers. But this instinctive approach is insufficient as proof.

Cantor’s approach was to define “selfish” and “non-selfish” correspondences. Assume that we could construct a one-to-one correspondence between N and P  (N). Then let’s examine the ith pair. Either ‘i’ is a member of the ith subset, or it is not. (For example, the 5th member of P  (N) might be {1, 3, 5, 7…}). If ‘i’ is indeed in the ith subset, then ‘i’ is a “selfish” number. All other numbers are “non-selfish”.

Then Cantor defined U = the set of “non-selfish” numbers under these assumptions, to consist of all the numbers ‘u’ that correspond to P  (N) members that do not contain ‘u’.

Clearly the set U is itself a member of P  (N). By the opening assumption, there must be a Natural number in correspondence to set U; let’s call it ‘j’.

Is ‘j’ in the set U? If it is, then ‘j’ is a “selfish” number because it is found in its corresponding member in P  (N). But we constructed U to consist only of “non-selfish” numbers, so ‘j’ must not be in U. This is a contradiction.

If we assume there are no elements in U, there still is a problem. That would mean that U = Ø = {}, so there is of course some ‘j’ corresponding to it. But if U is empty, then every natural number ‘j’ must be “selfish” and correspond to a non-empty member of P  (N) where it is an element. This is another contradiction.

The Cardinality of Any Power Set

Cantor’s general proof may be outlined as follows. First, it is clear that, for any set A, we can map from P  (A) to A. Since A = {a, b,…} and P  (A) includes {a} and {b}, we can just map {a} to ‘a’, {b} to ‘b’, and so on. It does not matter whether ‘a’ is a number or a complicated set; {a} is simply the set that only contains ‘a’.

Let’s assume that there is a function, f(x), that maps members of a set A to its power set P  (A). Let’s define B as a subset of A, with members that meet the criteria: B = {b} where all ‘b’ are in A but ‘b’ are not elements of {f(b)}. (This is very similar to the “non-selfish” set described above).

Therefore every member, b[i], of B is a member of A. However, b[i] is not a member of f(b[i]).

We had assumed that the function f(x) maps from A to P  (A); but all the b[i] in B (which also are from A) are not mapped there by the function f(x). (This is the generalized version of the “not-selfish” situation above).

Therefore we have a similar contradiction regardless of the cardinality of set A.

The Important Implication of Cantor’s Theorem

We can repeat the process of creating a power set, going from A through P  (A) through P  (P  (A)) and so on. In each case, Cantor’s Theorem states that |A| < |P  (A)| < |P  (P  (A))| and so on.

This proves that there is no “largest” infinite cardinality; we can always define the power set of the current champion, and thus create a “larger” cardinality.

References:

Enderton, H.B. Cantor’s Theorem. UCLA. Accessed November 26, 2011.

O’Connor, John J. and Robertson, Edmund F. Adolf Abraham Halevi Fraenkel. University of St Andrews, Scotland. (October, 2003). Accessed November 26, 2011.

Schwalbe, Ulrich and Walker, Paul. Zermelo and the Early History of Game Theory. Games and Economic Behavior. (1997-2000). PDF accessed November 26, 2011.

Weisstein, Eric W. Cantor’s TheoremPower SetZermelo-Fraenkel Axioms. MathWorld-A Wolfram Web Resource. (1999-2011). Accessed November 26, 2011.

Leave a Comment