4
$\begingroup$

I understand Cantor's diagonal argument, but it just doesn't seem to jive for some reason.

Lets say I assign the following numbers ad infinitum...

  1. $1\to 0.1$
  2. $2\to 0.2$
  3. $3\to 0.3$ ...
  4. $10\to 0.10$
  5. $11\to 0.11$

and so on... How come there's supposedly at least one more real number than you can map to a member of $\mathbb{N}$?

  • 5
    Because... Cantor explicitly tells us what that "one" real number is... ???2012-11-14
  • 6
    @agent154: By the way, where is $\frac13$ in your list?2012-11-14
  • 0
    @DejanGovc Wouldn't that easily be mapped to the natural number with the same number of 3s in it?2012-11-14
  • 2
    @agent154: Not exactly; $\frac13=0.333333333\ldots$ has an infinite number of 3's in its decimal expansion.2012-11-14
  • 2
    All of your real number have finite digital representations, which means they are of the form $\frac{n}{10^m}$ for some non-negative integers $n,m.$ There are tons of real numbers that are not in this list.2012-11-14
  • 0
    If $\mathbb{R}$ is countable, the Lebesgue measure of the unit interval $[0, 1]$ must be 0.2012-11-14
  • 6
    ...are you *sure* you understand Cantor's diagonal argument?2012-11-14
  • 6
    @MakotoKato That's a bit of a useless argument. Presumably, if he knew what the Lebesgue measure was, he would already be comfortable with Cantor's argument.2012-11-14
  • 0
    This *has* to already be a question here. Anybody have a good "duplicate" to close this to?2012-11-14
  • 1
    @ThomasAndrews It is a comment, not an answer. I think it's useful for people who don't like the Cantor's argument.2012-11-14
  • 1
    Yeah, and the intuitive version of the Lebesgue argument can be convincing - that we could cover the unit interval by a set of intervals with total length less than $1$ if $[0,1]$ were countable is an intuitive contradiction. But most people who don't know Cantor's proof don't know what "Lebesgue measure" even means.2012-11-14
  • 2
    @ThomasAndrews Probably not. So what? It's just a comment which also may be read by people other than the OP.2012-11-14

4 Answers 4

9

If we apply the Cantor diagonal argument to the list you have there, and assign the $n$th digit in our constructed number to be 0 if the $n$th digit of the $n$th number in the list is 1, and 1 if it isn't, we construct the real number $0.0111111\ldots$ (which happens to be equal to $\frac1{90}$) and in fact is not anywhere in your list, since there is no integer that looks like $0111111\ldots$. So the construction worked fine: you presented what you claim is a list of all real numbers, and then the construction produced a real number that you omitted. Where's the problem?

(If you're not happy with that, perhaps it's enough to point out that your list not only omits all the repeating decimals such as $\frac 13, \frac23, \frac 16, \frac 17, \frac 27\ldots$, but also all the numbers less than 1/10. So it's not even a list of all the rational numbers.)

  • 0
    the fact that you can inject $\mathbb R$ into $\mathbb N$ doesn't prove that there are more real numbers then natural ones. It just shows that there are no less real numbers then natural ones.2012-11-14
  • 0
    @mjd That actually helps make a bit more sense. At least my assignment doesn't work since it doesn't account for numbers less than 1/10 as you state. But I guess my issue is with the fact that I don't understand this well enough yet. I only just learned about countability, and even then very poorly, since my prof is not a good teacher.2012-11-15
6

Let's look at the interval $0 < x < 1.$ Let's assume all of its numbers are countable, i.e. they are listable. Let's say the list goes like:

  1. 0.12345...
  2. 0.32145...
  3. 0.87654...
  4. 0.28374...
  5. 0.67676...
  6. etc...

From the list, I make a new number. Its first decimal place is the same as the first number's, its second decimal place is the same as the second number's, its third decimal place is the same as the third number's, etc. The new number I get is:

$$0.12676...$$

Using this number, I create a new number. If a digit is a $1$ then I change it to a $2$. If a digit is anything else then I change it to a $1$. Thus:

$$0.12676... \mapsto 0.21111...$$

This new number, $0.21111...$ is not on my list. It's not the first number because it's different in the first place, it's not the second number because it's different in the second place, it's not the third number because it's different in the third place, it's not the fourth number because it's different in the fourth place, etc. It follows that my new number is not in my list, and so I could not have listed all of the numbers $0 < x < 1$. Thus, by contradiction, the interval is not countable.

Check out this YouTube clip.

  • 0
    As stated, I do understand the basic theory of the diagonalization method... but despite it saying that the new number couldn't possibly exist in the list, I just couldn't see a logical reason why I couldn't enumerate it as stated above. But I hadn't noticed that doing it my way at the very least omits all the numbers less than 1/102012-11-15
  • 0
    @agent154 To be blunt: you obviously didn't understand the basic theory. If you had then you wouldn't have posted the question that you did.2012-11-15
  • 0
    well that's not fair. Many smart people claim to have some kind of proof that Cantor was wrong, but it doesn't mean they don't understand his theory. I just can't take something at face value sometimes. I understand the logic behind the diagonal argument, but neglecting that, I just can't wrap my head around why you cannot possibly enumerate all the real numbers.2012-11-16
  • 0
    Good example. Most proofs on this are too long.2016-01-09
1

How come there's supposedly at least one more real number than you can map to a member of $\mathbb N$?

Well, suppose there isn't - that Cantor's conclusion, his theorem, is wrong, because our enumeration covers all real numbers. Wonderful, but let us see what happens when we take our enumeration and apply Cantor's diagonal technique to obtain a real number that can't be in this sequence. But that contradicts our supposition! Hence our supposition - that we can have an enumeration of all reals - is false. That the argument can be applied to any enumeration is what it takes for Cantor's theorem to be true.

Wilfred Hodges wrote an excellent survey of wrong refutations of Catonr' argument, his An Editor Recalls Some Hopeless Papers (Postscript). Section 7, dealing with how the counterfactual assumption confuses, might be of particular interest.

0

Cantor's diagonal is a trick to show that given any list of reals, a real can be found that is not in the list.

First a few properties:

  • You know that two numbers differ if just one digit differs.
  • If a number shares the previous property with every number in a set, it is not part of the set.

Cantor's diagonal is a clever solution to finding a number which satisfies these properties. The number which is the diagonal is transformed s.t. it doesn't share the first digit of the first number nor the second digit with the second and so on. Thus the number is unique to the list.

This is why Cantor's diagonal as a method proves the result that the reals are uncountable.