17 - Indefinability, Undecidability, Incompleteness

Summary

We are now in a position to give a unified treatment of some of the central negative results of logic: Tarski's theorem on the indefinability of truth, Church's theorem on the undecidability of logic, and Gödel's first incompleteness theorem, according to which, roughly speaking, any sufficiently strong formal system of arithmetic must be incomplete (if it is consistent). These theorems can all be seen as more or less direct consequences of a single exceedingly ingenious lemma, the Gödel diagonal lemma. This lemma, and the various negative results on the limits of logic that follow from it, will be presented in section 17.1. This presentation will be followed by a discussion in section 17.2 of some classic particular examples of sentences that can be neither proved nor disproved in theories of arithmetic like Q or P. Further such examples will be presented in the optional section 17.3. According to Gödel's second incompleteness theorem, the topic of the next chapter, such examples also include the sentence stating that P is consistent.

The Diagonal Lemma and the Limitative Theorems

By the results in the preceding chapter on the representability of recursive functions, we can ‘talk about’ such functions within a formal system of arithmetic. By the results of the chapter before that on the arithmetization of syntax, we can ‘talk about’ sentences and proofs in a formal system of arithmetic in terms of recursive functions.