The uncountability of the reals

Theorem

The uncountability of the reals

T-006Home MU-101Threads logic · structure

Statement

Let \(\mathbb{R}\) denote the complete ordered field of real numbers and \(\mathbb{N} = \{1,2,3,\dots\}\) the natural numbers. Then \(\mathbb{R}\) is uncountable: there is no surjection \(f\colon \mathbb{N} \to \mathbb{R}\). Equivalently, for every function \(f\colon \mathbb{N} \to \mathbb{R}\) — no matter how it is defined, and with repetitions allowed — there exists a real number \(x\) with \(x \notin f(\mathbb{N})\). In particular there is no bijection \(\mathbb{N} \to \mathbb{R}\), so the cardinality of \(\mathbb{R}\) strictly exceeds \(\aleph_0\). The hypotheses in force: (i) \(\mathbb{R}\) is Dedekind-complete (every nonempty set bounded above has a supremum); (ii) \(\mathbb{R}\) is Archimedean (a consequence of (i)); (iii) the statement quantifies over all functions \(f\colon \mathbb{N}\to\mathbb{R}\), not merely those given by an explicit rule.

Why it matters

This is the first theorem in mathematics to exhibit two genuinely different sizes of infinity. It splits the infinite into a hierarchy: \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\), and the algebraic numbers all share the cardinality \(\aleph_0\), while \(\mathbb{R}\) is strictly bigger. Existence proofs by counting fall out at once — transcendental numbers exist because there are too many reals for the countably many algebraic numbers to exhaust them — a striking non-constructive existence argument.

The method matters as much as the result. Cantor's diagonal argument is the template for Cantor's theorem \(\lvert X\rvert \lt \lvert \mathcal{P}(X)\rvert\), for the undecidability of the halting problem, for Gödel's incompleteness construction, and for Russell's paradox. Diagonalization is the single most-reused proof scheme in logic and computability; this theorem is where it enters the curriculum.

Hypotheses

Hypothesis (completeness of \(\mathbb{R}\)).Drop it and the conclusion fails: \(\mathbb{Q}\) is an Archimedean ordered field satisfying every axiom of \(\mathbb{R}\) except completeness, yet \(\mathbb{Q}\) is countable (enumerate fractions \(p/q\) by increasing \(\lvert p\rvert + q\)). Running the diagonal argument over an enumeration of \(\mathbb{Q}\) produces a number — but that number is irrational, so no contradiction arises. Completeness is used twice below: to make the digit series converge, and (via suprema) to build decimal expansions at all. Hypothesis (Archimedean property).Needed so that decimal digits faithfully separate numbers. In a non-Archimedean ordered field extension of \(\mathbb{R}\) (e.g. the field \(\mathbb{R}(t)\) of rational functions ordered by eventual dominance, or the hyperreals), two distinct elements can agree in every decimal digit — they differ by an infinitesimal — so "differs in digit \(n\)" no longer implies "distinct". In \(\mathbb{R}\) the Archimedean property follows from completeness, so it is not an independent axiom here, but it is the property the digit machinery actually consumes. Hypothesis (arbitrary \(f\), not just definable \(f\)).Restrict the quantifier and the theorem changes character: the set of computable reals is countable (there are only countably many Turing machines), yet no computable enumeration of it exists — the diagonal real built from a purported computable list would itself be computable, a contradiction. So "uncountable" must mean "no function whatsoever", not "no rule we can write down".

Proof

Strategy: given any \(f\colon \mathbb{N}\to\mathbb{R}\), we build a real \(x \in (0,1)\) whose decimal digits all lie in \(\{4,5\}\) and which disagrees with \(f(n)\) in the \(n\)-th digit. The digit set \(\{4,5\}\) is chosen to dodge the one subtlety of decimal notation: the double representation \(0.4999\ldots = 0.5000\ldots\).

Fix an arbitrary function \(f\colon \mathbb{N} \to \mathbb{R}\). It suffices to produce \(x \in \mathbb{R}\) with \(x \neq f(n)\) for every \(n \in \mathbb{N}\).

Definition of surjection: \(f\) is surjective iff every real is some \(f(n)\); exhibiting one missed value refutes surjectivity, and since \(f\) is arbitrary this rules out all candidate enumerations. A

Lemma (existence of decimal expansions). Every \(y \in [0,1)\) satisfies \[ y = \sum_{k=1}^{\infty} \frac{a_k}{10^k}, \qquad a_k := \lfloor 10^k y \rfloor - 10\,\lfloor 10^{k-1} y \rfloor \in \{0,1,\dots,9\}. \] Call \((a_k)\) the greedy expansion of \(y\).

