3.4 Diagonal Arguments: Uncountable Sets and Cantor’s Theorem

Every infinite set met so far has turned out to be countable: $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ , finite products of countable sets, countable unions of them (Theorem 3.3.3), and even the algebraic numbers (Theorem 3.3.4). Is every infinite set countable? This section shows that the answer is no, by one argument used three times. Given any list, it builds an object that the list misses. The argument proves that the set of 0–1 sequences is uncountable, that no set can be mapped onto the set of its subsets (Cantor’s theorem), and, with decimals, that $\mathbb{R}$ is uncountable.

3.4.1. A sequence that is not on the list

Recall from Section 1.4 that $\{0, 1\}^{\mathbb{N}}$ is the set of all functions $\mathbb{N} \to \{0, 1\}$ : the sequences of zeros and ones, indexed from $0$ . It is infinite, and it looks no bigger than $\mathbb{N} \times \mathbb{N}$ , which is countable. To show that it is not countable we must show, by Definition 3.2.1, that it is non-empty and that no function $f \colon \mathbb{N} \to \{0, 1\}^{\mathbb{N}}$ is onto. So we take an arbitrary list $f(0), f(1), f(2), \dots$ of sequences and look for a sequence that is not on it.

Write the list as a table: row $n$ is the sequence $f(n)$ , and the entry in row $n$ and column $k$ is the number $f(n)(k)$ . Here is the start of one such table, with the entries in places $(0, 0), (1, 1), (2, 2), (3, 3)$ boxed:

Diagram. Labels: k, f(0), 0, 1, f(1), f(2), f(3), g

The boxed entries run down the diagonal of the table. The bottom row $g$ is the diagonal with every entry flipped: $g(n) = 1 - f(n)(n)$ . It cannot be row $0$ , because it differs from $f(0)$ in place $0$ ; it cannot be row $1$ , because it differs from $f(1)$ in place $1$ ; and so on down the table. Nothing in this reasoning used the particular entries.

Theorem 3.4.1 (The 0–1 Sequences Are Uncountable)

The set $\{0, 1\}^{\mathbb{N}}$ of all sequences of zeros and ones is uncountable.

Proof. Let $f \colon \mathbb{N} \to \{0, 1\}^{\mathbb{N}}$ be any function. Define $g \colon \mathbb{N} \to \{0, 1\}$ by $g(n) \mathrel{:=} 1 - f(n)(n) \qquad (n \in \mathbb{N}) ;$ its values lie in $\{0, 1\}$ , since $1 - 0 = 1$ and $1 - 1 = 0$ . So $g \in \{0, 1\}^{\mathbb{N}}$ . For every $n \in \mathbb{N}$ , $g(n) \ne f(n)(n)$ , since no $b \in \{0, 1\}$ has $1 - b = b$ . Hence $g \ne f(n)$ : if $g = f(n)$ , then $g(n) = f(n)(n)$ , which is false; the two functions differ at place $n$ [ $\mathrm{{=}E}$ , $\mathrm{\neg I}$ ; Proposition 1.4.1]. So $g$ is not a value of $f$ , and $f$ is not surjective. Since $f$ was arbitrary, no function $\mathbb{N} \to \{0, 1\}^{\mathbb{N}}$ is surjective. The set $\{0, 1\}^{\mathbb{N}}$ is non-empty, since it contains the zero sequence. By Definition 3.2.1, $\{0, 1\}^{\mathbb{N}}$ is not countable.

This is the move of the section, and it has a name.

The diagonal. Given any list, build an object that differs from the $n$ -th entry at the $n$ -th place. The new object is not on the list, because it disagrees with every entry somewhere, and the place of disagreement is chosen by the entry’s own position.

Quick check. Run the proof on the list $f(n) \mathrel{:=} \mathbf{1}_{\{n\}}$ , the sequence with a $1$ in place $n$ and $0$ elsewhere. What is $g$ ? Is it on the list?

Solution. Here $f(n)(n) = \mathbf{1}_{\{n\}}(n) = 1$ for every $n$ , so $g(n) = 1 - 1 = 0$ for every $n$ : $g$ is the zero sequence. It is indeed not on the list, since every $f(n)$ has a $1$ in place $n$ .

Warning. The diagonal object depends on the list. “The diagonal sequence” is not one sequence: each list has its own, and a different list may well contain the $g$ built from this one (the list $g, f(0), f(1), \dots$ does). And the conclusion “uncountable” needs the list to be arbitrary. Running the construction on one list, or on a few, shows only that those lists miss something; concluding “so no list works” from them is the error (N1) of Logic and Proof, Example (What is not allowed). The proof above starts from “let $f$ be any function”, and that is what makes its conclusion universal.

