Interlude: Incompleteness and Isaacson's conjecture
Peter James Smith · Cambridge University Press eBooks · 2001
This Interlude discusses a couple of further questions about incompleteness that might well have occurred to you as you have been reading through recent chapters. But, given that the chapters since the last Interlude have been quite densely packed, we should probably begin with a quick review of where we've been. Taking stock Here's some headline news which is worth highlighting again: First, we showed that the restriction of the First Theorem to p.r. axiomatized theories is in fact no real restriction. Appealing to a version of Craig's Theorem, we saw that the incompleteness result applies equally to any consistent axiomatized theory which contains Q (or, indeed, is otherwise p.r. adequate). (Section 19.1) But our pivotal new result was Theorem 20.4, the general Diagonalization Lemma: if T is a nice theory and ϕ(x) is any wff of its language with one free variable, then there is a ‘fixed point’ γ such that T ⊢ γ ↔ ϕ(⌜γ⌝). And further, if ϕ(x) is Π 1 , then it has a Π 1 fixed point. (Section 20.5) We then proved the rather easy Theorem 21.1: if γ is any fixed point for ¬Prov T (x), then, if T is nice, T ⊬ γ, and if T is also ω-consistent, then T ⊬ ¬γ. Since the Diagonalization Lemma tells us that there is a fixed point for ¬Prov T (x), that gives us the standard incompleteness theorem again. […]