Multi-Page Printing

1.10. The “no-self-defeating object” argument, revisited 25 Actually Theorem 1.10.14 is marginally stronger than Proposition 1.10.6 because it makes the sentence G independent of the interpretation M, whereas Theorem 1.10.12 (when viewed in the contrapositive) allows G to depend on M. This slight strengthening will be useful shortly. An important special case of Theorem 1.10.14 is the first incompleteness theorem: Corollary 1.10.15 (G¨ odel’s first incompleteness theorem. (Informal state- ment)). Let L be a formal language containing the concepts of predicates and strings that has at least one interpretation M that gives the standard interpretation of strings (in particular, L must be consistent). Then there exists a sentence G in L that is undecidable in L (or more precisely, in a formal recursive proof system for L). Proof (Sketch). A language L that is powerful enough to contain predi- cates and strings will also be able to contain a provability predicate P(), so that a sentence x in L is provable in L’s proof system if and only if P(x) is true in the standard interpretation M. Applying Theorem 1.10.14 to this predicate, we obtain a G¨ odel sentence G such that the truth value of G in M differs from the truth value of P(G) in M. If P(G) is true in M, then G must be true in M also since L is consistent, so the only remaining option is that P(G) is false in M and G is true in M. Thus neither G nor its negation can be provable, and hence G is undecidable. Now we turn to the second incompleteness theorem: Theorem 1.10.16 (G¨ odel’s second incompleteness theorem. (Informal statement)). No consistent logical system which has the notion of a pred- icate and a string, can provide a proof of its own logical consistency. Here is the non-counterfactual version: Theorem 1.10.17 (Informal statement)). Let L,L be consistent logical systems that have the notion of a predicate and a string, such that every sentence in L is also a sentence in L, and such that the consistency of L can be proven in L. Then there exists a sentence G that lies in both L and L that is provable in L but is not provable in L . Proof (Sketch). In the common language of L and L , let T() be the pred- icate T(x) := “x is provable in L ”. Applying Theorem 1.10.14, we can find a sentence G (common to both L and L ) with the property that in any interpretation M of either L or L , the truth value of G and the truth value of T(G) differ.