Doubts about Gödel’s theorem

Wayne asked:

Typically all expositions of the 1st Gödel incompleteness theorem start with an instance of the diagonal lemma with the Gödel sentence on the left side of a biconditional and an abbreviated version of a horribly complex sentence one the right side.

The expositions continue with an argument by constructive dilemma. If the right hand side, which written out in basic syntax not abbreviated, is inconsistent with the Peano Axioms, you can never get the Gödel sentence from the instance of the diagonal lemma.

I am incapable of even imagining the full unabbreviated version of the right side of the instance of the diagonal lemma. So why should I assume it’s not inconsistent with PA? So why should I accept standard expositions of the 1st Gödel incompleteness theorem?

Answer by Geoffrey Klempner

First, I will state that I am not a mathematician and I could not reproduce an accurate version of the proof of Gödel’s First Incompleteness Theorem even if my life depended on it. However, your question isn’t really about that specific proof.

Decades ago for my BA Symbolic Logic paper, I studied an exposition of Gödel’s theorem by Nagel and Newman. I note that a newer version has appeared, edited by Douglas Hofstadter. That endorsement alone would be sufficient to convince me that the exposition is a good one.

I recall the basic point Nagel and Newman made, that the critical formula is not like the semantic paradoxes, such as ‘This sentence is false.’ What Gödel discovered was a way of defining statements about arithmetical propositions in terms of actual arithmetic functions. Using this method he was able to produce a formula that was true but unprovable within the system, as defined by the set of axioms for arithmetic devised by the mathematician Peano.

The actual proof is laborious, because of the necessity to ensure that every single mathematical formula or expression has a unique ‘Gödel number’. Plenty of room for error, don’t you think?

My answer to your question depends on whether you are a philosophy student or a maths student. If the latter, then there really is no excuse for you not to go back to Gödel’s original paper and work through it, line by line. You will burn a lot of midnight oil and learn quite a bit of maths too.

Diagonal proofs have a tendency to induce incredulity on a first encounter. So what if just one, one single formula falls outside the bag of theorems we can prove from Peano’s axioms? You get a similar reaction with Cantor’s proof of the existence of transfinite cardinals. The answer is, if we can devise one recalcitrant formula, we can make any number of them, because we now have a method for doing so.

Wittgenstein in his Remarks of the Foundations of Mathematics (1956) pondered the problems that arise with the unsurveyability of mathematical proofs. How can we be sure that we haven’t made a mistake somewhere? So what if some group of mathematicians agree that no errors are to be found? Couldn’t they all be wrong? There’s really no answer to that. Cantor faced a wall of hostile incredulity when he first published his theorem. Even professors of mathematics can turn out to be wrong.

I remember reading in the 80s the sensational announcement that with the aid of a computer a proof had been discovered of the Four Colour Theorem. The ‘proof’ runs to thousands of pages, and states that any possible map only requires four colours to define every boundary within the map. As Wikipedia states ‘It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. Since then the proof has gained wide acceptance, although some doubters remain.’

So, the problem you have raised is a real one. But on purely empirical grounds I doubt very much whether Gödel’s Theorem will turn out to have been unsound.