Recently, I learnt in my analysis class the proof of the uncountability of the reals via the Nested Interval Theorem (Wayback Machine). At first, I was excited to see a variant proof (as it did not use the diagonal argument explicitly). However, as time passed, I began to see that the proof was just the old one veiled under new terminology. So, till now I believe that any proof of the uncountability of the reals must use Cantor's diagonal argument.
Is my belief justified?
Thank you.
Mathematics isn't yet ready to prove results of the form, "Every proof of Theorem T must use Argument A." Think closely about how you might try to prove something like that. You would need to set up some plausible system for mathematics in which Cantor's diagonal argument is blocked and the reals are countable. Nobody has any idea how to do that.
The best you can hope for is to look at each proof on a case-by-case basis and decide, subjectively, whether it is "essentially the diagonal argument in disguise." If you're lucky, you'll run into one that your intuition tells you is a fundamentally different proof, and that will settle the question to your satisfaction. But if that doesn't happen, then the most you'll be able to say is that every known proof seems to you to be the same. As explained above, you won't be able to conclude definitively that every possible argument must use diagonalization.
ADDENDUM (August 2020). Normann and Sanders have a very interesting paper that sheds new light on the uncountability of $\mathbb R$. In particular they study two specific formulations of the uncountability of $\mathbb R$:
$\mathsf{NIN}$: For any $Y:[0,1] \to \mathbb{N}$, there exist $x,y \in [0,1]$ such that $x\ne_{\mathbb{R}} y$ and $Y(x) =_{\mathbb{N}} Y(y)$.
$\mathsf{NBI}$: For any $Y[0,1] \to \mathbb{N}$, either there exist $x,y \in [0,1]$ such that $x\ne_{\mathbb{R}} y$ and $Y(x) =_{\mathbb{N}} Y(y)$, or there exists $N\in\mathbb{N}$ such that $(\forall x\in [0,1])(Y(x) \ne N)$.
One of their results is that a system called ${\mathsf Z}_2^\omega$ does not prove $\mathsf{NIN}$. Their model of $\neg\mathsf{NIN}$ can therefore be interpreted as a situation where the reals are countable! Nevertheless we are still far from showing that Cantor's diagonal argument is needed to prove that the reals are uncountable. A further caveat is that Normann and Sanders argue that the unprovability of $\mathsf{NIN}$ in ${\mathsf Z}_2^\omega$—which might at first sight suggest that $\mathsf{NIN}$ is a strong axiom—is an artificial result, and that the proper framework for studying $\mathsf{NIN}$ and $\mathsf{NBI}$ is what they call a “non-normal scale,” in which $\mathsf{NIN}$ and $\mathsf{NBI}$ are very weak. In particular their paper gives lots of examples of statements that imply $\mathsf{NIN}$ and $\mathsf{NBI}$. I suspect, though, that you'll probably feel that the proofs of those other statements smuggle in Cantor's diagonal argument one way or another.
ADDENDUM (December 2022). I just listened to an amazing talk by Andrej Bauer, reporting on joint work with James Hanson. If you start listening around 14:53, you'll see how, in the context of intuitionistic logic, one can formulate precisely the question of whether there is a proof of the uncountability of the reals that doesn't use diagonalization. Bauer and Hanson don't answer this question, but they construct something they call a "parameterized realizability topos" in which the Dedekind reals are countable. In particular, this shows that higher-order intuitionistic logic (in which one cannot formulate the usual diagonalization argument) cannot show the reals are uncountable. Now, you could still justifiably claim that this whole line of research does not really address the original question, which I presume tacitly assumes classical logic; nevertheless, this still comes closer than anything else I've seen.
Mathematical logicians often joke that the diagonal method is the only proof method that we have in logic. This method is the principal idea behind a huge number of fundamental results, among them:
The uncountability of the reals.
More generally, the fact that the power set $P(X)$ of a set is strictly larger in cardinality.
The Russell paradox.
The undecidability of the halting problem.
The Recursion theorem.
More generally, huge parts of computability theory are based on diagonalization, such as uses of the priority method.
The fixed-point lemma and its use in proving the Incompleteness theorem.
The strictness of the arithmetic hierarchy, the projective hierarchy, etc.
Etc. etc. etc.
What about using Lebesgue outer measure? The interval $[0,1]$ has Lebesgue outer measure 1, while countable sets have Lebesgue outer measure $0$.
For the purposes of the proof, I define the Lebesgue outer measure $\mathcal{L}(E)$ of a set $E\subset\mathbb{R}$ as the infimum of the sums $\sum_i (b_i-a_i)$, where $E\subset \bigcup_i (a_i,b_i)$ (e.g. the infimum is over all countable coverings by open intervals).
It is a direct consequence of the definition that any countable set has Lebesgue outer measure 0. This can be even proved in the spirit of Gowers' first suggestion: suppose that $f:\mathbb{Q}\cap (0,1)\to A$ is a bijection. Then, given $\varepsilon>0$, the family $$\{ ( f(p/q)-\varepsilon/q^3, f(p/q)+\varepsilon/q^3): p/q\in [0,1], \text{g.c.d.}(p,q)=1\}$$ is a cover of $A$ by intervals, such that the sum of the lengths is $O(\varepsilon)$.
To prove that $\mathcal{L}([0,1])=1$, the following is the key claim: Let $\{ (a_i,b_i)\}$ be a finite cover of the interval $[c,d]$ with no proper subcover. Then $\sum_i (b_i-a_i) > d-c$.
The claim is proved by induction in the number of elements of the cover. It is clearly true if the cover has just one interval. Now if $[c,d] \subset \bigcup_{i=1}^n (a_i,b_i)$ with $n>1$, then $[c,d]\backslash (a_1,b_1)$ is either a closed interval $I$ or the union $I\cup I'$ of two disjoint closed intervals. In the first case $\bigcup_{i=2}^n (a_i,b_i)$ is a cover of $I$ and we apply the inductive hypothesis to it. Otherwise, $\{(a_i,b_i)\}_{i=2}^n$ can be split into two disjoint subfamilies, one which covers $I$ and one which covers $I'$. We then apply the inductive hypothesis to these families. (We use the property that the original cover has no proper subcover to make sure the covers of $I$ and $I'$ are disjoint.)
Now the claim and compactness of $[0,1]$ (ie. Heine-Borel) yield that $\mathcal{L}([0,1])\ge 1$.
Hence, $[0,1]$ is uncountable and so is $\mathbb{R}$.
Alternatively,
Prove that the reals are connected.
Prove that every countable dense subset $X$ of the reals must be order isomorphic to the rationals.
Prove that the rationals are not connected.
I thought about this question a while ago, while teaching a topics course. Since one can easily check that $${}|{\mathbb R}|=|{\mathcal P}({\mathbb N})|$$ by a direct construction that does not involve diagonalization, the question can be restated as:
Is there a proof of Cantor's theorem that ${}|X|<|{\mathcal P}(X)|$ that is not a diagonal argument?
I suspect the following works. Even if it doesn't, I believe there may be some interest in this presentation (Please let me know if you spot diagonalization somewhere).
A remark of François Dorais helped me (re)locate the argument in print. It is presented in A. Kanamori-D. Pincus. "Does GCH imply AC locally?", in Paul Erdős and his mathematics, II (Budapest, 1999), 413-426, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002. I believe it actually dates back to Zermelo's 1904 well-ordering paper. (I now think I learned the argument from Kanamori-Pincus, since I certainly used the paper in the topics course.)
a. There is obviously an injection $g:X\to{\mathcal P}(X)$. It is enough to show there is no surjection. Suppose there is, and call it $f$. Then $f^{-1}:{\mathcal P}^2(X)\to{\mathcal P}(X)$ is 1-1.
(If $h:A\to B$, $h^{-1}:{\mathcal P}(B)\to{\mathcal P}(A)$ is the map that to $C\subseteq B$ assigns $\{a\in A\mid h(a)\in C\}$. Since $f$ is surjective, we have that $f^{-1}$ is injective.)
(Of course, we could simply use an injection $g:{\mathcal P}(X)\to X$ and invoke Schröder-Bernstein at this point, but this route seems shorter.)
b. There is no injection $F:{\mathcal P}(Y)\to Y$ for any set $Y$. The reason is that for any $F$ we can (definably from $F$) produce a pair $(A,B)$ with $A\ne B$ and $F(A)=F(B)$. In effect, Zermelo proved that:
For any $F:{\mathcal P}(Y)\to Y$ there is a unique well-ordering $(W, \lt)$ with $W\subseteq Y$ such that:
- $\forall x\in W (F (\{y ∈ W \mid y \lt x\}) = x)$, and
- $F (W )\in W$.
We can then take $A=W$ and $B=\{y\in W\mid y\lt F(W)\}$.
c. Zermelo's theorem can be proved as follows: Simply notice that $W=\{a_\alpha\mid \alpha\lt \beta\}$ where $$ a_\alpha= F(\{a_\gamma\mid \gamma\lt \alpha\}) $$ and $\beta$ is largest so that this sequence is injective.
That $\beta$ exists is a consequence of Hartogs theorem that for any set $A$ there is a least ordinal $\alpha$ does not inject into $A$.
Uniqueness of $W$ is shown by considering the first place where two potential candidates for $(W, \lt)$ disagree.
d. Hartogs theorem is proved by noticing that if $\alpha$ is an ordinal and injects into $A$, then there is a subset $B$ of $A$ and a binary relation $R$ on $B$ such that $(B,R)$ is order isomorphic to $\alpha$. From this one easily sees that the collection of $\alpha$s that inject into $A$ forms a set, that is in fact an ordinal $\beta$. Then $\beta$ is least that does not inject into $A$.
Let me close with a remark, and a question: The proof above is formalizable in ZF, without choice. In fact, Zermelo's theorem is provable without using replacement, although the argument I sketched uses it.
The question is mentioned in Kanamori-Pincus: We showed that if $F:{\mathcal P}(Y)\to Y$ then $F$ is not injective by exhibiting a pair $(A,B)$ with $F(A)=F(B)$. If instead of Zermelo's argument we had used at this point the construction from the diagonal argument, we would have taken $$ A=\{y\in Y\mid \exists Z(y=F(Z)\notin Z)\}, $$ and checked that there must be a $B\ne A$ with $F(A)=F(B)$.
Can we define such $B$ from $F$?
(Update: In general, the answer to the question is no. See here.)
Update, Sep. 6, 2017: Let me add a few additional remarks. First, in comments, Martin Brandenburg asked why one should bother about trying to obtain a "diagonalization-free" proof. That the proof above avoids diagonalization is perhaps simply a curiosity (though one is left with the question of how to define precisely "diagonalization-free"); what matters is that the argument gives a bit more than Cantor's: As I pointed out in a comment, the proof just given shows that 1) The collection of well-orderable subsets of $X$ has strictly larger size than $X$. This is an improvement over Cantor's result in the context of $\mathsf{𝖹𝖥}$. 2) Given any $f\!:\mathcal P(X)\to X$, we can find $A\subsetneq B$ with $f(A)=f(B)$. This is also a combinatorial strengthening, and it can be pushed further. Stevo Todorcevic in particular obtained several extensions of this idea, see this answer in Math.Stackexchange.
Second, Hartogs's theorem can be used to provide a different (also "diagonalization-free") proof of Cantor's result, and actually establish a generalization in the context of quasi-ordered sets, due to Gleason and Dilworth. For the pretty argument and appropriate references, see here.
Although I very much take Timothy Chow's point, and don't have a way of constructing anything like a model where Cantor's diagonal argument is blocked (I'm not sure what the diagonal argument is in the abstract, given that there are variants), some sickness in me makes me want to try to answer the question anyway. One small thought that occurs to me is that all proofs depend (or can be very easily transformed so that they depend) on the following ingredients: a bijection between the countable set and the natural numbers, the use of the ordering on the natural numbers to order the countable set, the construction of a sequence that lives in a sequence of nested intervals that avoid the points of the countable set, one at a time.
Here are some questions that are more specific than the one in the OP. They are off the top of my head and therefore not guaranteed to be sensible.
Suppose we tried artificially to block the use of the ordering. It might seem impossible, since the definition of countability is that there is a bijection to the natural numbers, but we could, for instance, try proving the result for sets that are in bijection with the rationals and insist that at no point does the proof define an enumeration of that set.
Or we could start with the stronger hypothesis that X is a set of reals that is order-isomorphic to the rationals. Is it possible to prove that this set does not contain all reals without at the same time proving that it is countable?
I don't know how relevant this is, but I'd also like to mention a fascinating fact that I heard from Harvey Friedman recently that feels as though it's in the same ball park. He told me that there exists a Borel function f defined on sequences of reals such that for every sequence S the value f(S) is not a term of S. That's easy to prove from the diagonal argument. On the other hand, there is no Borel function from countable subsets of reals such that f(X) is not an element of X for any countable set X. (I think I remember that that's what he said, but I'm not certain that the result wasn't stronger.) Equivalently, you can't find an f that works for sequences and is also invariant under permutations of the terms in the sequence. This gives us a sort of hint that some kind of enumeration is essential to the proof, but I don't see how to make that hint into a precise thought.
There is a surjection from $\mathbb{R}$ onto $\omega_{1}$, but none from $\omega$.
(Edit: I see, buried amongst the many comments, that bof suggested this proof for $P(\omega)$ instead of $\mathbb{R}$; sorry.) I learnt it like this (from Komjath and Totik), using series expansions of reals.
Let us say that $x \in \mathbb{R}$ codes $\alpha < \omega_{1}$ if $\langle \omega, < \rangle$ is a well order of type $\alpha$, where $i < j \in \omega$ iff the $2^{i}3^{j}$-digit of $x$ is $1$.
Map $\mathbb{R}$ onto $\omega_{1}$ by sending $x$ to $\alpha$ if $x$ codes $\alpha$, otherwise map $x$ to $0$. Map to $0$ any real $x$ that does not code an ordered set, or that does code an ordered set but it is not well-ordered.
In the paper An Unusual Proof that the Reals are Uncountable a proof of the uncountability of the reals is given which is adapted from one of Bourbaki's proofs in "Fonctions d'une variable réelle". Let me give it here:
Suppose $R$ was countable. Then there is a function $a(x) : R → R$ such that:
$a(x) > 0$ for all $x$,
the sum of the $a(x)$ on any finite set is $≤ 1.$
(take $a(x) = 2^{-n}$ if $x$ is the $n$’th element in the counting).
Now, define for any $S\subseteq R$,
$m(S)=$ the supremum of the sums of $a(x)$ on finite subsets of $S$.
Then surely $0 ≤ m(S) ≤ 1$ for any $S$. Define:
$c := \sup\{x: m(-\infty, x)>x \}$
Since $a(c) > 0,$ there is a $y$ such that $y > c − a(c)$ and $m( − ∞, y)> y$, thus $y ≤ c$. Now, since $y ≤ c$, $( − ∞, y)$ does not contain $c$. But $( −∞, y + a(c))$ contains $c$ because $y > c − a(c).$ So by the definition of $m(S)$,
$m( − ∞, y + a(c)) ≥ m( − ∞, y) +a(c) > y + a(c)$,
But $y + a(c) > c$ a contradiction.
Cantor gave several proofs of uncountability of reals; one involves the fact that every bounded sequence has a convergent subsequence (thus being related to the nested interval property). All his proofs are discussed here:
MR2732322 (2011k:01009) Franks, John: Cantor's other proofs that R is uncountable. (English summary) Math. Mag. 83 (2010), no. 4, 283–289.
A nice proof based on the property that each bounded subset of the reals has a supremum can be found in Levy - An unusual proof that the reals are uncountable.
What about the Baire category theorem? It implies that every complete metric space without isolated points is uncountable. But of course, every proof uses some construction or rather characterization of $\mathbb{R}$. I think Cantor's diagonal argument is not bad at all.
Cantor's original proof of uncountability of the reals did not explicitly mention diagonalization. Nor did it use decimal digits.
As Andres implicitly pointed out, we may avoid diagonalization by working with ordinals directly. We can appeal to Hartogs' Theorem to show that there is an ordinal $\beta$ that does not inject into $\omega$. It is then easy to verify that the least such $\beta$ will be $\omega_1$ (i.e., the set of all countable ordinals). Now using Choice, we can construct an injection $f: \omega_1 \rightarrow \mathcal{P}(\omega)$ by encoding each countable ordinal as a unique subset of $\omega$. This can be done by letting $\langle f_{\alpha}| \alpha < \omega_1\rangle$ be a sequence such that each $f_{\alpha}$ is a bijection from $\omega$ into $\alpha$ and then defining $f(\alpha) = $ {$\langle m, n\rangle| f_{\alpha}(m) < f_{\alpha}(n)$} where $\langle \cdot, \cdot\rangle: \omega \times \omega \rightarrow \omega$ is the Cantor pairing function. This completes the proof as if there were an injection from the powerset of $\omega$ (or the Reals) into $\omega$, then there would be an injection from $\omega_1$ into $\omega$.
It is worth noting that in a standard proof of Hartogs' Theorem, we use the fact that an ordinal cannot be a member of itself ($\beta \notin \beta$). But because ordinals are well-ordered by the $\in$ relation, we can prove this fact without appealing to Foundation.
One can use the following theorem:
Every countable dense linear order without endpoints is order-isomorphic to $\Bbb Q$.
Since the real numbers are ordered densely and without endpoints, if $\Bbb R$ was countable it was isomorphic to $\Bbb Q$.
However $\Bbb R$ is order-complete, and $\Bbb Q$ is not. So they are clearly not isomorphic, and therefore $\Bbb R$ is uncountable.
How about this proof?
Let $\omega_1$ be the set of all ordinal numbers which are countable. Then $\omega_1$ is itself ordinal number, but it must be uncountable, otherwise it would contain itself. We will now find the subset of $2^\Bbb N$ (which, as we know, is equipotent with $\Bbb R$) which has power at least that of $\omega_1$.
Let us fix any coding of binary relations as infinite binary strings. Now, for infinite countable ordinal $\alpha$, let $D_\alpha$ be subset of $2^\Bbb N$ consisting of these strings, which code relations which are well-orders with order type $\alpha$. Then all of $D_\alpha$ are non-empty disjoint. We know that union of uncountably many disjoint non-empty sets is uncountable, so we can take $\bigcup_{\omega\leq\alpha<\omega_1} D_\alpha$, which is uncountable subset of $2^\Bbb N$, thus the latter set is uncountable, as is $\Bbb R$.
I like the following geometric argument.
Lemma. For any convex compact set $K\subset \mathbb{R}^2$ with non-empty interior there exists a point $x$ on the boundary such that the support line in $x$ is unique.
Proof. Let $p$ be interior point, and $x$ the closest to $p$ point of the boundary. Since the circle centered in $p$ and passing through $x$ is contained in $K$, the onliest support line in $x$ is perpendicular to the segment $px$.
Now assume that the points of $[0,1]$ are enumerated as $r_1,r_2,\dots$. Consider the convex function $f(x)=\sum_n 2^{-n}\max((r_n-1)x,r_n(x-1))$. Consider the set $K$ bounded by the graphs of $f$ and $-f$: $K=\{(x,y):f(x)\leqslant y\leqslant -f(x),x\in[0,1]\}$. It is easy to see that it does not satisfy the conclusion of Lemma, since the left derivative of $f$ is strictly smaller than the right derivative at any interior point of the segment $[0,1]$, and the derivative at endpoints is finite.
I have the following candidate: Fornasiero - Tame structures and open cores, section 7.4. Notice that in the setting of the article one cannot use diagonalization.
Matthew Baker (Uncountable Sets and an Infinite Real Number Game, Mathematics Magazine 80, no.5 (December 2007), 377-380) has proposed an amusing proof.
A subset $S$ of $[0,1]$ is being given. Let Alice and Bob play the following game, in which they successively choose elements of $[0,1]$. Alice begins with $a_0=0$, Bob with $b_0=1$. At the $n$th stage, Alice chooses $a_n$ such that $a_{n-1}<a_n<b_{n-1}$; then Bob chooses $b_n$ such that $a_n<b_n<b_{n-1}$. The sequence $(a_n)$ has a limit $\alpha$ in $[0,1]$, and Alice wins if $\alpha\in S$. Otherwise, Bob wins.
If $S$ is countable, then Bob has a winning strategy. Given an enumeration $(s_n)$ of $S$, it consists in choosing $b_n=s_n$ at the $n$th stage, if this is a legal move, and any other choice otherwise. One checks that $\alpha\not\in S$.
But if $S=[0,1]$, then Alice wins, obviously. Hence $S$ is uncountable.
Just to add a couple of references:
Today I attended a lecture, and this question was asked, after the talk, I realized the following proof, that might be interesting, at least for set theorists!!!:
Theorem (Cantor): The set of real numbers is uncountable.
Proof: Suppose not. Let $M$ be a countable transitive model of enough of ZFC such that $\mathbb R\in M$. By our assumption $\mathbb R\subseteq M$.
Let $\mathbb P=\operatorname{Add}(\omega,1)$ be the Cohen forcing for adding a new real, let $G\subseteq\mathbb P$ be generic over $M$ and let $r=\bigcup G$.
Then:
- $r\notin M$, as otherwise $G=\{r \restriction n: n<\omega \}\in M$ which is not possible
- $r\in\mathbb R\subseteq M$
A contradiction.
I haven't seen the following proof mentioned, which I learned from Hai Dang at Mississippi State.
Suppose the reals are countable, and let $a_1, a_2, a_3, \dots$ be an enumeration. For each $j$, let $I_j$ be an interval centered at $a_j$ and having length $1 / 2^j$.
Since the sequence $\{a_j\}$ enumerates the reals, it follows that $\bigcup_{j=1}^\infty I_j = \mathbb{R}$. But since the sum of the lengths of the $I_j$ is the geometric series $$ \sum_{j=1}^\infty \frac{1}{2^j} = 1,$$ this is nonsense.
(Pretty much the same proof yields that $[0,2]$ is uncountable.)
There's probably a relation with the outer measure proof previously posted, but this one seems more concrete.
Update: Two extended comments:
1) As mentioned below in my comment below, proving that [0,2] can't be covered by open intervals of length summing to 1 is easily done with compactness. I didn't quickly see how to prove it without compactness. And of course compactness of a closed interval uses the Nested Interval Theorem, as the original poster was trying to avoid.
2) I presented a proof along these lines in an Analysis I class. I liked how it came out a great deal, because it gave me a good reason to show students a typical application of compactness. Compactness is abstract and difficult for beginning students to grasp, and I usually find it difficult to find good applications. Students (or at least some of them) seemed to like this one a fair bit.
