Those of you who have the unofficial pdf version of Sider's book, I see from some earlier homeworks that the exercises in that MS don't always correspond to the exercises I'm assigning from the book version. If I mention some Sider problem and haven't yet supplied the text of that problem here, try to verify your copy against the book version.

  1. Do Sider's problem 2.3, on p. 46. Here is the text of the problem. You should prove the following sequents using Sider's proof system from pp. 37--46 (section 2.5):

    1. \(P\supset (Q\supset R) \Rightarrow (Q\wedge\neg R)\supset \neg P\)
    2. \(P,Q,R \Rightarrow P\)
    3. \(P\supset Q,R\supset Q \Rightarrow (P\vee R)\supset Q\)

  2. Do Sider's problem 2.4, on p. 50. Here is the text of the problem. You should prove the following using Sider's axiomatic system from pp. 46--49 (section 2.6). As Sider instructs, do not use the "toolkit" he develops on pp. 56--61 (section 2.8) for these problems.

    1. \(\vdash P \supset P\)
    2. \(\vdash (\neg P \supset P)\supset P\)
    3. \(\neg\neg P\vdash P\)

  1. Explain what a "deduction theorem" for some proof system says.

  2. Prove using Sider's axiomatic system: \(\vdash \phi \supset ((\phi\supset \psi)\supset \psi)\). This is his exercise 2.11a, on p. 62. For this problem, you can use the "toolkit" Sider develops on pp. 56--61 (section 2.8).

  3. Prove using Sider's axiomatic system: \(\vdash (\phi\supset (\psi\supset \chi)) \supset (\psi\supset (\phi\supset \chi))\). This is his exercise 2.11b, on p. 62. For this problem, you can use the "toolkit" Sider develops on pp. 56--61 (section 2.8).

  4. On p. 54 (section 2.7), Sider sketches a proof that his axiomatic system is "sound" in the sense that:

    Whenever \(\vdash \phi\), then \(\models \phi\)

    His problem 2.9, on p. 55, invites you to prove that the axiomatic system is sound in the stronger sense that:

    Whenever \(\Gamma \vdash \phi\), then \(\Gamma\models\phi\).

    Do this. Like Sider, you don't have to write out every detail, but you should make it clear what you're omitting and how the gaps would be filled in.

  5. Do Sider's problem 4.4, on p. 104. (At the end of his section 4.4.) Here is the text of the problem. Prove the following using Sider's axiomatic system from pp. 99--104 (section 4.4), which extends the earlier system from section 2.6. You may use the "shortcuts" Sider develops in section 4.4, including the "distribution" schema:

    \(\vdash \forall{{\color{green}{x}}}(\phi\supset \psi)\supset (\forall{{\color{green}{x}}}\phi \supset \forall{{\color{green}{x}}}\psi)\)

    1. \(\forall x(Fx\supset Gx),\forall x(Gx\supset Hx) \vdash \forall x(Fx\supset Hx)\)
    2. \(\vdash Fa \supset \exists xFx\)
    3. \(\vdash \forall x Rax \supset \forall x\exists y Ryx\)
    4. \(\exists x Rax, \forall y(Ray \supset \forall zRzy) \vdash \exists x\forall zRzx\)

  6. Do Bostock's problem 5.3.1a and 5.3.1b, on p. 207, in the reading on Axiomatic proofs. Here is the text of the problem. Use the "deduction theorem" to prove:

    1. \(\vdash \phi\supset \phi\)
    2. \(\phi\supset (\phi\supset \psi) \vdash \phi\supset \psi\)

  7. Do Bostock's problem 5.3.3b on p. 208, in the reading on Axiomatic proofs. Here is the text of the problem. To axioms [A1] and [A2] --- these are the axioms that Bostock shares with Sider, without their differing axioms for negation --- add the further axiom [Peirce's Law] that:

    \(\vdash ((\phi\supset \psi)\supset \phi)\supset \phi\)

    Using this new axiom, and the "deduction theorem", and modus ponens, prove:

    \((P\supset Q)\supset Q \vdash (Q \supset P)\supset P\)