I don't understand the concept of different sizes of infinity.

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.