<<

. 9
( 10 .)



>>

and then sum up.
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

<<

. 9
( 10 .)



>>