26 1. Logic and foundations By Corollary 1.10.15 (or more precisely, the proof of that corollary), G is not provable in L . Now we show that G is provable in L. Because L can prove the consistency of L , one can embed the proof of Corollary 1.10.15 inside the language L, and deduce that the sentence “G is not provable in L ” is also provable in L. In other words, L can prove that T(G) is false. On the other hand, embedding the proof of Theorem 1.10.14 inside L, L can also prove that the truth value of G and T(G) differ. Thus L can prove that G is true. The advantage of this formulation of the second incompleteness theo- rem, as opposed to the usual counterfactual one, is that one can actually trace through the argument with a concrete example. For instance, Zermelo- Frankel-Choice (ZFC) set theory can prove the consistency of Peano arith- metic (a result of Gentzen [Ge1936]), and so one can follow the above argument to show that the G¨ odel sentence of Peano arithmetic is provably true in ZFC, but not provable in Peano arithmetic. 1.10.3. Computability. By now, it should not be surprising that the no- self-defeating arguments in computability also have a non-counterfactual form, given how close they are to the analogous arguments in set theory and logic. For the sake of completeness, we record this for Turing’s theorem: Theorem 1.10.18 (Turing halting theorem. (Informal statement)). There does not exist a program P which takes a string S as input, and determines in finite time whether S is a program (with no input) that halts in finite time. Here is the non-counterfactual version: Theorem 1.10.19 (Informal statement). Let P be a program that takes a string S as input, returns a yes-no answer P(S) as output, and which always halts in finite time. Then there exists a string G that is a program with no input, such that if P is given G as input, then P does not determine correctly whether G halts in finite time. Proof. Define Q() to be the program taking a string R as input which does the following: (1) If R is not a program that takes a string as input, it halts. (2) Otherwise, it runs P with input R(R) (which is a program with no input). (3) If P(R(R)) returns “no”, it halts, while if P(R(R)) returns “yes”, it runs forever. Now, let G be the program Q(Q). By construction, G halts if and only if P(G) returns “no”, and the claim follows.

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.