A Refutation of the Diagonal Method

In the essay The Galileo Paradox we learned that there is more than one way to derive the set of evens from the set of integers. We could multiple each integer by two, or we could remove the odds. I called these methods the direct and natural approaches. For finite sets, the direct approach (multiplying by two) creates a new set that is the same size as our original set. The largest number in the new set is is twice the size of the largest integer. The natural approach produces a set that has half as many evens as integers. No member of the new set is larger than the largest integer.

If we are simply given the set of even numbers, we do not know its method of creation. Hence, there is a paradox. A set will appear to be the same size as a proper subset of itself.

I believe that infinity creates for mathematicians a problem akin to the wave/particle duality of physics. The method used to measure a set affects the result. If you perform a thought experiment that assumes the direct approach in creating infinite sets (such as a 1-1 function), it will appear that there are as many evens as there are integers. If you perform an experiment assuming the natural approach, the sets will appear to be different sizes. When given a the set of evens, we do not know the method of creation...hence the paradox.

Unfortunately Galileo's dialog between Salviati and Simplicio hinted that the infinity implied a higher level of thinking. Many mathematicians seemed to take that implication to mean the direct mapping was a higher level of thinking than the natural mapping.

The Hungarian mathematician Bernard Bolzano (1781-1848) suggested that the Galileo paradox was more than a paradox. He suggested that the paradox was the very nature of space and time. Bolzano even defined an infinite set as a set that is the same size as a proper subset of itself. The problem with this definition is that it injects a paradox into the foundations of mathematics.

Georg Cantor and the Diagonal Method

Georg Cantor's primary concern was the mysterious difference between discrete and continuous mathematics. The rational numbers are descrete. By definition, rational numbers are expressed as a ratio between two integers. Integers are by definition finite strings. This means that rational numbers are expressed by finite strings of numbers.

Mathematicians speculate that every number on a line can be expressed by a unique infinite decimal. Such speculation is a bit problematic as it is impossible to write an infinite decimal. However, the real numbers appear to be continuous. Any number between real number a and b is by definition real.

Cantor was looking for a method to describe the difference between discrete and continuous sets. The big difference between the rationals and the reals is that he rationals can be described with finite strings. The set of reals seem to require infinite decimals. This distinction in more pronounced when looking at the power set of the integers.

The big difference between the reals and rationals is that rationals can easily be represented with a finite string. The reals seem to require infinite decimals.

In exploring different sets of numbers. Cantor realized that the set of real numbers wasn't just a little bit larger than the set of rationals, but that the set of real numbers was at an entirely different level of infinity than the rationals.

Unfortunately, Cantor has a boss who was somewhat of a dialectician himself. Kronecker was working on foundational methods for mathematics that would completely remove reference to infinity from mathematics. This put Cantor in a horrible position of being completely incapable of refining his ideas. Cantor was desparate for anything that he could use to bring his work to the public's attention.

When Cantor discovered the diagonal method, he made a understandable misinterpratation of the meaning of the method. Even worse, he turned to the oppositional logics that were popular in his age to form the foundations of mathematics.

Let's review this situation: The common consensus at the time was that all infinite sets were the same size. Cantor's work suggested that the reals were at a higher level of infinity than the rationals. Oppositional logic was the style of the day. Cantor was locked in a power struggle with a boss fiercely opposed to his work. In this environment Cantor decided that there were two levels of infinity. Sets like the integers, rational and algebraic numbers (that could be expressed with finite strings) were at the lower level of infinity. Sets like the power set of the integers and real numbers (that required an infinity of infinite strings) were at a higher level of infinity. This is essentially the basis for the denumerable/nondenumerable dichotomy.

Cantor found what he was looking for in the diagonal method. He found a dichotomy. The question today is if that dichotomy was an illusion of infinity or is truly the foundational conflict from which all mathematics springs. So, I would like to take a moment to comtemplate the diagonal to see what we can see.

Contemplating the Diagonal

