Godel’s first incompleteness theorem

Summarised from various sources

Godel’s first incompleteness theorem is the starting point for Penrose’s approach to an explanation of the nature of mathematical understanding. In the later development of Penrose’s ideas by Stuart Hameroff mathematical understanding has been enlarged to mean consciousness, presumably on the argument that we need to consciously feel or appreciate the truth of a mathematical statement that is not provable by the immediately available axioms.

The theorem states that a theory capable of expressing arithmetic cannot be both consistent and complete. For any consistent formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable by means of the axioms of the theory.

For the purposes of discussing Penrose’s proposals relative to undertanding or consciousness the important phrase here is ‘true but not provable’.

This true but not provable statement is called the Godel sentence G. Of course this is not just one sentence; in fact there are an infinite number of Godel sentences. Each set of axioms containing the minimum required piece of number theory has a corresponding Godel sentence G saying that G cannot be proved to be true by the axioms of the theory. If G could be proved within one of these theorems, say theorem T, then it would mean that T had a theorem G, which would contradict itself, because G says that T does not have such a theorem. If G did exist in such a form it would make T inconsistent.

That’s not particularly easy, but it’s about as simple as it can be made.

It may sometimes have been suggested that there is a way round by making G and additional axiom of T as an enlarged theorem to be called T’. However, this enlarged set of axioms will have a new Godel sentence and so on and so. This appears to be an infinite regress.

The truth and provability of the Godel sentence is taken as a formalised version of the ‘Liar Paradox’. This last says: ‘This sentence is false’. The sentence is not true, because if it was true it would be false, just as if the Godel sentence could be proved by the axioms, it would show that they were not consistent. However it is also apparent that the sentence cannot be false, because it would then be true. A similar and more concrete example is the ‘Cretan Liar Paradox’ where a Cretan says that all Cretans are liars. Since the statement relies on a Cretan it contains the same nemesis of itself.

The Godel incompleteness theorem relates to an undecidable problem such as the ‘Halting Problem’ which asked if the processing of some problem would ever halt. An example might be Goldbach’s Conjecture, which says that every even number 4 or greater can be written as the sum of two prime numbers as in:- 2+2=4, 3+3=6 and 3+5=8. As here, it’s easy to test this for a small run of even numbers and for quite a long run on a super computer, but the search for an even number that is not the sum of two primes could go on indefinitely. When Godel’s incompleteness theorems were first produced, it was still hoped that a general algorithm might allow such undecidable problems to be tackled. However, Alan Turing, co-founder of the concept of computing by machines and breaker of the Nazi wartime codes, showed in 1936 that there was no programme that could solve the halting problem.

For Penrose’s approach to mathematical understanding and ultimately consciousness, the true but unprovable segment of the incompleteness theorem was taken to mean that the human mind could go beyond axioms that could be expressed as algorithms and run on a classical computer.