Recently, I learnt in my analysis class the proof of the uncountability of the reals via the [Nested Interval Theorem](http://personal.bgsu.edu/%7Ecarother/cantor/Nested.html) ([Wayback Machine](http://web.archive.org/web/20180402194030/http://personal.bgsu.edu/%7Ecarother/cantor/Nested.html)). 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.



Proofs of the uncountability of the reals
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](https://arxiv.org/abs/2007.07560) 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](https://www.youtube.com/watch?v=4CBFUojXoq4), reporting on joint work with James Hanson.
If you start listening around [14:53](https://youtu.be/4CBFUojXoq4?t=893), 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.


