An Abstract Form of Gödel’s Theorem – Part 8

Lemma (D) – A Diagonal Lemma¹

Part I

Prove: For any set A, if A* is expressible in L, then there is a Gödel sentence for A.

We first assume that A* is expressible in L.  That means there is a predicate H(n) such that the following holds…

(1) H(n) ∈ T ↔ n ∈ A*

By definition of set A* the following holds…

(2) n∈ A* ↔ d(n) ∈ A.

By definition, d(n) is the Gödel number of the predicate expressing A* instantiated with its own Gödel number.   In other words, if we let h be the Gödel number of H(n), then…

(3) d(h) = g(H(h))

Substituting (2) and (3) into (1) we get the following equivalence…

(4) H(h) ∈ T ↔ g(H(h)) ∈ A

We now have in (4) above the very definition of a Gödel sentence.  As such, H(h) is the Gödel sentence for A.  Q.E.D. 

Part II

Prove: If L satisfies condition G₁, then for any set A expressible in L, there is a Gödel sentence for A.

Condition G₁ says, “For any set A expressible in L, the set A* is expressible in L.”  If we assume set A is expressible in L and condition G₁ holds, then set A* is expressible in L. Then from Lemma D – Part I it follows that there is a Gödel sentence for A.  Q.E.D.

What is interesting here is that Lemma D leads to a very quick proof of Theorem (GT).  Since we are given that set * is expressible in L, then by Lemma D there is a Gödel sentence for .  This sentence is nothing more than a sentence that is true if and only if it is not provable in L.  If it is true, then it is not provable, and if it is false, then it is provable.  Since we are given that L is correct (it cannot prove a false statement), then this Gödel sentence must be true and not provable.

---

1. Smullyan – GIT, Pgs. 8-9.

Advertisement