Infinite Tables



The use of completed infinity can become even more problematic when comparing multiple infinite sets, a practice pioneered by Georg Cantor.  Here we analyze one of Cantor’s arguments commonly called the diagonalization argument.  

According to the diagonalization argument, if T is any infinite sequence of binary digits, then it is possible to use the entries of T to construct an element of T that is not found within T.  Cantor uses this result to prove that the set T is not countable.  His proof begins with an enumeration of elements from T; here, we use the series generated by counting in binary from zero to one, where there is an implicit decimal point on the left hand side of the entries and the left-most index varies fastest (i.e., [0, 1/2, 1/4, 3/4, 1/8, …]): 

Eq 1:

The binary complement of the nth digit from each series sn is used to create a new series (s), that differs from each element of T by at least one digit: in this example, s turns out to be the infinite-length series of all ones.  

The problem is fairly clear: the number which Cantor proves cannot be found in T, sn, is in fact the very last entry in the completed table. If this proves anything, it proves that the table is incomplete. However, Cantor’s proof requires that a completed infinite number of elements is necessary: if an incomplete table is used, it is not possible to prove that s is not a part of T. This problem can be expressed slightly more formally as follows:

  1. Cantor’s argument relies on a table, T, with a completed infinite number of rows (otherwise he could not show that the generated number was different from all of the rows).
  2. Applying the method of diagonalization to the table used above generates a number sn that is all ones.
  3. sn is the last entry in the completed table.
  4. Therefore, the process of diagonalization did not reach the end of the table.
  5. Therefore, Cantor’s argument is not effective

In other words, Cantors argument produces either a number within the table (the last entry), or it does not reach the end of the table (which is required by the construction).  In neither case does it produce a number different from all entries in that table.

For a finitist, the table size is not allowed to be infinite, which removes the problem (and prevents Cantor’s argument from working). To understand this, note that applying diagonalization to the following completed table of two digits produces a number which is in the table:

Eq 2:

A different way of understanding this argument relies on the fact that diagonalization is only suitable as an argument if the table construction proceeds downwards as fast as it proceeds to the right. This occurs only in tables that use non-position-based number systems. For example, the table which has a unit entry in only one position grows downwards as fast as it grows to the right, and cannot be used in Cantor’s “proof”:

Eq 3:

What exactly does this prove? I leave that up to mathematicians to decide. Personally, I take it to be an endorsement of finitist position in mathematical philosophy, or at least a disproof of Cantors argument. More generally, the problem is not the use of infinity, but rather the use of infinity outside of the context of a limit.  In other words, the problem is treating infinity like a number instead of a process.


Leave a Reply

Your email address will not be published. Required fields are marked *