102
$\begingroup$

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.

$\endgroup$
29
  • 11
    $\begingroup$ 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. $\endgroup$ Nov 22, 2010 at 17:39
  • 28
    $\begingroup$ 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: tea.mathoverflow.net/discussion/789/… $\endgroup$ Nov 22, 2010 at 17:46
  • 25
    $\begingroup$ 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. $\endgroup$ Nov 22, 2010 at 18:06
  • 13
    $\begingroup$ @Charles: I don’t want to seem particularly determined, but isn’t $\{x\ |\ \varphi^{-1}(x) \notin x\}$ exactly the diagonal argument? It’s always referred to as such by logicians (see e.g. tac.mta.ca/tac/reprints/articles/15/tr15abs.html or most Set Theory texts), and given as an example of such by Wikipedia en.wikipedia.org/wiki/Cantor%27s_diagonal_argument#General_sets. $\endgroup$ Nov 22, 2010 at 18:14
  • 32
    $\begingroup$ 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. $\endgroup$ Nov 22, 2010 at 18:20

21 Answers 21

84
$\begingroup$

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.

$\endgroup$
13
  • 17
    $\begingroup$ 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... $\endgroup$
    – Terry Tao
    Nov 22, 2010 at 23:28
  • 16
    $\begingroup$ 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. $\endgroup$ Nov 23, 2010 at 18:27
  • 8
    $\begingroup$ @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. $\endgroup$ Nov 24, 2010 at 2:28
  • 6
    $\begingroup$ 1. Are you saying reverse math never proves results of the form "Argument A is necessary for Theorem T" (in some reasonable sense of the word "necessary")? 2. You presume that diagonalization is necessary for Cantor's theorem - someone who believes not wouldn't need a model where the reals are countable. 3. Why is it that "being able to diagonalize" can't be axiomatized? A huge variety of arguments get referred to as compactness arguments, so naively one would think you couldn't axiomatize "being able to do a compactness argument", but doesn't Weak Konig's Lemma sort of do just that? $\endgroup$ Nov 25, 2010 at 8:44
  • 5
    $\begingroup$ @TimothyChow From what I've seen, I agree with you that this sort of mathematics hasn't been studied at nearly the level required to prove such a theorem, but "nobody has any idea", I don't think is a very good way to surmise the situation. In particular, for set theory developed over a certain paraconsistent logic, Cantor's theorem is unprovable. See "What is wrong with Cantor's diagonal argument?" by Ross Brady and Penelope Rush. So, if one developed enough of reverse mathematics in such a context, one could I think meaningfully ask this question. $\endgroup$ Oct 25, 2017 at 12:50
68
$\begingroup$

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.

$\endgroup$
11
  • 9
    $\begingroup$ 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. $\endgroup$
    – Unknown
    Nov 22, 2010 at 18:53
  • 11
    $\begingroup$ 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 $\endgroup$
    – David Roberts
    Nov 22, 2010 at 22:47
  • 12
    $\begingroup$ 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. $\endgroup$ Nov 22, 2010 at 23:30
  • 7
    $\begingroup$ 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. $\endgroup$
    – David Roberts
    Nov 23, 2010 at 4:54
  • 5
    $\begingroup$ The existence of forcing extensions is also an application of diagonalization. $\endgroup$ Sep 7, 2017 at 6:28
40
$\begingroup$

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

$\endgroup$
5
  • 6
    $\begingroup$ 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.) $\endgroup$
    – gowers
    Nov 25, 2010 at 22:15
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 26, 2010 at 0:38
  • 7
    $\begingroup$ 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. $\endgroup$
    – gowers
    Nov 27, 2010 at 18:06
  • 4
    $\begingroup$ this proof appears in hardy's pure mathematics, about 100 years ago. $\endgroup$
    – roy smith
    Dec 5, 2010 at 5:36
  • 3
    $\begingroup$ I am sorry I have the book in hard, but can't find where the proof is. Could you tell me where that is? $\endgroup$
    – Unknown
    Dec 22, 2010 at 16:38
36
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ @Bill : Doesn't the non-connectedness of ${\mathbb Q}$ rely on the uncountability of ${\mathbb R}$? How do you argue about it directly? $\endgroup$ Nov 23, 2010 at 0:03
  • 11
    $\begingroup$ 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}$. $\endgroup$ Nov 23, 2010 at 0:38
  • 4
    $\begingroup$ +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}$. $\endgroup$ Nov 23, 2010 at 0:52
  • 2
    $\begingroup$ If $a\lt b$ are rational then $a+(b-a)/\sqrt2$ is an irrational between them. $\endgroup$ Nov 23, 2010 at 6:11
  • 24
    $\begingroup$ 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. $\endgroup$ Nov 23, 2010 at 10:43
32
$\begingroup$

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:

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

