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)?
4
-
$\begingroup$ PS. I realize this is asking the same thing as another question but I have a different idea behind it, should I have just added mine as a comment on that post? $\endgroup$– notReallyDevJul 4, 2017 at 17:48
-
$\begingroup$ No, we could not say this in Cantor's diagonal argument. It already assumes that we have finished counting/enumeration, and then get a contradiction. $\endgroup$– Dietrich BurdeJul 4, 2017 at 17:51
-
$\begingroup$ No. To prove $\mathbb{R}$ is countable you would have to exhibit a single enumeration of every real numbers - you can't change it later. $\endgroup$– Jair TaylorJul 4, 2017 at 17:52
-
$\begingroup$ Oh, I see, so since in our attempt to count real numbers we first need to demonstrate a bijection between R and N (which must be onto, meaning all natural numbers are mapped to some corresponding value already) there are no natural numbers left to map to the new diagonal values. $\endgroup$– notReallyDevJul 4, 2017 at 20:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jul 4, 2017 at 17:56