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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.