$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 23, 2010 at 3:12
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 23, 2010 at 3:46
  • $\begingroup$ 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... $\endgroup$ Nov 26, 2010 at 15:25
  • $\begingroup$ @François : Oh, I should email Aki and ask him, then. Thanks! $\endgroup$ Nov 26, 2010 at 16:22
  • 12
    $\begingroup$ @MartinBrandenburg A very late reply, but here is a reason to bother: The argument 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{ZF}$. 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, see here). $\endgroup$ Feb 27, 2014 at 6:30
24
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ I'm obliged for your thoughts. $\endgroup$
    – Unknown
    Nov 23, 2010 at 11:21
  • $\begingroup$ 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. $\endgroup$ Nov 24, 2010 at 2:03
  • $\begingroup$ In case somebody missed it, Aaron posted the above as a question: mathoverflow.net/questions/47185/… $\endgroup$ Nov 28, 2010 at 23:21
  • $\begingroup$ @gowers This might answer (2) negatively. Suppose $T \models (X \subset \mathbb{R}$ is isomorphic to $\mathbb{Q})$. Then $T \models (X \in H(\omega_{1}))$, since $\mathbb{Q} \in H(\omega_{1})$ which satisfies Replacement; hence $X$ is countable. $\endgroup$
    – Avshalom
    Oct 19, 2014 at 9:48
18
$\begingroup$

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.

$\endgroup$
13
  • 1
    $\begingroup$ Yes, but without invariably proving that $\Bbb R$ and $\cal P(\Bbb N)$ have the same cardinality, how would you prove it? $\endgroup$
    – Asaf Karagila
    Oct 17, 2014 at 10:16
  • 1
    $\begingroup$ @Joel, so you need to know that the reals the $2^\omega$ are equipotent. That was my point. $\endgroup$
    – Asaf Karagila
    Oct 17, 2014 at 13:11
  • 1
    $\begingroup$ @Andres: Fine, so if $2^\omega\leq\Bbb R$, why do we have to work anymore than that? This suffices to show that $R$ is uncountable, since there is no surjection from $\omega$ onto $2^\omega$. $\endgroup$
    – Asaf Karagila
    Oct 17, 2014 at 15:51
  • 8
    $\begingroup$ This proof seems to me to be genuine proof without diagonalization! Doesn't this completely answer the question? $\endgroup$ Oct 19, 2014 at 1:38
  • 1
    $\begingroup$ I thought I had said in the comments on Bill's answer that I thought it did. $\endgroup$ Oct 19, 2014 at 3:37
18
$\begingroup$

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:

  1. $a(x) > 0$ for all $x$,

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

$\endgroup$
1
  • $\begingroup$ This is also mentioned in @Ralph's answer, without the details. $\endgroup$
    – LSpice
    Jan 14, 2021 at 17:13
12
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
10
  • 9
    $\begingroup$ The proof of the Baire Category Theorem I have in mind is a fairly direct generalisation of Cantor's Diagonal Argument. $\endgroup$
    – HJRW
    Nov 22, 2010 at 18:03
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 22, 2010 at 18:23
  • 7
    $\begingroup$ 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] $\endgroup$ Nov 22, 2010 at 18:24
  • 5
    $\begingroup$ 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. $\endgroup$ Nov 22, 2010 at 18:25
  • 4
    $\begingroup$ @Todd: The abstract Baire category argument requires (dependent) choice, but for the reals can be done without requiring extra choice. Instead, enumerate the rationals, then when asked to "choose" a point in a given open interval, choose the first rational in that interval. $\endgroup$ Nov 22, 2010 at 18:26
6
$\begingroup$

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

$\endgroup$
8
  • 8
    $\begingroup$ Unfortunately, this proof uses a diagonal argument. $\endgroup$ Nov 23, 2010 at 2:27
  • $\begingroup$ +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. $\endgroup$ Nov 23, 2010 at 2:27
  • 8
    $\begingroup$ @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}$. $\endgroup$ Nov 23, 2010 at 3:03
  • $\begingroup$ This information and the corresponding wikipedia link are already contained in my comment above :-) $\endgroup$ Nov 23, 2010 at 11:35
  • $\begingroup$ Michael, if you reflect upon it, you will see that the two arguments are fundamentally identical. Prescribing the successive digits of a real to have certain values is the same thing as placing the resulting real in certain intervals. $\endgroup$ Nov 23, 2010 at 13:45
6
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Wouldn't it be simpler to work with surjections instead of injections? There is a surjection from $\mathcal P(\omega)$ to $\omega_1$, there is no surjection from $\omega$ to $\omega_1$, therefore $\mathcal P(\omega)$ is uncountable. $\endgroup$
    – bof
    Jul 31, 2014 at 8:33
