# Can Cantor's theorem prove that $\mathbb N$ is uncountable (paradox)?

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.

• Please, try to write down your diagonal argument for natural numbers. – mfl Oct 27 '14 at 19:58
• @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. – Kent Munthe Caspersen Oct 27 '14 at 20:07
• $s_1$ is a natural number, not a digit. – mfl Oct 27 '14 at 20:08
• 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? – pinkwerther Oct 27 '14 at 20:09
• @KentMuntheCaspersen In your construction, $x$ will have infinitely many nonzero digits, so it won't be a valid natural number. – 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.

• Once again, this is a job for our favorite hero, Archimedes Plutonium!!!! – 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.

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