## Proofs of the uncountability of the reals.

Recently, I learnt in my analysis class the proof of the uncountability of the reals via the Nested Interval Theorem. 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.

-
It's not too hard to see that the reals have the same cardinality as the power set of the naturals. So we are reduced to showing that a set cannot have the same cardinality as its power set. This is shown using the same argument as the Russell Paradox (i.e., assume a bijection $\phi \colon \mathcal{P}(X) \to X$ exists, and take the set $T$ of all $x \in X$ such that $x \not\in \phi^{-1}(x)$. Then ask whether $\phi(T) \in T$.) I don't think this is the same as the diagonal argument, although I can imagine that someone sufficiently determined might be able to argue otherwise. – Charles Staats Nov 22 2010 at 17:39
Why the votes to close? I think that this is an interesting question. For what it's worth I cast a vote to keep open which should be taken into account by the next person wishing to vote to close. If you wish to do so, then please let's take this to meta, where I have started this thread: meta.mathoverflow.net/discussion/789/… – José Figueroa-O'Farrill Nov 22 2010 at 17:46
@Francesco: no, the uncountability isn’t a corollary of the countability of the algebraics! Cantor’s original uncountability argument is what the OP refers to as the Nested Interval Theorem. The corollary Cantor then draws from this, together with countability of the algebraics, is the existence of transcendentals (lots of ’em) within any interval. – Peter LeFanu Lumsdaine Nov 22 2010 at 17:59
The nested interval method and the diagonal method are fundamentally the same method, as is the Russell paradox method. These are all the diagonal method. – Joel David Hamkins Nov 22 2010 at 18:06
I also cast a vote against closing. The question is: "Is there a different proof of this theorem?" which, to me, sounds very interesting and a natural question that a mathematically mature but non-expert-in-set-theory person might ask. I've asked several questions that have exposed my lamentable ignorance of the subtleties of mathematical foundations and, so far, all have received very interesting and informative answers. This one feels as though it is in the same vein as those. – Andrew Stacey Nov 22 2010 at 18:20
show 21 more comments

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.

-
Oh...Thank you. I did not think the question will go this far. So, the question is pretty like the statement in Cosmology: "The observable universe is finite but nobody yet knows whether it is infinite or not, let alone boundedness." – To be cont'd Nov 22 2010 at 18:49
Well, there is Quine's New Foundations in set theory, in which the diagonal argument is blocked from disproving the existence of a set of all sets, because of the inability to express the predicate $x \not \in x$. But I gather that NF does not block the diagonal argument from demonstrating the uncountability of the reals, so this isn't quite an answer to the problem at hand... – Terry Tao Nov 22 2010 at 23:28
Thank you. Now, I know that it is possible to block diagonalization in some setting. – To be cont'd Nov 23 2010 at 11:55
Reverse mathematics (en.wikipedia.org/wiki/Reverse_mathematics) is almost exactly about studying which axioms and arguments are necessary for certain theorems. If you want to know whether axiom X is necessary for a theorem Y, you can try to see if there's a model of Y in which X doesn't hold. It's not as easy to see whether a certain argument is necessary, but often you can axiomatize what it means to be able to do a certain argument, e.g. there are systems which capture what it means to be able to use a compactness argument, or induction, or transfinite recursion, etc. – Amit Kumar Gupta Nov 23 2010 at 18:27
@Amit: Yes, I'm familiar with reverse mathematics. But let me repeat what I said above: Think closely! How would you axiomatize what it means to be able to diagonalize? What candidate do you have in mind for a model in which the reals are countable? I stand by what I said; nobody has a clue. – Timothy Chow Nov 24 2010 at 2:28
show 3 more comments

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.

-

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.

-
 Isn’t this basically the same as Bill Johnson’s answer? – Emil Jeřábek Apr 29 at 11:20 Oh crap, I didn't even see that. I feel bad now... – Asaf Karagila Apr 29 at 11:42

As Andres implicitly pointed out, we may avoid diagonalization by working with ordinals directly. We can appeal to Hartog's 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 Hartog's 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.

-

I have the following candidate: http://arxiv.org/abs/1003.3557, section 7.4. Notice that in the setting of the article one cannot use diagonalization.

-

Cantor's original proof of uncountability of the reals did not explicitly mention diagonalization. Nor did it use decimal digits.

