Philosophy 1880: Problem Sets

The PDF version of the syllabus also contains the problem sets.

Some Reminders

It is a requirement of the class that all of the problem sets must be completed and submitted for marking. (See here for a caveat.) Failure to submit all of the problem sets will automatically lead to a grade of NC. Please note that the requirement is that the problem sets should be "completed", and by that I mean that one has given them a proper effort. Simply turning in a piece of paper with a few random jottings does not count as completing a problem set.

Students are encouraged to work on the problems together. Submitted material, however, should be a student's own work. Do not come up with a group solution and then have everyone submit that.

Doing Problem Sets Electronically

You are of course welcome to do your problem sets by hand or on a computer. But if you are going to do the latter, then I would strongly recommend that you not use a traditional "word processor" to do so. They are simply not optimized for mathematics, and their output is awful. A much better option is LaTeX, and if you want to use LaTeX in an environment that feels a lot like a word processor, then you can use LyX. Especially if you have any intention of ever doing serious technical writing, you should start using LaTeX sooner rather than later. In the sciences, especially, it is the standard tool. Many scientific journals do not accept submissions in any other form.

Problem Set Grades

Problem sets will be marked on a scale of 1–5, with half points where appropriate. A 4.0 signifies a problem set that fully meets expectations. That is, it displays a perfectly adequate understanding of the material covered. A 4.5 signifies something beyond that: Problems that were done especially well, for example. A 5.0 is rare and signifies that a problem set displays an especially deep understanding of the material.

Scores below 4.0 signify some inadequacy in the understanding displayed. A 3.5 probably means a few too many mistakes, but nothing to be overly concerned about. A 3.0 means that the understanding of the material displayed is barely adequate. Scores below 3.0 signify increasing difficulties. Since, as with any math class, the material is cumulative, it is recommended that anyone receiving a 3.0 or lower score on a problem set see the instructor as soon as possible to make sure the student's difficulties are addressed.

The Problem Sets

Note that in many cases you have a choice of what problems to do, and of course you're welcome to do more than are assigned. You should do more problems than are assigned since that's how you actually learn this kind of material. And, as the book notes, you should be reading all the problems anyway, since some of them introduce important ideas not covered in the main text.

Problem sets are generally due a week after we finish the material in class.

NOTE: In many cases, the easiest way to do one problem is to appeal to the result of a previous problem. You may do this, even if you did not do the previous problem, unless that is obviously "cheating". (A good example would be to do 2.5 by appeal to 2.3 and 2.4, without doing either of those.)

Hints for the odd-numbered problems are contained in this document, which also contains a list of typos. There are quite a few typos, so you might want to have a look, especially before you do the problems.

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(x1, x2), 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 Γ ∪ {~∃viB(vi)} is satisfiable, then Γ ∪ {~B(vi)} 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(vi) is equivalent over M and β to G(vi), then ∀vi(F(vi)) is equivalent over M and α to vi(G(vi)).

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.


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 Γ = {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.

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

Richard Heck Department of Philosophy Brown University