1
$\begingroup$

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)?

$\endgroup$
  • $\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$ – Michelle Jul 4 '17 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 Burde Jul 4 '17 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 Taylor Jul 4 '17 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$ – Michelle Jul 4 '17 at 20:20
4
$\begingroup$

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:

  1. 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).

  2. 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).

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

  4. 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.

  5. 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.

$\endgroup$

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.