3.4.2. Cantor’s theorem

The table had a row for each $n \in \mathbb{N}$ and a column for each place $k \in \mathbb{N}$ . Nothing about the diagonal needs the rows and the columns to be indexed by $\mathbb{N}$ : it needs only that they are indexed by the same set. A subset $S$ of a set $X$ is a row with one entry for each $x \in X$ , “in” or “out”, the values of $\mathbf{1}_S$ . So the argument applies to any set and the set of its subsets.

Theorem 3.4.2 (Cantor’s Theorem)

Let $X$ be a set. Then there is no surjection $X \to \mathcal{P}\left( X \right)$ .

Try it first (ten minutes): given a function $f \colon X \to \mathcal{P}\left( X \right)$ , which subset of $X$ could be missed by $f$ ? Try $X = \{1, 2, 3\}$ with a function of your own first.

Idea. The first attempts look for a subset that is “too big” or “too small” to be a value, such as $X$ itself or $\emptyset$ , and fail: $f$ may well take both values. Size is the wrong idea. A set $D$ differs from $f(x)$ as soon as the two disagree about one element, and the only element we know anything about in connection with $f(x)$ is $x$ itself. So we make $D$ disagree with $f(x)$ at $x$ : put $x$ into $D$ exactly when $x \notin f(x)$ . This is the diagonal of the table, flipped.

Before reading on: where is surjectivity used?

Proof. Let $f \colon X \to \mathcal{P}\left( X \right)$ be a function, and let $D \mathrel{:=} \{ x \in X : x \notin f(x) \} ,$ a subset of $X$ by Definition 1.1.3, so $D \in \mathcal{P}\left( X \right)$ (Definition 1.2.2). Suppose $f$ is surjective. Then there is $d \in X$ with $f(d) = D$ (Definition 1.4.4). If $d \in D$ , then $d \notin f(d)$ by the definition of $D$ , that is, $d \notin D$ , a contradiction. Hence $d \notin D$ . Then $d \notin f(d)$ , and since $d \in X$ , the definition of $D$ gives $d \in D$ , a contradiction again. So $f$ is not surjective. This proves the theorem.

Surjectivity was used once, to obtain $d$ ; everything else holds for every function $f$ . Read without the supposition, the proof shows that $D \ne f(x)$ for every $x \in X$ : the two sets disagree about $x$ . Three consequences follow.

(i) Russell’s theorem is the same argument. In Theorem 1.1.4, the set $R_A = \{ x \in A : x \notin x \}$ is the set $D$ built from the rule $f(x) \mathrel{:=} x$ : each $x \in A$ is tested against itself. The proof that $D$ differs from every $f(x)$ becomes the proof that $R_A$ differs from every element of $A$ , that is, $R_A \notin A$ . (The rule $x \mapsto x$ need not map into $\mathcal{P}\left( A \right)$ , but the argument never used that $f(x) \subseteq X$ , only the test “ $x \in f(x)$ ”.)
(ii) The power set is strictly bigger. The map $x \mapsto \{x\}$ is an injection $X \to \mathcal{P}\left( X \right)$ , since $\{x\} = \{y\}$ gives $x = y$ . So $\mathcal{P}\left( X \right)$ has at least as many elements as $X$ , in the sense that $X$ is in bijection with a subset of it, and by the theorem it is not equinumerous with $X$ , since a bijection would be a surjection. Section 3.5 names this relation: $X$ is strictly smaller than $\mathcal{P}\left( X \right)$ .
(iii) There is no largest size. $\mathbb{N}$ , $\mathcal{P}\left( \mathbb{N} \right)$ , $\mathcal{P}\left( \mathcal{P}\left( \mathbb{N} \right) \right)$ , …: each set in this sequence is strictly bigger than the one before.

Corollary 3.4.3 (The Subsets of the Naturals)

The power set $\mathcal{P}\left( \mathbb{N} \right)$ is uncountable.

Proof. The set $\mathcal{P}\left( \mathbb{N} \right)$ is non-empty, since $\emptyset \in \mathcal{P}\left( \mathbb{N} \right)$ , and by Theorem 3.4.2 with $X = \mathbb{N}$ there is no surjection $\mathbb{N} \to \mathcal{P}\left( \mathbb{N} \right)$ . By Definition 3.2.1, $\mathcal{P}\left( \mathbb{N} \right)$ is not countable.

