# cantor's diagonalization argument (multiple sizes of infinities)

Yes, many people have asked the same question, and I have tried by best to get my head around it, but I still can't understand.

Every time I look at the proofs, they seem like a sleight of hand to me..

Kindly point out the faults in my arguments:

Argument - 1

To map every Real Number between 0 and 1, to a unique Natural Number, simply remove all trailing zeros, and then remove the decimal point!
so,
0.1                        maps to                1
0.254                    maps to             254
0.2540000           maps to             254               (because we are removing the trailing zeros)
0.31415926...       maps to             31415926...   (if a real number can have infinite precision, then most probably a natural number can be infinitely large? Am I wrong?)

Argument - 2

Every pair of Natural Numbers can be mapped to a unique Natural Number. (for eg, Cantor's Pairing Function).
Every Rational Number 'r' can be mapped to a pair of Natural Numbers (p,q) such that
r = p/q
Since for every rational number 'r', we have an infinite number of such pairs
{(p,q),(2p,2q),(3p,3q)...}
the cardinality of Natural Numbers must be greater than the cardinality of Rational Numbers.
So, Irrational Number can be mapped to Natural Numbers.
So, Real Numbers can be mapped to Natural Numbers.

-
Well, if you want to define infinite numbers of the form $31415...$, then you are going to get into some problems - these are not what we call "natural numbers." Natural numbers are by their nature finite. – Thomas Andrews Aug 5 '13 at 18:16
In particular, if you add these "infinite" numbers to the natural numbers, then you break mathematical induction - it no longer works for this bigger set of numbers. – Thomas Andrews Aug 5 '13 at 18:17
In the second argument, the second line should say that the cardinality of the set of natural numbers is greater than or equal to the cardinality of the set of rationals. – André Nicolas Aug 5 '13 at 18:17
@Thomas Andrews. Thank you. That makes a lot of sense. – Pragy Agarwal Aug 5 '13 at 18:31
Incidentally, don't beat yourself up for being confused by these arguments. They play with our childhood intuitions of "infinity" and blow them up, and quite a few people have trouble with this at first. It just seems wrong. It takes some adjusting. It might help to initially think of this in terms of "complexity" instead of "size," because we have a lot of expectations about infinite sizes. – Thomas Andrews Aug 5 '13 at 18:41

The problem with argument 1 is that no, natural numbers cannot be infinitely long, and so your mapping has no natural number to which $\frac{\pi}{10}$ maps.

The (Well, one, at least) problem with argument 2 is that you assume that there being an infinite number of pairs of naturals that represent each rational means that there are more natural numbers than rationals.

You have established that there is an injection from $\mathbb{N}^2 \to \mathbb{Q}$, and so the cardinality of the rationals is at least the cardinality of $\mathbb{N}^2$, which is the same as the cardinality of $\mathbb{N}$.

However, there are also injections from $\mathbb{Q}$ to $\mathbb{N}^2$ (For example, consider the function that takes the fraction $\frac{p}{q}$ to $(p,q)$, where $p$ and $q$ are relatively prime.), and so rather than $|\mathbb{N}|$ being greater than $|\mathbb{Q}|$, we can see that they are, in fact, equal.

-
Never mind about $\frac\pi{10}$; there is no natural number that maps to $\frac13$! – MJD Aug 5 '13 at 18:45
True, but $\frac{\pi}{10}$ was the example used in argument 1, and so it seemed more applicable. – qaphla Aug 5 '13 at 19:02
These people who are unhappy about Cantor's theorems always want to confuse themselves with $\pi$ and $e$, when what they need to do is to get a better grasp on $\frac12$ and $\frac13$. – MJD Aug 5 '13 at 20:20

Your first Argument is invalid because there exists no such Number $n\in \mathbb{N}$ with (f. ex.) $$\pi = 10^k\cdot n$$ which is essentially what you require.

Your second Argument has the same error. There only exists a bijection from $$\mathbb{N} \to \mathbb{Q}$$ but none from $\mathbb{N} \to \mathbb{R} \setminus \mathbb{Q}$ nor from $\mathbb{N} \to \mathbb{R}$

-

There is one other point to consider. It is quite common among those who do not understand diagonalization that they do what you did: construct a map they believe works. The answers so far do a good job of showing what is wrong with your attempts. But you need to understand that, despite you not yet understanding diagonalization, it is correct nonetheless. Any mathematician knows immediately that attempts like yours have to be wrong because diagonalization is correct.

So what would probably be more useful in your studies is to figure out exactly what parts of Cantor don't make sense to you, and then learn why they are correct. Who knows--not all proofs are perfect, and mathematicians do find errors in proofs. Diagonalization is very well studied, so you aren't likely to find an error. But the point is that the procedure that might convince a mathematician is to show where a seemingly correct proof is wrong, not to exhibit an example that a correct proof says does not exist.

-
Thanks a lot for your suggestion. I agree that the chances of finding a flaw in Cantor's Argument is quite low. That is exactly why I requested the community to find an error in my argument. – Pragy Agarwal Aug 5 '13 at 18:42
Sure, I understand. What I wanted to convey is that saying you don't understand some step in a correct proof is a very "mathematical" thing to do: all mathematicians find themselves in this situation at some point. But asking what is wrong with a "counterexample" to a correct proof risks you seeming like a "crank", someone who is unwilling to grapple with how proofs work. Now to you credit, your question was very reasonable, particularly your responses for help, which is great! But Cantor is notorious for attracting cranks, so you should just be aware of this. – trb456 Aug 5 '13 at 18:50