1.2–1.5 (note that there is a typo in 1.5); 2.1–2.4; also, 2.10 and 2.11

It's worth having a go at 1.7, as well. The interesting point about this problem is that doing it actually requires appeal to the axiom of choice, though informal proofs tend to mask this fact.

3.1, 3.3, 3.5; 4.1, 4.2, 4.3

5.1, 5.5, 5.10 and 5.11; 6.1, 6.3, 6.4, 6.7, 6.9 (using your coding from 6.7)

If you want to challenge yourself, try 5.7–5.9 or 6.5.

7.1, 7.3 (typo here), 7.4, 7.5, 7.6; 8.1, 8.2

For a challenge, try some of 7.12–7.17, which sketch a proof that the Ackerman function is not primitive recursive. Note that there is a typo in 7.15.

For 8.1, what is wanted is a definition of a two-place function strt(x_{1}, x_{2}), similar to the definition of strt(x) on p. 90. The idea is to show that this function is primitive recursive.

What is it that 8.2 implies? or at least starts to imply?

There are two options here, depending upon how strong your logic background is.

If you have not previously taken logic, or you would like to review basic logic stuff, then you should do:

9.2–9.5 (typo in 9.3), 10.2-10.5

If you have previously taken logic, and you do not think you need to review basic logic stuff, then you should do:

9.4–9.7, 10.6, 10.9–10.11

For 9.4, you might want to reflect on the fact that, if we do not use enough parentheses, then the corresponding claim is not true. E.g., suppose we use no parentheses. Then ¬A v B has as proper subformulas: A, B, ¬A, A v B. And both of these:

A, ¬A, B, ¬A v B

A, B, A v B, ¬A v B

are formation sequences for it. But neither contains all its subformulas.

For the problems in Chapter 10, if you are asked to show that one thing *A* implies another thing *B*, then you need to show that every interpretation that makes *A* true makes *B* true. That is how implication is defined.

In 10.5 and 10.9, do *not* assume that Γ and Δ are finite!

For 10.9(b), you can prove it in the following form: If Γ ∪ {~∃v_{i}B(v_{i})} is satisfiable, then Γ ∪ {~B(v_{i})} is satisfiable. Note that satisfiability for *formulae* needs to be understood as truth under an interpretation *and an assignment*.

The statements of 10.10 and 10.11 are somewhat confusing. The book asks you to show that the various statements hold for "equivalence over an interpretation". This notion is defined on p. 122, right after the completion of the proof. Since our treatment of quantification was somewhat different from the book's, this definition needs to be re-stated in terms of equivalence over an interpretation *and an assignment*. So two formulae *F* and *G* are equivalent over **M** and α just in case **M**⊨_{α} *F* iff **M**⊨_{α} *G*. So what you want to prove is, e.g., for 10.10(d): If *F* and *G* are equivalent over **M** and α, then ~*F* and ~*G* are equivalent over **M** and α.

Yes, some of the parts of 10.10 are totally trivial; others are mostly trivial; as usual, the one that isn't trivial is the one involving quantification. For that one (f), you can just prove it in the following form: If, for every β that is an i-variant of α, *F*(*v*_{i}) is equivalent over **M** and β to *G*(*v*_{i}), then ∀*v*_{i}(*F*(*v*_{i})) is equivalent over **M** and α to *v*_{i}(*G*(*v*_{i})).

Note that, once you have done 10.10, you have all but done 10.11(a,b). In fact, you do not really have to do those problems. You could just explain why what I just said is true.

11.1-11.4

Also, in the proof of Lemma 13.2 in the book, the cases of (S4)–(S8) were skipped. Do at least two of them, preferably two that are at least slightly different.

You should also do the cases of (C4), (C6), and (C7) in the proof of the Closure Lemma.

Note that there are only two ways, really, to do 11.3 and 11.4. The first, which is probably easiest, is to reason about interpretations: I.e., show that any interpretation that makes the premises true makes the conclusion true. An alternative would be to appeal to some of the facts about implication that were established in Examples 10.3 and 10.4. I'm not sure that is a very good method all by itself, but it could perhaps be mixed with the first one in some interesting way.

For a challenge, do some of the sequence 13.8–13.13.

Note that there are typos in many of the unassigned problems in Ch 11. There is also a typo in 13.8: The definition of isomorphism is given in section 12.1 of the book, not in section 13.1. It is on page 139.

The problems for Chapter 14 are 14.1(b), 14.2, 14.3, and 14.6. However, since we have used a different sequent calculus from the one in the book, some of them need to be restated. As follows:

14.1(b): Show that Γ implies A iff some finite subset Γ_{0} of Γ implies A.

14.3: Show that if Γ, A, B ⇒ C is derivable, then Γ, A∧B ⇒ C is derivable.

14.6: Show that if Γ, A(t) ⇒ C is derivable, then so is Γ, ∀xA(x) ⇒ C.

The problems for Chapter 15 are 15.2, 15.5, 15.7. But, again, since we have used a different notion of `theory', the first two need to be restated. As follows:

15.2: Show that Cl(Γ), the closure of Γ, is closed, for any Γ. (Extra credit: Show that, if Δ is a closed theory and Γ⊆Δ, then Cl(Γ)⊆Δ. I.e., Cl(Γ) is the smallest closed theory containing Γ.)

15.5: Let Γ = {A_{1}, A_{2}, …} be a countable set of sentences, and suppose that for no n is A_{n} derivable from {A_{1}, …, A_{n - 1}}. Show that Γ is not finitely axiomatizable. I.e., there is no finite set Δ (whether it is a subset of Γ or not) that has the same theorems as Γ, i.e., is such that Cl(Γ) = Cl(Δ).

For a challenge, try 15.8-15.10.

This is a longer one, as we're spending several sessions on Ch 16. Start early!

16.1, 16.3, 16.8–16.11, and 16.17

Note: For 16.3, 16.8, and 16.9, you can consider the theory I called **R**. These are all true for it. And note that in 16.3, "correct" and "incorrect" just mean: true and false (in the standard interpretation).

For 16.10 and 16.11, the "recursion equations for addition" are (Q3) and (Q4) on p. 208.

For 16.17, you should use the theory the book calls **Q**. (I don't think the theory I called **Q** proves this result.)

Remember that what the book calls ∃-rudimentary sentences are what I called Σ_{1} sentences, and what the book calls ∀-rudimentary sentences are what I called Π_{1} sentences.

For a challenge, try 16.4, or the series 16.5–16.7, or the series 16.13–16.15

17.1, 17.4-17.6

Note that the point of 17.1 is that we can prove that no consistent extension of Q (or R) proves all true Π_{1} sentences *without using diagonalization or any of the results of Ch. 17*, but *simply* by appealing to the existence of a set that is r.e. but not recursive (and what else we know about such sets, e.g., the results of Ch. 16). So you should *not* appeal to Gödel's Theorem in proving 17.1.

For a challenge, try 17.3 (generalize it further, if you can) and 17.7–17.8