So we've seen that there are as many squares as there are positive integers, and as many rational numbers as there are positive integers. That's because infinity is infinity, right? All infinite sets are infinite and therefore equal in size?

The answer, it turns out, is no. Georg Cantor, in fact, provided a simple and elegant proof that there are more real numbers even just between 0 and 1 (not counting 1) than there are integers, which is to say that there's no one-to-one mapping of real numbers and integers, though there is of rational numbers and integers.

Here's the proof. Let's assume that there is such a mapping, so that, for instance,

1 maps to 0.62584146011243...

2 maps to 0.43256984161433...

3 maps to 0.46543618463411...

4 maps to 0.68905671314112...

5 maps to 0.23348521001518...

...

Then let's construct a number based on the digits along the diagonal, with its first digit after the decimal point being 1 more than the first digit of the first number, the second digit being 1 more than the second digit of the second number, and so on (those are the underlined digits); but if some digit in the original mapping is an 8 or 9, we change it to a 0 instead of adding 1. The diagonal number for the mapping above, for instance, is 0.63508..., and the constructed number is 0.74610....

This constructed number is *not within the mapping*; it can't correspond to any integer n, because the nth digit of the constructed number is guaranteed to differ from the nth digit of the nth number in the mapping.

What's more, this is true of any mapping you can come up with. No matter how you try to map the real numbers between 0 and 1 to the positive integers, there will always be a real number between 0 and 1 that one can construct using Cantor's algorithm that will be guaranteed to be outside the mapping. Therefore, no such mapping can exist: It's not possible to map the real numbers between 0 and 1 to the positive integers. Cool, no? All infinite numbers are infinite, but some are more infinite than others.

Related Posts (on one page):