7. Use Div and sum up.

8. Use IsPrime and some ingenuity.

9. Use Exp and Div and some more ingenuity.

10. A suitable combination of Prime with other things will do.

11. A suitable combination of Prime and Power will do.

12. Throw the kitchen sink at this one . . .

13. Ditto.

14.10. For the hard direction, do an induction on how g was built

up from the initial functions.

14.11. A straightforward application of Theorem 14.10.

14.12. This is not unlike, though a little more complicated than,

showing that primitive recursion preserves computability.

14.13. It™s not easy! Look it up . . .

14.14. This is a very easy consequence of Theorem 14.13.

14.15. Listing the de¬nitions of all possible primitive recursive

functions is a computable task. Borrow a trick from Cantor™s proof

that the real numbers are uncountable. (A formal argument to this ef-

fect could be made using techniques similar to those used to show that

all Turing computable functions are recursive in the next chapter.)

CHAPTER 15

Hints

15.1. The strategy is obvious . . . Make sure that at each stage you

preserve a copy of the original input for use at later stages.

15.2. The primitive recursive function you de¬ne only needs to

check values of g(n1 , . . . , nk , m) for m such that 0 ¤ m ¤ h(n1 , . . . , nk ),

but it still needs to pick the least m such that g(n1 , . . . , nk , m) = 0.

15.3. This is very similar to Theorem 14.8.

15.4. This is virtually identical to Theorem 14.10.

15.5. This is virtually identical to Corollary 14.11.

15.6. In both cases, emulate Example 15.1.

15.7. Unwind De¬nition 15.5; you will need to do some factoring.

15.8. Find the codes of each of the positions in the sequence you

chose and then apply De¬nition 15.6.

1. It will probably be convenient to ¬rst devise a function

15.9.

which recognizes whether the input is of the correct form or not.

You may ¬nd it convenient to ¬rst show that following relation

is primitive recursive:

• TapePos, where TapePos(n) ⇐’ n is the code of a

tape position.

If the input is of the correct form, make the necessary changes

to n using the tools in Problem 14.9.

2. Piece TMM together by cases using the function Entry in each

case. You may wish to look back to the construction of an uni-

versal Turing machine in Chapter 12 for some idea of what needs

to be done.

3. You may ¬nd it convenient to ¬rst show that following relation

is primitive recursive:

• TapePosSeq, where TapePosSeq(n) ⇐’ n is the code

of a sequence of tape positions.

Use the function TMM to check that a sequence of tape positions

is a computation.

69

70 15. HINTS

15.10. The last part of Problem 15.9 and some unbounded mini-

malization are the key ingredients. You may also ¬nd Theorem 15.4

useful if you show that the following functions are recursive:

• Codek (n1 , . . . , nk ) = (0, 1, 01n1 0 . . . 01nk ) for any ¬xed k ≥ 1.

• Decode(t) = n if t = (i, k, 01n+1 ) (and anything you like

otherwise).

15.11. Take some creative inspiration from De¬nitions 15.5 and

15.6. Fpr example, if (s, i) ∈ dom(M) and M(s, i) = (j, d, t), you

could let the code of M(s, i) be

M(s, i) = 2s 3i 5j 7d+1 11t .

15.12. Much of what you need for both parts is just what was

needed for Problem 15.9. The additional ingredients mainly have to do

with using m = M properly.

15.13. Essentially, this is to Problem 15.12 as proving Theorem

15.10 is to Problem 15.9.

15.14. Use χP to help de¬ne a function f such that im(f) = P .

15.15. One direction is an easy application of Proposition 15.14.

For the other, given an n ∈ N, run the functions enumerating P and

N \ P concurrently until one or the other outputs n.

15.16. Consider the set of natural numbers coding (according to

some scheme you must devise) Turing machines together with input

tapes on which they halt.

15.17. See how far you can adapt your argument for Proposition

15.15.

CHAPTER 16

Hints

16.1. Compare De¬nition 16.2 with the de¬nition of maximal con-

sistency.

71

72 16. HINTS

CHAPTER 17

Hints

17.1. In each case, use De¬nitions 17.1 and 17.2, together with the

appropriate de¬nitions from ¬rst-order logic and the tools developed

in Problem 14.9.

17.2. In each case, use De¬nitions 17.1 and 17.2, together with the

appropriate de¬nitions from ¬rst-order logic and the tools developed

in Problems 14.9 and 17.1. (They™re all primitive recursive if ∆ is,

by the way.)

1. Use unbounded minimalization and the relations in

17.3.

Problem 17.2 to de¬ne a function which, given n, returns the

nth integer which codes an element of Th(∆).

2. If ∆ is complete, then for any sentence σ, either σ or ¬σ

must eventually turn up in an enumeration of Th(∆) . The

other direction is really just a matter of unwinding the de¬nitions

involved.

73

74 17. HINTS

CHAPTER 18

Hints

18.1. Every deduction from “ can be replaced by a dedudction of

Σ with the same conclusion.

18.2. If Σ were insconsistent it would prove entirely too much . . .

1. Adapt Example 18.1.

18.3.

2. Use the 1-place function symbol S of LN .

3. There is much less to this part than meets the eye . . .

18.4. In each case, you need to use the given representing formula

to de¬ne the one you need.

18.5. String together the formulas representing g1 , . . . , gm , and h

with §s and put some existential quanti¬ers in front.

18.6. First show that that < is representable in Th(A) and then

