$\mathbb{R}$ is uncountable (Cantor's nested intervals, 1874)

Let $\mathbb{R}$ be a complete ordered field (Complete ordered field (least-upper-bound property)). Then $\mathbb{R}$ is uncountable (Finite, countably infinite, countable, uncountable): there is no surjection $\mathbb{N} \to \mathbb{R}$, so $\mathbb{R}$ is neither finite nor countably infinite.

The proof is Cantor's original argument of 1874, not the decimal diagonal. Assuming a surjection $f : \mathbb{N} \to \mathbb{R}$, one builds nested closed intervals $[a_n, b_n]$ with $a_n < b_n$ and $f(n) \notin [a_{n+1}, b_{n+1}]$, and then $\sup\{a_n\}$ is a real number that $f$ misses. The decimal diagonal is deliberately avoided: decimal expansions are infinite series, which this library has not yet constructed, so a diagonal proof here would rest on machinery that does not exist. The diagonal argument survives in its non-circular form, on power sets, as Cantor's theorem earlier on this page; see the remarks below.

The construction uses no choice, and that is what the thirds are for. Given $[a_n, b_n]$ of length $d$, its three closed thirds $[a_n, a_n + d/3]$, $[a_n + d/3, a_n + 2d/3]$, $[a_n + 2d/3, b_n]$ cannot all contain $f(n)$, because the first and the third are disjoint; the rule takes the first one in that fixed order which does not contain $f(n)$. That is a definition by cases, so the whole construction is a single application of the recursion theorem (The recursion theorem) to one explicitly given function. A version of the argument that says "pick a third avoiding $f(n)$" would be using dependent choice, silently and unnecessarily.

• What the proof actually uses. Completeness enters once, at step 5.1, to produce $\sup\{a_n\}$; everything else is ordered-field arithmetic and the recursion theorem. The argument therefore applies verbatim to any ordered field with the least-upper-bound property, and it fails for $\mathbb{Q}$ exactly because the supremum of the left endpoints need not exist there, which is as it should be, since $\mathbb{Q}$ is countable ($\mathbb{Q}$ is countably infinite).

• Why thirds and not halves. Two closed halves share the midpoint, so if $f(n)$ happens to be that midpoint then both halves contain it and the rule "take the first closed half not containing $f(n)$" has nothing to return. Three closed thirds fix this: the first and the third are disjoint, so at least one of the three always misses $f(n)$, and listing them in a fixed order makes the selection a definition by cases rather than a choice. Open intervals would avoid the overlap too, but closed intervals are what make step 6.1 work, since the point $\sup\{a_n\}$ must be allowed to be an endpoint.

• The diagonal argument is not lost, only relocated. Cantor's theorem: $A \prec \mathcal{P}(A)$, proved earlier on this page, is Cantor's diagonal argument in a setting where it needs nothing but the Power Set and Separation axioms. What is unavailable here is only the decimal diagonal, and only because decimal expansions are infinite series.

• The choice-freeness matters beyond tidiness. It is what lets FALSE: countable unions of countable sets are countable is a theorem of ZF draw a conclusion about ZF: since this theorem is proved in ZF alone, any model of ZF in which $\mathbb{R}$ is a countable union of countable sets is a model in which the countable-union theorem fails.

• The argument gives more than the statement does. Nothing above depends on the starting interval being $(0,1)$, so re-seeding the recursion inside a given interval shows that every nondegenerate interval, open or closed, is uncountable. That extension is Every nondegenerate interval of $\mathbb{R}$ is uncountable, next on this page, where it is proved rather than asserted.