MTH 355
Homework 5
Assigned 3 Dec
due in class at 1:00 PM, 15 Dec
(i.e. the start of our final-exam time slot)

1. Exercise 3.1.4: prove that a subset of the naturals is definable in the naturals (with language 0, S) iff it is either finite or cofinite.

2. Exercise 3.1.5: prove that the < relation is not definable in the naturals (with language 0, S).

3. Exercise 3.1.6: prove that the theory of the naturals (with language 0, S) is not finitely axiomatizable.

4. Exercise 3.3.1: prove that the following are definable in the naturals (with language *, E):

   • the relation sum(x,y,z) which is true iff x+y=z
   • the relation zero(x) which is true iff x is zero
   • the relation <
   • the relation succ(x,y) which is true iff x+1=y
   Remember: you don't have +, 0, <, 1, or S in the language: you have to define all these things from multiplication and exponentiation!
   Hint: do them in the order listed above.

5. Exercise 3.3.8: prove that if functions g and h are representable in A_E, then so is the function f defined by natural successor recursion on g and h.

6. We already know that there are sentences that A_E can neither prove nor disprove; we already know that the set of sentences it can prove isn't recursive; and we already know that the set of sentences it can disprove isn't recursive. But it's worse than that: you can't even recursively draw a line between the provable and the disprovable.
   Exercise 3.5.1: prove that there is no recursive set that "separates" things that A_E can prove from things that A_E can disprove.

7. Exercise 3.6.9: prove that the set of programs that halt on at least two different inputs is Σ₁ but not Π₁.

8. Exercise 3.6.14: prove that various sets of programs are at various levels of the arithmetic hierarchy.

9. Exercise 3.7.1: Let σ be a statement that asserts its own provability in A_E. Is σ actually provable in A_E? Convince me of your answer.