I am struggling a bit trying to understand Cantor's theorem about the reals being uncountable.

How can you choose a real number that is different from all real numbers in an enumeration $S$?

I completely get the trick about finding a real $r \notin S$ by changing one digit from each element of $S$, but how can you do that when $S$ in infinite? I mean, you would never actually produce a number $r$, because you would just be in a race where you try to exhaust $S$, but you never reach the end of the list as $S$ is infinite.

Also, wouldn't a similar diagonalization strategy prove that the natural numbers are uncountable? That would contradict the fact that a set $A$ is countable if $|A| = |\mathbb{N}|$.

I can easily see how to count the real numbers: $1, 2, ... $, but what I question is the diagonalization argument, since I think it can be used in the same manner to prove the natural numbers uncountable.

  • 5
    $\begingroup$ Please, try to write down your diagonal argument for natural numbers. $\endgroup$ – mfl Oct 27 '14 at 19:58
  • $\begingroup$ @mfl If we were to enumerate all natural numbers, S = s1 s2 ..., we can make a number x that is not part of that enumeration by choosing the 1st digit of x to be different from the 1st digit of s1. The 2nd digit of x should be different from the 2nd digit of s2. In that way, x is different from any number in S, thus x is not in S. But constructed in this way, x is indeed a natural number, and hence x is in N. Therefore, S != N. $\endgroup$ – Kent Munthe Caspersen Oct 27 '14 at 20:07
  • $\begingroup$ $s_1$ is a natural number, not a digit. $\endgroup$ – mfl Oct 27 '14 at 20:08
  • 1
    $\begingroup$ so how many digits do your natural numbers have? can you list all the natural numbers with only one digit? are there natural numbers with infinitely many digits? $\endgroup$ – pinkwerther Oct 27 '14 at 20:09
  • 2
    $\begingroup$ @KentMuntheCaspersen In your construction, $x$ will have infinitely many nonzero digits, so it won't be a valid natural number. $\endgroup$ – Mike Earnest Oct 27 '14 at 20:12

The typical diagonal argument looks at numbers in the range $(0,1)$ expressed in decimal and by changing digits you create a new real number in that interval on the top-left to bottom-right diagonal. Each number $x_i$ in your list has a countably infinite number of digits (even if in some cases almost all of them are zero) so you can choose the $i$th digit of your new number to be different from the $i$th digit of $x_i$.

For natural numbers, you would have the diagonal running top-right to bottom-left. Each integer $n_i$ in your list would have an infinite number of leading zeros, so your newly constructed diagonal number would have an infinite number of non-zero digits and so would not be an integer.

  • $\begingroup$ Once again, this is a job for our favorite hero, Archimedes Plutonium!!!! $\endgroup$ – marty cohen Nov 30 '15 at 4:43

It is completely OK to do define all infinitely many digits of $r$ in this way, you don't have to define the digits "one a time," which means you would never finish, but can instead define them all at once.

Suppose someone claims they have a list $S$ which enumerates the interval $[0,1]$: $$ 0.x_1^1x^1_2x^1_3,\dots\\ 0.x^2_1x^2_2x^3_2,\dots\\ \vdots $$ Let $y_n = x^n_n+1$ (mod $10$), and let $$r=0.y_1y_2\dots y_n\dots$$

Notice we have defined $r$ in a single sentence, with a well-defined formula, so this defines the infinitely many digits of $r$ all at once.

  • $\begingroup$ There's still a technical problem, because you might end with $y_n$ to be eventually the constant $9$. $\endgroup$ – egreg Oct 27 '14 at 21:14
  • $\begingroup$ True, though the technicalities are not in the spirit of OP's confusion, so I won't try to figure them out $\endgroup$ – Mike Earnest Oct 27 '14 at 21:56
  • $\begingroup$ I was just pointing it out, having already upvoted. $\endgroup$ – egreg Oct 27 '14 at 21:57

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.