% More Homework Exercises due 29 September
EXERCISE 53 was listed on [this page](sept24.htm).
EXERCISE 54. Do Sider's exercise 2.1 on p. 35.
EXERCISE 55. Show that the following will be evaluated as true given any interpretation of the sentence constants. Warning: the question is about what semantic values these expressions will have. If you want to make use of some proof or derivation system you've learned for sentential logic, that may be acceptable, but only if you also explain what relevance provability in that system has to the question that was explicitly asked. Another strategy is to answer these questions using arguments like you used to answer exercise 54.
(a) $(P\horseshoe Q) \vee (Q\horseshoe P)$
(b) $P\vee (P\horseshoe Q)$
(c) $((P\horseshoe Q)\horseshoe P)\horseshoe P$
This last sentence is an instance of what's known as **Peirce's Law**. It may look ugly but in fact marks an important dividing line between classical logic and some weaker logics, in some ways more important than $\neg\neg P \horseshoe P$ or $P\vee\neg P$.
EXERCISE 56. Show that these are logically/semantically equivalent. See the comments on Exercise 55 above.
(a) $P\vee Q$, $(P\horseshoe Q)\horseshoe Q$
(b) $\neg P$, $P\horseshoe\bot$
(c) $P\horseshoe(Q\vee R)$, $(P\horseshoe Q)\vee(P\horseshoe R)$
(d) $(Q\vee R)\horseshoe P$, $(Q\horseshoe P)\vee(R\horseshoe P)$
(e) $P\horseshoe (Q\horseshoe R)$, $Q\horseshoe (P\horseshoe R)$, $(P\wedge Q)\horseshoe R$
(f) $P\horseshoe\neg Q$, $Q\horseshoe\neg P$
EXERCISE 57. Show that these are logically/semantically equivalent. See the comments on Exercise 55 above. Note that my convention is to always use letters like $P$ and $F$ to represent atomic sentence and predicate constants. If I want to represent something that might have further internal complexity, I'll use Greek letters.
(a) $\forall x(Fx\horseshoe P)$, $\exists x Fx\horseshoe P$
(b) $P\horseshoe \forall x Fx$, $\forall x (P\horseshoe Fx)$
(c) $\forall x\neg Fx$, $\neg\exists x Fx$
(d) $\forall x(Fx \wedge Gx)$, $\forall x Fx \wedge \forall x Gx$
(e) $\exists x(Fx \vee Gx)$, $\exists x Fx \vee \exists x Gx$
EXERCISE 58. Show that these are not equivalent.
(a) $\forall x(Fx \vee Gx)$, $\forall x Fx \vee \forall x Gx$
(b) $\exists x(Fx \wedge Gx)$, $\exists x Fx \wedge \exists x Gx$
EXERCISE 59. Do Sider's exercise 4.1 on p. 96. (There's a hint in Appendix A.)
EXERCISE 60. Do Bostock's 3.4.1 and 3.4.2 on pp. 90-91. (Exercise 59 above may help you with the second of these.)
In the hint to 3.4.1, Bostock recommends using the method of induction on the length of a formula. You may want to [read his explanation](restricted/Bostock-inductionbylength.pdf) of that. Note that although Bostock uses the term $length$ in his explanation, in fact you never have to talk about lengths. The style of inductive argument used here is just what I showed you earlier when we proved that every string has a finite length. It's just in this case, the base cases are the atomic formulas, not the empty string; and the inductive clauses are more complex because there are more ways to build a longer formula out of smaller pieces than in the case of an arbitrary string with no well-formedness constraints. Sider illustrates the same method on pp. 52--53 of his book, and calls it "induction on formula construction." It's also discussed on [p. 39 of Gamut](restricted/Gamut-inductionbylength.jpg), which I've provided a cellphone-scan of.