# 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 '10 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: tea.mathoverflow.net/discussion/789/… –  José Figueroa-O'Farrill Nov 22 '10 at 17:46
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 '10 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. –  Loop Space Nov 22 '10 at 18:20
Kevin, my criterion for keeping MO questions open has almost entirely to do with the level of mathematical sophistication, rather than degree of formalization, and questions of the form "Can we prove fundamental theorem X with (or without) method Y" are on topic. Although as you and Timothy Chow point out, ruling out a method seems difficult, providing a postive instance does not. In particular, if there is a proof of Cantor's theorem that differs fundamentally from those I know, I am keen to learn about it. Bill's answer comes close, but is at bottom still a diagonalization. –  Joel David Hamkins Nov 23 '10 at 12:50

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." –  Unknown Nov 22 '10 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 '10 at 23:28
Thank you. Now, I know that it is possible to block diagonalization in some setting. –  Unknown Nov 23 '10 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 '10 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 '10 at 2:28

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 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. –  Unknown Nov 22 '10 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 '10 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 '10 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 '10 at 4:54
In a sense, Gödel incompleteness is also proved using this method –  მამუკა ჯიბლაძე Oct 20 '14 at 0:05

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 '10 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 '10 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 '10 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 '10 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 '10 at 10:43

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

(Update: In general, the answer to the question is no. See here.)

-
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 '10 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 '10 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 '10 at 15:25
@François : Oh, I should email Aki and ask him, then. Thanks! –  Andres Caicedo Nov 26 '10 at 16:22
@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). –  Andres Caicedo Feb 27 '14 at 6:30

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 '10 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 '10 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 '10 at 18:06
this proof appears in hardy's pure mathematics, about 100 years ago. –  roy smith Dec 5 '10 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? –  Unknown Dec 22 '10 at 16:38

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. –  Unknown Nov 23 '10 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 '10 at 2:03
In case somebody missed it, Aaron posted the above as a question: mathoverflow.net/questions/47185/… –  Andres Caicedo Nov 28 '10 at 23:21
@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. –  Avshalom Oct 19 '14 at 9:48

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

-

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.

-

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. –  HJRW Nov 22 '10 at 18:03
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 '10 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 '10 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 '10 at 18:25
@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. –  Gerald Edgar Nov 22 '10 at 18:26

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 '10 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 '10 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 '10 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 '10 at 4:54
Fixed the link. –  David Roberts Nov 23 '10 at 5:00

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.

-
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. –  bof Jul 31 '14 at 8:33

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.

-
Yes, but without invariably proving that $\Bbb R$ and $\cal P(\Bbb N)$ have the same cardinality, how would you prove it? –  Asaf Karagila Oct 17 '14 at 10:16
@AsafKaragila You can get the surjection from the fact that every countable ordinal is isomorphic to a relation on $\omega$, and hence coded by a real. –  Joel David Hamkins Oct 17 '14 at 11:32
@Joel, so you need to know that the reals the $2^\omega$ are equipotent. That was my point. –  Asaf Karagila Oct 17 '14 at 13:11
@AsafKaragila No, all you need is that the Cantor set exists. Why would you need that $\mathbb R$ injects into $2^{\mathbb N}$? –  Andres Caicedo Oct 17 '14 at 14:49
This proof seems to me to be genuine proof without diagonalization! Doesn't this completely answer the question? –  Joel David Hamkins Oct 19 '14 at 1:38

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.

-

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 '13 at 11:20
Oh crap, I didn't even see that. I feel bad now... –  Asaf Karagila Apr 29 '13 at 11:42

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

-
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. –  François G. Dorais Sep 28 '14 at 15:07
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. –  Wojowu Sep 28 '14 at 15:25
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... –  François G. Dorais Sep 28 '14 at 15:37
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. –  Pietro Majer Oct 17 '14 at 9:18
@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. –  Asaf Karagila Oct 17 '14 at 10:23

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.

-
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. –  Asaf Karagila Oct 17 '14 at 22:13