1
$\begingroup$

This question already has an answer here:

The argument to prove that there are different sizes of infinity is by saying .. no matter how many decimal numbers you write you can always come up with new one different from all others listed already.So, there is no one-one correspondence between natural numbers and decimal numbers. But, every time you come up with new one, you can add that new one to the list and correspond that to a natural number(which can go to infinity). So, again we have one-one correspondence and same cardinality and Hence same size of infinities. Please can someone help me what is wrong with my argument and what am I missing? It seems like the original argument is relying on the assumption that list of natural numbers end somewhere and we come up with a new decimal number to disprove one-one correspondence.

$\endgroup$

marked as duplicate by Matthew Towers, Community Oct 30 '16 at 11:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ The argument is by contradiction. You assume that there is a bijective correspondece between $\Bbb{N}$ and $[0,1]$ and then it is shown that there is a decimal number which is not in the correspondence. This gives a contradiction. $\endgroup$ – mfl Oct 30 '16 at 10:35
  • 1
    $\begingroup$ This search should also give you several dozens of related questions, for example math.stackexchange.com/questions/39269/… $\endgroup$ – Asaf Karagila Oct 30 '16 at 10:59
  • 2
    $\begingroup$ @AsafKaragila: I looked for duplicates too, and it doesn't seem to be easy to find one that specifically addresses the common "but then we can just add it to the list" fallacy that appears in a very pure form here. Many of them are about the diagonalisation step itself, or about other objections. $\endgroup$ – Henning Makholm Oct 30 '16 at 11:06
  • 3
    $\begingroup$ @AsafKaragila: It's in the answer, yes (especially if one knows the explanation already so one can look for it specifically), but the question is not a duplicate. $\endgroup$ – Henning Makholm Oct 30 '16 at 11:15
  • 2
    $\begingroup$ I'd like to propose retitling the question to "Why can't we just keep extending the list in the diagonal argument?", or something like that. I can't think of a title that concisely captures what the question is about, though. $\endgroup$ – Jack M Oct 30 '16 at 12:20
6
$\begingroup$

What the argument proves is that

Whenever $f$ is a function $\mathbb N\to\mathbb R$, then there is a real number which is not in the range of $f$.

This is the same as saying

There is no function $f:\mathbb N\to\mathbb R$ whose range is all of $\mathbb R$.

Your counterargument is that if you have a function $f:\mathbb N\to\mathbb R$ with range $A$, and I point out that some particular $x\in\mathbb R$ is not in $A$, then you can construct a different function $g:\mathbb N\to\mathbb R$ with range $A\cup\{x\}$. And that is true as far as it goes, but it doesn't show that there's a function that hits all of the reals.

You can keep making new functions as many times as you like, but this repeated exercise will not produce a single function that hits everything. Even if we could imagine a way to get your sequence of functions to "converge" to a single function after an infinity of steps (and there are indeed ways to do this if we're careful), that single function still wouldn't hit everything. Sure enough it would hit all of the objections so far, but that just shows that there will be real numbers that have not yet been pointed out as missing even through an infinity of adjustment steps.

$\endgroup$
4
$\begingroup$

The point is that we are dealing with an argument by contradition, or reductio ad absurdum, which is sometimes a challenging concept for students to accept. Thus, we don't prove directly that there are more real numbers than natural numbers, but rather prove it indirectly. The argument goes roughly as follows. Suppose there are as many real numbers as integers $1,2,3,\ldots$. Then we can enumerate all the real numbers accordingly, as $r_1,r_2,r_3,\ldots$. Now based on this hypothesis, the next stage in the argument is to produce a contradiction. Of course it is possible to add the new number you constructed to the list, but that's not relevant to the logical structure of the argument.

I suggest you first study a simpler proof by contradiction; for example the proof that $\sqrt{2}$ is irrational, and then return to this "diagonal" argument of Cantor.

$\endgroup$
  • 3
    $\begingroup$ The pointless bickering has been removed. As collateral damage, some comments making a mathematical point have also been deleted. Please be constructive, or be silent, people. $\endgroup$ – Daniel Fischer Oct 30 '16 at 11:42
  • 2
    $\begingroup$ It is not necessary to frame the proof as a proof by contradiction, and many posts on this site and elsewhere have led me to believe that it's pedagogically better to not frame the diagonal argument as a proof by contradiction. $\endgroup$ – Daniel Fischer Oct 30 '16 at 12:04
  • 1
    $\begingroup$ @DanielFischer, when a student is asked for a proof that the reals are not countable, it seems a bit of a non-sequitur to start with the sentence "consider a function from N to R". A proof that starts with the issue at hand, namely countability or non-countability of R, seems more direct (even though this is slightly paradoxical, since it is the opening line in a proof by contradiction). In my teaching experience, I found that students are not any more convinced by a constructive proof of the irrationality of $\sqrt{2}$ than by a proof-by-contradiction; perhaps the opposite... $\endgroup$ – Mikhail Katz Oct 30 '16 at 12:16
  • 1
    $\begingroup$ ...due to the greater complexity of the latter. $\endgroup$ – Mikhail Katz Oct 30 '16 at 12:16
  • 1
    $\begingroup$ I'm not talking about constructive proofs. Just proving $(\forall f)(P(f) \implies \lnot Q(f))$. Sure, once people have come to grips with proof by contradiction, either is fine. But I've seen so many "but we assumed $f$ is bijective, so the argument that there is an $x$ not in the range of $f$ must be nonsense!" that I think it's better to avoid that assumption, unless you know your audience is happy with proofs by contradiction. $\endgroup$ – Daniel Fischer Oct 30 '16 at 12:28
3
$\begingroup$

So we have a list of real numbers $x_1, x_2, ...$, and using the diagonal argument we find a number $x$ which is not on that list. As you say, that's not a big deal: we can build a new list that does have $x$ in it. Just take $y_1 = x$, and then $y_2 = x_1, y_3 = x_2$, and so on. But now we can repeat the diagonal argument to find a new real number which isn't on that list. So our list still isn't exhaustive.

I think you understand this, which is why you included the step in your proof where you simply say:

[this process] can go to infinity...

In other words, if we repeat this process of adding real numbers to our list an infinite number of times, we should get a list which contains all real numbers. Here's the problem: that doesn't mean anything. What exactly do you mean, "repeat an infinite number of times"? Can you give me an actual definition for the list that you end up with after that infinite process? You'll find that no matter what definition you come up with to make precise your intuitive idea of "adding infinitely many numbers to the list", you won't be able to prove that it contains all real numbers.

I may as well reason like this: let's calculate the area of a disk. Well, if I take a single point in the disk, it has area zero. Adding another point, the union of those two points still has area zero. Taking this process to infinity, I'll have all the points in the disk, and since the area never changed at any step, the area will still be zero. So disks have zero area.

$\endgroup$
  • $\begingroup$ While I see what you're trying to say, I think this answer could be improved. The way it's written right now is (assuming CH) leading to an actual exhaustive list of all reals by a formal induction on this very process and does - on the surface - make it seem like the set of reals could be countable. Since the induction will actually take $2^{\aleph_{0}}$ many steps, this - obviously - won't happen - which again raises a slightly alternated version of OP's question. $\endgroup$ – Stefan Mesken Oct 30 '16 at 23:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.