Interactive Real Analysis - part of MathCS.org

Next | Previous | Glossary | Map | Discussion

Theorem 2.2.5: Cardinality of Power Sets

The cardinality of the power set P(S) is always bigger than the cardinality of S for an set S.

Proof:

The proof will be similar to proof about the uncountablility of the open interval (0,1): we will attempt to list all sets of P(S) next to all elements of S, and then exhibit a set that can not be in that list. However, we will do this in a more abstract fashion this time.

Let us denote the elements of the set S by small letters a, b, c, ..., and the elements of P(S) by capital letters A, B, C, .... Note that each member of P(S) is again a set in itself. Suppose there was a function f between S and P(S). That means, that we may have the following correspondence:

and so on. The fact that small letters and capital letters are the same is merely for convenience. Now define the set X as follows:
X = { s S: {s} f(s) = 0 }
or, in other words:
if T = f(t), then t is in X if and only if t is not contained in T
Hence, X contains all those elements that are not contained in their associated sets under the above function f. This is easy to understand by means of a concrete example:

Let S = {1, 2, 3}. Then P(S) = { 0, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }. An arbitrary function from S to P(S) might associate the elements of S as follows:

Then the set X defined above consist of the following elements: Hence, X = {1, 3}.

Incidentally, there is no element from S that is mapped to the set X.

Now let us return to the proof. Since X consists of elements of S, X is a subset of S, and hence X is an element of P(S). If the above map f was an onto map, then there must be an element x from S with f(x) = X. Where is that element x ?: Suppose x is contained in X:

Since X contains those elements that are not in its associated set, we have that x is not contained in f(x) = X.
Suppose x is not contained in X:
Since X contains exactly those elements that are not in its associated set, and x is assumed to be not in X = f(x), then x must be contained in X.
This is clearly not possible, showing that our assumption that f is onto is false. Hence, whatever map between S and P(S) exists, it can not be onto. But from a previous example we already know that the cardinality of P(S) is at least as large as the cardinality of S, i.e. there is a one-to-one map from S to P(S). Since this map can not also be onto, we have proved that card(P(S)) > card(S).

Next | Previous | Glossary | Map | Discussion