CS1231 Chapter 9

Countability

9.1 Countable sets

Definition 9.1.1 (Cantor). A set is countable if it is finite or it has the same cardinality
as N. A set is uncountable if it is not countable.

.. .. ..
. . .
2 b2

1 b1

0 b0
bijection
N B

Figure 9.1: A countable infinite set B

Note 9.1.2. Some authors allow only infinite sets to be countable.

Example 9.1.3. (1) N is countable by Proposition 8.2.4(1).
(2) As shown in Example 8.2.3, both N \ {0} and N \ {1, 3, 5, . . . , } are countable.

Proposition 9.1.4. Z is countable.

Proof. Define f : Z → N by setting, for each x ∈ Z,

(
2x, if x ⩾ 0;
f (x) =
2(−x − 1) + 1, if x < 0.

This definition indeed assigns to each element x ∈ Z an element f (x) ∈ N because if x ⩾ 0,

then 2x ⩾ 0 as well; and if x < 0, then x ⩽ −1 as x ∈ Z, and so 2(−x − 1) + 1 ⩾
2(−(−1) − 1) + 1 = 1 > 0. It suffices to show that f is bijective.
To show surjectivity, pick any y ∈ N. Then Proposition 3.2.21 tells us that y is either
even or odd. If y is even, say y = 2x where x ∈ Z, then x = y/2 ⩾ 0, and so f (x) = 2x = y.
If y is odd, say y = 2x + 1 where x ∈ Z, then
y−1 0−1 1
x+1= +1⩾ + 1 = > 0,
2 2 2

74
 .. .. ..
. . .
−3 5
−2 3
−1 1
.. .. ..
. . .
2 4
1 2
0 0
Z N

Figure 9.2: The countability of Z

and so f (−x − 1) = 2(−(−x − 1) − 1) + 1 = 2x + 1 = y. Thus some x ∈ Z makes f (x) = y

in all cases.
To show injectivity, pick x1 , x2 ∈ Z such that f (x1 ) = f (x2 ). If f (x1 ) is even, then
f (x1 ) = 2x1 and f (x2 ) = 2x2 by Proposition 3.2.17, and so x1 = x2 . If f (x1 ) is odd, then
f (x1 ) = 2(−x1 − 1) + 1 and f (x2 ) = 2(−x2 − 1) + 1 by Proposition 3.2.17, and so x1 = x2 .
Thus x1 = x2 in all cases.

Theorem 9.1.5 (Cantor 1877). N × N is countable.

Proof sketch.

.. .. .. .. .. .
. . . . . ..

(0, 4) (1, 4) (2, 4) (3, 4) (4, 4) ···

(0, 3) (1, 3) (2, 3) (3, 3) (4, 3) ···

(0, 2) (1, 2) (2, 2) (3, 2) (4, 2) ···

(0, 1) (1, 1) (2, 1) (3, 1) (4, 1) ···

(0, 0) (1, 0) (2, 0) (3, 0) (4, 0) ···

The function f : N → N × N such that f (0), f (1), f (2), . . . are respectively

(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), (0, 3), (4, 0), (3, 1), (2, 2), (1, 3), . . .
| {z } | {z } | {z }
sum = 1 sum = 2 sum = 3
is a bijection. This shows N × N is countable.

Proposition 9.1.6. {0, 1}∗ is countable.

75
Proof sketch. Let f : N → {0, 1}∗ such that f (0), f (1), f (2), . . . are respectively

ε, 0, 1 , 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, . . . ,
|{z} | {z } | {z }
length length length
1 2 3

where ε denotes the empty string. Then f is a bijection. This shows {0, 1}∗ is countable.

9.2 Countability

Lemma 9.2.1. Let A and B be sets of the same cardinality. Then A is countable if and
only if B is countable.

Exercise 9.2.2. Prove Lemma 9.2.1. (Hint: imitate the proof of Lemma 8.2.8.)  9a

..
. infinite

..
.
countable 2
1
0

Figure 9.3: The smallest cardinalities

Technique 9.2.3. To prove ∃x P (x), where P (x) is a sentence, produce an algorithmic

procedure that outputs an object z for which P (z) is true.

Justification. This is based on Note 2.2.5(4).

Proposition 9.2.4. Every infinite set B has a countable infinite subset.

Proof. Let B be an infinite set. Run the following procedure.

1. Initialize i = 0.
2. While B \ {g1 , g2 , . . . , gi } =
̸ ∅ do:
2.1. Pick any gi+1 ∈ B \ {g1 , g2 , . . . , gi }.
2.2. Increment i to i + 1.
Suppose this procedure stops. Then a run results in g1 , g2 , . . . , gℓ , where ℓ ∈ N. Define
g : {1, 2, . . . , ℓ} → B by setting g(i) = gi for all i ∈ {1, 2, . . . , ℓ}. Notice B \ {g1 , g2 , . . . , gℓ } =
∅ as the stopping condition is reached. This says any element of B is equal to some gi , thus
some g(i). So g is surjective. We know g is injective because each gi+1 ̸∈ {g1 , g2 , . . . , gi } by
line 2.1. As g is a bijection {1, 2, . . . , ℓ} → B, we deduce that B is finite. This contradicts
the condition that B is infinite.

76
 So this procedure does not stop. Define A = {gi : i ∈ Z+ }, and g : N → A by setting
g(i) = gi+1 for each i ∈ N. Then g is surjective by construction. It is injective because each
gi+1 ̸∈ {g1 , g2 , . . . , gi } by line 2.1. As g is a bijection N → A, we deduce that A is countable.
With g, we know A has the same cardinality as N. So A is infinite by Lemma 8.2.8 and
Exercise 8.2.7.
Example 9.2.5. Knowing that R \ Q is infinite tells us R \ Q has a countable infinite subset
by Proposition 9.2.4.

Proposition 9.2.6. Let A, B be sets such that A ⊆ B.

(1) If B is finite, then A is finite.

(2) If B is countable, then A is countable.

.. .. .. .. .. ..
. . . . . .
4 f (4) 4 f (4)
3 f (3) 3
2 f (2) 2 f (2)
1 f (1) 1
0 f (0) 0 f (0)
f g
N B N A

Figure 9.4: Countability of any subset A of a countable set B

Proof sketch. One can prove part (1) in a way similar to how we handle part (2) below. So
we leave the proof of (1) as an exercise and concentrate on (2). Suppose B is countable. If  9b
B is finite, then (1) tells us that A must also be finite and thus countable. So let us suppose
B is infinite. As B is countable and infinite, there is a bijection N → B, say f . Run the
following procedure.
1. Initialize i = 0.
2. While A \ {g1 , g2 , . . . , gi } =
̸ ∅ do:
2.1. Let mi+1 be the smallest element in {m ∈ N : f (m) ∈ A\{g1 , g2 , . . . , gi }}.
2.2. Set gi+1 = f (mi+1 ).
2.3. Increment i to i + 1.
On the one hand, suppose we are at line 2.2 when this procedure is run. Then the loop
condition tells us A \ {g1 , g2 , . . . , gi } ̸= ∅. If ai ∈ A \ {g1 , g2 , . . . , gi }, then ai = f (m) for
some m ∈ N because f is a surjection N → B and A ⊆ B. This says {m ∈ N : f (m) ∈
A \ {g1 , g2 , . . . , gi }} =
̸ ∅. So mi+1 must exist by the Well-Ordering Principle.
On the other hand, by the choices of mi+1 and gi+1 on lines 2.2 and 2.1,
each gi+1 ∈ A \ {g1 , g2 , . . . , gi }. (∗)

Case 1: this procedure stops after finitely many steps. Then a run results in
m1 , m2 , . . . , mℓ and g1 , g2 , . . . , gℓ
where ℓ ∈ N. Define g : {1, 2, . . . , ℓ} → A by setting g(i) = gi for all i ∈ {1, 2, . . . , ℓ}.
Notice A\{g1 , g2 , . . . , gℓ } = ∅ as the stopping condition is reached. This says any element
of A is equal to some gi , thus some g(i). So g is surjective. We know g is injective by (∗).
As g is a bijection {1, 2, . . . , ℓ} → A, we deduce that A is finite and hence countable.

77
 uncountable f uncountable

A injection range(f ) B

Figure 9.5: Injecting an uncountable set into another set

Case 2: this procedure does not stop. Then a run results in

m1 , m2 , m3 , . . . and g1 , g2 , g3 , . . . .

Define g : N → A by setting g(i) = gi+1 for all i ∈ N. As one can verify, this g is a bijection
N → A. So A is countable.

Explanation of why g is bijective in the proof above (extra material). We claim

that mi+1 < mi+2 for all i ∈ N. Let i ∈ N. Line 2.2 tells us gi+1 = f (mi+1 ) and gi+2 =
f (mi+2 ), but gi+1 ̸= gi+2 by (∗). So mi+1 ̸= mi+2 . Note that f (mi+2 ) = gi+2 ∈ A \
{g1 , g2 , . . . , gi+1 } ⊆ A \ {g1 , g2 , . . . , gi }. Thus mi+2 ∈ {m ∈ N : f (m) ∈ A \ {g1 , g2 , . . . , gi }}.
Since we chose mi+1 to be the smallest element of this set and mi+1 ̸= mi+2 , we deduce that
mi+1 < mi+2 , as claimed.
To show the surjectivity of g, assume we have y ∈ A such that g(i) ̸= y for any i ∈ N.
As f is a surjection N → B and A ⊆ B, we get n ∈ N making f (n) = y. The claim in the
previous paragraph tells us that 0 ⩽ m1 < m2 < · · · < mn+2 . So mn+2 ⩾ n + 1 > n. Also,
our assumption on y implies f (n) = y ∈ A \ {g(0), g(1), . . . , g(n)} = A \ {g1 , g2 , . . . , gn+1 }.
However, we chose mn+2 to be the smallest m ∈ N such that f (m) ∈ A \ {g1 , g2 , . . . , gn+1 }.
This contradiction shows the surjectivity of g.
We know g is injective by (∗). ■

Corollary 9.2.7. (1) A set B is infinite if there is an injection f from some infinite set A
to B.

(2) A set B is uncountable if there is an injection f from some uncountable set A to B.

Proof. The proofs of the two parts are similar. So we concentrate on (2) and leave the proof
of (1) as an exercise.  9c
As f is an injection A → B, Exercise 8.2.5 implies that A has the same cardinality
as range(f ). Since A is uncountable, Lemma 9.2.1 tells us range(f ) is also uncountable.
Recall from Remark 7.2.3(2) that range(f ) ⊆ B. Hence B is uncountable too by Proposi-
tion 9.2.6(2).
Example 9.2.8. The set of all programs is countable.
Proof. Every program is stored in a computer as a string over {0, 1}. So the set of all
programs is a subset of the set {0, 1}∗ of all strings over {0, 1}, which we know is count-
able from Proposition 9.1.6. So Proposition 9.2.6(2) tells us that the set of all programs is
countable.

9.3 Uncountable sets

Theorem 9.3.1 (Cantor 1891). No set A has the same cardinality as P(A).

78
 0 1 2 3 4 ...
f (0) ∈
/ ∈ ∈
/ ∈
/ ∈
/ ...
f (1) ∈ ∈
/ ∈ ∈
/ ∈ ...
f (2) ∈
/ ∈ ∈ ∈
/ ∈ ...
f (3) ∈
/ ∈
/ ∈ ∈
/ ∈
/ ...
f (4) ∈ ∈
/ ∈ ∈ ∈
/ ...
.. .. .. .. .. .. ..
. . . . . . .

R ∈ ∈ ∈
/ ∈ ∈ ...

Figure 9.6: Illustration of Cantor’s diagonal argument

Proof. We consider here only the particular case when A = N. The general case is very
similar, and is left as an exercise.  9d
Given any function f : N → P(N), we will produce an element of P(N) that is not equal
to f (x) for any x ∈ N. This will show that there is no surjection f : N → P(N), and thus N
cannot have the same cardinality as P(N).
Let f : N → P(N). Define R = {x ∈ N : x ̸∈ f (x)}. Then R ∈ P(N) by the definition of
power sets. We claim that R ̸= f (x) for any x ∈ N. We prove this by contradiction. Suppose
we have a ∈ N such that R = f (a). From the definition of R,


∀x ∈ N x ∈ R ⇔ x ̸∈ f (x) . (†)

As R = f (a), applying (†) to x = a gives

a ∈ f (a) ⇔ a ̸∈ f (a). (‡)

Split into two cases.

• Case 1: assume a ∈ f (a). Then a ̸∈ f (a) by the ⇒ part of (‡). This contradicts our
assumption that a ∈ f (a).
• Case 2: assume a ̸∈ f (a). Then a ∈ f (a) by the ⇐ part of (‡). This contradicts our
assumption that a ̸∈ f (a).

In either case, we get a contradiction. This completes the proof of the claim and thus of the
theorem.

Corollary 9.3.2. Let A be a countable infinite set. Then P(A) is uncountable. Hence P(N)
is uncountable.

Proof. We consider here only the particular case when A = N. The general case is very
similar, and is left as an exercise.  9e
According to the definition of countability, we need to show that P(N) is infinite, and that
P(N) does not have the same cardinality as N. We already have the latter from Theorem 9.3.1.
For the former, let f : N → P(N) defined by setting f (n) = {n} for each n ∈ N. Then
f is injective because if n1 , n2 ∈ N such that f (n1 ) = f (n2 ), then {n1 } = {n2 }, and thus
n1 = n2 by the definition of set equality. Recall that N is infinite from Exercise 8.2.7. So
Corollary 9.2.7(1) tells us P(N) is infinite too, as required.

9.4 Non-computability
Assumption 9.4.1. Our programs have no time and memory limitation.

79
Corollary 9.4.2. There is a subset S of N that is not computed by any program, i.e., no
program can, when given any input n ∈ N,

• output T if n ∈ S; and
• output F if n ̸∈ S.

Proof. Suppose that every subset S ⊆ N is computed by a program. For each S ∈ P(N), let
f (S) be the smallest program that computes S. This defines a function f : P(N) → {0, 1}∗ ,
because each program has a unique representation by an element of {0, 1}∗ within a computer.
This function f is injective because if S1 , S2 ∈ P(N) such that f (S1 ) = f (S2 ), then S1 and S2
are computed by the same program, and thus S1 = S2 by the definition of set equality.
Recall from Corollary 9.3.2 that P(N) is uncountable. So Corollary 9.2.7(2) implies {0, 1}∗ is
uncountable as well. This contradicts the countability of {0, 1}∗ from Proposition 9.1.6.

Theorem 9.4.3 (Turing 1936, extra material). The set

H = {σ ∈ {0, 1}∗ : σ is a program that does not stop on the empty input}

is not computed by any program, i.e., no program can, when given any input σ ∈ {0, 1}∗ ,
• output T if σ ∈ H; and
• output F if σ ̸∈ H.

Proof. Suppose not. Use a program that computes H to devise a program R satisfying
 σ is a program that does 
∀σ ∈ {0, 1}∗ R stops on input σ ⇔ . (§)
not stop on input σ

Applying (§) to σ = R gives

R is a program that does

R stops on input R ⇔ (¶)
not stop on input R

Split into two cases.

• Case 1: assume R stops on input R. Then R does not stop on input R by the ⇒ part
of (¶). This contradicts our assumption that R stops on input R.
• Case 2: assume R does not stop on input R. Then R stops on input R by the ⇐ part
of (¶). This contradicts our assumption that R does not stop on input R.
In either case, we get a contradiction, as required.

Tutorial exercises
An asterisk (*) indicates a more challenging exercise.
9.1. It is often desirable for small sets to be closed under (binary) unions, i.e., the union of
two small sets should also be small. (Can you guess why?) The aim of this exercise is
to show that finite sets are a kind of small sets with this desirable property.
Let A and B be sets. Prove that, if A and B are finite, then A ∪ B is finite.
(Hint: start with the special case when A ∩ B = ∅. Then use Further Exercise 4.9(a)
to generalize to all cases.)

80
9.2. The aim of this exercise is to show that countable sets are another kind of small sets
with the desirable property put forward in Exercise 9.1.
Let A and B be sets. Prove that, if A and B are countable, then A ∪ B is countable.
(Hint: as in Exercise 9.1, start with the special case when A∩B = ∅. Then use Further
Exercise 4.9(a) to generalize to all cases.)
Sn
9.3. Recall the definition of i=0 Ai from Further Exercise 4.11.
(Induction
Sn corner) Let A0 , A1 , A2 , . . . be countable sets. Prove by induction on n that
A
i=0 i is countable for every n ∈ N.
S∞
9.4.∗ Recall the definition of i=0 Ai from Further Exercise 4.11.

(a) Someone claims that one can deduce directly from what S∞ we established in Exer-
cise 9.3 that, if A0 , A1 , A2 , . . . are countable sets, then i=0 Ai is countable. What
is wrong with this claim?
S∞
(b) Prove that, if A0 , A1 , A2 , . . . are countable sets, then i=0 Ai is countable.
S∞
(Hint: find an injection i=0 Ai → N × N.)

9.5. For each of the following propositions, determine whether it is true. Prove that your
answers are correct.

(a) If a set B has an uncountable subset A, then B is uncountable.

(b) If A is an uncountable set and B is a countable set, then A \ B is uncountable.
9.6. Corollary 9.3.2 states that the power set of a countable infinite set is uncountable. The
aim of this exercise is to show that this corollary remains true even when one omits the
word “countable” there.
Prove that the power set P(A) of any infinite set A is uncountable.

Further exercises
9.7. According to our definition, there are two kinds of countable sets: finite sets, and
sets that have the same cardinality as N. Conceivably, this may lead to painful case-
splittings in proofs about countable sets. Fortunately, in many circumstances, one can
ignore the finite case via what we establish in this exercise.
Prove that, for every countable set A, there is a countable infinite set A∗ such that
A ⊆ A∗ .

9.8. We defined countability using (the notion of same-cardinality and thus) bijections. We
show in this exercise how one could have defined countability using injections instead.
Prove that a set A is countable if and only if there is an injection A → N.
9.9. We saw in Theorem 9.1.5 that N × N is countable. In this exercise, we generalize this
to the Cartesian product of any two countable sets, not only N.
Let A, B be countable sets. Use Theorem 9.1.5 to prove that A × B is countable.

81