6
$\begingroup$

Let's start with Hilbert's Hotel. A hotel exists with infinite rooms. The rooms are all full with infinite guests. A new guest arrives. The manager asks every person to go to their room number plus one and voila - Room 1 is open for the new guest. $\infty + 1 = \infty$.

Now let's look at Cantor's diagonal argument. Are there more natural numbers than numbers between 0 and 1? We have an infinite sheet of paper. On the left we write our naturals, 1, 2, 3, and so on. On the right we write numbers between 0 and 1 in any order. The argument says I can add a new number to the right by adding 1 to the nth decimal place of the nth number on the list. And it must be unique. Therefore the list wasn't complete and it proves that there are more of these than integers.

I just don't agree with this logic. I'm wrong but I can't grasp why I am wrong and what I am missing.

  1. If $\infty + 1 = \infty$ (Hilbert) then why does $\infty + 1 = uncountable$ $\infty$ (Cantor)?
  2. If all we did in Cantor is prove that the list of decimals between 0 and 1 was incomplete, then didn't we prove that the list of integers was incomplete in Hilbert? Seems like the same argument? Can't the last guy that moved have taken a number mapping to Cantor's new found number?
  3. I can directly map a 1-1 set of all rational numbers in the set [0, 1) to integers. How? Take any integer and reverse the digits. Now add "0." to the start. So the integer 12345 becomes 0.54321 and the integer 100 becomes 0.001. The reason for the reversal is because 10 and 100 would map to 0.10 and 0.100 which is the same thing if you didn't do this. Any decimal you give me I can remove the "0." from it, reverse it, and make it a new and unique integer. Doing this I can find Cantor's new number found by the diagonal modification.
  4. If Cantor's argument included irrational numbers from the start then the argument was never needed. The entire natural set of numbers could be represented as $\frac{\sqrt 2}{n}$ (except 1) and fit between [0,1) no problem. And that's only covering irrationals and only a small fraction of those.

I understand that there are different levels of infinity, but the count of all natural numbers and the count of rationals between [0,1) seem to both be $\aleph_0$ to me.

$\endgroup$
5
  • 5
    $\begingroup$ I don't have the time to write a full answer at the moment, but I just want to say that these are reasonable questions! Please be assured that Cantor's proof is correct and there are indeed more real numbers than naturals. You've fallen victim to a few common misunderstandings, but nothing that the talented people of this site can't help with :) $\endgroup$ Jun 4, 2021 at 1:47
  • 3
    $\begingroup$ To make a quick note: the number of rationals in $[0,1)$ is the same as the number of naturals! They are both $\aleph_0$. Cantor's proof shows that the cardinality of the entire interval $[0,1)$ is strictly larger than $\aleph_0$. $\endgroup$ Jun 4, 2021 at 1:49
  • 7
    $\begingroup$ Suppose it were possible to list all the real numbers between $0$ and $1$. Ok, you show me your list. Now I write down a number that is not on your list. That's a contradiction. So the original assumption must have been false. Sure, you could modify the list to include that particular number, but then why didn't you just show me a list that contained all of $[0,1]$ in the first place if it were possible to do so? Answer: it's not possible. $\endgroup$
    – littleO
    Jun 4, 2021 at 1:50
  • $\begingroup$ @diracdeltafunk Yep I'm sure I have fallen victim to that. But how :)? $\endgroup$
    – Paul
    Jun 4, 2021 at 5:33
  • 2
    $\begingroup$ At least two, and perhaps all four, of your numbered questions have been asked and answered before on this site. And re-explaining the diagonal argument in general has been done many times. Can you either focus on just one question and/or comment about why existing answers you've found (on this site or elsewhere) still leave you unsatisfied for this questions? That would help us get at the root of your questions or direct you to the most helpful similar question on the site. $\endgroup$
    – Mark S.
    Jun 4, 2021 at 6:32

2 Answers 2

3
$\begingroup$

I hate to post an answer to my own question. The fact is and has always been true that there are more numbers between 0 and 1 than there are integers. And my question wasn't asking that. I was really just asking what was wrong with my thought process in the numbers above. So that's the question I'll answer here: How I got my head around the concept.

  1. $\infty + 1$ is still countable in the Hilbert example and is uncountable in the Cantor example. This is abundantly clear but wasn't to me before.
  2. Same answer as #1.
  3. In my thought experiment where I mapped integers to decimals I specifically said rational numbers. I was purposely ignoring irrationals due to what I said in #4. However I missed literally all repeating fractions! $\frac{1}{3}$ for example. I only was imagining non repeating and terminating sequences.

Once I realized #3 I essentially had proven this argument to myself already. Because if I could map all terminating decimal values to a corresponding integer one-to-one then those sets are the same size. But there are an infinite number of non-terminating decimals also. $\frac{1}{{3^n}}$ is another infinite set matching all integers. I still don't like the original argument of simply adding one but I finally get it now. Thanks to the commenters for getting me to think outside the box.

$\endgroup$
1
  • 3
    $\begingroup$ 1. It is not "uncountable in the Cantor example". In the Cantor example, all you are doing is saying "Every countable list of real numbers is incomplete." There is no assertion that adding just one more number will complete the list (in fact, it cannot). So you are not concluding that "$\infty + 1$ is uncountable". It's just an assertion that you aren't done yet. $\endgroup$ Sep 29, 2021 at 16:37
1
$\begingroup$

Some interesting questions, but as was observed, some of them have been answered previously on this site.

  1. You proceed from a false premise. $\infty + 1$ is not uncountable. That part of the argument simply says that if you claim to have a complete enumerated list—and it's important that it is a (potentially infinite) enumerated list, not just a set—then I can construct a number that isn't on your list, but is indubitably real. Adding that number doesn't complete the reals; it just demonstrates your original claim turned out not to be true.

  2. Because cardinality doesn't work that way. In a sense, the Hilbert Hotel argument shows that a countably infinite set (the positive integers) can be placed in a one-to-one correspondence with a proper subset of itself (the positive integers except for $1$). But that doesn't show that the positive integers can't be placed in a one-to-one correspondence with itself; obviously, it can (using the identity mapping $x \mapsto x$). With finite sets, this isn't an issue; that's why infinite sets are typically defined as possessing a one-to-one mapping with a subset of themselves.

  3. This isn't true. What is the last digit of the integer that $1/7$ (clearly a rational number) is paired with? However, that doesn't show there isn't a one-to-one mapping of the integers with the rationals, which there is, in fact. See here: Produce an explicit bijection between rationals and naturals?

  4. Your proposed set of irrationals is incomplete. For example, $\sqrt{3}$ is not in that list, nor is $\pi$ or any transcendental number. (I'm not entirely sure I understand your question, so this may not exactly answer it. But I'm quite certain that just encoding numbers as $\sqrt{2}/n$ will not address the kinds of numbers I allude to.)

$\endgroup$
2
  • $\begingroup$ Though often presented that way (confusingly, in my opinion), there is in fact no need to assume the enumerated list is "complete". Just that it is an enumerated list of real numbers. You then show the list is in fact not complete. The assumption that it is complete is never used in the argument (except to claim a contradiction at the end, which is unnecessary). $\endgroup$ Sep 29, 2021 at 17:16
  • $\begingroup$ @ArturoMagidin: You're quite right. And I knew that, I just keep forgetting it. Thanks for the reminder. $\endgroup$
    – Brian Tung
    Sep 29, 2021 at 17:51

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.