Uncountable sets and the diagonal argument

Result 1. Proof. Let A be nonempty. If A = \{a_1, \dots, a_r\} is finite, the function f(n) = a_{\min(n + 1, r)} is onto. If A is countably infinite, a bijection \mathbb{N} \to A is onto. Conversely, if some f : \mathbb{N} \to A is onto, A is countable by Result 4 of Countable sets. \square

Result 2. Proof. We argue by contradiction. Suppose \{0, 1\}^{\mathbb{N}} is countable. It is nonempty, so by Result 1 there is an onto function f : \mathbb{N} \to \{0, 1\}^{\mathbb{N}}. Write s_n = f(n), so s_n(k) is the term of the nth sequence in place k. Define a sequence t by

Each t(n) is 0 or 1, so t \in \{0, 1\}^{\mathbb{N}}. Since f is onto, t = s_m for some m. Compare the two in place m: on one hand t(m) = s_m(m), because t = s_m; on the other t(m) = 1 - s_m(m) by definition. So 2 s_m(m) = 1, which no value s_m(m) \in \{0, 1\} satisfies. This contradiction shows \{0, 1\}^{\mathbb{N}} is not countable. \square

Result 3. Proof. Let c and d be different expansions of the same number and let j be the first place where they differ; name them so that c_j < d_j. The places before j agree, so subtracting them leaves

Every digit is at most 9 and \sum_{k > j} 9 \cdot 10^{-k} = 10^{-j}, so the left side is at most c_j 10^{-j} + 10^{-j} = (c_j + 1) 10^{-j}, with equality only if c_k = 9 for every k > j. Every digit is at least 0 and d_j \ge c_j + 1, so the right side is at least (c_j + 1) 10^{-j}, with equality only if d_j = c_j + 1 and d_k = 0 for every k > j. The two sides are equal, so both equalities hold. An expansion with no 0 and no 9 can be neither c nor d, so no other expansion gives its number. \square

Result 4. Proof. For decimals it is tidier to number a list from 1; a list a_1, a_2, \dots is a function \mathbb{N} \to (0, 1) shifted by one place. Suppose (0, 1) is countable. By Result 1 there is a list a_1, a_2, a_3, \dots in which every number in (0, 1) appears. For each n fix one decimal expansion of a_n, and let e_n be its nth digit. Put

and let x = 0.c_1 c_2 c_3 \dots. Every digit of x is 4 or 5, so \displaystyle \frac{4}{9} = 0.444\ldots \le x \le 0.555\ldots = \frac{5}{9}, and x \in (0, 1). So x = a_m for some m. Then 0.c_1 c_2 \dots and the chosen expansion of a_m are two expansions of one number, and they are different, since c_m \ne e_m. But the expansion of x uses no 0 and no 9, so by Result 3 it is the only expansion of x. This contradiction proves the result. \square

The digits 4 and 5 are what make the proof honest. Differing from a_m in one digit does not by itself make x a different number, since 0.4999\ldots and 0.5000\ldots differ in every digit and are equal. Keeping 0s and 9s out of x gives it a single expansion, and then a different digit does mean a different number.

Result 5. Proof. Matching two sets one to one built a bijection h : (0, 1) \to \mathbb{R}, namely \displaystyle h(x) = \frac{1 - x}{x} - \frac{x}{1 - x}, so the two sets are the same size. If \mathbb{R} were countable, there would be an injection g : \mathbb{R} \to \mathbb{N} (Result 4 of Countable sets), and g \circ h would be an injection (0, 1) \to \mathbb{N}, making (0, 1) countable, against Result 4. \square

Result 6. Proof. Let U \subseteq B with U uncountable. If B were countable, its subset U would be countable by Result 5 of Countable sets. \square

Result 7. Proof. \mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q}), and \mathbb{Q} is countable. If \mathbb{R} \setminus \mathbb{Q} were countable, the union of two countable sets would be countable (Result 7 of Countable sets), so \mathbb{R} would be, against Result 5. \square

Result 8. Proof. The algebraic numbers are countable (Result 11 of Countable sets, given there with a sketch). The same argument as for Result 7, with the algebraic reals in place of \mathbb{Q}, shows the rest of \mathbb{R} is uncountable. \square

Result 9. A sequence s \in \{0, 1\}^{\mathbb{N}} is a rule giving each place k a term s(k) \in \{0, 1\}, which is exactly a function \mathbb{N} \to \{0, 1\}: one set under two names, so Result 2 applies.

