Why isn't the set of real numbers countably infinite? I am a bit confused about the distinction between uncountable and countable infinite. In Cantor's Diagonalization, could we not say that every time we create a new real number using diagonalization we map it to the next natural number? Isn't this sort of a method of counting/enumeration, to just continue to diagonalize one-by-one to infinity (since there are infinite natural numbers every one can be mapped)?
 A: In Cantor's diagonalization, all of the natural numbers are already in use - the idea is that we begin with a mapping from the naturals to the reals, and construct a real that is not in the range of that mapping. So there is no "next" natural number.
The thing to realize is that the single diagonalization on its own doesn't prove uncountability - it's certainly the case that I can add one more element to an infinite list without changing its cardinality. The important thing about Cantor's diagonalization is that it works no matter what listing we start with. Here's the basic structure of the argument:


*

*If the real numbers were countable, then there would be a listing of them by the naturals (i.e., a map $f$ from $\mathbb{N}$ to $\mathbb{R}$ that covers every real).

*Suppose (for proof by contradiction) that the real numbers are countable. Let $f$ be a listing that proves this (so, $f$ is a map from $\mathbb{N}$ to $\mathbb{R}$ that covers every real).

*We apply diagonalization to construct a real $r \in \mathbb{R}$ that is not in the range of $f$.

*This contradicts our assumption about $f$ (that the range of $f$ includes every real). But $f$ was chosen arbitrarily, so this argument could be applied to any function you might suggest as a listing of the reals.

*Therefore, any proposed listing of the reals is not actually a listing of all of the reals. There is therefore no listing of the reals by the naturals, so by step (1) above we know that $\mathbb{R}$ is not countable.
