The wider significance of Gödel's Incompleteness Theorem

Torkel Franzén [1950-2006] devoted a lot of time and energy to playing down the wider significance of Gödel's Incompleteness Theorem.* And there is no doubt that a great many extravagant claims about its significance have been made, usually along the lines that Gödel has demonstrated some fatal limitation in what scientific research can achieve, and an equal and opposite conclusion about human spirituality and artistic creativity.

I don't want to suggest that all claims for the general (as distinct from the mathematical and logical) significance of Gödel's work are mistaken: there is genuine disagreement between very knowledgeable people on the matter. But Franzén's position is widely respected as being scrupulously rigorous and based on a thorough understanding of the logical and mathematical concepts involved.

I personally found his views refreshingly straightforward when I came across them a couple of years ago. I guess I had read one too many of those contentious claims and wanted to develop a better understanding before looking again at more general questions.

Let me say, however, that I think there is abiding interest in Gödel's results, for example, in the contrast between formal systems like first-order logic (which he proved to be complete**) and stronger systems like the one outlined in Russell and Whitehead's Principia Mathematica (which he proved to be incomplete). Franzén points out that 'the incompleteness of any sufficiently strong consistent axiomatic theory ... concerns only what may be called the arithmetical component of the theory. A formal system has such a component if it is possible to interpret some of its statements as statements about the natural numbers, in such a way that the system proves some of the basic principles of arithmetic.'

We know that the natural numbers have surprising (not to say mysterious) properties, and I am tempted to say that the gulf between the first-order predicate calculus and stronger systems which Gödel's completeness and incompleteness theorems establish underscores an informal distinction between the pedestrian logic of commonsense and everyday life (which holds no surprises, life's surprises arising from complex concatenations of events rather than from our naive analyses thereof) and mathematical thinking.

Be that as it may, Gödel's work has another, perhaps more solid, claim to significance which flows from the discovery that a class of functions (recursive) which Gödel defined in the course of elaborating his famous proof turns out to be equivalent to some apparently quite different concepts developed in subsequent years (in particular by Alonzo Church, Alan Turing and Emil Post). David Berlinski writes:

'The idea of an algorithm had been resident in the consciousness of the world's mathematicians at least since the seventeenth century; and now, in the third [sic***] decade of the twentieth century, an idea lacking precise explication was endowed with four different definitions, rather as if an attractive but odd woman were to receive four different proposals of marriage where previously she had received none. The four quite different definitions ... were provided by Gödel, Church, Turing and Post. Gödel had written of a certain class of functions; Church of a calculus of conversion; and Turing and Post had both imagined machines capable of manipulating symbols drawn from a finite alphabet. What gives this story its dramatic unity is the fact that by the end of the decade it had become clear to the small coterie of competent logicians that the definitions were, in fact, equivalent in the sense that they defined one concept by means of four verbal flourishes. Gödel's recursive functions were precisely those functions that could be realized by lambda-conversion; and the operations performed by those functions were precisely those that could be executed by a Turing machine or a Post machine. These equivalencies, logicians were able first to imagine and then to demonstrate.

... A concept indifferent to the details of its formulation, Gödel asserted, is absolute. And in commenting on the concept to an audience of logicians, he remarked that the fact that only one concept had emerged from four definitions was something of an epistemological "miracle".' ****

I don't know about a miracle, but the equivalence of the various definitions is certainly suggestive that the underlying concept has a certain robustness and depth.



* This article (pdf), written just before his untimely death, gives a concise statement of his point of view.

** A set of axioms is complete if for any statement in the axioms' language either that statement or its negation is provable from the axioms.

*** This is a strange error for a mathematician to make - we're talking of the 1930s!

**** The Advent of the Algorithm (Harcourt 2001), pp. 205-6.