The two diagonal proofs are one. By the correspondence of Section 1.4, $S \mapsto \mathbf{1}_S$ is a bijection $\mathcal{P}\left( \mathbb{N} \right) \to \{0, 1\}^{\mathbb{N}}$ , with inverse $b \mapsto \{ n \in \mathbb{N} : b(n) = 1 \}$ (Theorem 1.5.4). Given $f \colon \mathbb{N} \to \mathcal{P}\left( \mathbb{N} \right)$ , the sequence $g(n) = 1 - \mathbf{1}_{f(n)}(n)$ of Theorem 3.4.1 is $1$ exactly when $n \notin f(n)$ , so $g = \mathbf{1}_D$ for the set $D$ of Cantor’s proof.

3.4.3. Decimal expansions

The real numbers should be next. A real number in $[0, 1)$ is written as a decimal $0.d_1 d_2 d_3 \ldots$ , a sequence of digits, so the diagonal suggests itself: list the numbers, write their decimals as the rows of a table, and change the diagonal digits. Two questions must be answered first. What does it mean that a sequence of digits is the decimal of $x$ ? And what is $0.999\ldots$ ? School says it equals $1$ , and a diagonal that produces $0.4999\ldots$ when $0.5000\ldots$ is on the list has produced a number that is on the list.

An infinite sum would answer the first question, but this book has not yet defined one. Finite sums are enough. The first $n$ digits of $x$ should pin $x$ down to within $10^{-n}$ .

A digit sequence is a decimal of $x$ when each of its finite truncations is within one unit of its last place below $x$ .

Definition 3.4.1 (Decimal Expansion)

A digit sequence is a function $k \mapsto d_k$ from $\mathbb{Z}_{>0}$ to $\{0, 1, \dots, 9\}$ . For $n \ge 1$ let $t_n \mathrel{:=} \sum_{k=1}^{n} d_k 10^{-k}$ (Definition 2.3.1), where $10^{-k} \mathrel{:=} (1/10)^k$ (Definition 2.3.2). The digit sequence is a decimal expansion of $x \in [0, 1]$ if for every $n \ge 1$ , $t_n \le x \le t_n + 10^{-n} .$

In words: $t_n$ is the number written with the first $n$ digits, $0.d_1 \ldots d_n$ , and the condition says that $x$ lies in the closed interval of length $10^{-n}$ starting at $t_n$ , for every $n$ . The digits are indexed from $1$ , so that $d_k$ is the digit in the $k$ -th place after the point. No infinite sum appears: every $t_n$ is a finite sum.

Examples.

Zero. The all-zero sequence has $t_n = 0$ , and $0 \le 0 \le 10^{-n}$ ; it is an expansion of $0$ .
One half, twice. The sequence $5, 0, 0, \dots$ has $t_n = \frac12$ for every $n \ge 1$ , and $\frac12 \le \frac12 \le \frac12 + 10^{-n}$ . The sequence $4, 9, 9, \dots$ has $t_n = \frac{4}{10} + \sum_{k=2}^{n} 9 \cdot 10^{-k} = \frac12 - 10^{-n}$ , by Proposition 2.3.6, so $t_n \le \frac12 \le t_n + 10^{-n} = \frac12$ . Both are expansions of $\frac12$ .
One. The all-nine sequence has $t_n = \sum_{k=1}^{n} 9 \cdot 10^{-k} = 1 - 10^{-n}$ (Proposition 2.3.6), so $t_n \le 1 \le t_n + 10^{-n} = 1$ : it is an expansion of $1$ .

A non-example by minimal change. Keep the sequence $5, 0, 0, \dots$ and move $x$ from $\frac12$ to $0.51$ . The inequalities still hold for $n = 1$ ( $0.5 \le 0.51 \le 0.6$ ) and for $n = 2$ ( $0.50 \le 0.51 \le 0.51$ ), and they fail at $n = 3$ : $0.51 > 0.500 + 0.001$ . So $5, 0, 0, \dots$ is not an expansion of $0.51$ ; the clause “for every $n \ge 1$ ” is what fails.

Why this definition. Both inequalities are non-strict. With a strict right inequality, $x < t_n + 10^{-n}$ , the all-nine sequence would be an expansion of no number at all: it would need $x < 1$ together with $1 - 10^{-n} \le x$ for every $n$ , and no real number satisfies both, by the Archimedean property (a school fact; Analysis on the Real Line, Chapter 1 proves it). The non-strict form is what makes $0.999\ldots = 1$ true, and true by the definition: the inequalities for $x = 1$ are checked in Example 3, and no other number satisfies them, since $1 - 10^{-n} \le x \le 1$ for every $n$ forces $x = 1$ , again by the Archimedean property (this is the uniqueness half of (D2) below). Example 2 shows that the price is two expansions for some numbers.