The floor function is well defined by the Archimedean property (the set \(\{ m \in \mathbb{Z} : m \leq 10^k y \}\) is nonempty and bounded above, hence has a greatest element by completeness of \(\mathbb{R}\) applied to \(\mathbb{Z}\)-bounded sets). That \(a_k \in \{0,\dots,9\}\) follows from \(10^{k}y - 10\lfloor 10^{k-1}y\rfloor \in [0,10)\). The partial sums satisfy \(\sum_{k=1}^{n} a_k 10^{-k} = 10^{-n}\lfloor 10^n y\rfloor \in (y - 10^{-n},\, y\,]\), so they converge to \(y\): the series is a telescoping consequence of the digit definition, and convergence of the bound \(10^{-n} \to 0\) is again Archimedean. C

Lemma (separation of expansions). Let \((a_k), (b_k)\) be digit sequences in \(\{0,\dots,9\}\) with \(a_n \neq b_n\) for some \(n\), and suppose the sequence \((a_k)\) never takes the values \(0\) or \(9\). Then \[ \sum_{k=1}^{\infty} \frac{a_k}{10^k} \;\neq\; \sum_{k=1}^{\infty} \frac{b_k}{10^k}. \]

Suppose the sums are equal and let \(m\) be the least index with \(a_m \neq b_m\); without loss of generality \(a_m \lt b_m\). Subtracting the common initial segment and comparing tails, \[ 0 = \sum_{k \geq m}\frac{b_k - a_k}{10^k} \;\geq\; \frac{1}{10^m} - \sum_{k \gt m} \frac{a_k - b_k}{10^k} \;\geq\; \frac{1}{10^m} - \sum_{k \gt m} \frac{9}{10^k} = 0, \] using \(b_m - a_m \geq 1\) and \(a_k - b_k \leq 9\), with the geometric series \(\sum_{k \gt m} 9 \cdot 10^{-k} = 10^{-m}\). Equality forces \(a_k - b_k = 9\) for all \(k \gt m\), i.e. \(a_k = 9,\, b_k = 0\) for all \(k \gt m\). This contradicts the assumption that \((a_k)\) avoids the digit \(9\). (This is the standard classification: two distinct digit sequences represent the same real precisely when one is eventually \(9\)s and the other the matching eventually-\(0\)s tail; sequences avoiding \(\{0,9\}\) therefore represent their real uniquely.) C

For each \(n \in \mathbb{N}\): if \(f(n) \in [0,1)\), let \((a_{n,k})_{k \geq 1}\) be the greedy expansion of \(f(n)\) from Step 2. Define the diagonal digit \[ d_n := \begin{cases} 4 & \text{if } f(n) \in [0,1) \text{ and } a_{n,n} = 5,\\ 5 & \text{otherwise.} \end{cases} \]

Key idea: \(d_n\) is engineered so that \(d_n \neq a_{n,n}\) whenever \(f(n) \in [0,1)\), while every \(d_n\) lies in \(\{4,5\}\) — never \(0\) or \(9\) — so Step 3 will apply. The case split is exhaustive and each case is decidable from the data of \(f\). B

Define \[ x := \sum_{n=1}^{\infty} \frac{d_n}{10^n}. \] The series converges and \(x \in \left[\tfrac{4}{9}, \tfrac{5}{9}\right] \subseteq (0,1)\).

Comparison with the geometric series: \(0 \lt \sum d_n 10^{-n} \leq \sum 5 \cdot 10^{-n} = \tfrac{5}{9} \lt 1\), and monotone bounded partial sums converge by completeness of \(\mathbb{R}\) (monotone convergence for sequences). The lower bound is \(\sum 4 \cdot 10^{-n} = \tfrac{4}{9}\). A

Claim: \(x \neq f(n)\) for every \(n\) with \(f(n) \notin [0,1)\).

Immediate: \(x \in (0,1) \subseteq [0,1)\) by Step 5, so \(x\) cannot equal any value of \(f\) lying outside \([0,1)\). A

Claim: \(x \neq f(n)\) for every \(n\) with \(f(n) \in [0,1)\).

