Anyone familiar with the Diagonal Proof? I’ve studied Philosophy, Mathematics, and Computer Science at the college level, though I never got beyond a B.A. As a result, I kind of think my reasoning would be suspicious even in my prime … which has long since passed me by. I’ve said elsewhere that my philosophy brain has gone to rot; the same is true for my mathematics brain, and my computer science brain. Anyhoo, a topic that has interested me for some time is Transfinite Set Theory. Interested me because I know of it. I’ve never studied it. So, let me preface this post with a request to take everything I say with a grain of salt; if someone whose philosophy/math/computer science brain has not gone to rot reads this and thinks it is an interesting point, please let me know.

Anyway, what is the nature of infinity? That is one of the questions that perplexes me. Back in college, one of the philosophy professors showed me (and the class) the Diagonal Proof. Basically, according to the mathematicians you can prove that the set of natural numbers is the same size as the set of even numbers, or the set of squares, and a number of mind-numbing other such sets that instinctively we think should be too small. Yes, the Set (1,2,3,4,5 …) is the SAME size as the Set (1,4,9,16, 25 …). Welcome to the wonderful world of infinity. There are other weird mathematical results revolving around the nature of infinity. Once the mathematician convinces you that the set of squares is the same size as the set of natural numbers, he/she next demonstrates that the set of decimal numbers is LARGER than the set of natural numbers. How? With proofs, of course. My first introduction to such was the Diagonal Proof (there may be others).

Here’s my math-rotting brain’s reconstruction of the Diagonal Proof. Two sets are said to be equal if you can make a bijection between the two sets—basically, a mapping of one set onto the other. For example,

1 => 1

2 => 4

3 => 9

… ….

Hence, the natural numbers are the same size as the squares. There is no number in one list, that doesn’t appear on the other list somewhere.

Now, what about the Diagonal Proof? We’ll try to form a bijection between the natural numbers and the decimal numbers using any random combination of decimal numbers.

1 => .__1__2678…

2 => .3__4__853…

3 => .74__5__21…

4 => .912__3__4….

5 => .8654__3__…

… …

Now, note the underlined digits in the decimal numbers. They go along the diagonal (hence, the name of the proof). Now, form a new number by placing the decimal point and forming each successive digit by taking in sequence the underlined digits of the listed decimal numbers but add one (or you could subtract, or whatever, as long as you use a different digit—rolling over from 9 to 0 or 0 to 9 as appropriate). So, you form the number: .25644…

Now, here’s the result: the number you form cannot possibly be on the list of decimals above. Why? Because if it were in the first place (across from 1), it would differ from the number listed there in the first digit. If it were in the second place, it would differ in the second digit, etc… So, we know that .25644… is not on the list. There is at least one decimal number that doesn’t fit on the list of natural numbers. In fact, there are an infinite number that don’t fit on the list since every digit can be altered nine ways. Hence, no bijection and the set of decimal numbers is larger than the set of natural numbers. That is my poor rotting brains reconstruction of the Diagonal Proof. Not sure I explained it well enough, but you should see the point. Now, how do we take it down?

I’m not sure this is an actual takedown, I’ll leave that to better mathematicians, especially since I’m still half convinced I’m totally wrong. Let’s convert to binary.

1 => .11001…

10 => .10101…

11 => .01010…

100 => .00100…

101 => .10001…

… …

You can construct your number again: .01110… But, here’s the kicker. This is the one and ONLY number (I think) that can be proven to not be on the list. When dealing with infinity having only one number left over, doesn’t BLOODY count! I’m not sure what this means. I may be wrong … there may be other numbers my math-rotting brain isn’t aware of. But I think it is terribly problematic to have one and only one number that doesn’t fit on your infinite list. It kind of makes me think that decimal numbers are the work of Satan. But no one listens to me about that!

Before parting, would someone please shoot me down. Someone who has a better grasp of Transfinite Set Theory than I do. If you have to go into Cardinality and Orthogonality (those the right words?) to do so, just say, “Yes, you are wrong, but the explanation why is too technical for your blog post.”