Proofs of the uncountability of the reals. - MathOverflow

Proofs of the uncountability of the reals.

2010-11-22T17:19:28Z

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.

Answer by Martin Brandenburg for Proofs of the uncountability of the reals.

2010-11-22T17:42:22Z

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.

Answer by Timothy Chow for Proofs of the uncountability of the reals.

2010-11-22T18:25:07Z

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.

Answer by Joel David Hamkins for Proofs of the uncountability of the reals.

2010-11-22T18:27:10Z

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.

Answer by gowers for Proofs of the uncountability of the reals.

2010-11-22T21:02:35Z

Although I very much take Timothy Chow's point, and don't have a way of constructing anything like a model where Cantor's diagonal argument is blocked (I'm not sure what the diagonal argument is in the abstract, given that there are variants), some sickness in me makes me want to try to answer the question anyway. One small thought that occurs to me is that all proofs depend (or can be very easily transformed so that they depend) on the following ingredients: a bijection between the countable set and the natural numbers, the use of the ordering on the natural numbers to order the countable set, the construction of a sequence that lives in a sequence of nested intervals that avoid the points of the countable set, one at a time.

Here are some questions that are more specific than the one in the OP. They are off the top of my head and therefore not guaranteed to be sensible.

Suppose we tried artificially to block the use of the ordering. It might seem impossible, since the definition of countability is that there is a bijection to the natural numbers, but we could, for instance, try proving the result for sets that are in bijection with the rationals and insist that at no point does the proof define an enumeration of that set.
Or we could start with the stronger hypothesis that X is a set of reals that is order-isomorphic to the rationals. Is it possible to prove that this set does not contain all reals without at the same time proving that it is countable?

I don't know how relevant this is, but I'd also like to mention a fascinating fact that I heard from Harvey Friedman recently that feels as though it's in the same ball park. He told me that there exists a Borel function f defined on sequences of reals such that for every sequence S the value f(S) is not a term of S. That's easy to prove from the diagonal argument. On the other hand, there is no Borel function from countable subsets of reals such that f(X) is not an element of X for any countable set X. (I think I remember that that's what he said, but I'm not certain that the result wasn't stronger.) Equivalently, you can't find an f that works for sequences and is also invariant under permutations of the terms in the sequence. This gives us a sort of hint that some kind of enumeration is essential to the proof, but I don't see how to make that hint into a precise thought.

Answer by Ralph for Proofs of the uncountability of the reals.

2010-11-22T23:38:07Z

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

Answer by Bill Johnson for Proofs of the uncountability of the reals.

2010-11-23T00:00:12Z

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.

Answer by Andres Caicedo for Proofs of the uncountability of the reals.

2010-11-23T00:01:30Z

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:

$\forall x\in W (F (\{y ∈ W \mid y \lt x\}) = x)$ , and

$F (W )\in W$.

We can then take $A=W$ and $B=\{y\in W\mid y\lt F(W)\}$ .

c. Zermelo's theorem can be proved as follows: Simply notice that $W=\{a_\alpha\mid \alpha\lt \beta\}$ where $$ a_\alpha= F(\{a_\gamma\mid \gamma\lt \alpha\}) $$ and $\beta$ is largest so that this sequence is injective.

That $\beta$ exists is a consequence of Hartogs theorem that for any set $A$ there is a least ordinal $\alpha$ does not inject into $A$.

Uniqueness of $W$ is shown by considering the ﬁ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$?

Answer by Pablo Shmerkin for Proofs of the uncountability of the reals.

2010-11-23T00:50:20Z

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

Answer by Michael Hardy for Proofs of the uncountability of the reals.

2010-11-23T00:53:32Z

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

Answer by Antongiulio for Proofs of the uncountability of the reals.

2010-11-26T13:26:00Z

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.

Answer by Jason for Proofs of the uncountability of the reals.

2010-12-05T02:04:44Z

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.

Answer by Asaf Karagila for Proofs of the uncountability of the reals.

2013-04-28T23:44:10Z

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.

Answer by Margaret Friedland for Proofs of the uncountability of the reals.

2013-04-30T14:33:34Z

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.