Proof sketch of Gödel's incompleteness theorems

In this post, I will follow the outline of the proof given in Section VII of Nagel and Newman's book. Recall that:

• a formal system F is consistent if there is no well-formed formula (wff) w such that F proves both w and ¬ w, and
• a formal system is (semantically) complete if it can prove all of the true wff's that it can express.

Now, Gödel's first incompleteness theorem can be paraphrased as:

Any consistent formal system that is expressive enough to model arithmetic is both incomplete and "incompletable."

and Gödel's second incompleteness theorem can be paraphrased as:

Any consistent formal system that is expressive enough to model arithmetic cannot prove its own consistency.

According to Nagel and Newman, a proof of the first theorem can be sketched in 4 steps:

• Step 1: Build a wff (call it G) in the formal system F such that the meta-mathematical interpretation of G is: "G is not provable in F."
• Step 2: Show that: "G is provable in F" if and only if "¬ G is provable in F." In other words, either both G and ¬ G are provable in F or neither one of them is. Therefore, if F is consistent, then neither G nor ¬ G is provable in F.
• Step 3: Show (using meta-mathematical reasoning) that G is true. Therefore, G is true but not provable in F, hence...
• Step 4: F is incomplete. Also, adding G as an axiom to F would make G (trivially) provable in the new formal system F'. However, then we could build another wff, say G', that is both true but unprovable in F'. This process can be repeated forever, meaning that it is not possible to make F complete simply by adding Gödel's sentences as axioms. In short, any consistent and sufficiently expressive formal system is "incompletable."

Now, here is Nagel and Newman's proof sketch of Gödel's second theorem:

• Step 1: Build a wff (call it C) of the formal system F such that the meta-mathematical interpretation of C is: "F is consistent."
• Step 2: Prove the wff C → G in F (recall that C → G means "C implies G" and is logically equivalent to ¬ C ∨ G).
• Step 3: Sub-proof by contradiction:
• Assume C is provable in F.
• By modus ponens applied to the premises C and C → G, we can prove G in F.
• But G is not provable in F; so we have exhibited a contradiction.
• Therefore, C is not provable in F.

The crucial step in Gödel's proofs is a constructive one: he showed how to build in F a wff G with Gödel number g whose meta-mathematical interpretation is the following: "The wff with Gödel number g is not provable in F." In other words, the wff G can be interpreted (at the meta-level) to mean that G is not provable within the formal system. In short, the meta-mathematical interpretation of G is "I am not provable."

Therefore, the crux of the proofs is how to build Gödel's sentence, that is, the wff G (step 1 of the first proof).

Recall the following expressions in F (on the right) and their meta-mathematical interpretations (on the left) that we described in this post:

meta-mathematical statement ⇔ mathematical proposition in F the sequence s is a proof of w ⇔ ProofOf( Φ(s) , Φ(w) ) meta-mathematical numerical expression ⇔ mathematical/numerical expression in F the Gödel number of the wff obtained by substituting (the numeral in F for) the number n for the free variable x in the wff with Gödel number m ⇔ Sub( n , 17 , m ) where Φ(w) is the Gödel number of the wff w and Φ(s) is the Gödel number of s, which is a sequence of wff's. Now, to the construction of Gödel's sentence G... The wff ProofOf(y,z) means "the sequence with Gödel number y is a proof of the wff with Gödel number z." Hence: The wff  ¬ProofOf(y,z) means "the sequence with Gödel number y is NOT a proof of the wff with Gödel number z." Therefore: The wff ∀y (¬ProofOf(y,z)) means "For every integer y, the sequence with Gödel number y is NOT a proof of the wff with Gödel number z." In other words:  The wff ∀y (¬ProofOf(y,z)) means "The wff with Gödel number z is not provable in F." Note that z is a free variable in the wff ∀y (¬ProofOf(y,z)). So we'll refer to this wff as G(z).  G(z) is neither true nor false until we assign a specific numerical value to z. If we could find a value v such that G(v) has Gödel number v, then we would be done! Recall that G(v) means "the wff with Gödel number v is not provable." So, if Φ(G(v)) = v, then G(v) means "I am not provable" and G(v) is Gödel's sentence G.  The last step is to find this value v.  It is now time to use the second formal expression in F described above, namely: Sub( n , 17 , m ) In fact, let's consider, as a special case of it: Sub( x , 17 , x ) which represents in F the Gödel number α of the wff obtained by substituting the number x for the free variable x in the wff with Gödel number x. Since α is a number, we can replace it (that is, its numeral in F) for the numerical variable z in G(z), yielding: ∀y (¬ProofOf(y, Sub(x,17,x) )) Obviously, this wff has a Gödel number. Let's call this number h and see what happens when we replace the free variable x above by the numeral for h: ∀y (¬ProofOf( y , Sub(h,17,h) ) ) It turns out that this wff is G! Why? Because... this wff means "the wff with Gödel number Sub(h,17,h) is not provable."  this wff is the wff with Gödel number Sub(h,17,h) remember how we built this wff, namely by substituting h for x in the wff with Gödel number h. Therefore, the value of v we were looking for is Sub(h,17,h). In conclusion, Gödel's sentence G is G(v) = G( Sub(h,17,h) ), that is: ∀y (¬ProofOf( y , Sub(h,17,h) ) )