philcrissman.com

It’s safe to say that I became interested in computers, especially computer programming, because of math.

I don’t mean algebra or calculus, but the sort of mathematics that deals with logic, recursion, and paradox (or seeming paradox). My introduction to this sort of math was in the book Godel, Escher, Bach by Douglas Hofstadter, to which I recently paid a small homage in a post having to do with new years resolutions. Hofstadter’s book is full of interesting ideas, about math, art, music, and artificial intelligence — and somehow or another, it all also ties in to computers. At some point I decided that if this was what computer science was all about, then that was bound to be pretty darn interesting.

Back to math. An interesting thing to think about is simply the idea of counting.

Counting probably seems pretty boring; it’s possibly the most basic math-related concept one could think of. However, there are a lot of interesting ideas related to counting.

For example, you are probably familiar with the idea of sets. You have the set of natural numbers (1, 2, 3, …), the set of integers (…, -2, -1, 0, 1, 2, …), and so forth. Any one set could potentially be set in one-to-one correspondence with any other set. For example, the prime numbers could be set to correspond to the natural numbers…

You can see that if you continue on this way, you would essentially be counting prime numbers.

You could also, if you wanted, count the set of all odd (not evenly divisible by 2) natural numbers:

Here we come up to an interesting situation; in any given span of natural numbers, only half (give or take one) will belong to the set of odd numbers. Without giving it much thought, then, you’d be inclined to think that the set of all natural numbers would be exactly twice the size of the set of all odd numbers… but it isn’t. You can see that if you take the above table, and imagine it extending for an infinity, each odd number will correspond to a natural number… neither set can ever be larger than the other.

If I recall correctly, Cantor called any infinite set which could be mapped to the natural numbers a countable infinity. This might sound odd, because we’re used to thinking that infinity is infinity is infinity — that there’s only one infinity, and it’s infinite (duh), so why make a distinction that there are “countable” infinities? Why, that would imply that there are also uncountable infinities, and that these are somehow different.

It turns out that this counter-intuitive notion about infinities is correct, and it was Cantor, again, who developed this. (Again… IIRC; I’m an amatuer mathematician).

One interesting thing Cantor showed was that rational numbers are countable. In other words, you could directly map the set of all rational numbers to the set of natural numbers. The method Cantor devised for showing this could be done was quite clever, and looked like the following table:

If you follow the pattern that is presented, you can easily prove to yourself that on an infinite canvas, every possible rational number would eventually be listed on this table. To count them, Cantor proposed that we start in the first corner and “zig-zag” diagonally across the table… like so:

Again, if you continue on like this you will eventually count every rational number in the table. Of course, there are an infinite number of them, but we have infinite natural numbers to map to them, so we conclude, as Cantor did, that rational numbers are a countable infinity.

What about Real numbers? That’s where it gets tricky.

The Real numbers include all the rational numbers plus the irrational ones… numbers like pi and √2, and any other infinite non-repeating decimal numbers (IIRC, if an infinite decimal can be found to repeat, it is rational; proof of this is left to the reader).

Cantor’s argument was that the Real numbers could not be mapped one-to-one to the natural numbers, and his proof was called the diagonizational argument. He proposed that even if we did come up with a scheme to list all Real numbers which we felt would eventually list them all, there would always be a number left out. Say, for example, a part of our list of Real numbers looks like this:

0.23678484…
0.48235767…
0.37846328…
0.64944147…
0.16137573…

(I know there’s no rhyme or reason to this particular list, but for the sake of the argument it doesn’t matter.)

Given any list of Real numbers, such as the above, we could create a new number x whose first digit differed from the first digit of the first number, second digit differed from the second digit of the second number, third digit differed from the third digit of the third number, and so on. No matter how long our list, creating a new number in this way will result in a number which does not exist anywhere on our current list.

That’s not even taking into account that there is no way, that I know of, to begin to list Real numbers in such a way that we could be convinced that we’d eventually list all of them; Cantor’s argument was that even if we proposed a method, his diagonalization method would come up with a number which was not anywhere in the list. Therefore the Real numbers were an uncountable infinity.

Or, to paraphrase Orwell, All infinities are created infinite; but some are more infinite than others.