Theorem 2.2.5: Cardinality of Power Sets
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:
- a corresponds to A, i.e. A = f(a)
- b corresponds to B, i.e. B = f(b)
- c corresponds to C, i.e. C = f(c)
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 THence, 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:
- 1 is associated with {3}
- 2 is associated with {1,2,3}
- 3 is associated with {1,2}.
- f(1) = {3}, and 1 is not in {3}. Thus, {1} is in X.
- f(2) = {1,2,3}, and 2 is in {1,2,3}. Thus, {2} is not in X.
- f(3) = {1, 2}, and 3 is not in {1,2}. Thus, {3} is in X.
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).