5
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ The last part relies on the fact that a partition of a set never has more parts than there are elements in the underlying set. This is actually not necessarily true! That is, that fact is a weak form of the Axiom of Choice as explained by Dr. Strangechoice. That said, the argument does work to show that $|2^{\mathbb{N}}| \gt \aleph_0$ since the contrary assumption $|2^{\mathbb{N}}| \leq \aleph_0$ entails that $2^{\mathbb{N}}$ is wellorderable. $\endgroup$ Sep 28, 2014 at 15:07
  • $\begingroup$ I was wondering if I can come up with a proof which both doesn't use choice and doesn't use contradiction, but it looks like this argument won't exactly work. $\endgroup$
    – Wojowu
    Sep 28, 2014 at 15:25
  • $\begingroup$ The issue is that "uncountable" is a negative statement and the natural way to prove a negative is by deriving a contradiction from the positive statement. Note that this is not a proof by contradiction, which consists of proving a positive by deriving a contradiction from the negative... $\endgroup$ Sep 28, 2014 at 15:37
  • $\begingroup$ I think this answer goes in the right direction. It seems to me that a way (if not the way) to give a precise meaning to the original question is proving $|\mathbb{R}|>|\mathbb{N}|$ in an axiomatic context where one can't prove $|\mathbb{R}|=|2^\mathbb{N}|$, which is a consequence of the diagonal argument. $\endgroup$ Oct 17, 2014 at 9:18
  • $\begingroup$ @François, the proof is choice free. Only the conclusion that $\aleph_1\leq2^{\aleph_0}$ uses choice. However if you already know that $\Bbb R$ and $\cal P(\Bbb N)$ are equipotent, why so you need to continue? Cantor's theorem, the general one, is easier. $\endgroup$
    – Asaf Karagila
    Oct 17, 2014 at 10:23
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think you need the Nested Interval Theorem referred to in the question to prove that the $x$ in the Lemma exists. $\endgroup$
    – Michael
    Oct 2, 2017 at 20:04
  • $\begingroup$ Definitely I need (or some other variant of completeness axiom.) This proof is not the best in logical or set-theoretical sense. $\endgroup$ Oct 2, 2017 at 20:17
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ Isn’t this basically the same as Bill Johnson’s answer? $\endgroup$ Apr 29, 2013 at 11:20
  • 1
    $\begingroup$ Oh crap, I didn't even see that. I feel bad now... $\endgroup$
    – Asaf Karagila
    Apr 29, 2013 at 11:42
4
$\begingroup$

Just to add a couple of references:

  1. John Franks' paper titled "Cantor’s Other Proofs that R Is Uncountable" is available at https://www.jstor.org/stable/10.4169/002557010X521822 (unfortunately, not for free)
  2. and Akihiro Kanamori & David Pincus' paper titled "Does GCH Imply AC Locally" is available at http://math.bu.edu/people/aki/7.pdf (for free).
  3. You might also like looking at "Diagonalizing by Fixed-Points" by "Ahmad Karimi & Saeed Salehi" (available at arxiv.org) where some of the above mentioned proofs have been discussed.
$\endgroup$
0
4
$\begingroup$

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:

  1. $r\notin M$, as otherwise $G=\{r \restriction n: n<\omega \}\in M$ which is not possible
  2. $r\in\mathbb R\subseteq M$

A contradiction.

$\endgroup$
3
  • $\begingroup$ The problem here is that we use such heavy machinery that it's not clear if we used the uncountability of the reals somewhere in the process. If we did, the proof is circular. $\endgroup$
    – Asaf Karagila
    Jan 14, 2021 at 9:32
  • 1
    $\begingroup$ This is cute, but likely diagonalization is recognizable arguing that generics exist and don't belong to the ground model. $\endgroup$ Jan 14, 2021 at 17:20
  • $\begingroup$ @AndrésE.Caicedo At least not visible. To show the existence of generic filter, we just count dense sets and build the filter inductively. To show the generic filter is not in the ground model, we just use the fact that its complement is dense. $\endgroup$ Jan 15, 2021 at 4:48
3
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ This is exactly the argument of nested intervals. By the way, the fact that Bob might not have a winning strategy doesn't mean that Bob has to lose. $\endgroup$
    – Asaf Karagila
    Oct 17, 2014 at 22:13
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ When you say "this is nonsense" you need explanation. One explanation is existence of Lebesgue measure. What you show is: a countable set has measure at most $1$. You also need: the real line has measure ${}> 1$. But (so far) you have not proved that. $\endgroup$ Oct 6, 2017 at 11:54
  • 2
    $\begingroup$ I agree there's a detail there, but I think it's straightforward. Measure theory makes it immediate, but isn't necessary. For example, if you use open intervals, you could take a finite subcover of [0,2] by compactness. Now you have a finite set of intervals with total length < 1, which cover an interval of length 2. $\endgroup$ Oct 6, 2017 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.