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

Question

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.

Answer 1

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.

Answer 2

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.