The Diagonal Method on Finite Binary Strings

Georg Cantor developed the diagonal method to study infinite sets, but to understand the diagonal method, it is best to begin by applying the technique to finite sets. For example, we could apply the diagonal method to all permutations of a three character binary strings. This set is as follows:

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

Anyone who has studied basic computer architecture knows that there are eight ways to order a three character binary string. We can list these permutations in any order. In this case, the first three permutations are: 000, 001, 010. The digits on the diagonal are 000. If I replace the zeros with ones and ones with zeros (the bitnot function), I get the string 111. The string 111 is a permutation of a three character binary string. But it is not in the first three positions of the set!

We can shuffle this set and, in every case, the diagonal method will produce a three character binary string that is not in the first three positions of the set. For example, the first three members of an ordering might be: 100,001,111. The characters on the diagonal are 101. The bitnot function produces the string 010.

This phenomena is not restricted to three character binary strings. We can perform the diagonal method on say a six character binary strings, as follows:

0     010010
1     111000
2     010101
3     111101
4     100011
5     000111

In this experiment, the digits on the diagonal are 010111. The diagonal method produces the string 101000. This string is not in the first six strings in the list.

Applying the diagonal method to an n-character binary string produces an n-character string that is not in the first n members of the set. We have just proven that the set of permutations of an n-character binary string is wider than it is deep. We have proven that 2^n > n, where n > 1.

Liar's Paradox

Cantor's diagonal method is function that takes a full set as its input and produces a string of characters as its output. The length of the string is determined by the size of the set. As a computer scientist, I prefer to work in binary. The function takes one character from each member in the set to create a string. It then returns the bitnot of that string.

When looking at a finite set that contains nothing but the diagonal of itself, we get an interesting case of the liar's paradox. Imagine the set A = {dp(A)}. This set contains only one member—the diagonal product of itself. By definition dp(A) must return 0 or 1. It cannot return a 0, because the bitnot of 0 is 1. It cannot return a 1 because the bitnot of 1 is 0. This is the exact same form as the paradox: "This sentence is false." If the sentence were false, then it is true, which means that it is false ...

Whenever you try to include the diagonal product in the first n members of set of n-digit binary strings, your set returns a liar's paradox. For example, were I to define set B = {100, 101, dp(B)}, my set would return an anomaly. dp(B) returns a three digit binary string. The first two characters of the diagonal are 10. The third character cannot be 0 as the bitnot of 0 is 1. It cannot be 1 as the bitnot or 1 is 0.

In Boolean algebra, the not function is a form of negation. The bit not might be called a form of hypernegation. When performed on an infinite, it is a form of ultra-hyper negation. However, it should be clear that when performed on the set of Reals, the absurdity returned by the diagonal method is of the same form as the Liar's Paradox.

Let's say I defined a set A that simply included a

The Set of Halves

The diagonal method is a function that operates on the first n members of a set. It records enough information about the first members to produce a number that should be part of the main set, but is not yet recorded. This leads me to wonder if it is possible to create a similar operation for the so called "denumerable" sets.

For example, lets look at the set of all halves. The set of all halves can be listed as follows:

 1   2    3    4    5    6    7    8    9    ...
1/2  1   3/2   2   5/2   3   7/2   4   9/2   ... 

Note, there are 2n members of this set that are less than or equal to n. I would like to define a function on the first n members of this set that will return either the number 1/2 or the lowest valued member of the set not in the first n members of the set. The pseudo code for this function might be as follows:

FUNCTION halver(nArray   array of numbers)
RETURN Number
   i, n        Number;
   bArray(n)   Array of Boolean;
BEGIN
   // n is the length of the array
   rv = 1/2+  // set the initial return value to 1/2
   n = nArray.length;
   
   // Initialize the values of boolean array to false.
   For i=1 to n
      str(i) = False;
   End Loop;
   
   // Process the in coming array.
   For i = 1 to n
      If nArray(n) is an integer
         bArray(i) = True;
      Else
         // Do nothing
      End If;
      If nArray(n) = rv Then
         // Find the next lowest value not in list
         Loop
            rv ++;
         Exit When bArray(rv)
         End Loop;
         If rv = n then
            // this will never happen
            print "Wow. The set of halves is the same size as the set of integers!!!"
         End If;
      End If;
   End Loop;
   
   RETURN rv;
END;

Like the diagonal method, this function returns a member of the set of halves that is not yet listed. This new function  proves conclusively that 2n > n, where n > 1. 

It is possible to extend this function to the set of rational numbers. The rational versions of this function returns the number 1/2, or the lowest natural number not within the first n members of the set. Once again this function proves that the number rational numbers created with the first n numbers is greater than n.

To Infinity and Beyond

Now, to the heart of the matter. Georg Cantor conjectured that, when performed on a completed infinity, the diagonal method would continue to return a valid real number, while the halver function would stop returning a valid number. This supposition is not proven by the diagonal method. However, the diagonal method gives us a starting place to make the supposition.

Perhaps the best way to describe this is to say that, if you fed the halver function an infinite set, it would return a transfinite number.

Of course, it is impossible to verify this conjecture. As you check through the code for the function, you will see that the halver function blows apart when I try to initialize an infinite array. Just like a program would explode if you tried feeding it an infinite decimal.

Conclusion

When performed on a set of finite binary strings, the diagonal method simply demonstrates that 2^n > n, for n >1. The diagonal method simply shows that the set of real numbers is wider than it is deep. It is possible to create similar functions for so called denumerable sets. 

Just as the diagonal method shows that there is a real number not yet in any given list of real numbers, we can create programs that show there is a rational number not yet in any given list of rational numbers.

Perhaps one of the greatest mistakes that a teacher can make while presenting the diagonal method is to confuse this attribute of the proof on finite sets with the much more subtle distinctions that Cantor was trying to make on infinite sets.

Rate This Article

Descriptive Mathematics - - Sponsors - - Next