For we know in part

and we prophesy in part

1st Corinthians 13.

There are major lacunae in reasoning in seemingly safe sciences. Here is one from the field of Mathematics.

A Flaw in Cantor's Diagonalverfahren

The famous diagonal "proof" of Danish mathematician Georg Cantor (1845-1918) appears to be flawed. (As versions of his diagonal proof were later used in important work by both Gödel & Turing, some rethinking of portions of their work may be in order.)

The diagonal "proof" opens with a window into a representation of the upper-left hand corner of an array that is regarded as infinite to the right and infinite downwards. There is a single digit in each cell. Each horizontal row representx one series.

where the p's are single digits (0 to b-1 in base b, 0 to 9 in base ten, or 0 and 1 in base 2), and no series is represented twice.

Cantor claimed to be able to demonstrate that he could produce a series that isn't in the infinite array, which would show that the so-called complete array wasn't complete.. It is the series, Cantor claimed, constructed by writing not(p11), not(p22), not(p33), ... which in words could be called a "negation of the diagonal". We need proceed no further. Cantor's claim is false. Let us see how.

In Euclidian geometry all squares, all rectangles, all polygons with more than 3 sides have diagonals, lines connecting non-adjacent vertices. Finite arrays are different from Euclidian n-gons. Only square finite arrays have full diagonals. Rectangular finite arrays have partial diagonals. Consider the finite array of width 2, containing all possible series of length 2, to the base 2:

Cantor's diagonal is 01, and his negated diagonal is not(0), not(1); or 1= which is in the array, below his diagonal. We can summarise: Finite square arrays do not contain all possible series and finite rectangular arrays contains no full diagonal, but only partial diagonals; a negated partial diagonal constructs a series that is contained inside the array. Why should it be any different with infinite arrays?, Cantor to the contrary not withstanding.

Infinite arrays are clearly also of at least two kinds, square and rectangular. The square ones do not contain all possible series; the rectangular ones have no full diagonal, so their Cantor diagonal when negated constructs a series that is in fact contained in the array, below the point where the partial (or Cantor) diagonal terminates. Full diagonals, found only in square arrays, reach the diagonally opposite corner of the array; Cantor or partial diagonals never do as they only reach part way down the array. The array is infinite, so Cantor diagonals do reach infinitely far down the array, but not all the way to the lower right-hand "corner".

It would appear that Cantor has not proved what he claimed to have proved, that the set of all decimals is not denumerable. Here, for what they are worth, are mentioned two proofs, one from 1932, one from 1992, that the set of all decimals can be put into a correspondence with the reals in the unit interval. Whether this means both sets are denumerable or not we leave as an exercise.

1932: This proof is due to Arthur F Bentley & can be found in his book Linguistic Analysis of Mathematics, pages 199-206.

1992: Given the doubly infinite (Leftwards and Down) array LD of all non-negative whole numbers, written for simplicity as infinite strings of 0's and 1's, then using a mirror-image bijection, the new doubly infinite (Rightwards and Down) array RD contains all the real numbers in the unit interval. QED.

To make certain the mapping above is understood, the third line in each set maps the (decimal) integer 2 to the (decimal) real 0.25. It is not difficult from the above to go on to show that the set of all reals is countable, and that other portions of Cantor's work are flawed.

Conclusion

Since its appearance between 1874 & 1895 in the work of Cantor the diagonal argument, (construction, device, method, motto, principle, procedure, process, proof, trick) which was his second diagonal procedure, has been used as an apparently sound mathematical proof by many workers, notably Godel in 1931 and Church, Kleene, Post, Rosser, & Turing in 1936.

Both Godel's "integer arithmetic", which is concerned with undecidable propositions, and Turing's proof that "the halting problem is undecidable" seem to rest critically on Cantor's diagonal argument.

No proof is likely to be reliable where any of its elements are less than well-defined. It is difficult to imagine that the diagonal argument works when there is no such diagonal.

As for the theorems of Godel, Turing, Church and others which rely on the Diagonal Argument, they may well turn out to be true, but unprovable.
  

A more extended treatment of the above material has been prepared.

END

Acknowledgements

This file was located in the:

• TPH Twilight Archive

HTML validation by:

• W3C online validation service for HTML 4.0

reset in HTML 4.0 in June 2000