The diagonal method is an ingenious trick for examining sets. As a computer programmer, I prefer to present the diagonal method in binary, as opposed to base ten. My first assumption is that all real numbers can be expressed as an infinite binary decimal. An infinite binary decimal is a string 0s and 1s. Binary decimals work like base 10 decimals, except there are fewer characters to worry about. Base ten has the characters {0,1,2,3,4,5,6,7,8,9}.

The diagonal method is a reducio ad absurdum argument. I start with the assumption that I have a complete list of infinite binary decimals between 0 and 1. This listing might appear as follows:

   0.010011011101...
   0.111001101100...
   0.010101010101...
   0.110011001101...
   0.111110111110...
   ...

I can create a new from the digits on the diagonal. In this case the digits are: 01001... I can create a new string by performing a bitnot of the diagonal. The bit not changes all of the 1s to 0s and all of the 0s to 1. For simplicity, I will call the bitnot of the diagonal the diagonal product, and represent it with the function dp().

The diagonal product produces a number between 0 and 1 that is not in my listing. The proves that the set of real numbers between 0 and 1 is larger than the set of integers.

The Completed Infinity

The first thing to point out is that the diagonal method assumes a completed infinity. If you hold that infinity is inherently incomplete, then the method simply produces a number not yet in a given list. The best way around this is to imagine the diagonal product as a function that operates on an entire set. So if I have set A which consists of all the numbers between 0 and 1. dp(A) returns a number between 0 and 1 that cannot be in A.

The Liar's Paradox

The second thing to notices is that the diagonal method is a clever rendition of the Russell Paradox. The simplest form of the Russell Paradox is the liar's paradox: This sentence is false. The liar's paradox contains a self reference and a negation that throws the reader into an infinite loop. The liar's paradox has been known since antiquity.

Russell is famous for applying the paradox to set theory. His version starts with the set of all sets. The set of all sets is a set. Therefore it includes itself. There are some sets which include themselves and others that do not. Looking at the set of all sets that do include itself. Well, if it doesn't include itself, then it must include itself, which means it shouldn't include itself. Arrrrgggggh!!!!!!

For those unfamiliar with boolean algebra, the bitnot is a form of negation. You might call it a hyper-negation. Imagine an array of true false statements. The bitnot turns all of the true statements to false and all of the false statements to true.

The diagonal product is a function that operates on an entire set, and returns a value that should be a member of the set. This is a form of self reference. The diagonal product has the two components of the liar's paradox. It has a self reference and a negation. The diagonal method is just another form of the Russell paradox.

In some ways, the diagonal product should be called a paradox. Let R1 be the set of integers between 0 and 1. dp(R1) returns a real number between 0 and 1, yet the number cannot exist in R1

The relation between the diagonal product and the liar's paradox is clear if we look at the set that contains only one element—the diagonal product of itself. I will call this set X. X = {dp(X)}. As dp(X) has only one element, it should return either a 0 or a 1. As dp(1) = 0, the value can't be 0. As dp(0) = 1, the value cannot be 1. The diagonal method is just another form of the liar's paradox.

The Diagonal Method on Finite Binary Strings

I can see no reason to restrict the use of the diagonal method to infinite strings. It is possible to create 2^n strings from n binary characters. Here is a list of all possible three digit binary strings:

0     000
1     001
2     010
3     011
4     100
5     101
6     110
7     111

As I am listing the set in numerical order, the digits on the diagonal are 000. dp(000) = 111. I could take any three three digit strings. The diagonal product will return a three character string that is different from the three strings of the input.

When performed on finite binary strings, the diagonal method simply proves that n^2 > n for n > 1.

More on the diagonal method on finite binary strings.

The Set of Namable Numbers

I believe that the set of namable numbers provides the most insight into the nature of infinite sets and the diagonal method. This set consists of all numbers that can be named with a string of ASCII characters. The set is unbound. We can keep naming numbers until the cows come home, and still not run out of numbers we can describe with ASCII characters.

ASCII is a bit inefficient, but it is a standard. The first 31 ASCII characters are special characters; So, I will restrict myself to characters 32 through 126. My character set conversion table is as follows:

   032 : Space   033 : !       034 : "       035 : #       036 : $     