1. s_n(n) = 1 since 2n is even, so t = (0, 0, 0, \dots). The list holds two sequences: s_n = (1, 0, 1, 0, \dots) for even n and (0, 1, 0, 1, \dots) for odd n.
2. n < 2^n, so the 2^n place of n is 0: s_n(n) = 0 and t = (1, 1, 1, \dots). Base-2 numerals are unique, so the list holds each sequence with finitely many 1s exactly once, and nothing else.
3. Diagonal digits 2, 6, 5, 6, 5 (from 0.25, 0.666\ldots, 0.375, 0.1666\ldots, 0.555\ldots), so x = 0.55454\ldots. With 0.374999\ldots the third digit is 4, so c_3 = 5 and x = 0.55554\ldots.
4. Each digit lies between 4 and 5, so x lies between \displaystyle \sum_{k \ge 1} 4 \cdot 10^{-k} = \frac{4}{9} and \displaystyle \sum_{k \ge 1} 5 \cdot 10^{-k} = \frac{5}{9}, comparing the series term by term.
5. \displaystyle \frac{7}{20} = 0.35000\ldots = 0.34999\ldots and \displaystyle \frac{13}{40} = 0.325000\ldots = 0.324999\ldots. By Result 3 a number with two expansions has one ending in 0s, so it is \displaystyle \frac{m}{10^j}. But \displaystyle 10^j \cdot \frac{2}{7} is not an integer, since the prime 7 divides neither 2 nor 10.
6. Proof. Given any list s_0, s_1, \dots of such sequences, put t(2n) = 1 - s_n(2n) and t(2n + 1) = 1. Then t has a 1 in every odd place, so infinitely many, and t \ne s_n in place 2n. The set is nonempty, so Result 1 applies. \square
7. Proof. Let j : A \to B be an injection. If B were countable, with injection g : B \to \mathbb{N}, then g \circ j would be an injection A \to \mathbb{N}, making A countable. \square
8. Proof. By Result 3 such a number has an expansion ending in 0s, so it equals \displaystyle \frac{m}{10^j} for integers m, j, and is rational. The set is a subset of \mathbb{Q}, so countable. \square
9. Proof. Suppose a list s_0, s_1, \dots misses only u_1, \dots, u_r. Then u_1, \dots, u_r, s_0, s_1, \dots is a list (the term in position n is u_{n+1} for n < r and s_{n-r} after) that misses nothing, against Result 2. \square
10. Proof. The map \varphi(x) = a + (b - a)x is a bijection (0, 1) \to (a, b), with inverse \displaystyle y \mapsto \frac{y - a}{b - a}. So (a, b) is uncountable: an injection g : (a, b) \to \mathbb{N} would make g \circ \varphi an injection (0, 1) \to \mathbb{N}, against Result 4. If every number of (a, b) were in C, then (a, b) would be a subset of a countable set and so countable (Result 5 of Countable sets). \square
11. Proof. By Exercise 10, (a, b) is uncountable. Its algebraic members form a subset of the countable set of algebraic numbers, so they are countable. If its transcendental members were countable too, (a, b) would be a union of two countable sets and so countable. \square
12. g_s(0), \dots, g_s(5) are 1, 3, 4, 7, 8, 10. s = (0, 1, 0, 1, \dots), with s(n) = 1 exactly for odd n. No: g_s(2) is 4 or 5, and 3 \cdot 2 = 6.
13. (0, 0, 1, 1, 0, 1, 0, 1, 0, 0). The function with f(n) = 1 when 3 \mid n and 0 otherwise.
14. Length-4 strings start at position 15 with 0000, so w_{20} is the sixth of them, 0101 (5 in base 2). 1101 is 13 in base 2, so it is at position 15 + 13 = 28.
15. The listed strings are exactly those with finitely many nonzero digits, and t uses only 4s and 5s, so it has infinitely many. It is the reversed digit string of no natural number. The argument shows these strings do not exhaust all digit strings, nothing about \mathbb{N}.
16. Proof. x \in (0, 1) and, as in the proof of Result 4, x \ne a_n for every n. Every rational number in (0, 1) is some a_n, so x is not rational. \square
17. Proof. If x^2 = q is rational then q \ge 0 and \displaystyle x = \sqrt{q} or \displaystyle x = -\sqrt{q}. So the reals with x^2 rational are the union of the images of the nonnegative rationals under \displaystyle q \mapsto \sqrt{q} and \displaystyle q \mapsto -\sqrt{q}, two countable sets, so countable. The rest of \mathbb{R} is uncountable, as in Result 7. \square
18. Proof. Every f \in F has f(0) = 0, so no new function can differ from f_0 in place 0. Shift by one: given a list f_0, f_1, \dots of F, put g(0) = 0 and g(n + 1) = 1 if f_n(n + 1) = 0, otherwise g(n + 1) = 0. Then g(m) \le m for all m, so g \in F, and g \ne f_n in place n + 1. F is nonempty, so Result 1 applies. \square
19. Proof. An eventually periodic sequence is u followed by v repeated forever, for a finite string u and a nonempty finite string v. Send the string u\#v over \{0, 1, \#\} to that sequence. This is onto the eventually periodic sequences from a subset of the countable set of strings (Countable sets, Results 5 and 9), so they are countable (Result 4 there). The rest of \{0, 1\}^{\mathbb{N}} is uncountable, by the argument of Result 7. \square