17.3*. UNDECIDABLE SENTENCES WITHOUT THE DIAGONAL LEMMA 229

of symbols in any encyclopedia remains far less than 10 10. So if n is denominated by the formula L(x), its complexity is less than 10 10. Since this is impossible, it follows that no sentence of form GC(n) can be proved: no specific number n can be proved to have complexity greater than 10 10. This reasoning can be adapted to any other reasonable measure of complexity.

(For example, suppose we take the complexity of a number to be the smallest number of states needed for a Turing machine that will produce that number as output given zero as input. To establish that ‘the complexity of x is y’ and related formulas can be expressed in the language of arithmetic we now need the fact that Turing machines can be coded by recursive functions in addition to the fact that recursive functions are representable. And to show that if there is any proof that some number has complexity greater than 10 10, then the number n identified by the lead witness can be generated as the output for input zero by some Turing machine, we need in addition to the arithmetizability of syntax the fact also of the Turing computability of recursive functions. Almost the whole of this book up to this point is involved just in outlining how one would go about writing down the relevant formula and designing the relevant Turing machine. But while filling in the details of this outline might fill an encyclopedia, still it would not require anything approaching 10 10 symbols, and that is all that is essential to the argument. In the literature, the label Chaitin’s theorem refers especially to this Turing-machine version, but as we have said, similar reasoning applies to any reasonable notion of complexity.)

Thus on any reasonable measure of complexity, there is an upper bound b—we have used 10 10, though a closer analysis would show that a much smaller number would do, its exact value depending on the particular measure of complexity being used—such that no specific number n can be proved in Q to have complexity greater than b. Moreover, this applies not just to Q but to any stronger true theory, such as P or the theories developed in works on set theory that are adequate for formalizing essentially all ordinary mathematical proofs. Thus Chaitin’s theorem, whose proof we have sketched, tells us that there is an upper bound such that no specific number can be proved by ordinary mathematical means to have complexity greater than that bound.

Problems

17.1Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some correct-rudimentary sentence.

17.2Let T be a consistent, axiomatizable theory extending Q. Consider the set Pyes of (code numbers of) formulas that are provable in T , and the set Pno of (code

numbers of) formulas that are disprovable in P. Show that there is no recursive set R such that Pyes is a subset of R while no element of R is an element of Pno.

17.3Let B1(y) and B2(y) be two formulas of the language of arithmetic. Generalizing the diagonal lemma, show that there are sentences G1 and G2 such that

Q G1 ↔ B2( G2 )

Q G2 ↔ B1( G1 ).

For instance, there are a pair of sentences such that the first says the second is provable, while the second says the first is unprovable.

The set of (code numbers of) sentences of the language of arithmetic {<, 0, , +, ·} that are correct, or true in the standard interpretation, is not recursive. Actually, it can be shown that the set of (code numbers of) sentences of the language {+, ·} that are true in the standard interpretation is not recursive. The next few problems are pieces of the proof.

17.4Explain why, to establish the stronger result just stated, it would suffice to associate in a recursive way to every sentence A of the language {<, 0, , +, ·} a sentence A† of the language {+, ·} such that A is correct if and only if A† is correct.

17.5Continuing the preceding problem, show that there is a formula D0(x) of the language {+, ·} such that the following is correct: x(x = 0 ↔ D0(x)). Then explain how to associate in an effective (and therefore, assuming Church’s thesis, a recursive) way to every sentence A of the language {<, 0, , +, ·} a sentence A† of the language {<, , +, ·} such that A is correct if and only if A† is correct.

17.6Continuing the preceding series of problems, exhibit a formula Ds (x, y) of the language {+, ·} such that

x y(x = y ↔ Ds (x, y))

is correct, and a formula D< (x, y) of the language {+, ·} such that

x y(x < y ↔ D< (x, y))

is correct. Then show how, say, the statements in Example 16.7 can be naturally expressed in the language {+, ·}.

17.7Let T = Q, let R be the Rosser sentence of T , let T0 be T + { R}, the set of consequences of T { R}, and let T1 = T + { R}; then {T0, T1} is a set of two consistent, axiomatizable extensions of Q that are inconsistent with each other

in the sense that their union is inconsistent. Show that for every n there is a set of 2n consistent, axiomatizable extensions of Q that are pairwise inconsistent in the sense that any two of them are inconsistent with each other.

17.8Show that there is a nonenumerable set of consistent extensions of Q that are pairwise inconsistent.

17.9Let L1 and L2 be finite or recursive languages, and T a theory in L2. A translation of L1 into T is an assignment to each sentence S of L1 of a sentence S† of L2 such that:

(T0) ( A)† is logically equivalent to (A)†.

(T1) The function taking the code number of a sentence of L1 to the code number of its translation is recursive.

(T2) Whenever A1, . . . , Ak , B are sentences of L1 and B is a consequence of A1, . . . , Ak , then B† is a consequence of T { A†1, . . . , A†k }.

Show that if T is a consistent, axiomatizable theory in a language L, and if there is a translation of the language of arithmetic into T such that the translation of

every axiom of Q is a theorem of T , then the set of sentences of the language of arithmetic whose translations are theorems of T is a consistent, axiomatizable extension of Q.

17.10Show that under the hypotheses of the preceding problem, T is incomplete and undecidable.

17.11Let L be a language, N (u) a formula of L. For any sentence F of L, let the relativization FN be the result of replacing each universal quantifier x in F by x(N (x) → · · ·) and each existential quantifier x by x(N (x) & . . .). Let T be a theory in L such that for every name c, N (c) is a theorem of T and for every function symbol f the following is a theorem of T :

x1 . . . xk ((N (x1) & . . . & N (xk )) → N ( f (x1, . . . , xk ))).

Show that for any model M of T , the set of a in |M| that satisfies N (x) is the domain of an interpretation N such that any sentence S of L is true in N if and only if its relativization SN is true in M.

17.12Continuing the preceding series of problem, show that the function assigning each sentence S of L its relativization SN is a translation. (You may appeal to Church’s thesis.)

17.13Consider the interpretation Z of the language {<, 0, , +, ·} in which the

domain is the set of all integers (including the negative ones), and the denotation of 0 is zero, of is the function that adds one to a number, of + and · are the usual addition and multiplication functions, and of < is the usual order relation. Show that the set of all sentences that are true in Z is undecidable, and that this is still so if < is dropped.