9
$\begingroup$

I recently started studying set theory and am having quite a bit of difficulty accepting Cantor's diagonal proof for the uncountability of the reals. I also saw a topological proof via nested sets for uncountability which still does not satisfy me completely, given that just like the diagonal it relies on a never ending process. In fact, the nested sets proof sounds very much like the diagonalization proof to me.

Do all proofs of the uncountability of the reals involve diagonalization? Are there any other proofs I can look at to understand? I couldn't find any on searching stack exchange. Thanks.

$\endgroup$
  • $\begingroup$ There is no "never ending process." You should look at the proof again. It's valid, and if you have a more specific concern, I would be happy to address it. $\endgroup$ – Potato Apr 28 '13 at 6:39
  • $\begingroup$ How do you define real numbers? If it relies on any kind of sequences then the definition is rooted in a never ending process. I can only guess what the "nested sets" proof is but it sounds like it constructs a real number by a sequence of shrinking intervals, which is one way to define real numbers in the first place. $\endgroup$ – WimC Apr 28 '13 at 7:04
  • $\begingroup$ @ Potato: From what I understand of the diagonal process given on wikipedia and the nested intervals proof, both rely on some form of a never ending process. For example, the wikipedia proof on diagonalisation tries to construct a sequence that is not in our original list of sequences through in infinite recursive process. However, at no point does that process stop and actually give a sequence that is not in our original list of sequences, unless our original list is finite. Do you understand my point here, or am I misunderstanding this? $\endgroup$ – Elastine Apr 28 '13 at 7:24
  • 1
    $\begingroup$ @MathNewbie Do you not like the part where the sequence is defined, or where we show it is not on the original list? It sounds to me like it's the first one. The process isn't recursive, so there are no problems with it going on forever. If you want to know the $n$th digit, I can tell you without looking at any of the other digits. The definition happens "all at once," roughly. $\endgroup$ – Potato Apr 28 '13 at 17:07
  • 1
    $\begingroup$ @MathNewbie keep in mind that an infinite list still has everything in it at some finite position. You seem to be assuming that, to define a position in the list, we have to step through it one element at a time. Not necessary. We can just as easily specify a rule for which elements are at which points in the list. The set of square numbers, for example, is infinite. But no single number is "infinitely far" down the line: if you ask for any square number, I can give you its finite position in the list. Nothing actually has to be "at infinite", just at arbitrarily large finite values. $\endgroup$ – Robert Mastragostino Apr 28 '13 at 23:00
9
$\begingroup$

The real numbers are a complete densely ordered set without endpoints. That is, there is no minimum, no maximum, between every two points there is a third, and every set which has an upper bound has a least upper bound.

Theorem: Every countable dense order without endpoints is order-isomorphic to the rational numbers.

Since the rational numbers are not order complete, the real numbers are not order-isomorphic to the rationals. Therefore the real numbers cannot be countable.

$\endgroup$
  • 1
    $\begingroup$ This really seems in the spirit of the original question; it does not require knowledge of any other uncountable sets (like the power set of the naturals), nor does it require any "fancy" machinery to prove. Of course, it doesn't let us "pin down" the cardinality of the reals the way some of the other solutions do. $\endgroup$ – Iian Smythe Apr 28 '13 at 23:15
  • $\begingroup$ This is a good answer, but the argument does implicitly use diagonalization to construct the isomorphism. This is because it arranges the construction as a sequence of required properties, and then does a construction in stages such that stage $i$ is exactly intended to make sure property $i$ is satisfied. $\endgroup$ – Carl Mummert Apr 29 '13 at 0:44
  • 1
    $\begingroup$ Carl, one can argue (and semi-correctly, too) that diagonalization is the only trick in logic and set theory, and we use it for everything. But this is not Cantor's diagonal argument in the sense that we write a table and switch digits from the diagonal. $\endgroup$ – Asaf Karagila Apr 29 '13 at 0:46
  • $\begingroup$ @Carl, I just noticed that the previous comment didn't ping you (because there was another user who commented before you). Sorry 'bout that! $\endgroup$ – Asaf Karagila Apr 29 '13 at 1:21
  • $\begingroup$ @ Thanks. This is kinda the type I was looking for. Can you please elaborate on diagonalization being the "only trick" in logic and set theory? For example, what if we reject diagonalization? $\endgroup$ – Elastine Apr 29 '13 at 3:02
4
$\begingroup$

The real numbers are a perfect set, and all perfect sets are uncountable. In particular, this gives a proof of the uncountability of real numbers that does not reference decimal expansions.

$\endgroup$
  • 5
    $\begingroup$ This is nice, because it can be pushed to prove more: Given any Borel subset of the reals, it is either countable, or else it contains a perfect set. And any perfect set is not just uncountable, but in fact it has the same size as the reals. This shows that the continuum hypothesis holds when we restrict ourselves to Borel sets of reals. $\endgroup$ – Andrés E. Caicedo Apr 28 '13 at 22:30
4
$\begingroup$

Not all proofs of uncountability of the reals involve diagonalization. In fact, one can prove without diagonalization that $\mathbb R$ and $\mathcal P(\mathbb N)$ have the same size, and then give a diagonalization-free proof that, for any $X$, its power set $\mathcal P(X)$ has size strictly larger. This was first noticed by Zermelo. The details can be found in this MO answer.

Briefly: You prove that if $f:\mathcal P(X)\to X$, then $f$ is not injective, by explicitly exhibiting a pair $A\ne B$ of subsets of $X$ with $f(A)=f(B)$. Zermelo's approach uses well-orderings. You find $A,B$ by using transfinite recursion, to define an injective sequence $\langle a_\alpha\mid \alpha<\tau\rangle$ of elements of $X$ such that for all $\beta<\tau$ we have $f(\{a_\alpha\mid \alpha<\beta\})=a_\beta$, but $f(\{a_\alpha\mid \alpha<\tau\})=a_\gamma$ for some $\gamma<\tau$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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