Fix such an \(n\). By Step 2, \(f(n) = \sum_k a_{n,k} 10^{-k}\); by Step 5, \(x = \sum_k d_k 10^{-k}\). The digit sequence \((d_k)\) takes values in \(\{4,5\}\), hence avoids \(0\) and \(9\); and by construction (Step 4) \(d_n \neq a_{n,n}\). The separation lemma (Step 3, applied with \((a_k) = (d_k)\) and \((b_k) = (a_{n,k})\)) gives \(x \neq f(n)\). B

Conclusion: \(x \notin f(\mathbb{N})\), so \(f\) is not surjective. Since \(f\colon \mathbb{N}\to\mathbb{R}\) was arbitrary, no surjection \(\mathbb{N}\to\mathbb{R}\) exists; a fortiori no bijection exists, and \(\mathbb{R}\) is uncountable. \(\blacksquare\)

Steps 6 and 7 cover all \(n \in \mathbb{N}\), giving \(x \neq f(n)\) for every \(n\); this is exactly the negation of surjectivity demanded in Step 1. Uncountability is by definition the nonexistence of a surjection from \(\mathbb{N}\) (equivalently, of a bijection, since a bijection is in particular a surjection). A

Result

\[ \nexists \; f\colon \mathbb{N} \twoheadrightarrow \mathbb{R} \qquad\text{i.e.}\qquad \aleph_0 = \lvert \mathbb{N} \rvert \lt \lvert \mathbb{R} \rvert = 2^{\aleph_0}. \]

Reading. However you try to list the real numbers — one for each natural number, repeats allowed, no requirement that the list follow any rule — the list must miss some real. The diagonal construction hands you a concrete missed number: read the \(n\)-th digit of the \(n\)-th listed number and write down something different. Infinity comes in genuinely different sizes, and the continuum is strictly the larger.

Scope. The theorem is about \(\mathbb{R}\) as the complete Archimedean ordered field; the same argument proves \([0,1]\), any nondegenerate interval, \(\{0,1\}^{\mathbb{N}}\), \(\mathcal{P}(\mathbb{N})\), and \(\mathbb{C}\) uncountable. It does not apply to \(\mathbb{Q}\), to the algebraic numbers, or to the computable reals — all countable — because for those sets the diagonal number escapes the set itself rather than the list. The equality \(\lvert\mathbb{R}\rvert = 2^{\aleph_0}\) uses in addition the binary-expansion bijection up to a countable set; the strict inequality \(\aleph_0 \lt 2^{\aleph_0}\) is this theorem.

Corollaries & converses

Transcendental numbers exist, and form an uncountable set: the algebraic numbers are countable (Worked Example 1), so they cannot exhaust \(\mathbb{R}\). This existence proof (Cantor, 1874) exhibits no specific transcendental — contrast Liouville (1844).
The irrationals \(\mathbb{R}\setminus\mathbb{Q}\) are uncountable (Worked Example 2): a countable set removed from an uncountable set leaves an uncountable set.
Every nondegenerate interval \((a,b)\) is uncountable: \(x \mapsto a + (b-a)x\) injects \([0,1]\) into \([a,b]\), and an uncountable set admits no injection into a countable one.
\(\mathbb{R}\) is not the union of countably many countable sets — modulo the countable axiom of choice, which is needed to prove that countable unions of countable sets are countable.
Cantor's theorem generalizes the method: for every set \(X\), \(\lvert X \rvert \lt \lvert \mathcal{P}(X) \rvert\) — the same diagonal trick with "\(n \in f(n)\)" in place of digits. The present theorem is essentially the case \(X = \mathbb{N}\).
Converse-type question. "Is every uncountable set of reals of cardinality \(\lvert\mathbb{R}\rvert\)?" is the Continuum Hypothesis, proved independent of ZFC (Gödel 1940, Cohen 1963): neither provable nor refutable. So the theorem gives \(\aleph_0 \lt 2^{\aleph_0}\) but ZFC alone cannot say which aleph \(2^{\aleph_0}\) is.
Naive converse fails. "Uncountable" does not follow from "dense and unbounded ordered field": \(\mathbb{Q}\) is a dense unbounded ordered field and is countable. Completeness is the load-bearing hypothesis.

Fails without