exploit this fact.

1. n | m if and only if there is some k such that n · k = m.

18.7.

2. n is prime if and only if there is no such that | n and 1 < < n.

3. pk is the ¬rst prime with exactly k ’ 1 primes less than it.

4. Note that k must be minimal such that nk+1 m.

5. You™ll need a couple of the previous parts.

6. Ditto.

18.8. Problem 18.7 has most of the necessary ingredients needed

here.

18.9. Problems 18.7 and 18.8 have most of the necessary ingredi-

ents between them.

18.10. Proceed by induction on the numbers of applications of com-

position, primitive recursion, and unbounded minimalization in the re-

cursive de¬nition f, using the previous results in Chapter 18 at the

basis and induction steps.

75

76 18. HINTS

CHAPTER 19

Hints

19.1. A is a ¬nite set of sentences.

19.2. First show that recognizing that a formula has at most v1 as

a free variable is recursive. The rest boils down to checking that sub-

stituting a term for a free variable is also recursive, which has already

had to be done in the solutions to Problem 17.1.

19.3. Let ψ be the formula (with at most v1, v2 , and v3 free) which

represents the function f of Problem 19.2 in Th(A). Then the formula

∀v3 (ψ v2 v1 ’ •v1 ) has only one variable free, namely v1 , and is very

v3

close to being the sentence σ needed. To obtain σ you need to substitute

S k O for a suitable k for v1.

19.4. Try to prove this by contradiction. Observe ¬rst that if Σ is

recursive, then Th(Σ) is representable in Th(A).

1. If “ were recursive, you could get a contradiction to

19.5.

the Incompleteness Theorem.

2. If ∆ were complete, it couldn™t also be recursive.

3. Note that A ‚ Th(N).

19.6. Modify the formula representing the function ConclusionΣ

(de¬ned in Problem 17.2) to get Con(Σ).

19.7. Try to do a proof by contradiction in three stages. First,

¬nd a formula • (with just v1 free) that represents “n is the code of

a sentence which cannot be proven from Σ” and use the Fixed-Point

Lemma to ¬nd a sentence „ such that Σ „ ” •(S p„ q). Second, show

that if Σ is consistent, then Σ „ . Third ” the hard part ” show

that Σ Con(Σ) ’ •(S p„ q). This leads directly to a contradiction.

19.8. Note that N |= A.

19.9. If the converse was true, A would run afoul of the (First)

Incompleteness Theorem.

19.10. Suppose, by way of contradiction, that Th(N) was de¬n-

able in N. Now follow the proof of the (First) Incompleteness Theorem

as closely as you can.

77

78 19. HINTS

Bibliography

[1] Jon Barwise (ed.), Handbook of Mathematical Logic, North Holland, Amster-

dam, 1977, ISBN 0-7204-2285-X.

[2] C.C. Chang and H.J. Keisler, Model Theory, third ed., North Holland, Ams-

terdam, 1990.

[3] Martin Davis, Computability and Unsolvability, McGraw-Hill, New York, 1958;

Dover, New York, 1982, ISBN 0-486-61471-9.

[4] Martin Davis (ed.), The Undecidable; Basic Papers On Undecidable Propo-

sitions, Unsolvable Problems And Computable Functions, Raven Press, New

York, 1965.

[5] Herbert B. Enderton, A Mathematical Introduction to Logic, Academic Press,

New York, 1972.

[6] Douglas R. Hofstadter, G¨del, Escher, Bach, Random House, New York, 1979,

o

ISBN 0-394-74502-7.

[7] Jerome Malitz, Introduction to Mathematical Logic, Springer-Verlag, New

York, 1979, ISBN 0-387-90346-1.

[8] Yu.I. Manin, A Course in Mathematical Logic, Graduate Texts in Mathemat-

ics 53, Springer-Verlag, New York, 1977, ISBN 0-387-90243-0.

[9] Roger Penrose, The Emperor™s New Mind, Oxford University Press, Oxford,

1989.

[10] T. Rado, On non-computable functions, Bell System Tech. J. 41 (1962), 877“

884.

[11] Raymond M. Smullyan, G¨del™s Incompleteness Theorems, Oxford University

o

Press, Oxford, 1992, ISBN 0-19-504672-2.

79

80 BIBLIOGRAPHY

Index

A, 49 IsPrime, 33, 52

Length, 33, 52

Con(Σ), 54

Logical, 46

∆ , 46

•(S m1 0, . . . , S mk 0), 50 Mult, 31

f : Nk ’ N, 25 O, 27, 29, 51

Power, 33, 52

iN , 26

LN , 43 Pred, 27, 31

N, 25 Premiss∆ , 46

Nk \ P , 32 Prime, 33, 52

Nk , 25 Sentence, 46

Sim, 39

N, 44

P © Q, 32 Subseq, 33

P ∪ Q, 32 Sub, 53

P § Q, 32 Sum, 27, 30

P ∨ Q, 32 S, 27, 29, 51

S m 0, 50 TapePosSeq, 69

¬P , 32 TapePos, 69

k Term, 46

πi , 29, 51

TM, 39

Th(N), 54

TMM , 38

Th(Σ), 44

Ackerman™s Function, 33

A, 33

alphabet, 7, 13

±, 33

Codek , 70 blank

Comp, 39 cell, 7

CompM , 38 tape, 7

Conclusion∆ , 46 bounded minimalization, 36