Counting Real Numbers?


There's a question mark in the title of this section for a reason. There are so many real numbers, we can't put them all into a list. In fact, we can't even put the real numbers between 0 and 1 into a list. Thought 1 was a small number? Think again. It's a giant among fractions. Sometimes it even tromps through their village, kicking them aside as if they were ants.

In other words, we can't make a complete sequence out of all the real numbers. No matter how hard we try, we'll always be skipping a few terms in our sequence. But talk is cheap, so let's prove it.

Overview of the proof:

Once again, we're going to prove this by contradiction. We'll assume that you have a list of all the real numbers between 0 and 1 (even though we know you're bluffing). Then we'll show that this list can't contain all the real numbers between 0 and 1 after all. This means our assumption was false, so we can't list all the real numbers between 0 and 1. And then we'll take your so-called list and turn it into the authorities so that you can be exposed for the fraud that you are.

Sorry. Sometimes we get carried away with hypotheticals.

Guts of the proof:

Pretend that you could make a list of all the real numbers between 0 and 1. All real numbers can be represented by infinite decimals (a rational number that ends can be thought of as an infinite decimal by sticking infinitely many zeros on the end). Let's write each digit of each infinite decimal like this:

0.d11 d12 d13 ...
0.d21 d22 d23 ...
0.d31 d32 d33 ...

It looks kinda bizarre, but here's how it works: the first digit after the decimal point is written as d11 in the first number. So if the first term in our sequence were 0.164, we'd have d11 = 1, and d12 = 6, and d13 = 4.

This is supposed to be a list of all the real numbers. However, it can't be, because we can find at least one number that didn't make it onto the list. We'll construct, one digit at a time, a real number between 0 and 1 that isn't in this list. The fun bus is leaving the station. Buckle up.

For the first digit of our brand-new imagined decimal, choose any digit other than d11. For the second digit, choose any digit other than d22. For the third digit, choose any digit other than d33, and so on.

You can keep on keepin' on forever! We won't make you, but you can now imagine how it would be very possible to do so. The number that results is a decimal, so it's certainly a real number. It doesn't have any digits before the decimal place, so it's between 0 and 1.

However, it isn't on the list. This number can't be the same as the first number on the list, since it differs from the first number in the first decimal place. This number can't be the same as the second number in the list, since it differs from the second number in the second decimal place. This number can't be on the list at all, since it differs from every number in the list in at least one place!

This argument, known as "Cantor's Diagonal Argument," (if you're guessing this was named after some guy named Cantor, you'd be right) shows that there are too many real numbers to count, even if we only look at real numbers between 0 and 1. This should be a huge relief to abacus makers everywhere.