Without completeness — \(\mathbb{Q}\): the rationals satisfy every ordered-field axiom of \(\mathbb{R}\) except completeness, and \(\mathbb{Q}\) is countable: enumerate \(0, 1, -1, \tfrac12, -\tfrac12, 2, -2, \tfrac13, \dots\) by increasing \(\lvert p \rvert + q\) for \(p/q\) in lowest terms. Diagonalizing over this list produces a real number that is simply irrational; nothing breaks inside \(\mathbb{Q}\).
Without closure of the ambient set — the algebraic numbers \(\overline{\mathbb{Q}} \cap \mathbb{R}\): countable (Worked Example 1) despite being a field dense in \(\mathbb{R}\) and closed under taking real roots of its own polynomials. The diagonal real built from a list of all algebraic numbers is transcendental — it exits the set, so no contradiction with countability arises.
Without "arbitrary \(f\)" — the computable reals: the set of reals whose digit sequence is output by some Turing machine is countable, yet the diagonal argument does not make it uncountable: given a (necessarily non-computable) enumeration, the diagonal real fails to be computable. Restricting the quantifier to computable enumerations turns the theorem into a different (true) statement: the computable reals are not computably enumerable.
Without the Archimedean property — hyperreal-style fields: in a non-Archimedean ordered field, elements differing by a positive infinitesimal share every decimal digit, so "the constructed number differs in digit \(n\)" no longer yields "the constructed number is different". The digit-separation lemma (Step 3) is exactly where Archimedes is consumed.

Common errors

The \(0.999\ldots\) trap. Building the diagonal number with digits \(0\) and \(9\) (or \(0\) and \(1\)) and asserting "different digits, hence different number". False in general: \(0.4999\ldots = 0.5000\ldots\). The fix is a digit alphabet avoiding \(0\) and \(9\) (here \(\{4,5\}\)), plus an explicit uniqueness lemma (Step 3). A proof omitting this is incomplete.
The "just add it to the list" repair. "Fine — append the diagonal number \(x\) as item \(0\); now the list is complete." No: the theorem quantifies over all lists, so the repaired list is itself a function \(\mathbb{N}\to\mathbb{R}\) and the argument produces a new missed real for it. The proof is a machine that defeats every list, not one particular list.
Diagonalizing \(\mathbb{Q}\) into a contradiction. Applying the argument to an enumeration of \(\mathbb{Q}\) and concluding \(\mathbb{Q}\) is uncountable. The error: the diagonal number is not shown to be rational — indeed it is irrational — so it was never required to appear on the list.
Assuming the list must be given by a formula. Students sometimes argue "no explicit pattern can list the reals". The theorem is stronger: even a completely arbitrary, non-definable, choice-like assignment \(n \mapsto f(n)\) misses a real. Conversely, "I can't imagine a list" is not a proof.
Confusing "unbounded" or "dense" with "uncountable". \(\mathbb{Q}\) is dense in \(\mathbb{R}\) and unbounded, yet countable. Topological size (density) and set-theoretic size (cardinality) are independent axes.
Misstating the conclusion as "the reals cannot be well-ordered". Uncountability says no countable enumeration exists; under the axiom of choice \(\mathbb{R}\) can be well-ordered — just in a transfinite sequence longer than \(\mathbb{N}\).

Discussion

Cantor proved the uncountability of \(\mathbb{R}\) twice, and the two proofs have different descendants. The 1874 proof (in the same paper that proves the algebraic numbers countable) uses no digits at all: given a purported enumeration, one constructs a nested sequence of closed intervals, each chosen to exclude the next listed number, and completeness delivers a common point missed by the entire list (Problem 5). The diagonal argument dates from 1891, where Cantor stated it first for the set of all infinite binary sequences — deliberately sidestepping decimal-representation subtleties — and remarked that it applies to the continuum. The 1891 method proved the more contagious: it is a fixed-point-free self-reference scheme, and Lawvere's fixed-point theorem (1969) exposes Cantor's theorem, Russell's paradox, Tarski's undefinability of truth, and Turing's halting problem as instances of one categorical statement.

The theorem forced mathematics to take actual infinity seriously as a graded notion. Before Cantor, "infinite" was a single attribute; after, cardinal arithmetic is a subject: \(\aleph_0 \lt 2^{\aleph_0} \lt 2^{2^{\aleph_0}} \lt \cdots\), each step by the diagonal method. Kronecker's hostility to this work is well documented, and Hilbert's later defence — the famous remark about the paradise Cantor created — marks the moment set theory became the accepted foundation. The theorem also recalibrates intuition about "most" numbers: almost every real (in cardinality, and also in Lebesgue measure and Baire category) is transcendental, yet exhibiting specific transcendentals (\(e\), Hermite 1873; \(\pi\), Lindemann 1882) remains hard. Whether \(e + \pi\) is transcendental is still open.

