Showing $\aleph_{0} < 2^{\aleph_{0}}$ without using Cantor's diagonal argument

Question

In my (admittedly limited) mathematical experience, I don't think I've seen a proof of $\aleph_{0} < 2^{\aleph_{0}}$ that doesn't apply some form of Cantor's diagonal argument. Do such proofs exist? Or can it be shown that any proof of this fact actually requires using (some form of) Cantor's diagonal argument?

Answer 1

The diagonal argument for real numbers was actually Cantor's second proof of the uncountability of the reals. His first proof does not use a diagonal argument.

First, one can show that the reals have cardinality $2^{\aleph_0}$. We can inject the power set of the positive integers into the reals by mapping a subset $S$ to the real number $\sum_{i\in S}\frac{5}{10^i}$. And we can inject the real numbers into the power set of $\mathbb{Q}$ by associating to every real number $r$ the set $\{q\in\mathbb{Q}\mid q\leq r\}$. Then we apply the Cantor-Bernstein Theorem to conclude from $2^{\aleph_0}\leq|\mathbb{R}|$ and $|\mathbb{R}|\leq 2^{\aleph_0}$ that $|\mathbb{R}|=2^{\aleph_0}$. None of these proofs uses a diagnoal argument.

Theorem. (Cantor) Given any sequence of real numbers $x_1,x_2,\ldots$ and any interval $[a,b]$, $a\lt b$, in the real line, there is a point $c\in(a,b)$ that is not in the given sequence.

This proves that the real numbers are uncountable, since given a function $f\colon \mathbb{N}\to\mathbb{R}$, there is a point in, say, $(0,1)$ which is not in the range of $f$, so no function from the naturals to the reals is surjective.

Proof. If there are only finitely many points in the sequence that lie in $(a,b)$, then we can find a point different from those finitely many points. So assume infinitely many terms of the sequence lie in the open interval.

Let $a_1$ and $b_1$ be the first two terms of the sequence that lie in $(a,b)$, with $a_1\lt b_1$. If just one of the subsequent terms of the sequence lie in $(a_1,b_1)$, we are done; otherwise, let $a_2\lt b_2$ be the next two terms of the sequence that lie in $(a_1,b_1)$.

Continuing this way, either we get a "last" interval $(a_{M},b_{M})$ that contains at most one term of the sequence (in which case we are done), or else we obtain a subsequence of points $a\lt a_1\lt a_2\lt\cdots$ and another subsequence of points $\cdots \lt b_2\lt b_1\lt b$, with $a_i\lt b_j$ for all $i$ and $j$.

Note also that , because of how we chose $a_{i+1}$ and $b_{i+1}$, as the first two distinct terms of the sequence $x_1,x_2,\ldots$ that lie in the interval $(a_i,b_i)$, it must be the case that $x_1,\ldots,x_{2i}\notin (a_{i+1},b_{i+1})$: for we have already selected $a_1,\ldots,a_i,b_1,\ldots,b_i$ which are pariwise distinct and must precede $a_{i+1}$ and $b_{i+1}$ in the sequence, which excludes $2i$ terms of the sequence, and thus at least $x_1,\ldots,x_{2i}$.

The sequence $a_1,a_2,\ldots$ is an increasing sequence of real numbers which is bounded above, and so has a supremum/limit, $a_{\infty}=\lim_{n\to\infty}a_n$. Likewise, the sequence $b_1,b_2,\ldots$ is a decreasing sequence of real numbers which is bounded below, so it has an infimum/limit, $b_{\infty}=\lim_{n\to\infty}b_n$. Moreover, since every $a_i$ is a lower bound for all $b_j$, we know $a_i\leq b_{\infty}$ for all $i$, and therefore $b_{\infty}$ is an upper bound for all $a_i$, so $a_{\infty}\leq b_{\infty}$.

We claim that any number $r$ in $[a_{\infty},b_{\infty}]$ is not in the sequence. Indeed, for all $n$ we have that $x_n\notin (a_{n+1},b_{n+1})$ (since $x_1,\ldots,x_{2n}\notin (a_{n+1},b_{n+1})$). But $a_{n+1}\lt a_{\infty}\leq b_{\infty}\lt b_{n+1}$, so $x_n\notin (a_{n+1},b_{n+1})$, and $[a_{\infty},b_{\infty}]\subseteq (a_{n+1},b_{n+1})$; thus, if $r\in [a_{\infty},b_{\infty}]$, then $r\neq x_n$ for all $n$. Thus, there are points in $(a,b)$ that are not in the sequence, as claimed. $\Box$

This proof does not use a diagonal argument, but it does use a number of properties of the real numbers, e.g., the completeness property: every nonempty set of reals that is bounded above has a supremum, every nonempty set of reals that is bounded below has an infimum. And the Diagonal Argument is an important idea, so it is usually highlighted.