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:

Mappings and the arithmetization of meta-mathematics

In an earlier post, we discussed mappings in general and then described Gödel numbering, which is a mapping between the set of well-formed formulas (wff's) in a formal system and the set of positive integers.

In part B of section VII, Nagel and Newman describe a more interesting mapping used in Gödel's proof. In this mapping, the domain is the set of meta-mathematical statements about structural properties of wff's, while the co-domain is the set of wff's. This post describes how this mapping enabled Gödel to arithmetize meta-mathematics.

Mappings and Gödel numbering

Section VI of Nagel and Newman's book describes mappings. A mapping is an operation that applies to two sets called the domain and the co-domain. More specifically, a mapping associates to each element of the domain one or more elements of the co-domain.