Problem Set 1
1.2–1.5 (note that there is a typo in 1.5)
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.
2.1–2.4; also, 2.10 and 2.11
1.2–1.5 (note that there is a typo in 1.5)
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.
2.1–2.4; also, 2.10 and 2.11
Problem Set 2
3.1, 3.3, 3.5
4.1, 4.2, 4.3
3.1, 3.3, 3.5
4.1, 4.2, 4.3
Problem Set 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.
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.
Problem Set 4
7.1, 7.3 (typo here), 7.4, 7.5, 7.6
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.
8.1, 8.2
What is it that 8.2 implies? or at least starts to imply?
7.1, 7.3 (typo here), 7.4, 7.5, 7.6
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.
8.1, 8.2
What is it that 8.2 implies? or at least starts to imply?
Problem Set 5
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 (do not assume that Γ is finite!)
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 reason about interpretations and show that every interpretation that makes A true makes B true. That is how implication is defined.
Note that, once you have done 10.10, you have all but done 10.11. In fact, you do not really have to do 10.11. You could just explain why what I just said is true.
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 (do not assume that Γ is finite!)
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 reason about interpretations and show that every interpretation that makes A true makes B true. That is how implication is defined.
Note that, once you have done 10.10, you have all but done 10.11. In fact, you do not really have to do 10.11. You could just explain why what I just said is true.
Problem Set 6
11.1--11.4
Note that there are typos in many of the unassigned problems in Ch 11.
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.
For a challenge, do some of the sequence 13.8–13.13.
Note that there is 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.
11.1--11.4
Note that there are typos in many of the unassigned problems in Ch 11.
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.
For a challenge, do some of the sequence 13.8–13.13.
Note that there is 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.
Problem Set 7
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.8, 15.10. But, again, since we have used a different notion of `theory', they 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 Γ = {A1, A2, …} be a countable set of sentences, and suppose that for no n is An derivable from {A1, …, An - 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.
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.8, 15.10. But, again, since we have used a different notion of `theory', they 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 Γ = {A1, A2, …} be a countable set of sentences, and suppose that for no n is An derivable from {A1, …, An - 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.
Problem Set 8
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
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
Problem Set 9
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
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