Incompleteness Theorem

The Incompleteness Theorem is Gödel's main contribution to 20th century thought. Gödel showed that within a logical system such as Russell and Whitehead had developed for arithmetic, propositions can be formulated that are undecidable or undemonstrable within the axioms of the system. That is, within the system, there exist certain clear-cut statements that can neither be proved or disproved. Hence one cannot, using the usual methods, be certain that the axioms of arithmetic will not lead to contradictions. It appears to destroy the hope of mathematical certitude through the use of the obvious methods. It also deconstructs an ideal of science, that we can devise a set of axioms from which all phenomena of the external world can be deduced. What happens if there are not only limits to that which is knowable, but if contradictions are unavoidable? The result is a new approach to mathematics, called inconsistent mathematics.

Gödel's first formulation of the incompleteness theorem.

"Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true,but not provable in the theory."

(Stephen Kleene 1967, Mathematical Logic. Reprinted by Dover, 2002. p. 250).")


In his book Logical Journey (1996) Hao Wang published Gödel's commentary on his discovery of the incompleteness theorems:

In the summer of 1930 I began to study the consistency problem of classical analysis. It is mysterious why Hilbert wanted to prove directly the consistency of analysis by finitary methods. I saw two distinguishable problems: to prove the consistency of number theory by finitary number theory and to prove the consistency of analysis by number theory … Since the domain of finitary number theory was not well-defined, I began by tackling the second half… I represented real numbers by predicates in number theory… and found that I had to use the concept of truth (for number theory) to verify the axioms of analysis. By an enumeration of symbols, sentences and proofs within the given system, I quickly discovered that the concept of arithmetic truth cannot be defined in arithmetic. If it were possible to define truth in the system itself, we would have something like the liar paradox, showing the system to be inconsistent… Note that this argument can be formalized to show the existence of undecidable propositions without giving any individual instances. (If there were no undecidable propositions, all (and only) true propositions would be provable within the system. But then we would have a contradiction.)… In contrast to truth, provability in a given formal system is an explicit combinatorial property of certain sentences of the system, which is formally specifiable by suitable elementary means…

Quotes and Commentary about the Incompleteness Theorem

From Rucker, Infinity and the Mind:


  1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.

  2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.

  3. Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."

  4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.

  5. If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.

  6. We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").

  7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."

With his great mathematical and logical genius, Gödel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics ...

Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth ... But, paradoxically, to understand Gödel's proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Gödel's name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.

Rucker, Infinity and the Mind

From: Hofstadter, Gödel, Escher, Bach

All consistent axiomatic formulations of number theory include undecidable propositions ...

Gödel showed that provability is a weaker notion than truth, no matter what axiom system is involved ...

How can you figure out if you are sane? ... Once you begin to question your own sanity, you get trapped in an ever-tighter vortex of self-fulfilling prophecies, though the process is by no means inevitable. Everyone knows that the insane interpret the world via their own peculiarly consistent logic; how can you tell if your own logic is "peculiar' or not, given that you have only your own logic to judge itself? I don't see any answer. I am reminded of Gödel's second theorem, which implies that the only versions of formal number theory which assert their own consistency are inconsistent.

The other metaphorical analogue to Gödel's Theorem which I find provocative suggests that ultimately, we cannot understand our own mind/brains ... Just as we cannot see our faces with our own eyes, is it not inconceivable to expect that we cannot mirror our complete mental structures in the symbols which carry them out? All the limitative theorems of mathematics and the theory of computation suggest that once the ability to represent your own structure has reached a certain critical point, that is the kiss of death: it guarantees that you can never represent yourself totally.


Related articles