Book of Proof
Page 33
Case 1. If a ∈ B, then the definition of B implies a ∉ f (a), and since f (a) = B
we have a ∉ B, which is a contradiction.
Case 2. If a ∉ B, then the definition of B implies a ∈ f (a), and since f (a) = B
we have a ∈ B, again a contradiction.
Since the assumption that there is a surjection f : A → P(A) leads to a
contradiction, we conclude that there are no such surjective functions.
In conclusion, we have seen that there exists an injection A → P(A) but
no surjection A → P(A), so Definition 13.4 implies that |A| < |P(A)|.
■
Beginning with the set A = N and applying Theorem 13.7 over and over
again, we get the following chain of infinite cardinalities.
ℵ0 = |N| < |P(N)| < |P(P(N))| < |P(P(P(N)))| < ···
(13.2)
Thus there is an infinite sequence of different types of infinity, starting
with ℵ0 and becoming ever larger. The set N is countable, and all the sets
P(N), P(P(N)), etc., are uncountable.
In the next section we will prove that |P(N)| = |R|. Thus |N| and |R|
are the first two entries in the chain (13.2) above. They are are just two
relatively tame infinities in a long list of other wild and exotic infinities.
Unless you plan on studying advanced set theory or the foundations
of mathematics, you are unlikely to ever encounter any types of infinity
beyond ℵ0 and |R|. Still you will in future mathematics courses need to
distinguish between countably infinite and uncountable sets, so we close
with two final theorems that can help you do this.
Theorem 13.8
An infinite subset of a countably infinite set is countably
infinite.
Proof. Suppose A is an infinite subset of the countably infinite set B.
Because B is countably infinite, its elements can be written in a list
Comparing Cardinalities
231
b1, b2, b3, b4, . . . Then we can also write A’s elements in list form by proceed-
ing through the elements of B, in order, and selecting those that belong to
A. Thus A can be written in list form, and since A is infinite, its list will
be infinite. Consequently A is countably infinite.
■
Theorem 13.9
If U ⊆ A, and U is uncountable, then A is uncountable.
Proof. Suppose for the sake of contradiction that U ⊆ A, and U is uncount-
able but A is not uncountable. Then since U ⊆ A and U is infinite, then A
must be infinite too. Since A is infinite, and not uncountable, it must be
countably infinite. Then U is an infinite subset of a countably infinite set
A, so U is countably infinite by Theorem 13.8. Thus U is both uncountable
and countably infinite, a contradiction.
■
Theorems 13.8 and 13.9 can be useful when we need to decide whether
a set is countably infinite or uncountable. They sometimes allow us to
decide its cardinality by comparing it to a set whose cardinality is known.
For example, suppose we want to decide whether or not the set A = R2
is uncountable.
Since the x-axis U = ©(x, 0) : x ∈ Rª ⊆ R2 has the same
cardinality as R, it is uncountable.
Theorem 13.9 implies that R2 is
uncountable. Other examples can be found in the exercises.
Exercises for Section 13.3
1. Suppose B is an uncountable set and A is a set. Given that there is a surjective
function f : A → B, what can be said about the cardinality of A?
2. Prove that the set C of complex numbers is uncountable.
3. Prove or disprove: If A is uncountable, then |A| = |R|.
4. Prove or disprove: If A ⊆ B ⊆ C and A and C are countably infinite, then B is
countably infinite.
5.
©
Prove or disprove: The set 0, 1ª × R is uncountable.
6. Prove or disprove: Every infinite set is a subset of a countably infinite set.
7. Prove or disprove: If A ⊆ B and A is countably infinite and B is uncountable,
then B − A is uncountable.
8.
©
Prove or disprove: The set (a1, a2, a3, . . .) : ai ∈ Z} of infinite sequences of integers
is countably infinite.
9. Prove that if A and B are finite sets with |A| = |B|, then any injection f : A → B
is also a surjection. Show this is not necessarily true if A and B are not finite.
10. Prove that if A and B are finite sets with |A| = |B|, then any surjection f : A → B
is also an injection. Show this is not necessarily true if A and B are not finite.
232
Cardinality of Sets
13.4 The Cantor-Bernstein-Schröeder Theorem
An often used property of numbers is that if a ≤ b and b ≤ a, then a = b. It
is reasonable to ask if the same property applies to cardinality. If |A| ≤ |B|
and |B| ≤ |A|, is it true that |A| = |B|? This is in fact true, and this section’s
goal is to prove it. This will yield an alternate (and highly effective) method
of proving that two sets have the same cardianlity.
Recall (Definition 13.4) that |A| ≤ |B| means that |A| < |B| or |A| = |B|. If
|A| < |B| then (by Definition 13.4) there is an injection A → B. On the other
hand, if |A| = |B|, then there is a bijection (hence also an injection) A → B.
Thus |A| ≤ |B| implies that there is an injection f : A → B.
Likewise, |B| ≤ |A| implies that there is an injection g : B → A.
Our aim is to show that if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. In
other words, we aim to show that if there are injections f : A → B and
g : B → A, then there is a bijection h : A → B. The proof of this fact, though
not particularly difficult, is not entirely trivial, either. The fact that f and
g guarantee that such an h exists is called the the Cantor-Bernstein-
Schröeder theorem. This theorem is very useful for proving two sets A
and B have the same cardinality: it says that instead of finding a bijection
A → B, it suffices to find injections A → B and B → A. This is useful because
injections are often easier to find than bijections.
We will prove the Cantor-Bernstein-Schröeder theorem, but before
doing so let’s work through an informal visual argument that will guide
us through (and illustrate) the proof.
Suppose there are injections f : A → B and g : B → A. We want to use
them to produce a bijection h : A → B. Sets A and B are sketched below.
For clarity, each has the shape of the letter that denotes it, and to help
distinguish them the set A is shaded.
A
B
Figure 13.3. The sets A and B
The injections f : A → B and g : B → A are illustrated in Figure 13.4.
Think of f as putting a “copy” f (A) = © f (x) : x ∈ Aª of A into B, as illustrated.
This copy, the range of f , does not fill up all of B (unless f happens to be
surjective). Likewise, g puts a “copy” g(B) of B into A. Because they are
The Cantor-Bernstein-Schröeder Theorem
233
not necessarily bijective, neither f nor g is guaranteed to have an inverse.
But the map g : B → g(B) from B to g(B) = {g(x) : x ∈ B} is bijective, so there
is an inverse g−1 : g(B) → B. (We will need this inverse soon.)
g
f
g−1
&n
bsp; Figure 13.4. The injections f : A → B and g : B → A
Consider the chain of injections illustrated in Figure 13.5. On the left,
g puts a copy of B into A. Then f puts a copy of A (containing the copy of
B) into B. Next, g puts a copy of this B-containing-A-containing-B into A,
and so on, always alternating g and f .
f
f
f
g
g
g
· · ·
Figure 13.5. An infinite chain of injections
The first time A occurs in this sequence, it has a shaded region A − g(B).
In the second occurrence of A, the shaded region is (A− g(B))∪(g◦ f )(A− g(B)).
In the third occurrence of A, the shaded region is
(A − g(B)) ∪ (g ◦ f )(A − g(B)) ∪ (g ◦ f ◦ g ◦ f )(A − g(B)).
To tame the notation, let’s say (g ◦ f )2 = (g ◦ f ) ◦ (g ◦ f ), and (g ◦ f )3 =
(g ◦ f )◦(g◦ f )◦(g◦ f ), and so on. Let’s also agree that (g◦ f )0 = ι A, that is, it is
the identity function on A. Then the shaded region of the nth occurrence
of A in the sequence is
n−1
[ (g ◦ f )k(A − g(B)).
k=0
This process divides A into gray and white regions: the gray region is
∞
G = [ (g ◦ f )k(A − g(B)),
k=0
234
Cardinality of Sets
and the white region is A − G. (See Figure 13.6.)
Figure 13.6 suggests our desired bijection h : A → B. The injection f
sends the gray areas on the left bijectively to the gray areas on the right.
The injection g−1 : g(B) → B sends the white areas on the left bijectively
to the white areas on the right. We can thus define h : A → B so that
h(x) = f (x) if x is a gray point, and h(x) = g−1(x) if x is a white point.
A
B
f
g−1
f
g−1
...
Figure 13.6. The bijection h : A → B
This informal argument suggests that given injections f : A → B and
g : B → A, there is a bijection h : A → B. But it is not a proof. We now
present this as a theorem and tighten up our reasoning in a careful proof,
with the above diagrams and ideas as a guide.
Theorem 13.10 (The Cantor-Bernstein-Schröeder Theorem)
If |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. In other words, if there are injections
f : A → B and g : B → A, then there is a bijection h : A → B.
Proof. (Direct) Suppose there are injections f : A → B and g : B → A. Then,
in particular, g : B → g(B) is a bijection from B onto the range of g, so it
has an inverse g−1 : g(B) → B. (Note that g : B → A itself has no inverse
g−1 : A → B unless g is surjective.) Consider the subset
∞
G = [ (g ◦ f )k(A − g(B)) ⊆ A.
k=0
The Cantor-Bernstein-Schröeder Theorem
235
Let W = A − G, so A = G ∪ W is partitioned into two sets G (think gray) and
W (think white). Define a function h : A → B as
(
f (x)
if x ∈ G
h(x) =
g−1(x)
if x ∈ W.
Notice that this makes sense: if x ∈ W, then x ∉ G, so x ∉ A − g(B) ⊆ G, hence
x ∈ g(B), so g−1(x) is defined.
To finish the proof, we must show that h is both injective and surjective.
For injective, we assume h(x) = h( y), and deduce x = y. There are three
cases to consider. First, if x and y are both in G, then h(x) = h( y) means
f (x) = f (y), so x = y because f is injective. Second, if x and y are both in W,
then h(x) = h( y) means g−1(x) = g−1( y), and applying g to both sides gives
x = y. In the third case, one of x and y is in G and the other is in W.
Say x ∈ G and y ∈ W. The definition of G gives x = (g ◦ f )k(z) for some
k ≥ 0 and z ∈ A − g(B). Note h(x) = h(y) now implies f (x) = g−1(y), that is,
f ((g ◦ f )k(z)) = g−1(y). Applying g to both sides gives (g ◦ f )k+1(z) = y, which
means y ∈ G. But this is impossible, as y ∈ W. Thus this third case cannot
happen. But in the first two cases h(x) = h( y) implies x = y, so h is injective.
To see that h is surjective, take any b ∈ B. We will find an x ∈ A with
h(x) = b. Note that g(b) ∈ A, so either g(b) ∈ W or g(b) ∈ G. In the first case,
h(g(b)) = g−1(g(b)) = b, so we have an x = g(b) ∈ A for which h(x) = b. In the
second case, g(b) ∈ G. The definition of G shows
g(b) = (g ◦ f )k(z)
for some k > 0, and z ∈ A − g(B). Thus
g(b) = (g ◦ f ) ◦ (g ◦ f )k−1(z).
Rewriting this,
³
´
g(b) = g f ¡(g ◦ f )k−1(z)¢ .
Because g is injective, this implies
b = f ¡(g ◦ f )k−1(z)¢.
Let x = (g ◦ f )k−1(z), so x ∈ G by definition of G. Observe that h(x) = f (x) =
f ¡(g ◦ f )k−1(z)¢ = b. We have now seen that for any b ∈ B, there is an x ∈ A
for which h(x) = b. Thus h is surjective.
Since h : A → B is both injective and surjective, it is also bijective.
■
236
Cardinality of Sets
Here are some examples illustrating how the Cantor-Bernstein-Schröeder
theorem can be used. This includes a proof that |R| = |P(N)|.
Example 13.6
The intervals [0, 1) and (0, 1) in R have equal cardinalities.
Surely this fact is plausible, for the two intervals are identical except for
the endpoint 0. Yet concocting a bijection [0, 1) → (0, 1) is tricky. (Though
not particularly difficult: see the solution of Exercise 11 of Section 13.1.)
For a simpler approach, note that f (x) = 1
x
4 + 1
2
is an injection [0, 1) → (0, 1).
Also, g(x) = x is an injection (0, 1) → [0, 1). The Cantor-Bernstein-Schröeder
theorem guarantees a bijection h : [0, 1) → (0, 1), so |[0, 1)| = |(0, 1)|.
Theorem 13.11
The sets R and P(N) have the same cardinality.
Proof. Example 13.4 shows that |R| = |(0,1)|, and Example 13.6 shows
|(0, 1)| = |[0, 1)|. Thus |R| = |[0,1)|, so to prove the theorem we just need to
show that |[0, 1)| = |P(N)|. By the Cantor-Bernstein-Schröeder theorem, it
suffices to find injections f : [0, 1) → P(N) and g : P(N) → [0, 1).
To define f : [0, 1) → P(N), we use the fact that any number in [0, 1) has
a unique decimal representation 0.b1b2b3b4 . . ., where each bi one of the
digits 0, 1, 2, . . . , 9, and there is not a repeating sequence of 9’s at the end.
(Recall that, e.g., 0.359999 = 0.360, etc.) Define f : [0, 1) → P(N) as
f ¡0.b1b2b3b4 . . . ¢ = ©10b1, 102b2, 103b3, ...ª.
For example, f (0.121212) = ©10, 200, 1000, 20000, 100000, . . . ª, and f (0.05) =
©0,500ª. Also f (0.5) = f (0.50) = ©0,50ª. To see that f is injective, take two
unequal numbers 0.b1b2b3b4 . . . and 0.d1d2d3d4 . . . in [0, 1). Then bi 6= di for
some index i. Hence bi10i ∈ f (0.b1b2b3b4 . . .) but bi10i ∉ f (0.d1d2d3d4 . . .), so
f (0.b1b2b3b4 . . .) 6= f (0.d1d2d3d4 ...). Consequently f is injective.
Next, define g : P(N) → [0, 1), where g(X ) = 0.b1b2b3b4 . . . is the number
for which bi = 1 if i ∈ X and bi
= 0 if i ∉ X . For example, g¡©1, 3ª¢ = 0.101000,
and g¡©2, 4, 6, 8, . . . ª¢ = 0.01010101. Also g(;) = 0 and g(N) = 0.1111. To see
that g is injective, suppose X 6= Y . Then there is at least one integer i
that belongs to one of X or Y , but not the other. Consequently g(X ) 6= g(Y )
because they differ in the ith decimal place. This shows g is injective.
From the injections f : [0, 1) → P(N) and g : P(N) → [0, 1), the Cantor-
Bernstein-Schröeder theorem guarantees a bijection h : [0, 1) → P(N). Hence
|[0, 1)| = |P(N)|. As |R| = |[0,1)|, we conclude |R| = |P(N)|.
■
The Cantor-Bernstein-Schröeder Theorem
237
We know that |R| 6= |N|. But we just proved |R| = |P(N)|. This suggests
that the cardinality of R is not “too far” from |N| = ℵ0. We close with a few
informal remarks on this mysterious relationship between ℵ0 and |R|.
We established earlier in this chapter that ℵ0 < |R|. For nearly a century
after Cantor formulated his theories on infinite sets, mathematicians
struggled with the question of whether or not there exists a set A for which
ℵ0 < |A| < |R|.
It was commonly suspected that no such set exists, but no one was able
to prove or disprove this. The assertion that no such A exists came to be
called the continuum hypothesis.
Theorem 13.11 states that |R| = |P(N)|. Placing this in the context of
the chain (13.2) on page 230, we have the following relationships.
ℵ0
|R|
=
=
|N| < |P(N)| < |P(P(N))| < |P(P(P(N)))| < ···
From this, we can see that the continuum hypothesis asserts that no set
has a cardinality between that of N and its power set.
Although this may seem intuitively plausible, it eluded proof since
Cantor first posed it in the 1880s. In fact, the real state of affairs is
almost paradoxical. In 1931, the logician Kurt Gödel proved that for any
sufficiently strong and consistent axiomatic system, there exist statements
which can neither be proved nor disproved within the system.
Later he proved that the negation of the continuum hypothesis cannot
be proved within the standard axioms of set theory (i.e., the Zermelo-
Fraenkel axioms, mentioned in Section 1.10). This meant that either the
continuum hypothesis is false and cannot be proven false, or it is true.
In 1964, Paul Cohen discovered another startling truth: Given the laws
of logic and the axioms of set theory, no proof can deduce the continuum