There are instructive alternative proofs. Measure-theoretically: a countable set \(\{x_1, x_2, \dots\}\) is covered by intervals of lengths \(\varepsilon 2^{-n}\) with total length \(\varepsilon\), so it is Lebesgue-null, while \([0,1]\) has measure \(1\). Topologically: the Baire category theorem says a complete metric space without isolated points is not a countable union of nowhere-dense sets, but a countable \(\mathbb{R}\) would be a countable union of singletons. A third route: any countable dense linear order without endpoints is order-isomorphic to \(\mathbb{Q}\) (Cantor's back-and-forth theorem), but \(\mathbb{Q}\) is not complete — so \(\mathbb{R}\), being complete, cannot be countable. Each proof isolates a different facet: measure, category, and order-completeness all separately certify that the continuum is big.

Set-theoretically the theorem is remarkably robust: the diagonal argument uses no choice principles whatsoever and goes through in ZF, indeed in weak subsystems of second-order arithmetic (it is provable in \(\mathsf{RCA}_0\), suitably formalized). What is not robust is the surrounding landscape. In ZF without choice it is consistent that \(\mathbb{R}\) is a countable union of countable sets (Feferman–Lévy model) — yet even there \(\mathbb{R}\) remains uncountable, because the diagonal argument needs no choice while "countable unions of countables are countable" does. And the position of \(2^{\aleph_0}\) in the aleph hierarchy is wildly undetermined: by Easton-style forcing, \(2^{\aleph_0}\) can consistently be \(\aleph_1\), \(\aleph_2\), \(\aleph_{17}\), or \(\aleph_{\omega+1}\) — essentially anything of uncountable cofinality (König's theorem, \(\operatorname{cf}(2^{\aleph_0}) \gt \aleph_0\), is the only ZFC constraint). Common misconceptions. Uncountability is not about "infinite decimals go on forever" — \(\tfrac13 = 0.333\ldots\) has an infinite expansion and \(\mathbb{Q}\) is countable. Nor does the theorem say uncountable sets are "unstructured": \(\mathbb{R}\) is uncountable yet separable, with a countable dense subset and a countable base of open intervals. And the diagonal number is not "random": it is fully determined by the given list — the proof is explicit relative to its input, non-constructive only in the sense that no single \(x\) works for all lists.

Worked examples

Example 1 (transcendental numbers exist). A real number is algebraic if it is a root of some nonzero polynomial with integer coefficients, and transcendental otherwise. We show transcendental numbers exist — indeed form an uncountable set — without exhibiting a single one.

For each pair \((d, H) \in \mathbb{N}^2\), the set \(P_{d,H}\) of polynomials \(c_d x^d + \cdots + c_1 x + c_0\) with \(c_i \in \mathbb{Z}\), \(\lvert c_i \rvert \leq H\), and \(c_d \neq 0\) is finite.

Each of the \(d+1\) coefficients ranges over the finite set \(\{-H, \dots, H\}\), so \(\lvert P_{d,H}\rvert \leq (2H+1)^{d+1}\); a finite product of finite sets is finite. A

The set \(P\) of all nonzero integer polynomials is countable: \[ P = \bigcup_{d=1}^{\infty} \bigcup_{H=1}^{\infty} P_{d,H}, \] a countable union of finite sets.

Enumerate the pairs \((d,H)\) diagonally by \(d + H\) (a countable union of countable sets indexed by \(\mathbb{N}^2\); for finite sets with an explicit ordering, no choice is needed) and concatenate the finite lists. B

Each nonzero polynomial of degree \(d\) has at most \(d\) real roots, so the set \(A\) of real algebraic numbers is a countable union of finite sets, hence countable.

The root bound is the factor theorem plus induction on degree (a degree-\(d\) polynomial over a field has at most \(d\) roots). Replacing each polynomial in the enumeration of Step 2 by its finite, explicitly ordered list of real roots gives a surjection from a countable set onto \(A\). A

If \(\mathbb{R} \setminus A\) were countable, then \(\mathbb{R} = A \cup (\mathbb{R}\setminus A)\) would be a union of two countable sets, hence countable — contradicting the theorem (T-006).

Union of two countable sets is countable: interleave the two enumerations, listing \(a_1, b_1, a_2, b_2, \dots\) (explicit, choice-free). The contradiction with T-006 is direct. B

\[ \mathbb{R} \setminus A \text{ is uncountable: transcendental numbers not only exist, they outnumber the algebraic numbers.} \]

Reading. Counting alone proves existence: the algebraics are too few to fill \(\mathbb{R}\). This is Cantor's 1874 argument, published decades before anyone could prove \(\pi\) transcendental.

Scope. The argument gives uncountably many transcendentals in every nondegenerate interval (intersect with the corollary that intervals are uncountable); it names none of them.

Example 2 (the irrationals are uncountable). We show \(\mathbb{R}\setminus\mathbb{Q}\) is uncountable — so in the sense of cardinality, "most" reals are irrational.

\(\mathbb{Q}\) is countable: map \(\tfrac{p}{q}\) (lowest terms, \(q \geq 1\)) into an enumeration ordered by \(\lvert p \rvert + q\), breaking ties by \(p\).

For each value of \(\lvert p\rvert + q = N\) there are finitely many candidates (at most \(2N\)), so the enumeration reaches every rational after finitely many steps; injectivity of lowest-terms representation makes the list well defined. A

Suppose, for contradiction, \(\mathbb{R}\setminus\mathbb{Q}\) is countable, with enumeration \(y_1, y_2, y_3, \dots\)

Negation of the claim; "countable" here means there is a surjection \(\mathbb{N} \to \mathbb{R}\setminus\mathbb{Q}\) (the empty case is impossible since \(\sqrt{2}\) is irrational, by the classical parity argument). A

Interleave the two lists into one function \(g\colon \mathbb{N} \to \mathbb{R}\): \[ g(2n-1) = q_n \; (\text{the } n\text{-th rational}), \qquad g(2n) = y_n. \] Then \(g\) is a surjection onto \(\mathbb{Q} \cup (\mathbb{R}\setminus\mathbb{Q}) = \mathbb{R}\).

Every real is rational or irrational (trichotomy of the partition), hence appears in one of the two lists, hence in the range of \(g\); parity of the index recovers which list. B

A surjection \(g\colon \mathbb{N}\to\mathbb{R}\) contradicts T-006. Hence \(\mathbb{R}\setminus\mathbb{Q}\) is uncountable.

Direct application of the theorem: no such surjection exists. The contradiction traces back to Step 2, the only unproved assumption. A

\[ \mathbb{R}\setminus\mathbb{Q} \text{ is uncountable.} \]

Reading. Removing the countably many rationals barely dents the continuum: the leftover irrationals are still too many to list. The same subtraction argument shows \(\mathbb{R}\) minus any countable set is uncountable.

Scope. Works for any partition of an uncountable set into a countable piece and a remainder; it needs only the choice-free fact that two countable sets have countable union.

Problems

(Routine.) Let \(S \subseteq [0,1]\) be the set of reals having a decimal expansion using only the digits \(4\) and \(5\). Prove that \(S\) is uncountable.

Solution

Let \(f\colon \mathbb{N} \to S\) be arbitrary. Each element of \(S\) has by definition an expansion \(\sum_k c_k 10^{-k}\) with \(c_k \in \{4,5\}\); since these digits avoid \(0\) and \(9\), the separation lemma (Step 3 of the main proof) shows this expansion is the unique decimal expansion of the number, so the digit sequence \((c_{n,k})_k\) of \(f(n)\) is well defined. Define \[ d_n := \begin{cases} 4 & \text{if } c_{n,n} = 5, \\ 5 & \text{if } c_{n,n} = 4, \end{cases} \qquad x := \sum_{n=1}^{\infty} \frac{d_n}{10^n}. \] The series converges by comparison with \(\sum 5\cdot 10^{-n}\), and \(x \in S\) since its digits lie in \(\{4,5\}\). For every \(n\), the expansions of \(x\) and \(f(n)\) both use only digits in \(\{4,5\}\) and differ at position \(n\) (namely \(d_n \neq c_{n,n}\)), so by the separation lemma \(x \neq f(n)\). Hence \(f\) is not surjective; as \(f\) was arbitrary, \(S\) is uncountable. (Note this strengthens T-006: even this thin subset of \([0,1]\) is uncountable. \(S\) is in fact a homeomorphic copy of the Cantor set.)
(Routine.) Prove that the set \(\{0,1\}^{\mathbb{N}}\) of all infinite binary sequences is uncountable. Explain why this version of the diagonal argument needs no lemma about non-unique representations.

Solution

Let \(F\colon \mathbb{N} \to \{0,1\}^{\mathbb{N}}\) be arbitrary; write \(F(n) = (F(n)_1, F(n)_2, \dots)\). Define \(s \in \{0,1\}^{\mathbb{N}}\) by \(s_n := 1 - F(n)_n\). For each \(n\) we have \(s_n \neq F(n)_n\), so \(s \neq F(n)\) — here two sequences are equal by definition iff they agree at every coordinate, so disagreement at one coordinate immediately gives inequality. Hence \(s \notin F(\mathbb{N})\) and \(F\) is not surjective; \(\{0,1\}^{\mathbb{N}}\) is uncountable.

No representation lemma is needed because sequences are the raw objects: there is no quotient identifying distinct sequences, unlike decimals, where the map \(\text{digit sequences} \to \mathbb{R}\) is not injective (\(0.4999\ldots = 0.5\)). The decimal proof must rule out the possibility that the diagonal number equals a listed number via a different expansion; the sequence proof has no such possibility. This is exactly why Cantor's 1891 paper worked with abstract two-symbol sequences.
(Moderate.) A binary sequence is eventually constant if there exist \(N\) and \(b \in \{0,1\}\) with \(s_n = b\) for all \(n \geq N\). Show that the set \(E\) of eventually constant sequences is countable, and deduce that the set of sequences that are not eventually constant is uncountable. Conclude that \((0,1)\) and \(\{0,1\}^{\mathbb{N}}\) have the same cardinality.

Solution

\(E\) is countable. An eventually constant sequence is determined by its finite prefix \((s_1,\dots,s_{N-1})\) and the constant tail value \(b\). For each \(N\) there are at most \(2^{N-1}\cdot 2\) such sequences, so \(E = \bigcup_{N} E_N\) is a countable union of finite sets, hence countable (enumerate by increasing \(N\), then lexicographically — explicit, no choice).

The complement is uncountable. If \(\{0,1\}^{\mathbb{N}} \setminus E\) were countable, then \(\{0,1\}^{\mathbb{N}} = E \cup (\{0,1\}^{\mathbb{N}}\setminus E)\) would be a union of two countable sets, hence countable, contradicting Problem 2.

Equinumerosity with \((0,1)\). Map each \(s \in \{0,1\}^{\mathbb{N}}\setminus E'\) to \(\sum_n s_n 2^{-n} \in [0,1]\), where \(E'\) is the countable set of sequences that are eventually \(0\) or eventually \(1\). On the complement of \(E'\) this map is injective (the binary analogue of the separation lemma: two binary expansions coincide only in the eventually-\(0\)/eventually-\(1\) tail situation, which we have excluded) and its image is \((0,1)\) minus the countable set of dyadic rationals' finite expansions — in fact every non-dyadic point of \((0,1)\) has exactly one such expansion, so the map is a bijection between two sets each equal to an uncountable set minus a countable set. Two sets differing from \(\{0,1\}^{\mathbb{N}}\) and \((0,1)\) respectively by countable sets are equinumerous with them: if \(X\) is uncountable and \(C \subseteq X\) countable, choose a countably infinite \(D \subseteq X \setminus C\) (possible since \(X\setminus C\) is infinite) and shuffle \(C\) into \(C \cup D\) by a bijection fixing everything else. Composing gives \(\lvert (0,1)\rvert = \lvert \{0,1\}^{\mathbb{N}}\rvert\). Hence also \(\lvert \mathbb{R} \rvert = 2^{\aleph_0}\), via the bijection \((0,1) \to \mathbb{R}\), \(x \mapsto \tan\left(\pi x - \tfrac{\pi}{2}\right)\).
(Harder.) Prove Cantor's theorem: for every set \(X\) there is no surjection \(g\colon X \to \mathcal{P}(X)\). Explain precisely how the diagonal proof of T-006 is the special case \(X = \mathbb{N}\), identifying what plays the role of the "diagonal set".

Solution

Cantor's theorem. Let \(g\colon X \to \mathcal{P}(X)\) be arbitrary. Define \[ D := \{\, x \in X : x \notin g(x) \,\} \in \mathcal{P}(X). \] Suppose \(D = g(x_0)\) for some \(x_0 \in X\). Then \(x_0 \in D \iff x_0 \notin g(x_0) \iff x_0 \notin D\), a contradiction. Hence \(D \notin g(X)\) and \(g\) is not surjective. (This is choice-free and works for \(X = \emptyset\) too: \(\mathcal{P}(\emptyset)\) has one element, \(\emptyset\) has none, and there is no map from \(\emptyset\) onto a nonempty set.)

Specialization to \(X = \mathbb{N}\). Identify a subset \(A \subseteq \mathbb{N}\) with its characteristic sequence \(\chi_A \in \{0,1\}^{\mathbb{N}}\), \(\chi_A(n) = 1\) iff \(n \in A\); this is a bijection \(\mathcal{P}(\mathbb{N}) \to \{0,1\}^{\mathbb{N}}\). Under this identification, a function \(g\colon \mathbb{N}\to\mathcal{P}(\mathbb{N})\) is a listing of binary sequences, and the diagonal set \(D = \{n : n \notin g(n)\}\) has characteristic sequence \(\chi_D(n) = 1 - \chi_{g(n)}(n)\) — exactly the flipped-diagonal sequence of Problem 2. So the "diagonal set" of Cantor's theorem is the diagonal sequence, and T-006 follows by transporting uncountability of \(\mathcal{P}(\mathbb{N}) \cong \{0,1\}^{\mathbb{N}}\) to \(\mathbb{R}\) along the injection of Problem 3 (an injection from an uncountable set into \(\mathbb{R}\) forces \(\mathbb{R}\) uncountable, since a subset of a countable set is countable). The digit gymnastics of the main proof are precisely the cost of replacing abstract sequences by their images in \(\mathbb{R}\).
(Hard.) Give Cantor's original (1874) proof that \(\mathbb{R}\) is uncountable, using nested closed intervals and completeness but no decimal expansions: given any sequence \((x_n)_{n\geq 1}\) of reals, construct a real not equal to any \(x_n\). State exactly where completeness is used, and exhibit a countable ordered field in which the construction fails.

Solution

Construction. Let \((x_n)\) be any sequence of reals. Build closed intervals \([a_k, b_k]\) with \(a_k \lt b_k\) recursively. Start with \([a_1, b_1] := [x_1 + 1,\, x_1 + 2]\), a closed interval that certainly excludes \(x_1\). Given \([a_k, b_k]\) not containing \(x_1, \dots, x_k\), split it into three closed subintervals of equal length \[ \left[a_k,\, a_k + \tfrac{b_k - a_k}{3}\right], \quad \left[a_k + \tfrac{b_k-a_k}{3},\, a_k + \tfrac{2(b_k-a_k)}{3}\right], \quad \left[a_k + \tfrac{2(b_k-a_k)}{3},\, b_k\right]. \] The single point \(x_{k+1}\) can lie in at most two of the three (only by being a shared endpoint); choose \([a_{k+1}, b_{k+1}]\) to be a subinterval not containing \(x_{k+1}\) — say the leftmost such, to keep the construction canonical and choice-free. Then \(a_1 \leq a_2 \leq \cdots \leq b_2 \leq b_1\), and \(x_n \notin [a_k, b_k]\) whenever \(k \geq n\).

Completeness enters here. The set \(\{a_k : k \in \mathbb{N}\}\) is nonempty and bounded above (by every \(b_j\): for any \(k, j\) one has \(a_k \leq a_{\max(k,j)} \leq b_{\max(k,j)} \leq b_j\)). By Dedekind completeness it has a supremum \(x := \sup_k a_k\), and \(a_k \leq x \leq b_k\) for every \(k\) (upper bound property gives the left inequality; each \(b_k\) is an upper bound for all \(a_j\), so minimality of the supremum gives the right). Thus \(x \in \bigcap_k [a_k, b_k]\).

Conclusion. For every \(n\), \(x \in [a_n, b_n]\) while \(x_n \notin [a_n, b_n]\), hence \(x \neq x_n\). The sequence misses \(x\); since the sequence was arbitrary, \(\mathbb{R}\) is uncountable. (Nothing here needed intervals to shrink to zero length; the intersection may be a whole interval, and any of its points works.)

Failure in a countable field. Take \(\mathbb{Q}\) with an enumeration \((x_n)\) of all rationals. The construction still produces nested rational intervals \([a_k,b_k]\) excluding \(x_1,\dots,x_k\), but the conclusion requires a point in \(\bigcap_k [a_k, b_k] \cap \mathbb{Q}\), and this intersection is empty: any rational in it would be some \(x_n\), which is excluded from the \(n\)-th stage onward. Precisely the supremum step fails — \(\sup_k a_k\) exists in \(\mathbb{R}\) but is irrational here, and \(\mathbb{Q}\) has no completeness axiom to supply a point of its own. This isolates completeness as the exact hypothesis carrying the theorem, in agreement with the Hypotheses section.