Gödel’s theorems
Authors: Detlefsen Michael 
Published: September 2018

Utilizing the formalization of mathematics and logic found in Whitehead and Russell’s Principia Mathematica (1910), Hilbert and Ackermann (1928) gave precise formulations of a variety of foundational and methodological problems, among them the so-called ‘completeness problem’ for formal axiomatic theories – the problem of whether all truths or laws pertaining to their subjects are provable within them. Applied to a proposed system for first-order quantificational logic, the completeness problem is the problem of whether all logically valid formulas are provable in it.

In his doctoral dissertation (1929), Gödel gave a positive solution to the completeness problem for a system of quantificational logic based on the work of Whitehead and Russell. This is the first of the three theorems that we here refer to as ‘Gödel’s theorems’.

The other two theorems arose from Gödel’s continued investigation of the completeness problem for more comprehensive formal systems – including, especially, systems comprehensive enough to encompass all known methods of mathematical proof. Here, however, the question was not whether all logically valid formulas are provable (they are), but whether all formulas true in the intended interpretations of the systems are.

For this to be the case, the systems would have to prove either S or the denial of S for each sentence S of their languages. In his first incompleteness theorem, Gödel showed that the systems investigated were not complete in this sense. Indeed, there are even sentences of a simple arithmetic type that the systems can neither prove nor refute, provided they are consistent. So even the class of simple arithmetic truths is not formally axiomatizable.

The idea behind Gödel’s proof is basically as follows. Let a given system T satisfy the following conditions: (1) it is powerful enough to prove of each sentence in its language that if it proves it, then it proves that it proves it, and (2) it is capable of proving of a certain sentence G (Gödel’s self-referential sentence) that it is equivalent to ‘G is not provable in T’. Under these conditions, T cannot prove G, so long as T is consistent. For suppose T proved G. By (1) it would also prove ‘G is provable in T’, and by (2) it would prove ‘G is not provable in T’. Hence, T would be inconsistent.

Under slightly stronger conditions – specifically, (2) and (1′) every sentence of the form ‘X is provable in T’ that T proves is true – it can be shown that a consistent T cannot prove ‘not G’ either. For if ‘not G’ were provable in T it would follow by (2) that ‘G is provable in T’ would also be provable in T. But then by (1′) G would be provable. Hence, T would be inconsistent.

The proof of Gödel’s second incompleteness theorem essentially involves formalizing in T a proof of a formula expressing the proposition that if T is consistent, then G. The second incompleteness theorem (that is, the claim that if T is consistent it cannot prove its own consistency) then follows from this and the first part of the proof of the first incompleteness theorem.

The two incompleteness theorems have been applied to a wide variety of concerns in philosophy. The best known of these are critical applications to Hilbert’s programme and logicism in the philosophy of mathematics and to mechanism in the philosophy of mind.