A Review of the Diagonal Method

Well, if you skipped the parody, you didn't miss much.

The standard introduction to the diagonal method consists of three steps. They are: 

Step One: Define One-to-One Correspondence

In the first step, the teacher introduces the term "one-to-one correspondence" and shows that, if you compared a list of natural numbers against a list of squares, you will not run out of squares before running out of natural numbers. The teacher concludes that the two sets must be the same size. Here is the mapping:

      1    2    3    4    5 ...  n   ...
      1    4    9   16   25 ...  n^2 ...

Step Two: Cross Section Method

In the second step, the teacher shows that, by taking cross sections of a table, it is possible to translate a two dimensional table into a one dimensional list. Repeating the cross section proof, it is possible to map all elementals of an n-dimensional table onto a one dimensional list. Since rational numbers can be expressed with a numerator and denominator, the teacher concludes that the rational numbers are denumerable.

Step Three: Diagonal Method

In the final step, the teacher shows that you can use the diagonal method to produce a real number not yet in a given listing.

A Few Tiny, Little, Gaping Holes

The proof appears to be straight forward and clean. Basically, step one and two state that if you are able to put a set in a list, that it is "denumerable." Step states shows that if you perform an operation that finds a number not yet in a set then the set is not denumerable.

As we go back and think about the process, however, things become hazy. It is very easy to start a list of the real numbers. This is the biggest hang up for most students of transfinite theory. In his work, Georg Cantor is not just talking about starting a list of rational numbers. He is talking about creating a complete and full listing of the rational numbers! He is talking about completing an infinite list.

Think about step two. When you started putting the rational numbers in a table, can you complete that list? It is very easy to make a program that generates a rational number that is not yet in any given list of rational numbers. What makes the diagonal method specialer than the functions which generate a rational number not yet in a list of rational numbers? Let's say you had a function that took one half the smallest number in your list of rationals. That number is a rational number and is not yet in your list.

When you simply give students step 1, step 2 and step 3. They have insufficient information to understand transfinite theory. There is obviously something weird going on with this proof. Think about it! Why can't the number generated by the diagonal process simply be the next number in the list?

When we look at the The Diagonal Method on Finite Binary Strings, the diagonal method appears to tell us nothing more than the obvious truth that 2^n > n, where n > 0. It does not appear to be opening the doors to paradise as the transfinite theorists contend.

The diagonal method appears to run into other troubles as well. Lets take the simple set of all Namable Numbers. By a namable number, I mean a number that can be described by a finite string of characters. Such a set, I understand is denumberable. Think for a moment. The reference: "The Diagonal Method of the Namable Numbers" is a finite binary string. It should be a member of the set of namable numbers; however, like the diagonal method on the real numbers, it produces a number which is not in any given list of Namable Numbers.

Transfinite theory is pocked with such paradoxes, yet transfinite theorist seem intent on holding open our gullets, and forcing it down our throats as the basis of arithmetic.

The standard presentation of the diagonal method does not give students enough information to understand the theory. Anyone who really thinks about the words the teacher gives in the lecture is likely to stray the course, and fail. The standard presentation is simply not acceptable. Huffing one's snout in the air and belittling students who "don't get it" is not a valid option. Such teachers are no better than the Brother Mathematicus mocked in the transfinite parody, and such teachers actual do a great harm to the entire subject of mathematics.

I am not saying that transfinite theory is "wrong." I am saying, that it is up to proponents of the theory to come up with a better introduction than the diagonal method. Simply telling people to take their words on faith is not sufficient. It may well be as my first professor claimed. There may well be a secret supernatural ability existing in the brains of a tiny percent of people that let them see completed infinities. I don't have super natural abilities, but you might. However, founding all of mathematics on the existence of some supernatural power kicks sand in the face of the entire western scientific tradition.

Now, I confess, I am not the one to be able to come up with a better foundation for the theory. I have pounded my tiny finite brain against this theory for several years. I haven't a clue what the transfinite theorists are trying to say. But I am willing to tell you what I have learned in the off chance that it might help clarify. Although I cannot perceive completed infinities, I can conceive of a powerful idea I've dubbed an arbitrarily large set. We can learn a lot about infinity by studying such sets.

Your choice from here is to read about the diagonal method on finite binary striings, namable numbers or move into the discussion of arbitrarily large sets.

Descriptive Mathematics, Salt Lake City, Index, Sponsors
©2002 Kevin Delaney