What this book does not prove are the facts that make expansions behave as school says. We state them once and use them in this section and the next, always by name.

(D1) Every $x \in [0, 1)$ has a decimal expansion that does not end in all $9$ s.
(D2) Every digit sequence is a decimal expansion of exactly one $x \in [0, 1]$ .
(D3) If two different digit sequences are expansions of the same $x$ , then one of them ends in all $9$ s and the other ends in all $0$ s.

Here a digit sequence ends in all $9$ s if there is $N \ge 1$ with $d_k = 9$ for every $k \ge N$ , and likewise for $0$ s. By the uniqueness in (D2), we may write $x = 0.d_1 d_2 d_3 \ldots$ for “ $x$ is the number of which $d_1, d_2, d_3, \dots$ is an expansion”. So $0.4999\ldots = 0.5000\ldots = \frac12$ , as in (D3).

Neither (D1) nor (D2) follows from what we have so far. (D3) does, by a finite computation at the first place where the two sequences differ (Theorem 2.1.3, Proposition 2.3.6); we state it with the others to quote it by name. The existence half of (D2), that some $x$ satisfies all the inequalities at once, is where the completeness of $\mathbb{R}$ hides, and Analysis on the Real Line, Chapter 1 takes completeness as an axiom. The uniqueness half of (D2) and the “not ending in all $9$ s” of (D1) rest on the Archimedean property: two numbers $x, x'$ with $\left| x - x' \right| \le 10^{-n}$ for every $n$ must be equal, which Analysis on the Real Line, Chapter 1 also proves. Until then we use them as school facts, and each use names the fact it uses.

One consequence is used below. A digit sequence with no digit $0$ and no digit $9$ is the only expansion of its number. Indeed, by (D3) a second expansion of the same number would force one of the two to end in all $9$ s and the other in all $0$ s; the given sequence ends in neither, since it has no $9$ s and no $0$ s at all.

3.4.4. The real numbers are uncountable

With the facts in hand, the diagonal runs on digits. Two precautions are built in. Each number on the list gets its expansion by a rule, so that no choosing is needed. And the new digits avoid $0$ and $9$ , so that the new number has only one expansion.

Theorem 3.4.4 (The Reals Are Uncountable, by Decimals)

The interval $[0, 1)$ is uncountable. Hence $\mathbb{R}$ is uncountable.

Idea. Take an arbitrary list of numbers in $[0, 1)$ , write each as its expansion with no tail of $9$ s, and change the $n$ -th digit of the $n$ -th number to $4$ or $5$ . The resulting digit sequence is an expansion of some $y$ , by (D2). If $y$ were the $n$ -th number, it would have two different expansions, one with no $0$ s or $9$ s, against (D3).

Proof. Let $f \colon \mathbb{N} \to [0, 1)$ be any function. For $n \ge 1$ let $x_n \mathrel{:=} f(n - 1)$ , so that the list $x_1, x_2, x_3, \dots$ has the same values as $f$ .

For each $n \ge 1$ , $x_n$ has an expansion not ending in all $9$ s, by (D1), and only one: by (D3), two different such expansions would include one ending in all $9$ s. Let $(d_{n,k})_{k \ge 1}$ be this expansion. It is named by a rule, “the expansion of $x_n$ not ending in all $9$ s”, so no choice is involved. Define a digit sequence by $e_n \mathrel{:=} \begin{cases} 5 & \text{if } d_{n,n} \ne 5, \\ 4 & \text{if } d_{n,n} = 5, \end{cases} \qquad (n \ge 1) .$ Then $e_n \ne d_{n,n}$ for every $n \ge 1$ . By (D2), there is $y \in [0, 1]$ of which $(e_k)_{k \ge 1}$ is an expansion. Its first truncation is $t_1 = e_1/10 \in \{0.4, 0.5\}$ , so $0.4 \le t_1 \le y \le t_1 + 0.1 \le 0.6$ , and in particular $y \in [0, 1)$ .