037 : % 038 : & 039 : ' 040 : ( 041 : )
042 : * 043 : + 044 : , 045 : - 046 : .
047 : / 048 : 0 049 : 1 050 : 2 051 : 3
052 : 4 053 : 5 054 : 6 055 : 7 056 : 8
057 : 9 058 : : 059 : ; 060 : < 061 : =
062 : > 063 : ? 064 : @ 065 : A 066 : B
067 : C 068 : D 069 : E 070 : F 071 : G
072 : H 073 : I 074 : J 075 : K 076 : L
077 : M 078 : N 079 : O 080 : P 081 : Q
082 : R 083 : S 084 : T 085 : U 086 : V
087 : W 088 : X 089 : Y 090 : Z 091 : [
092 : \ 093 : ] 094 : ^ 095 : _ 096 : `
097 : a 098 : b 099 : c 100 : d 101 : e
102 : f 103 : g 104 : h 105 : i 106 : j
107 : k 108 : l 109 : m 110 : n 111 : o
112 : p 113 : q 114 : r 115 : s 116 : t
117 : u 118 : v 119 : w 120 : x 121 : y
122 : z 123 : { 124 : | 125 : }

To make my job simple, I will restrict my set to the namable numbers to those between 0 and 1. I will call this set NN1. I can add any number that I can name. I can name a number with the decimals, or I could name the numbers with a funtion. For example 1/sqrt(2) is the reciprocal of the square root of two.

The table below has three columns. The first column shows the name of the number, the second column shows the ASCII code in decimal of the number, the final column shows the first digits of the binary expansion of the number.

Name ASCII Expansion Binary Expansion
gamma 103 097 109 109 097 0.100100111100010...
1/pi 049 047 112 105 0.010100010111110...
half 104 097 108 102 0.100000000000000...
0.9 048 046 057 0.111001100110011...
1/sqrt(2) 049 047 115 113 114 116 040 050 041 0.101101010000010...
a third 097 032 116 104 105 114 100 0.010101010101010...
0.25 0.001000000000000...
ln(2) 108 110 040 050 041 0.101100010111001...
... ... ...

The set of namable numbers is potentially infinite. I call this set NN. I denote the diagonal product of the namable numbers with the name dp(NN). In the above case, the digits on the diagonal are 11000101, and the diagonal product is 00111010.... The function "dp(NN)" has the ASCII representation of 100 112 040 078 078 041. Just like the diagonal product of the reals, The function returns a namable number that cannot be in the list.

Look closely at the sample. Every namable number has an ASCII representation. This representation is a decimal. Hence the namable numbers is a proper subset of the integers. This means that the set of namable numbers is a subset of the reals that fails the diagonal method.

Conclusions from the Method

One of the problems with paradoxes is that you can draw any number of conclusions from a paradox. Aristotle was wise when he opted to draw a distinction between potential and absolute infinity. The easiest conclusion to draw is that infinite sets are never complete. Cantor's conclusion was that the diagonal creates a dichotomy between the rationals and reals—the denumerable/nondenumerable. The reason for this conclusion is quite simple. The reals and power set of the integers are expressed with infinite strings. Integers and rational numbers are expressed with finite strings.

Of course, if this is really the foundation of transfinite theory, why not just come out and say that infinite strings are different from finite strings? Why cloud the issue with diagonal method voodoo?

My conclusion from the diagonal method is a bit different from Cantor's. My conclusion is that Galileo's Paradox is a true paradox. A tool like the diagonal method that assumes a natural mapping between the sets will indicate sets are different sizes, and one that assumes a direct mapping produces results that are the same size.

Let's review the method again. We began the demonstration of the diagonal method with the assumption that all infinite sets were the same size. The diagonal method produced a number not in a given listing of real numbers. This result doesn't simply imply that the real numbers are a different size than the integers. It completely shatters the assumption that all infinite sets are the same size.

The set of integers is different from the set of rationals, which is different from the set of reals. Infinity is richer than the denumerable/nondenumerable dichotomy. The dichtomy is an illusion.

Refutation ~ Critique of the Diagonal Method ~ Sponsors