-
Unfortunately, this proof uses a diagonal argument. – Andres Caicedo Nov 23 2010 at 2:27
+1. I consider this to be a very different proof. It is constructive, or can be made so with little change. The diagonal argument actually proves the uncountability of 2^N, and no effective bijection between R and 2^N exists. – Daniel Mehkeri Nov 23 2010 at 2:27
@Daniel : I am not sure I understand what you mean. The proof uses a diagonal argument. The typical diagonal argument proofs are constructive. And it is easy to describe explicitly bijections between ${\mathbb R}$ and $2^{\mathbb N}$. – Andres Caicedo Nov 23 2010 at 3:03
Here is a hack to fix links to Wikipedia: go to "cite this page" and remove &oldid=XXXX from the URL. – Victor Protsak Nov 23 2010 at 4:54
Fixed the link. – David Roberts Nov 23 2010 at 5:00
show 3 more comments

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}$.

-
I'd be quite surprised if you could prove that that family you define doesn't cover the whole of [0,1] without using something very like the nested-intervals version of the diagonal argument. (That is, I'd like to know more about your proof that [0,1] has outer measure 1.) – gowers Nov 25 2010 at 22:15
I edited my post with a sketch of a proof that $[0,1]$ has outer measure $1$, modulo compactness of closed intervals. I do not see that I'm using a diagonal/nested intervals argument, but I could be totally wrong. The usual proof of Heine-Borel also doesn't appear to me to use a diagonal argument (see e.g. math.utah.edu/~bobby/3210/heine-borel.pdf). At no point in the proof there is an enumeration of an infinite set. – Pablo Shmerkin Nov 26 2010 at 0:38
Maybe you've convinced me. One can take the family you describe and define x to be the supremum over all reals x such that [0,x] can be covered by finitely many of its members. Such an x can't be covered itself (since the sets are open). This is just the proof of Heine-Borel in this special case. Also, your lemma gives us that x can't be 1. So one ends up using the least upper bound axiom instead of the nested-intervals property, which is perhaps enough to qualify the argument as genuinely different. – gowers Nov 27 2010 at 18:06
this proof appears in hardy's pure mathematics, about 100 years ago. – roy smith Dec 5 2010 at 5:36
I am sorry I have the book in hard, but can't find where the proof is. Could you tell me where that is? – To be cont'd Dec 22 2010 at 16:38

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 a unique well-ordering $(W, \lt)$ with $W\subseteq Y$ such that:

1. $\forall x\in W (F (\{y ∈ W \mid y \lt x\}) = x)$, and
2. $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 ﬁrst 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$?

-
 Although I think this is very interesting, I still wonder why we bother trying to avoid the diagonal argument by using tons of more advanced arguments, which perhaps in the end, when we enfold them into elementary arguments, use some sort of diagonal argument. – Martin Brandenburg Nov 23 2010 at 3:12 Hehe. As I mentioned, I found this argument while teaching a topics course; meaning: I was lecturing on ideas related to the arguments above, and while preparing notes for the class, it came to me that one would get a diagonalization-free proof of Cantor's theorem by following the indicated path; I looked in the literature, and couldn't find evidence of this being known. I wasn't explicitly looking for it at any point. Anyway, there is technical interest in the matter, precisely because the argument is so ubiquitous, as Joel's answer indicates. – Andres Caicedo Nov 23 2010 at 3:46 Now that I see it, I think I had seen this proof in a talk by Aki Kanamori. If I remember correctly, Aki attributed the proof to Tarski. Since this is from a long time ago, my memory may be off... – François G. Dorais♦ Nov 26 2010 at 15:25 @François : Oh, I should email Aki and ask him, then. Thanks! – Andres Caicedo Nov 26 2010 at 16:22 @Martin: I think rather than "coming to me", I read the argument in a paper by Kanamori-Pincus. I added a reference. – Andres Caicedo Nov 26 2010 at 17:37
show 2 more comments

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.

-
@Bill : Doesn't the non-connectedness of ${\mathbb Q}$ rely on the uncountability of ${\mathbb R}$? How do you argue about it directly? – Andres Caicedo Nov 23 2010 at 0:03
The rationals are clearly not connected. Partition then into the open sets of rationals less than $\sqrt{2}$ and the rationals greater than $\sqrt{2}$. – George Lowther Nov 23 2010 at 0:38
All you need to do is prove that between two rationals is an irrational. A variant of the well known proof that sqrt(2) is irrational should do the trick here. Just exploit the sparsity of squares among "large" integers. – Michael Renardy Nov 23 2010 at 0:40
+1. I voted this up, but it doesn't satisfy Gowers criterion (1), since the proof of Cantor's theorem that every countable dense subset of $\mathbb{R}$ is order isomorphic to $\mathbb{Q}$ involves enumerating $\mathbb{Q}$. – Joel David Hamkins Nov 23 2010 at 0:52
Bill, the point is that to get the final contradiction, if $f:\mathbb{Q}\to\mathbb{R}$ is the order isomorphism, then the resulting disconnection of $\mathbb{R}$ is the cut determined by $f[\\{q\mid q\lt\sqrt{2}\\}]$, say, which has least upper bound $z$, but no real works, since the $n$-th real in the enumeration was placed into the range of $f$ at stage $n$. So this is diagonalization. – Joel David Hamkins Nov 23 2010 at 10:43
show 4 more comments

A nice proof based on the property that each bounded subset of the reals has a surpremum can be found in this article.

-

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.

1. 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.

2. 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.

-
I'm obliged for your thoughts. – To be cont'd Nov 23 2010 at 11:21
That is a really great point about the importance of having an order for countability. I can't say that I see why for every Borel function $f$ defined on countable subsets of reals there is a countable set of reals $X$ such that such that $f(X) \in X$ (if that is a fair restatement) but I don't see any reason to doubt that. – Aaron Meyerowitz Nov 24 2010 at 2:03
In case somebody missed it, Aaron posted the above as a question: mathoverflow.net/questions/47185/… – Andres Caicedo Nov 28 2010 at 23:21

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.

-
Thank you. All this evidence is not a joke for me. By now I believe the founding of diagonal argumentation is tantamount to the the founding of the group concept. – To be cont'd Nov 22 2010 at 18:53
A lot of these can be captured by Lawvere's formalisation of the diagonal argument as a fixed-point theorem: tac.mta.ca/tac/reprints/articles/15/tr15abs.html – David Roberts Nov 22 2010 at 22:47
David, I agree, but another perspective is simply that the fixed-point theorem is another instance of diagonalization. That is, these arguments are already unified as diagonalizations. – Joel David Hamkins Nov 22 2010 at 23:30
Joel - I agree that calling them diagonalisation arguments or fixed point theorems is just a point of linguistics (actually the diagonal argument is the contrapositive of the fixed point version), it's just that Lawvere's version, to me at least, looks more like a single theorem than a collection of results that rely on an particular line of reasoning. This, I hope, helps the OP or those answering the question in isolating what a diagonal argument "is", and avoid it if possible. – David Roberts Nov 23 2010 at 4:54

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.

-
The proof of the Baire Category Theorem I have in mind is a fairly direct generalisation of Cantor's Diagonal Argument. – HW Nov 22 2010 at 18:03
Yes, the Baire category argument is (I believe) equivalent to the axiom of dependent choice in ZF, and thus non-constructive. – Todd Trimble Nov 22 2010 at 18:14
Similarly, we can use the existence of (countably additive) Lebesgue measure to conclude that $\mathbb{R}$ is uncountable. Or on $2^{\mathbb{N}}$ the existence of the (countably additive) product measure. Or, from probability theory, the existence of an i.i.d. sequence of non-trivial random variables. – Gerald Edgar Nov 22 2010 at 18:23
If you unwind the Baire Category proof of uncountability, it actually turns into a diagonal argument after all. Given any sequence $(x_i)$ of real numbers, you argue that the intersection over $i$ of $\mathbb{R} \setminus \{x_i\}$ is dense, by BCT, hence non-empty. The standard proof of BCT constructs an element of this intersection by first taking a ball contained in $\mathbb{R} \setminus \{x_0\}$, then a sub-ball of this contained $\mathbb{R} \setminus \{x_1\}$, and so-on. In other words, we construct a real by a countable sequence of approximations, [cont’d] – Peter LeFanu Lumsdaine Nov 22 2010 at 18:24
with the $n$th approximation ensuring that the resulting limit is not equal to $x_n$. So this is a version diagonal argument in the same sense that the nested limit theorem is. – Peter LeFanu Lumsdaine Nov 22 2010 at 18:25
show 5 more comments