I was talking to a friend at work about this, so figured I’d pass it on:

Here’s how an infinite list of numbers cannot contain every possible number.  It was discovered by Cantor (hence the name “Cantor diagonal”).  In this illustration, the “…” will be for “on to infinity.”  For ease of writing, we’ll use fractions (represented in decimal format): thus, 1/3 = 0.3333…, etc.  Also, I’m using Curier font since the rows need to line up to see the diagonal.  Finally, note that you can’t repeat any of the previous decimals in this list (i.e. in the list, N1 can’t equal N2, etc.)If we were to list out the infinite number of decimals, we could start in the following manner:

N1 = 0.333333…
N2 = 0.123456…
N3 = 0.837741…
N4 = 0.937151…
N5 = 0.999999…

.

.

.

The N series goes on to infinity.  Therefore, this is a list of an infinite number of numbers (of which we only represent the first part above).

Now, what we need to do is create a diagonal on the digits (excluding the 0. prefix), running from upper left to lower right.  So we get (in bold is the diagonal):

N1 = 0.333333…
N2 = 0.123456…
N3 = 0.837741…
N4 = 0.937151…
N5 = 0.999999…

D1 = 0.32719…

Now we construct a NEW diagonal off the original by adding 1 digit to each digit in the original diagonal.  However, this is done modularly where 9 + 1 = 0, not 10.  Thus, the NEW Diagonal (D2) is:

D1 = 0.32719…
    +0.11111…
     ——-
D2 = 0.43820…

Now we know that the first digit in D2 does not match the first digit in N1, so:

D2 <> N1    ( <> is the computer term for “does not equal”; since I don’t have a mathematical font, it will have to do)

We also know that the SECOND digit in D2 does not match the SECOND digit in N2, so:

D2 <> N2

And the third digit in D2 does not match the third digit in N3.

Etc.

Therefore, D2 <> anything in the N series.

This gives us one number that is not in an infinitely long list of numbers.  But there are more numbers not in that list!

We created D2 by adding 1 to the digits in D1.  Instead of doing that, we could add 2, 3, 4…etc. up to 9.  To demonstrate this, let’s make D3 by adding 5 to each of the digits:

D1 = 0.32719…
    +0.55555…
     ——-
D3 = 0.87264…

Again, the first digit in D3 <> the first digit in D1, but it’s ALSO <> the first digit in D2!  This gives us now 9 numbers that are not contained in the original infinitely long list of numbers.

But there’s more!  Why is it that we limit ourselves to adding the same number to each digit?  Why couldn’t we do the following instead?

D1 = 0.32719…
    +0.34971… * (this is just a random number I typed down)
     ——-
D4 = 0.66680…

D4 <> D1, D2 or D3.  And, since these numbers are infinitely long, there are an infinite number of ways you can alter how you add to the numbers (the only stipulation being that you can’t add 0 to any particular digit–it must be at greater than or equal to 1 and less than or equal to 9).

So, this means that in an infinitely long list of numbers, you are missing an infinite number of numbers.  Of course, it’s all a function of the fact that the list is WRITTEN down.  If the list wasn’t actually created, then you would have a set of numbers containing all possible numbers; however, as soon as you list out that set, it is impossible for the list to contain all the numbers.  I’m pretty sure there’s some metaphyical reason to this :-P  I’ll let you figure it out!

Â