Let $n \ge 1$ , and suppose $y = x_n$ . Then $(e_k)$ and $(d_{n,k})$ are both expansions of $y$ , and they are different, since they differ in place $n$ . But $(e_k)$ has no digit $0$ and no digit $9$ , so by the consequence of (D3) stated above it is the only expansion of $y$ , a contradiction. So $y \ne x_n$ for every $n \ge 1$ , and $y$ is not a value of $f$ . Since $f$ was arbitrary, no function $\mathbb{N} \to [0, 1)$ is surjective; and $[0, 1)$ is non-empty, since it contains $0$ . By Definition 3.2.1, $[0, 1)$ is not countable.

Finally, if $\mathbb{R}$ were countable, its subset $[0, 1)$ would be countable by Proposition 3.2.3. So $\mathbb{R}$ is uncountable.

Why the digits $4$ and $5$ . The first rule that comes to mind is $e_n \mathrel{:=} 9 - d_{n,n}$ , which also changes every diagonal digit. Run it on the list $x_1 = \frac12$ , $x_n = 0$ for $n \ge 2$ (that is, $f(0) = \frac12$ and $f(n) = 0$ for $n \ge 1$ ). The expansions are $0.5000\ldots$ and $0.000\ldots$ , so $d_{1,1} = 5$ and $d_{n,n} = 0$ for $n \ge 2$ . The naive rule produces $e_1 = 4$ and $e_n = 9$ for $n \ge 2$ : the sequence $0.4999\ldots$ , which is an expansion of $\frac12 = x_1$ by Example 2. The new digit sequence differs from every row, and its number is on the list. The rule with $4$ and $5$ , on the same list, gives $0.4555\ldots = \frac{41}{90}$ , which is on no row. Avoiding $0$ and $9$ is exactly what the last paragraph of the proof uses.

Analysis on the Real Line, Chapter 1 proves that $\mathbb{R}$ is uncountable again, with no decimals at all, directly from its least upper bound axiom; that proof needs none of (D1)–(D3).

3.4.5. Transcendental numbers

A real number that is not algebraic is called transcendental. Section 3.3 showed that the set $\mathrm{Alg}$ of algebraic numbers is countable (Theorem 3.3.4).

Corollary 3.4.5 (Transcendental Numbers Exist)

The set $\mathbb{R} \setminus \mathrm{Alg}$ of transcendental numbers is uncountable. In particular, there is a real number that is not algebraic.

Proof. By excluded middle (Logic and Proof, Proposition 2.5.3), every real number is in $\mathrm{Alg}$ or not, so $\mathbb{R} = \mathrm{Alg} \cup (\mathbb{R} \setminus \mathrm{Alg})$ . Suppose $\mathbb{R} \setminus \mathrm{Alg}$ is countable. Since $\mathrm{Alg}$ is countable by Theorem 3.3.4, $\mathbb{R}$ is countable by Proposition 3.2.5, contradicting Theorem 3.4.4. So $\mathbb{R} \setminus \mathrm{Alg}$ is uncountable. In particular $\mathbb{R} \setminus \mathrm{Alg} \ne \emptyset$ , since $\emptyset$ is countable (Definition 3.2.1). So not every $x$ satisfies $x \notin \mathbb{R} \setminus \mathrm{Alg}$ : otherwise $\mathbb{R} \setminus \mathrm{Alg}$ would be an empty set (Definition 1.1.4), hence equal to $\emptyset$ (Proposition 1.1.3). By the classical law Logic and Proof, Proposition 6.2.1 (a) and $\mathrm{\neg\neg E}$ , some $x$ lies in $\mathbb{R} \setminus \mathrm{Alg}$ ; this $x$ is a real number that is not algebraic. This last passage, from “not empty” to “has an element”, is a classical step (Logic and Proof, Section 8.7).

Remark. The proof names no transcendental number: it shows that the set of them is too large to be countable, hence not empty. Its classical steps are the split of $\mathbb{R}$ into $\mathrm{Alg}$ and its complement (excluded middle) and the last one, from “not empty” to “has an element”. Compare the classical proof of Logic and Proof, Theorem 8.7.1 in Logic and Proof, Section 8.7, which also names no witness (unlike Logic and Proof, Proposition 8.7.2, which does). Proving that a particular number, such as $\pi$ , is transcendental is a different and much harder matter.

3.4.6. Exercises

A. Check your understanding

Exercise (A1)

These parts are about the proof of Theorem 3.4.2.

(a) Where in the proof is the surjectivity of $f$ used, and what does it supply?
(b) Run the proof on $X = \{1, 2, 3\}$ and $f(1) = \{1, 2\}$ , $f(2) = \emptyset$ , $f(3) = \{1, 3\}$ . What is $D$ ? Is $D$ a value of $f$ ?
(c) State the idea of the proof in two sentences.
(d) Why does the same argument not show that there is no surjection $X \to X$ ?

