Exercises 273States) showed that the continuum hypothesis is neither provable nor disprovable from the
standard axioms for set theory (unless it is possible to prove a contradiction from Zermelo-
Frankel set theory).
4.8.4 Cardinalities of Power Sets
A variant of Cantor's second diagonal method can be used to prove that for any set X,
I X I < I P(X) 1. Of course, that result is already known for finite sets X (see Theorem 2
in Section 1.7.4), but it is interesting that a single proof works for all sets, both finite and
infinite. This proof looks even more like the proof of Russell's paradox (see Section 1.1.1).
It follows that if F : X -+ P (X), then for each x E X, F(x) is a subset of X. So it makes
sense to ask whether x E F(x).
Theorem 11. Let X be any set. Then, I X I < IP(X) 1.
Proof. To show that [ X < IP(X) 1, find a 1-1 function F: X -+ P(X). The function
F mapping each x E X to {x } is easily seen to be such a function.
To show that IP(X) I • I X 1, show that there is no 1-1 correspondence F :X -
P(X). This can be accomplished by showing that no function F : X --* P(X) is onto.
So, suppose F : X -÷ 7P(X) is an onto function. Let Y = {x E X : x ý F(x)}. Show that
Y ý range(F). Now, suppose it were, say, Y = F(y), and ask whether y E F(y):
y E F(y) , y 0 Y by definition of Y
€ y g F(y) by assumption that Y = F(y)
which is a contradiction. So, the assumption that Y E range(F) is false, and we conclude
that F is not onto. M
The cardinality of the set of all subsets of N is called 21°. It is equal to the cardinality
of IR, and it is denoted by c, for continuum.
Exercises
1. Show that ifXCY, IXI <IYI.
- Prove that the sets X = {2n + 1: n E Z1, Y = {10j : j E Z}, and Z = {3n : n E Z}
have the same cardinality. - In the first quadrant of the x-y plane, draw a path that passes exactly once through each
point with both coordinates being integers. Each stopping place on the path should
only be one unit right, one unit up, one unit left, or one unit down from the previous
stopping place. Start the path at (0, 0). Use the path to construct a bijection from N to
NxN.
- Show that the following sets are countably infinite:
(a) {q E Q: q > 101
(b) {q E Q :q^2 <q}
(c) {q E Q :q = i/j where i is odd and j is even}