# 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}$

-