Solution.

(a) It is used once, right after $D$ is defined: surjectivity supplies an element $d \in X$ with $f(d) = D$ . The two cases $d \in D$ and $d \notin D$ are then both refuted. Everything before that line holds for every function $f$ .
(b) Test each $x$ against $f(x)$ : $1 \in f(1)$ , so $1 \notin D$ ; $2 \notin f(2) = \emptyset$ , so $2 \in D$ ; $3 \in f(3)$ , so $3 \notin D$ . Hence $D = \{2\}$ . It is not a value of $f$ : the values are $\{1, 2\}$ , $\emptyset$ , $\{1, 3\}$ , and $D$ differs from $f(x)$ about $x$ in each case ( $1 \in f(1) \setminus D$ , $2 \in D \setminus f(2)$ , $3 \in f(3) \setminus D$ ).
(c) Build the set $D$ of those $x$ that are not in their own image $f(x)$ . Then $D$ disagrees with every $f(x)$ about the element $x$ , so it is not a value of $f$ .
(d) The set $D$ is a subset of $X$ , so it is a candidate value only for a function into $\mathcal{P}\left( X \right)$ . For $f \colon X \to X$ , the argument (where the test $x \in f(x)$ makes sense at all) shows that $D$ is not a value of $f$ , but $D$ need not be an element of $X$ , so nothing contradicts surjectivity. Indeed $\operatorname{id}_X$ is a surjection $X \to X$ ; with $f = \operatorname{id}_X$ the argument is Russell’s, and shows only that $D = R_X$ is not an element of $X$ (Theorem 1.1.4).

B. Practice

Exercise (B1: A faded diagonal)

Let $\mathbb{N}^{\mathbb{N}}$ be the set of all functions $\mathbb{N} \to \mathbb{N}$ . Here is a proof that $\mathbb{N}^{\mathbb{N}}$ is uncountable, with its last step left blank. Name the move, then complete it.

Let $f \colon \mathbb{N} \to \mathbb{N}^{\mathbb{N}}$ be any function, and write $f_n \mathrel{:=} f(n)$ , so that $f_0, f_1, f_2, \dots$ is a list of elements of $\mathbb{N}^{\mathbb{N}}$ . Define $g \colon \mathbb{N} \to \mathbb{N}$ by $g(n) \mathrel{:=} f_n(n) + 1$ . (Last step: ____________________.) Since $f$ was arbitrary, no function $\mathbb{N} \to \mathbb{N}^{\mathbb{N}}$ is surjective, and as $\mathbb{N}^{\mathbb{N}}$ is non-empty (it contains the zero function), $\mathbb{N}^{\mathbb{N}}$ is not countable.

Solution. The move is the diagonal: $g$ is built to disagree with the list’s $n$ -th entry in place $n$ . The last step: for every $n \in \mathbb{N}$ , $g(n) = f_n(n) + 1 \ne f_n(n)$ , so $g \ne f_n$ by Proposition 1.4.1 (two equal functions agree at $n$ ). Hence $g$ is not on the list: $g$ is an element of $\mathbb{N}^{\mathbb{N}}$ (its values $f_n(n) + 1$ are natural numbers) that is not a value of $f$ , and $f$ is not surjective.

Exercise (B2)

Prove that the set of infinite subsets of $\mathbb{N}$ is uncountable.

Solution. Let $\mathcal{F}$ be the set of finite subsets of $\mathbb{N}$ and $\mathcal{I}$ the set of infinite ones, both subsets of $\mathcal{P}\left( \mathbb{N} \right)$ defined by specification. By excluded middle (Logic and Proof, Proposition 2.5.3), every subset of $\mathbb{N}$ is finite or not finite, that is, finite or infinite (Definition 3.1.3), so $\mathcal{P}\left( \mathbb{N} \right) = \mathcal{F} \cup \mathcal{I}$ . The set $\mathcal{F}$ is countable by Exercise (C1: Finite subsets of the natural numbers). If $\mathcal{I}$ were countable, $\mathcal{P}\left( \mathbb{N} \right)$ would be countable by Proposition 3.2.5, contradicting Corollary 3.4.3. So $\mathcal{I}$ is uncountable.

Exercise (B3: Expansions of three numbers)

For each of $x = \frac13$ , $\frac12$ , $1$ , find all decimal expansions of $x$ , checking the inequalities of Definition 3.4.1 for each one you give, and say which of (D1)–(D3) each case illustrates.

