Theorem:
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:
- a corresponds to A, i.e. A = f(a)
- b corresponds to B, i.e. B = f(b)
- c corresponds to B, i.e. C = f(c)
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:
- 1 is associated with {3}
- 2 is associated with {1,2,3}
- 3 is associated with {1,2}.
Then what elements does the set X defined above consist of ?
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).
To Theory |
Glossary |
Map
(bgw)