- 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:

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

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:

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:

According to Nagel and Newman, a proof of the first theorem can be sketched in 4 steps:Any consistent formal system that is expressive enough to model arithmetic cannot prove its own consistency.

- 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:

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
Hence:
The wff ¬
Therefore:
The wff
In other words:
The wff
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) ) )- 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.
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) ) ) |

## No comments:

## Post a Comment