Solution. We use Proposition 2.3.6 with $r = \frac{1}{10}$ , after taking the constant factor $\frac{1}{10}$ out of the sum: $\sum_{k=1}^{n} 10^{-k} = \frac{1}{10} \sum_{k=1}^{n} (\frac{1}{10})^{k-1} = \frac{1}{10} \cdot \frac{1 - 10^{-n}}{9/10} = \frac19 (1 - 10^{-n})$ .

$x = \frac13$ . The all-three sequence has $t_n = \frac39 (1 - 10^{-n}) = \frac13 - \frac13 10^{-n}$ , so $t_n \le \frac13 \le t_n + 10^{-n}$ . It is an expansion, and it does not end in all $9$ s, as (D1) promises. It ends in neither $9$ s nor $0$ s, so by (D3) no other expansion of $\frac13$ exists. Answer: $0.333\ldots$ only.

$x = \frac12$ . Example 2 after Definition 3.4.1 checks that $0.5000\ldots$ and $0.4999\ldots$ are expansions. There are no others: if three different expansions existed, two of them would both end in all $9$ s or both not; but by (D3), of two different expansions of one number, one ends in all $9$ s and the other in all $0$ s, and a sequence ending in all $0$ s does not end in all $9$ s (from some place on, its digits would be both $0$ and $9$ ). Answer: exactly these two, which illustrate (D3); the first is the one (D1) promises.

$x = 1$ . The all-nine sequence is an expansion (Example 3). Conversely, let $(d_k)$ be an expansion of $1$ , and suppose $d_m \le 8$ for some $m$ . Since every digit is at most $9$ , $t_m \le \sum_{k=1}^{m} 9 \cdot 10^{-k} - 10^{-m} = 1 - 2 \cdot 10^{-m}$ , so $t_m + 10^{-m} \le 1 - 10^{-m} < 1$ , against the definition. So every digit is $9$ . Answer: $0.999\ldots$ only. The all-nine sequence is an expansion of $1$ , an instance of the existence half of (D2). Here (D3) has no second expansion to compare. The case also shows why (D1) is stated for $[0, 1)$ only: the one expansion of $1$ ends in all $9$ s.

C. Going deeper

Exercise (C1: Exit check: Cantor)

Prove Theorem 3.4.2: for every set $X$ , there is no surjection $X \to \mathcal{P}\left( X \right)$ . Deduce that $\mathcal{P}\left( \mathbb{N} \right)$ is uncountable.

Solution. Let $f \colon X \to \mathcal{P}\left( X \right)$ be a function, and let $D \mathrel{:=} \{ x \in X : x \notin f(x) \}$ , a subset of $X$ , so $D \in \mathcal{P}\left( X \right)$ . Suppose $f$ is surjective. Then $D = f(d)$ for some $d \in X$ . If $d \in D$ , then $d \notin f(d) = D$ by the definition of $D$ , a contradiction; so $d \notin D$ . But then $d \notin f(d)$ and $d \in X$ , so $d \in D$ by the definition of $D$ , a contradiction. Hence $f$ is not surjective, and since $f$ was arbitrary, no surjection $X \to \mathcal{P}\left( X \right)$ exists.

For $X = \mathbb{N}$ : by Definition 3.2.1, $\mathcal{P}\left( \mathbb{N} \right)$ is countable only if it is empty or there is a surjection $\mathbb{N} \to \mathcal{P}\left( \mathbb{N} \right)$ . It is not empty, since $\emptyset \in \mathcal{P}\left( \mathbb{N} \right)$ , and the theorem excludes the surjection. So $\mathcal{P}\left( \mathbb{N} \right)$ is uncountable.

Marking scheme. (10 points) - 2: takes an arbitrary $f \colon X \to \mathcal{P}\left( X \right)$ and either assumes it onto, towards a contradiction, or sets out to show that it misses a set. - 3: defines $D = \{ x \in X : x \notin f(x) \}$ and notes that it is a subset of $X$ . - 2: uses surjectivity to obtain $d$ with $f(d) = D$ (or, in the direct form, fixes an arbitrary $x$ ). - 2: refutes both cases, $d \in D$ and $d \notin D$ (or shows that $D$ and $f(x)$ disagree about $x$ ). - 1: the deduction for $\mathcal{P}\left( \mathbb{N} \right)$ , handling both clauses of “countable”: non-empty, and no surjection from $\mathbb{N}$ . The direct form (“ $D \ne f(x)$ for every $x$ , since they disagree about $x$ ”) earns the same points: 2 for the arbitrary $f$ , 3 for $D$ , 4 for the disagreement at every $x$ , 1 for the deduction. Fatal errors (0 for the step): $D = \{ x \in X : x \in f(x) \}$ (it may well be a value of $f$ ); checking the claim for one particular $f$ and concluding for all, as in (N1) of Logic and Proof, Example (What is not allowed) (0 for the first step).

Exercise (C2: Permutations of the naturals)

Prove that the set of all bijections $\mathbb{N} \to \mathbb{N}$ is uncountable.

Solution (Hint 1). Consider the bijections that only swap $2n$ and $2n + 1$ , for some of the $n \in \mathbb{N}$ , and fix every other number.

Solution (Hint 2). Such bijections correspond to $\{0, 1\}^{\mathbb{N}}$ : the $n$ -th entry says whether the pair $2n, 2n + 1$ is swapped.

Solution. Every $m \in \mathbb{N}$ is $2q + r$ for exactly one pair $(q, r)$ with $q \in \mathbb{N}$ and $r \in \{0, 1\}$ (Theorem 2.2.3 with divisor $2$ , the quotient lying in $\mathbb{N}$ as in the proof of Proposition 3.2.5). For $b \in \{0, 1\}^{\mathbb{N}}$ define $\pi_b \colon \mathbb{N} \to \mathbb{N}$ by $\pi_b(2q + r) \mathrel{:=} \begin{cases} 2q + r & \text{if } b(q) = 0, \\ 2q + 1 - r & \text{if } b(q) = 1, \end{cases}$ so $\pi_b$ swaps $2q$ and $2q + 1$ when $b(q) = 1$ and fixes them otherwise. It maps each pair $\{2q, 2q + 1\}$ to itself, and applying it twice returns every number to its place, so $\pi_b \circ \pi_b = \operatorname{id}_{\mathbb{N}}$ , and $\pi_b$ is a bijection by Theorem 1.5.4.

Let $B$ be the set of bijections $\mathbb{N} \to \mathbb{N}$ ; it is non-empty, since $\operatorname{id}_{\mathbb{N}} \in B$ . Let $f \colon \mathbb{N} \to B$ be any function, and write $f_n \mathrel{:=} f(n)$ . Define $b \in \{0, 1\}^{\mathbb{N}}$ by $b(n) \mathrel{:=} 1$ if $f_n(2n) = 2n$ , and $b(n) \mathrel{:=} 0$ otherwise, and let $\pi \mathrel{:=} \pi_b \in B$ . For every $n \in \mathbb{N}$ , $\pi(2n) \ne f_n(2n)$ : if $f_n(2n) = 2n$ , then $b(n) = 1$ and $\pi(2n) = 2n + 1$ ; if $f_n(2n) \ne 2n$ , then $b(n) = 0$ and $\pi(2n) = 2n$ . So $\pi \ne f_n$ for every $n$ (Proposition 1.4.1), and $f$ is not surjective. Since $f$ was arbitrary and $B \ne \emptyset$ , $B$ is uncountable (Definition 3.2.1).

This is the diagonal again, with the $n$ -th entry tested at the place $2n$ . Alternatively, $b \mapsto \pi_b$ is an injection $\{0, 1\}^{\mathbb{N}} \to B$ , since $\pi_b(2q)$ is $2q$ or $2q + 1$ according to $b(q)$ ; if $B$ were countable, composing with an injection $B \to \mathbb{N}$ (Theorem 3.2.2) would make $\{0, 1\}^{\mathbb{N}}$ countable, against Theorem 3.4.1.

Marking scheme. (10 points) - 3: defines, for each $b \in \{0, 1\}^{\mathbb{N}}$ (or each set of pairs), the bijection that swaps $2n$ and $2n + 1$ exactly when $b(n) = 1$ , and proves it is a bijection. - 4: given an arbitrary list of bijections, defines $b$ from the $n$ -th entry’s value at a place belonging to the $n$ -th pair, and shows that the resulting bijection differs from the $n$ -th entry; or shows that $b \mapsto \pi_b$ is injective. - 3: concludes, with the non-emptiness of the set of bijections or through Theorem 3.4.1 and the closure properties of countable sets. Fatal errors (0 for the step): the plain diagonal $g(n) \mathrel{:=} f_n(n) + 1$ , which is not a bijection; a “bijection” that moves numbers between different pairs without checking that it stays one-to-one and onto.