Exercise 1.1 (a), (c), and (d) are \(\mathfrak {L}_{M}\)-sentences, (b), (e), and (f) are not.

Exercise 1.2 Here is a combined truth table for all the classical connectives:

Exercise 1.3 An operator \(O\) is truth-functional if you can figure out the truth-value of \(Op\) from the truth-value of \(p\).

(c) and (g) are truth-functional; (a), (b), (d), and (e) are not truth-functional.

(f) is truth-functional if God is omniscient (and infallible); it is also truth-functional if God doesn’t exist, or if God believes all and only false things; otherwise (f) is not truth-functional.

Exercise 1.4

(a)

\(\Diamond p\) \(p\): I offended the principal.

(b)

\(\neg \Diamond p\) \(p\): It is raining.

(c)

\(\Diamond p\) \(p\): There is life on Mars.

(d)

\(\Box (p \to q)\) \(p\): The murderer escaped through the window; \(q\): There are traces on the ground.

(e)

\(\Diamond (p \land q)\) \(p\): The murderer escaped through the window; \(q\): There are traces on the ground.

Exercise 1.5

(a)

\(\Box p\) \(p\): I go home.

(b)

\(\neg \Box p\) \(p\): You come.

(c)

\(\neg \Diamond p\) \(p\): You have another beer.

(d)

\(\Box (\neg p \to q)\) \(p\): You have a ticket; \(q\): You pay a fine.

Exercise 1.6

(a)

\(\Diamond p\) \(p\): I study architecture.

(b)

\(\Diamond p\) \(p\): The bridge collapses.

(c)

\(\neg \Diamond (p \land q)\) \(p\): You are talking to me from the kitchen; \(q\): I hear you.

(d)

\(p \to \Diamond q\) \(p\): You have a smartphone; \(q\): You use an electronic ticket.

Exercise 1.7 The proposed definition is equivalent to definition 1.2 for many languages, but not for all. Consider the sentence \(\exists x \exists y \neg (x = y)\) in the language of predicate logic. If we treat the identity symbol as logical, this sentence contains no non-logical expressions at all. And the sentence is true, because there is in fact more than one object. So the sentence is true under any interpretation of its non-logical vocabulary. But it’s not logically true; it doesn’t logically follow from any premises whatsoever. The sentence is false in any scenario in which there is only one object.

Exercise 1.8 The following pairs are duals: (a) and (c), (b) and (d), (e) and (g), (f) and (h), (i) and (k), (l) and (l), (m) and (m).

Exercise 1.9 (b) and (e) are equivalent to \(\Diamond \Diamond \neg p\), (a), (c), and (d) are not.

As a rule, you can always replace a modal operator by its dual, insert a negation on both sides, and remove any double negations to get an equivalent sentence.

Exercise 1.10 (b) and (d)

Exercise 1.11 (a) \(\Diamond \Diamond A \to \Diamond A\), (b) \(\Diamond \Box A \to \Box A\), (c) \(\Box A \to \Diamond A\).

Exercise 1.12 (a) \(\neg \Box p \land \neg \Box \neg p\); (b) \(\Diamond p \land \Diamond \neg p\); (c) \(\neg \nabla p \land p\). The last answer assumes that every necessary proposition is true. Without that assumption there is no answer to (c).

Exercise 1.13

(a)

All of them.

(b)

Only (K) and (CPL).

(c)

All except (T).

(d)

All of them.

Exercise 1.14

(a)

\begin {alignat*} {2} 1.\quad & \Box p \to p &\quad & \text {(T)}\\ 2.\quad & \Box (\Box p \to p) &\quad & \text {(1, Nec)} \end {alignat*}

(b)

\begin {alignat*} {2} 1.\quad & p \to (q \to (p \land q)) &\quad & \text {(CPL)}\\ 2.\quad & \Box (p \to (q \to (p \land q))) &\quad & \text {(1, Nec)}\\ 3.\quad & \Box (p \to (q \to (p \land q))) \to (\Box p \to \Box (q \to (p \land q))) &\quad & \text {(K)}\\ 4.\quad & \Box p \to \Box (q \to (p \land q))) &\quad & \text {(2, 3, CPL)}\\ 5.\quad & \Box (q \to (p \land q))) \to (\Box q \to \Box (p\land q)) &\quad & \text {(K)}\\ 6.\quad & \Box p \to (\Box q \to \Box (p\land q)) &\quad & \text {(4, 5, CPL)}\\ 7.\quad & (\Box q \land \Box q) \to \Box (p\land q) &\quad & \text {(6, CPL)} \end {alignat*}

(c)

\begin {alignat*} {2} 1.\quad & \neg \Diamond \neg p \leftrightarrow \Box \neg \neg p &\quad & \text {(Dual)}\\ 2.\quad & \neg \neg \Diamond \neg p \leftrightarrow \neg \Box \neg \neg p &\quad & \text {(1, CPL)}\\ 3.\quad & \Diamond \neg p \leftrightarrow \neg \Box \neg \neg p &\quad & \text {(2, CPL)}\\ 4.\quad & \neg \neg p \to p &\quad & \text {(CPL)}\\ 5.\quad & \Box (\neg \neg p \to p) &\quad & \text {(4, Nec)}\\ 6.\quad & \Box (\neg \neg p \to p) \to (\Box \neg \neg p \to \Box p)&\quad & \text {(K)}\\ 7.\quad & \Box \neg \neg p \to \Box p&\quad & \text {(5, 6, CPL)}\\ 8.\quad & p \to \neg \neg p &\quad & \text {(CPL)}\\ 9.\quad & \Box (p \to \neg \neg p) &\quad & \text {(8, Nec)}\\ 10.\quad & \Box (p \to \neg \neg p) \to (\Box p \to \Box \neg \neg p)&\quad & \text {(K)}\\ 11.\quad & \Box p \to \Box \neg \neg p &\quad & \text {(9, 10, CPL)}\\ 12.\quad & \Box \neg \neg p \leftrightarrow \Box p &\quad & \text {(7, 11, CPL)}\\ 13.\quad & \neg \Box \neg \neg p \leftrightarrow \neg \Box p &\quad & \text {(12, CPL)}\\ 14.\quad & \Diamond \neg p \leftrightarrow \neg \Box p &\quad & \text {(3, 13, CPL)} \end {alignat*}

Exercise 1.15 In an axiomatic calculus, every line in a proof is either an axiom or follows from an earlier line by one of the rules. (Nec) therefore assumes that whenever a sentence \(A\) is provable in the axiomatic calculus, then it is necessarily true (reading the box as ‘it is necessary that’).

The rules of the axiomatic calculus cannot be used to directly derive assumptions from arbitrary premises. To show that \(A\) entails \(B\), you have to prove \(A \to B\).

Exercise 2.1 Consider a scenario in which (say) it is raining at some worlds and not raining at others. Let \(p\) express that it is raining. In this scenario, under this interpretation, \(\Diamond p\) is true, because \(p\) is true at some world. But \(\Box p\) is false, because \(p\) is not true at all worlds. So there are conceivable scenarios and interpretations that render \(\Diamond p\) true and \(\Box p\) false.

Exercise 2.2 (b), (e), and (f) are true at \(w_{1}\), the others false.

Exercise 2.3 \(\Diamond p \to (q \lor \Diamond \Box p)\) is true at both worlds.

Exercise 2.4 The two definitions are not equivalent, as can be seen from the fact that the definition proposed in the exercise would render \(p \models \Box p\) true. Whenever \(p\) is true at every world in a model then (by definition 2.2) \(\Box p\) is also true at every world in the model. Definition 2.4 renders \(p \models \Box p\) false, since there are models in which \(p\) is true at some worlds and not at others.

Exercise 2.5 By definition 2.3, a sentence is valid iff it is true at every world in every model. Suppose for reductio that \(\Box p \to \Diamond p\) is false at some world \(w\) in some model. By definition 2.2, \(\Box p\) is then true at \(w\) and \(\Diamond p\) false. But if \(\Diamond p\) is false at \(w\) then (by definition 2.2) \(p\) is false at every world in the model. And then \(\Box p\) isn’t true at \(w\) (by definition 2.2). Contradiction.

Exercise 2.6 Suppose \(A\) is valid – true at all worlds in all models (definition 2.3). It follows that in any given model, \(A\) is true at every world. By definition 2.2, it follows that \(\Box A\) is true at every world in any model.

Exercise 2.7 \(p\to \Box p\) is false at world \(w\) in the model(s) given by \(W = \{ w, v \}, V(p) = \{ w \}\).

This shows that the truth of \(p\) (at a world in a model) does not entail the truth of \(\Box p\) (at the world in the model), even though the validity of \(p\) entails the validity of \(\Box p\), as per the previous exercise.

Exercise 2.8 Assume \(\models A \to B\). Then there is no world in any model at which \(A\) is true and \(B\) is false. So if \(A\) is true at every world in a model, then \(B\) is also true at every world in the model. It follows that \(\Box A \to \Box B\) is true at every world in every model.

Exercise 2.9

(a)

Target: \(p\to q\)

Countermodel: \(W = \{ w \}, V(p) = \{ w \}, V(q) = \emptyset \).

(b)

Target: \(p \to \Box (p \lor q)\)

Countermodel: \(W = \{ w, v \}, V(p) = \{ w \}, V(q) = \emptyset \).

(c)

Target: \(\Box p \lor \Box \neg p\)

Countermodel: \(W = \{ w,v,u \}, V(p) = \{ u \}\).

(d)

Target: \(\Diamond (p \to q) \to (\Diamond p \to \Diamond q)\)

Countermodel: \(W = \{ w,v,u \}, V(p) = \{ u \}, V(q) = \emptyset \).

(e)

\(\Box \Diamond p \to p\)

tree grows forever. The target sentence isn’t valid, but the tree method only gives us an infinite countermodel. In such a case, it may be useful to read off a model from an incomplete version of the tree and manually check whether it is a genuine countermodel. The model determined by the first five nodes of the present tree is \(W = \{ w,v \}, V(p)=\{ v \}\), and you can confirm that it is a countermodel to the target sentence.

If you read off a model from an incomplete tree, you can’t be sure that it is a countermodel for the target sentence. You must always double-check!

Exercise 2.10 You can enter the schemas at umsu.de/trees. After entering a formula, tick the checkbox for ‘universal (S5)’. Alternatively, follow these links: (K), (T), (4), (5),

Exercise 2.11 (a), (b), (c) and (e) are valid. You can find the trees at umsu.de/trees (Remember to tick the checkbox for ‘universal (S5)’) or by following these links: (a), (b), (c), (e).

(d) and (f) are invalid. Here is a tree for (d):

can choose either of the open branches to read off a countermodel. In fact, here we get the same countermodel no matter which open branch we choose: \(W = \{ w,v,u \}, V(p)=\{ v\}, V(q)=\{u\}\).

A tree for (e) might begin like this:

tree grows forever. The model determined by the first seven nodes of the present tree is \(W = \{ w,v,u \}, V(p)=\{ v \}\). It is a countermodel to the target sentence.

Exercise 2.12 By observation 1.1, \(A_{1},\ldots ,A_{n}\) entail \(B\) iff \((A_1\land \ldots \land A_n) \to B\) is valid. To show that \(A_{1},\ldots ,A_{n}\) entail \(B\) we could therefore draw a tree for \((A_1\land \ldots \land A_n) \to B\). In practice, we can save a few steps by starting the tree with multiple assumptions: one for each of the premises \(A_{1},\ldots , A_{n}\), and one for the negated conclusion \(\neg B\). (All of these are assumed to be true at world \(w\).) If the tree closes, \(A_1,\ldots ,A_n\) entail \(B\).

To show that \(A\) and \(B\) are equivalent, we can draw a tree for \(A \leftrightarrow B\).

Exercise 3.1

(a)

One answer: \(A\) is physically necessary iff \(A\) is true at all worlds that are compatible with the laws of physics. A possibly better answer: \(A\) is physically necessary iff \(A\) is true at all worlds that are compatible with the laws of physics and the current state of the universe.

(b)

A simple, if somewhat uninformative answer: We know that \(A\) iff \(A\) is true at all worlds that are compatible which our knowledge.

(c)

It is true that \(A\) iff \(A\) is true at all worlds that are identical to the actual world.

Exercise 3.2 \(v\) has access to no world. So any sentence \(A\) is true at all (zero) worlds accessible from \(v\).

If this seems strange, remember that \(\Box A\) is equivalent to \(\neg \Diamond \neg A\). And \(\Diamond \neg A\) means that there’s an accessible world where \(\neg A\) is true. If there are no accessible worlds, then this is false. So \(\neg \Diamond \neg A\) is true.

Exercise 3.3 (a) \(w_{1}, w_{2}\), and \(w_{3}\); (b) \(w_{3}\); (c) –; (d) \(w_{1}, w_{2}\) and \(w_{4}\); (e) all.

Exercise 3.4 There are infinitely many correct answers for each world. For example: \(w_1: \Diamond \Box p\), \(w_2: \neg p \land \neg q\), \(w_3: \Box p\), \(w_4: \Box q\).

Exercise 3.5

Exercise 3.6

(a)

For example: \(W = \{ w,v \}\), \(R = \{ (w,v), (v,w) \}\), \(V(p) = \{ v \}\). \(\Box p \to \Box \Box p\) is false at \(w\). (‘\(R = \{ (w,v), (v,w) \}\)’ means that \(R\) relates \(w\) to \(v\) and \(v\) to \(w\) and nothing else to anything else.)

(b)

For example: \(W = \{ w,v \}\), \(R = \{ (w,w), (w,v) \}\), \(V(p) = \{ w \}\). \(\Diamond p \to \Box \Diamond p\) is false at \(w\).

Exercise 3.7 For example: \(\Box (p \lor \neg p) \to (p \lor \neg p)\).

Exercise 3.8 By clause (g) of definition 3.2, \(\Box (p \lor \neg p)\) is false at a world \(w\) in a Kripke model only if \(p \lor \neg p\) is false at some world accessible from \(w\). By clause (d) of definition 3.2, \(p \lor \neg p\) is false at a world only if both \(p\) and \(\neg p\) are false at the world, which by clause (a) means that \(p\) is both true and false at the world. This is impossible. So \(\Box (p \lor \neg p)\) is not false at any world in any Kripke model.

Exercise 3.9 By definition 3.2, \(\Box p \to \Diamond p\) is false at a world \(w\) in a Kripke model only if \(\Box p\) is true at \(w\) and \(\Diamond p\) is false at \(w\). But if \(w\) has access to itself then the truth of \(\Box p\) at \(w\) implies that \(p\) is true at \(w\), and then \(\Diamond p\) is false at \(w\). So \(\Box p \to \Diamond p\) can’t be false at any world in any Kripke model in which each world has access to itself.

Exercise 3.10 Reflexive no, serial no, transitive no, euclidean no, symmetric yes, universal no.

Exercise 3.11

(a)

Suppose \(R\) is symmetric and transitive, and that \(xRy\) and \(xRz\). By symmetry, \(yRx\). By transitivity, \(yRz\).

(b)

Suppose \(R\) is symmetric and euclidean, and that \(xRy\) and \(yRz\). By symmetry, \(yRx\). By euclidity, \(xRz\).

(c)

Suppose \(R\) is reflexive and euclidean, and that \(xRy\). By reflexivity, \(xRx\). By euclidity, \(yRx\).

Exercise 3.12 It’s true that if \(R\) is symmetric and transitive then \(wRv\) implies \(vRw\) which implies \(wRw\). But this only shows that every world \(w\) that can see some world \(v\) can see itself. Symmetry, transitivity, and seriality together imply reflexivity. Symmetry and transitivity alone do not.

Exercise 3.13

(a)

Every world has access only to itself.

(b)

No world has access to any world.

Exercise 3.14 You can enter the sentences at umsu.de/trees. To check for K-validity, leave all the checkboxes (for ‘universal’ etc.) empty.

Exercise 3.15 You can enter the sentences at umsu.de/trees. To test for K4-validity, check the ‘transitive’ box. To test for D-validity, check ‘serial’. To test for B-validity, check ‘symmetric’. To test for T-validity, check ‘reflexive’.

Exercise 4.1 Methods A and B are genuine proof methods. Method C is not because there is no simple mechanical check of whether a sentence occurs in some logic textbook.

Exercise 4.2 Method A is complete, but not sound. Everything that’s K-valid is provable with the method, but so is everything that’s not K-valid.

Method B is sound, but not complete. Since every instance of \(\Box (A \lor \neg A)\) is K-valid, everything that is provable with method B is K-valid. But many K-valid sentences (e.g., \(p \to p\)) aren’t provable with method B.

Method C is neither sound nor complete. It is not sound because many K-invalid sentences figure in logic textbooks. It is not complete because there are infinitely many K-valid sentences almost all of which don’t occur in any textbooks.

Exercise 4.3 For \(A\to B\): Suppose \(\beta \) contains a node of the form \(A \to B \;(\omega )\) and the branch is split into two, with \(\neg A \;(\omega )\) appended to one end and \(B \;(\omega )\) to the other. Since the expanded node is a correct statement about \(M\) under \(f\), we have \(M,f(\omega ) \models A \to B\). By clause (e) of definition 3.2, it follows that either \(M,f(\omega ) \not \models A\) or \(M,f(\omega ) \models B\). By clause (b), this means that either \(M,f(\omega ) \models \neg A\) or \(M,f(\omega ) \models B\). So at least one of the resulting branches also correctly describes \(M\).

For \(\neg \Diamond A\): Suppose \(\beta \) contains nodes of the form \(\neg \Diamond A \;(\omega )\) and \(\omega R \upsilon \), and the branch is extended by adding \(\neg A \;(\upsilon )\). Since \(\neg \Diamond A \;(\omega )\) and \(\omega R \upsilon \) are correct statement about \(M\) under \(f\), we have \(M,f(\omega ) \models \neg \Diamond A\) and \(f(\omega )Rf(\upsilon )\). By clause (b) of definition 3.2, \(M,f(\omega ) \models \neg \Diamond A\) implies \(M,f(\omega ) \not \models \Diamond A\). By clause (h), it follows that \(M,f(\upsilon ) \models \neg A\). So the extended branch correctly describes \(M\).

Exercise 4.4 Yes. The function \(f\) can map both ‘\(w\)’ and ‘\(v\)’ to \(w\).

Exercise 4.5 A sentence is K4-valid iff it is true at all worlds in all transitive Kripke models. We only need to check that the Transitivity rule is sound, in the sense that if a branch correctly describes a transitive model \(M\), and the branch is extended by the Transitivity rule, then the resulting branch also correctly describes \(M\). (The Transitivity rule allows adding a node \(\omega R \upsilon \) to a branch that already contains nodes \(\omega R \nu \) and \(\nu R \upsilon \). If these nodes correctly describe a transitive model then so does \(\omega R \upsilon \).)

Exercise 4.6 For \(B\to C\): If \(A\) is a conditional \(B\to C\), then \(\beta \) contains either \(\neg B \;(\omega )\) or \(C \;(\omega )\). By induction hypothesis, \(M,\omega \models \neg B\) or \(M,\omega \models \neg C\). Either way, clauses (b) and (e) of definition 3.2 imply that \(M,\omega \models A\).

For \(\neg \Diamond B\): If \(A\) is a negated diamond sentence \(\neg \Diamond B\), then \(\beta \) contains a node \(\neg B \;(\upsilon )\) for each world variable \(\upsilon \) for which \(\omega R \upsilon \) is on \(\beta \) (because the tree is fully developed). By induction hypothesis, \(M, \upsilon \models \neg B\), for each such \(\upsilon \). By definition 4.2, it follows that \(M,\upsilon \models \neg B\) for all worlds \(\upsilon \) such that \(\omega R \upsilon \). By clauses (b) and (g) of definition 3.2, it follows that \(M, \omega \models A\).

Exercise 4.7 We need to check that the model induced by an open branch on a fully developed K4-tree is transitive. (Suppose the model contains worlds \(w\), \(v\), \(u\) for which \(wRv\) and \(vRu\). Then the Transitivity rule has been applied to the corresponding nodes on the branch, generating a node \(wRu\). By definition 4.2, \(wRu\) holds in the induced model.)

Exercise 4.8 Suppose \(A\) is true at some world in some Kripke model. Then \(\neg A\) is K-invalid. Take any regular K-tree for \(\neg A\). By observation 4.1, that tree is fully developed. By the soundness theorem for K-trees, the tree has an open branch. Let \(M\) be the model induced by some such branch \(\beta \). Then \(M\) is acyclical. This is because the only rules that allow adding a node \(\omega R \upsilon \) to a branch of a K-tree are the rules for expanding \(\Diamond A\) and \(\neg \Box A\) nodes. In both cases, the rule requires that the relevant world variable \(\upsilon \) is new on the branch. (Call this the novelty requirement.) Now suppose the accessibility relation in \(M\) has a cycle \(\omega _{1} R \omega _{2}\), \(\omega _{2} R \omega _{3}\), …, \(\omega _{n-1} R \omega _{n}\), \(\omega _{n} R \omega _{1}\). Each of these facts about \(R\) must correspond to a node on \(\beta \). Of these nodes, the one that was added last (to \(\beta \)) violates the novelty requirement. So \(M\) is acyclical.

By the Completeness Lemma, the target sentence \(\neg \neg A\) is true at world \(w\) in \(M\). So \(A\) is true at \(w\) in \(M\). So \(A\) is true at some world in some acyclical model.

Exercise 4.9 The S5 rules are not sound with respect to K-validity. For example, \(\Box p \to p\) is provable with the S5 rules, but it isn’t K-valid. The rules are, however, complete with respect to K-validity. This follows from the completeness of the S5 rules and the fact that every K-valid sentence is S5-valid (observation 3.1).

Exercise 4.10 We need to show that everything that’s derivable in the axiomatic calculus for S4 is true at every world in every transitive and reflexive Kripke model. From the soundness proof for K, we know that all instances of (Dual) and (K) are true at every world in every Kripke model. From observation 3.2, we know that all instances of (T) are true at every world in every reflexive Kripke model. From observation 3.3, we know that all instances of (4) are true at every world in every transitive Kripke model. So all axioms in the S4-calculus are valid in the class of transitive and reflexive Kripke frames. Since (CPL) and (Nec) preserve validity in any class of Kripke frames, it follows that everything that’s derivable in the S4-calculus is valid in the class of transitive and reflexive frames.

Exercise 4.11 (a), (b), and (c) are K-consistent, (d) is not.

Exercise 4.12 We have to show that all S5-valid sentences are provable in the axiomatic calculus for S5, which extends the calculus for T by the axiom schemas \(\Box A \to \Box \Box A\) and \(\Diamond A \to \Box \Diamond A\). (The second schema alone would be sufficient, as I mentioned in chapter 1, but it doesn’t hurt to have the first.) The argument is by contraposition: We suppose that some sentence is not S5-provable and show that it is not S5-valid.

Suppose \(A\) is not S5-provable. Then \(\{ \neg A \}\) is S5-consistent. It follows by Lindenbaum’s Lemma that \(\{ \neg A \}\) is included in some maximal S5-consistent set \(\Gamma \). By definition of canonical models, this set is a world in the canonical model \(M_{S5}\) for S5. Since \(\neg A\) is in \(\Gamma \), it follows from the Canonical Model Lemma that \(M_{S5},\Gamma \models \neg A\). So \(M_{S5},S \not \models A\).

It remains to show that the accessibility relation in \(M_{S5}\) has the right formal properties. We know that a sentence is S5-validity iff it is valid in the class of Kripke models whose accessibility relation is an equivalence relation. So we will show that the accessibility relation in \(M_{S5}\) is reflexive, transitive, and symmetric.

By definition, a world \(v\) in a canonical model is accessible from \(w\) iff whenever \(\Box A \in w\) then \(A \in v\). Since the worlds in \(M_{S5}\) are maximal S5-consistent sets of sentences, and every such set contains every instance of the (T)-schema \(\Box A \to A\), there is no world in \(M_{S5}\) that contains \(\Box A\) but not \(A\). So every world in \(M_{S5}\) has access to itself.

For transitivity, suppose for some worlds \(w,v,u\) in \(M_{S5}\) we have \(wRv\) and \(vRu\). We need to show that \(wRu\). Given how \(R\) is defined in \(M_{S5}\), we have to show that \(u\) contains all sentences \(A\) for which \(w\) contains \(\Box A\). So let \(A\) be an arbitrary sentence for which \(w\) contains \(\Box A\). Since every world in \(M_{S5}\) contains every instance of \(\Box A \to \Box \Box A\), we know that \(w\) also contains \(\Box \Box A\). From \(wRv\), we can infer that \(v\) contains \(\Box A\). And from \(vRu\), we can infer that \(u\) contains \(A\).

For symmetry, suppose for some worlds \(w,v\) in \(M_{S5}\) we have \(wRv\) and not \(vRw\). Given how \(R\) is defined, this means that there is some sentence \(A\) for which \(\Box A\) is in \(v\) but \(\neg A\) is in \(w\). Since \(w\) contains the T-provable sentence \(\neg A \to \Diamond \neg A\) and the (5)-instance \(\Diamond \neg A \to \Box \Diamond \neg A\), it also contains \(\Box \Diamond \neg A\). So \(v\) contains \(\Diamond \neg A\). This contradicts the assumption that \(v\) is S5-consistent, given that \(v\) contains \(\Box A\).

Exercise 4.13 (a) Method A from exercise 4.1 is sound and complete for \(X\). (b) No set of \(\mathfrak {L}_{M}\)-sentences is \(X\)-consistent, but every Kripke model must have at least one world.

Exercise 4.14 Let \(\Gamma \) be an infinite set of \(\mathfrak {L}_{M}\)-sentences. If \(\Gamma \) is K-satisfiable then obviously every finite subset of \(\Gamma \) is satisfiable as well. For the converse direction, assume \(\Gamma \) is not K-satisfiable: There is no world in any Kripke model at which all members of \(\Gamma \) are true. Then there is no world in any Kripke model at which all members of \(\Gamma \) are true while \(p \land \neg p\) is false. So \(\Gamma \models p\land \neg p\). By the compactness theorem, it follows that there is a finite subset \(\Gamma ^{-}\) for which \(\Gamma ^{-} \models p \land \neg p\). If \(\Gamma ^{-} \models p \land \neg p\) then there is no world in any Kripke model at which all members of \(\Gamma ^{-}\) are true while \(p \land \neg p\) is false. Since \(p\land \neg p\) is false at every world in every Kripke model, it follows that there is no world in any Kripke model at which all members of \(\Gamma ^{-}\) are true. This shows that if \(\Gamma \) is not K-satisfiable then there is a finite subset (\(\Gamma ^{-}\)) of \(\Gamma \) that is not K-satisfiable. Conversely, if every finite subset of \(\Gamma \) is K-satisfiable then \(\Gamma \) is K-satisfiable.

Exercise 4.15 Suppose there is a proof of \(\neg \Box (p \land \neg p)\). By (CPL), we can infer \(\Box (p \land \neg p) \to (p \land \neg p)\), because \(A \to B\) is a truth-functional consequence of \(\neg A\). By (Nec), we get \(\Box (\Box (p \land \neg p) \to (p \land \neg p))\). By (GL) and modus ponens (an instance of (CPL)), we can derive \(\Box (p \land \neg p)\).

Exercise 5.1 For an agent who knows all truths only the actual world is epistemically accessible. For an agent who knows nothing all worlds are epistemically accessible.

Exercise 5.2

(a)

\(\mathsf {K}(r \lor s)\)
\(r\): It is raining; \(s\): It is snowing

(b)

\(\mathsf {K} r \lor \mathsf {K} s\)
\(r\): It is raining; \(s\): It is snowing

(c)

\(\mathsf {K} r \lor \mathsf {K} \neg r\)
\(r\): It is raining

(d)

This sentence is ambiguous. On one reading, it could be translated as \(\mathsf {M} g\to \mathsf {K} g\), on the other as \(\mathsf {K}(\mathsf {M} g \to g)\)
\(g\): You are guilty

Exercise 5.3 You can use umsu.de/trees/ to create the tree proof. We can assume S5 for the box because it quantifies unrestrictedly over all worlds (as in chapter 2).

Exercise 5.4 (NT) is valid on all and only the frames in which no world can see any world.

Exercise 5.5 We assume that ignorance of \(A\) can be formalized as \(A \land \neg \mathsf {K} A\). Ignorance of ignorance of \(A\) is therefore formalized as \((A \land \neg \mathsf {K} A) \land \neg \mathsf {K}(A \land \neg \mathsf {K} A)\). A tree proof shows that the former K-entails the latter.

Exercise 5.6 In a Gettier case, the relevant proposition \(p\) (say, that you’re looking at a barn) is true but unknown. By (0.4), it would follow that the agent knows that they don’t know \(p\). But in a typically Gettier case the agent does not know that they don’t know \(p\).

Exercise 5.7 All except (a) and (d) are correct. You can find trees or counterexamples for (a)-(e) on umsu.de/trees/ if you write \(\mathsf {K}\) as a box and \(\mathsf {M}\) as a diamond. Here is a tree for (f):

Exercise 5.8 see https://plato.stanford.edu/entries/dynamic-epistemic/appendix-B-solutions.html (where all the dates are 10 days later than they are in my version).

Exercise 5.9 (a) and (b) are valid, (c) and (d) are invalid. Here is a tree proof for (a).

The tree for (c) doesn’t close:

We could add a few more applications of Reflexivity, but the tree would remain open. It also gives us a countermodel: let \(W\) = \(\{ w,v,u \}\); \(w\) has 1-access to \(v\) and \(u\); each world has 1- and 2-access to itself; \(V(p) = \{ v \}\). In this model, at world \(w\), \(\mathsf {M}_1\mathsf {K}_2 p\) is true while \(\mathsf {M}_2\mathsf {K}_1 p\) is false.

Cases (b) and (d) are similar.

Exercise 5.10 The (5)-schema for \(\mathsf {E}_G\) states that \(\neg \mathsf {E}_G \neg A \to \mathsf {E}_G \neg \mathsf {E}_G \neg A\). To show that some instance of this is invalid, we need to find a case where some instance of \(\neg \mathsf {E}_G \neg A\) is true while \(\mathsf {E}_G \neg \mathsf {E}_G \neg A\) is false. We can take the simplest instance, with \(A=p\). Assume the relevant group has two agents, and consider a world \(w\) at which \(\mathsf {K}_1 \neg p\) and \(\neg \mathsf {K}_2 \neg p\) are true. By the assumption that (5) is valid for \(\mathsf {K}_i\), \(\mathsf {K}_2\neg \mathsf {K}_2\neg p\) is also true at \(w\). But \(\mathsf {K}_1\neg \mathsf {K}_2\neg p\) can be false (at \(w\)). If it is, then \(\neg \mathsf {E}_G \neg p\) is true at \(w\) while \(\mathsf {E}_G \neg \mathsf {E}_G \neg p\) is false.

Exercise 5.11 No, a transitive, serial, and euclidean relation is not always symmetric. Counterexample: wRv, vRv. This means that not all instances of (B) (which corresponds to symmetry) are valid in KD45.

Exercise 5.12 You can e.g. do a tree proof, using \(\mathsf {B}\) as the box.

Exercise 5.13 Let \(A\) be an arbitrary proposition.

By (PI), \(\mathsf {B} A \to \mathsf {K}\mathsf {B} A\) is valid. By (KB), so is \(\mathsf {K}\mathsf {B} A \to \mathsf {B}\mathsf {B} A\). By propositional logic, these entail \(\mathsf {B} A \to \mathsf {B}\mathsf {B} A\).

By (NI), \(\neg \mathsf {B} \neg A \to \mathsf {K}\neg \mathsf {B} \neg A\) is valid. By (KB), so is \(\mathsf {K}\neg \mathsf {B} \neg A \to \mathsf {B}\neg \mathsf {B} \neg A\). By propositional logic, these entail \(\neg \mathsf {B} \neg A \to \mathsf {B}\neg \mathsf {B} \neg A\).

Exercise 5.14 The left-to-right direction is (KB). For the right-to-left direction, let \(A\) be an arbitrary proposition. By (SB), \(\mathsf {B} A \to \mathsf {B}\mathsf {K} A\) is valid. By (D) for belief, \(\mathsf {B} \mathsf {K} A \to \neg \mathsf {B} \neg \mathsf {K} A\) is valid. The contraposition of (KB) gives us \(\neg \mathsf {B} \neg \mathsf {K} A \to \neg \mathsf {K}\neg \mathsf {K} A\). Finally, the contraposition of (5) for knowledge yields \(\neg \mathsf {K}\neg A \to \mathsf {K} A\). The target proposition \(\mathsf {B} A \to \mathsf {K} A\) is a truth-functional consequence of these four propositions.

Exercise 5.15 If the logic of belief is KD45 then \(\Box \Diamond p\) is equivalent to \(\Diamond p\) (as you can show, for example, with a tree proof).

Exercise 5.16 Suppose \(\mathsf {B}(p \land \neg \mathsf {B} p)\). In any logic that extends K, it follows that \(\mathsf {B} p\) and \(\mathsf {B} \neg \mathsf {B} p\). By (4), \(\mathsf {B} p\) entails \(\mathsf {B}\mathsf {B} p\). Now we have \(\mathsf {B} \neg \mathsf {B} p\) and \(\mathsf {B}\mathsf {B} p\), which violates (D).

Exercise 6.1

(a)

\(\mathsf {O} \neg p\); \(p\): You go into the garden.

(b)

\(\mathsf {O} \neg p\); \(p\): You go into the garden.

(c)

\(\mathsf {O} p\); \(p\): Jones helps his neighbours.

(d)

\(\mathsf {O} (p \to q)\); \(p\): Jones helps his neighbours, \(q\): Jones tells his neighbours that he’s coming.

(e)

You might try \(\mathsf {O} (\neg p \to \neg q)\) or \(\neg p \to \mathsf {O} \neg q\) \(p\): Jones helps his neighbours, \(q\): Jones tells his neighbours that he’s coming.

See section 6.3, especially exercise 6.14, for why neither translation of (e) is fully satisfactory.

Exercise 6.2 No, not unless all (or no) worlds are ideal. If \(w\) is ideal and \(v\) is not, then \(wRv\) but not \(vRw\).

Exercise 6.3 \(R\) is euclidean if \(\forall x \forall y \forall z((xRy \land xRz) \to yRz)\). Suppose \(wRv\). Instantiating the universal formula with \(w\) for \(x\) and with \(v\) for \(y\) and \(z\), we have \((wRv \land wRv) \to vRv\). So \(vRv\).

Exercise 6.4 Let \(w\) be a world in which the only relevant norm is that one must drive on the left. Let \(v\) and \(u\) be worlds in which everyone drives on the left even though the law requires driving on the right. Both \(v\) and \(u\) are accessible from \(w\), but \(u\) is not accessible from \(v\), and \(v\) is not accessible from itself.

Exercise 6.5 Use https://www.umsu.de/trees/. (Write \(\mathsf {O}\) as a box and \(\mathsf {P}\) as a diamond. For D, make the accessibility relation serial; for KD45, make it serial, transitive, and euclidean.)

Exercise 6.6 (Dual1) says that \(\neg \Diamond A\) is equivalent to \(\Box \neg A\). If nothing is permitted then \(\neg \Diamond A\) is true for all \(A\). But if nothing is forbidden then \(\Box \neg A\) is false for all \(A\).

(Dual2) says that \(\neg \Box A\) is equivalent to \(\Diamond \neg A\). If nothing is forbidden then \(\neg \Box A\) is true for all \(A\). But if nothing is permitted then \(\Diamond \neg A\) is false for all \(A\).

Exercise 6.7 We assume that every world has some norms. (See the previous exercise.) Suppose a world \(v\) is accessible from a world \(w\), meaning that \(v\) conforms to the norms of \(w\). Since the norms are intolerant, the norms at \(v\) must be the same as at \(w\). So whatever is accessible from \(v\) is accessible from \(w\). It follows that the accessibility relation is transitive and euclidean. (In fact, the complete relativist logic of intolerant norms is KD45.)

Note that the absolutist approach validates schemas like \(\mathsf {O} A \to \mathsf {O}\mathsf {O} A\) without assuming that the norms say anything about whether they should be in force.

Exercise 6.8 \(\mathsf {P} A\) could be defined as \(\neg \Box (\mathsf {N} \to \neg A)\), or more simply (and equivalently) as \(\Diamond (\mathsf {N} \land A)\).

Exercise 6.9 In the Leibnizian language, the (U)-schema turns into \(\Box (\mathsf {N} \to (\Box (\mathsf {N} \to A) \to A))\). You can use a tree proof to show that this is T-valid. (See umsu.de/trees/.)

Exercise 6.10 In the described situation, it ought to be the case that Amy is either obligated to help Betty or obligated to help Carla, but Amy is neither obligated to help Betty nor to help Carla. So if \(p\) translates ‘Amy helps Betty’ and \(q\) ‘Amy helps Carla’, we seem to have \(\mathsf {O}(\mathsf {O} p \lor \mathsf {O} q)\) and \(\neg \mathsf {O} p\) and \(\neg \mathsf {O} q\). But these assumptions are inconsistent in K5. You can draw a K5-tree (using the K-rules and the Euclidity rule) starting with \(\mathsf {O}(\mathsf {O} p \lor \mathsf {O} q)\) and \(\neg \mathsf {O} p\) and \(\neg \mathsf {O} q\) on which all branches close. This shows that there is no world in any euclidean model at which the three assumptions are true.

Exercise 6.11 Since we assume that there is always at least one best world among the accessible worlds, and the accessible worlds comprise just one world, it follows that \(\mathsf {O} A\) is true at \(w\) iff \(A\) is true at \(w\). The logic we get is the “Triv” logic that is axiomatized by adding the (Triv)-schema \(\Box A \leftrightarrow A\) to the standard axioms and rules for K. This logic is stronger than S5: all S5-valid sentences are Triv-valid. We also have, among other things, all instances of \(\Box A \leftrightarrow \Diamond A\). The choice between absolutism and relativism makes no difference.

Exercise 6.12 Use umsu.de/trees/.

Exercise 6.13 Deontic detachment is valid. Suppose \(A\) is true at the best of the (circumstantially) accessible worlds, and \(B\) is true at the best of the accessible worlds at which \(A\) is true. Then \(B\) is true at the best of the accessible worlds.

Factual detachment is invalid. A counterexample is the “gentle murder puzzle”. Suppose John is determined to kill his grandmother. If he will go ahead and kill her, he ought to do so gently. Can we conclude that John ought to gently kill his grandmother? Arguably not. He shouldn’t kill her at all! We have \(k\) and \(\mathsf {O}(g/k)\), but not \(\mathsf {O}(g)\). Formally, \(g\) is true at the best of the accessible \(k\)-worlds, but since all the \(k\)-worlds are quite bad, \(g\) is not true at the best of the accessible worlds.

Exercise 6.14 (c) can obviously be translated as \(\mathsf {O} p\), (f) as \(\neg p\).

You probably translated (d) as either \(p \to \mathsf {O} q\) or as \(\mathsf {O}(p \to q)\). \(p \to \mathsf {O} q\) is entailed by (f), so it violates the non-entailment condition. Assume then that (d) is translated as \(\mathsf {O}(p \to q)\).

The most obvious translations for (e) are \(\neg p \to \mathsf {O}\neg q\) and \(\mathsf {O}(\neg p \to \neg q)\). The latter is entailed by (c). If we choose the former, then (c)–(f) constitute a deontic dilemma: (e) and (f) would entail \(\mathsf {O} \neg t\), but (c) and (d) would entail \(\mathsf {O} t\).

Exercise 6.15 Simply replace ‘all’ in the semantics for \(\mathsf {O}(B/A)\) with ‘some’.

Exercise 6.16 Ross’s Paradox: ‘Alice must be in the office or in the library’ seems to imply that Alice might be in the office and that she might be in the library.

The Paradox of Free Choice: ‘Alice might be in the office or in the library’ seems to imply that Alice might be in the office and that she might be in the library.

Exercise 6.17 For every world \(w\), every member of \(N(w)\) contains \(w\).

Exercise 6.18 In Kripke semantics, \(\Box p\) and \(\Box q\) together entail \(\Box (p \land q)\). But if the probability of \(p\) is above the threshold and the probability of \(q\) is above the threshold, it does not follow that the probability of \(p\land q\) is above the threshold. For example, we could have Pr\((p)=0.95\), Pr\((q)=0.94\), and Pr\((p \land q) = 0.95 \times 0.94 = 0.893\).

Exercise 7.1

(a)

\(\mathsf {H} \neg p\)
\(p\): It is warm

(b)

\(\mathsf {F} p\)
\(p\): There is a sea battle

(c)

\(\neg \mathsf {F} \mathsf {P} p\) or, perhaps, \(\mathsf {F}\neg \mathsf {P} p\)
\(p\): There is a sea battle

(d)

\(\mathsf {F}(p \lor \mathsf {P} q)\) or \(\mathsf {F}(\mathsf {F} p \lor \mathsf {F}\mathsf {P} q)\)
\(p\): It is warm

(e)

\(\neg \mathsf {P} p \to \neg \mathsf {F} q\) or \(\mathsf {G}(\neg \mathsf {P} p \to \neg q)\)
\(p\): You study, \(q\): you pass the exam

(f)

\(\mathsf {P}(p \land q)\)
\(p\): I am having tea, \(q\): the door bell rings

Exercise 7.2 (a), (c), (f), (g), and (h) are true, (b), (d), and (e) are false.

Exercise 7.3 (Con1): Suppose some sentence of the form \(A \to \mathsf {G}\mathsf {P} A\) is false at some time \(t\) in some temporal model. By clause (e) of definition 7.2, this means that \(A\) is true at \(t\) and \(\mathsf {G}\mathsf {P} A\) is false at \(t\). By clause (h), the latter means that there is a time \(s\) with \(t<s\) such that \(\mathsf {P} A\) is not true at \(s\). By clause (i), it follows that \(A\) is not true at \(t\). Contradiction.

The argument for (Con2) is analogous.

Exercise 7.4

(a)

(b)

(c)

(d)

(e)

Exercise 7.5 Suppose < is transitive, and \(x > y\) and \(y > z\). Equivalently, \(y < x\) and \(z < y\).By transitivity of <, we have \(z < x\). So \(x > z\).

Exercise 7.6 Suppose \(R\) is transitive. If there are points \(x\) and \(y\) for which \(xRy\) and \(yRx\) then \(xRx\) by transitivity. So if \(R\) isn’t asymmetric then it isn’t irreflexive. If \(R\) isn’t irreflexive then there is a point \(x\) with \(xRx\). This violates asymmetry, because asymmetry demands that if \(xRx\) then not \(xRx\).

Exercise 7.7 If time is transitive and circular, then it is neither asymmetric nor irreflexive.

Exercise 7.8 (a), (d), and (e) are invalid. Here are trees for (b), (c), and (f). I can’t typeset the one for (g).

(b)

(c)

(f)

Exercise 7.9

(a)

For example, \(\mathsf {G} A \to \mathsf {F} A\).

(b)

For example, \(\mathsf {H} A \to \mathsf {P} A\).

(c)

No schema corresponds to the class of frames with a last time. If we also assume linearity, \(\mathsf {G}(A \land \neg A) \lor \mathsf {F}\mathsf {G}(A \land \neg A)\) works.

(d)

No schema corresponds to the class of frames with a first time. If we assume linearity, then \(\mathsf {H}(A \land \neg A) \lor \mathsf {P}\mathsf {H}(A \land \neg A)\) works.

Exercise 7.10 Assume a frame is dense. Suppose for reductio that some instance of \(\mathsf {F} A \to \mathsf {F}\mathsf {F} A\) is false at some point \(t\) in some model \(M\) based on that frame. Then \(\mathsf {F} A\) is true at \(t\) and \(\mathsf {F}\mathsf {F} A\) is false. Since \(\mathsf {F} A\) is true at \(t\), it follows by definition 7.2 that \(A\) is true at some point \(s\) such that \(t<s\). By density, there is a point \(r\) such that \(t<r<s\). But since \(A\) is true at \(s\), \(\mathsf {F} A\) is true at \(r\), and so \(\mathsf {F}\mathsf {F} A\) is true at \(t\); contradiction.

In the other direction, we have to show that if a frame isn’t dense then some instance of \(\mathsf {F} A \to \mathsf {F}\mathsf {F} A\) is false at some point \(t\) in some model \(M\) based on that frame. We take the simplest instance \(\mathsf {F} p \to \mathsf {F}\mathsf {F} p\). If a frame isn’t dense then there are points \(t,s\) such that \(t<s\) and no point lies in between \(t\) and \(s\). Let \(V\) be an interpretation function that makes \(p\) true at \(s\) and false everywhere else. Then \(\mathsf {F} p\) is true at \(t\) but \(\mathsf {F}\mathsf {F} p\) is false. So \(\mathsf {F} p \to \mathsf {F}\mathsf {F} p\) is false at \(t\).

Exercise 7.11 Without assumptions about the flow of time there is no way to express in \(\mathfrak {L}_T\) that \(p\) is true at all times (or at some time). In linear flows, \(p \land \mathsf {H} p \land \mathsf {G} p\) does the job.

Exercise 7.12 Consider a model with three times ordered by \(s<t\) and \(s<r\). Assume \(p\) is true at \(t\) and not at \(r\). Then \(p \to \mathsf {H}\mathsf {F} p\) is false on the Peircean interpretation.

Exercise 7.13 (a)–(d) are valid, (e) is invalid.

To show that a schema is valid, assume for reductio that there is some time \(t\) on some history \(H\) in some model \(M\) at which the schema is false. Then (repeatedly) use definition 7.3 to derive a contradiction.

For (e), consider a model with three times \(t,s,r\) such that \(s < t\), \(r< t\), and neither \(s < r\) nor \(r< s\). Let \(q\) be true at \(s\) and false at the other two times. \(\mathsf {P} q \to \Box \mathsf {P} \Diamond q\) is false at \(t\) on the history \(\langle s,t \rangle \).

Exercise 7.14 A sentence \(A\) is super-valid iff \(M,t \models A\) for all temporal models \(M\) and times \(t\) in \(M\). By supervaluationism, this holds iff \(M,H,t \models A\) for all \(M,t\), and histories \(H\) containing \(t\). That’s how Ockhamist validity was originally defined.

Exercise 7.15 Ockham-entailment is stronger than super-entailment: whenever \(A\) Ockham-entails \(B\), then \(A\) super-entails \(B\), but not the other way around.

Suppose \(A\) Ockham-entails \(B\). Let \(t\) be any time in any temporal model at which \(A\) is true, i.e.: true relative to all histories through \(t\). Since \(A\) Ockham-entails \(B\), \(B\) is true at \(t\) relative to all histories through \(t\). So \(A\) super-entails \(B\).

But suppose \(A\) super-entails \(B\). Let \(t\) be any time on any history \(h\) in any temporal model at which \(A\) is true. We can’t infer that \(B\) is true at \(t\) on \(h\), for \(A\) may be false at \(t\) relative to other histories \(h'\). So we can’t infer that \(A\) Ockham-entails \(B\). Indeed, \(\mathsf {F} p\) super-entails \(\Box \mathsf {F} p\), but \(\mathsf {F} p\) does not Ockham-entail \(\Box \mathsf {F} p\).

Exercise 7.16 \((A \land \neg A) \mathsf {U} A\).

Exercise 7.17 \(\mathsf {A} p \to p\).

Exercise 8.1 (E1)–(E5) are invalid assuming that ‘if \(A\) then \(B\)’ is true iff both \(A\) and \(B\) are true. There are, of course, strong reasons against the analysis of English conditionals as conjunctions.

Exercise 8.2 For example: \(\neg A \,\unicode {x297D}\, A\) or \((A\lor \neg A) \,\unicode {x297D}\, A\).

Exercise 8.3 \(W = \{ w \}\), \(R = \emptyset \), \(V(p) = \{ w \} \), \(V(q)=\emptyset \).

Exercise 8.4 Use umsu.de/trees/.

Exercise 8.5 (E1)–(E5) all work equally well in the subjunctive mood. For (E4) and (E5):

• If our opponents had been cheating, we would never have found out. Therefore: If we had found out that our opponents are cheating, then they wouldn’t have been cheating.

• If you had added sugar to your coffee, it would have tasted good. Therefore: If you had added sugar and vinegar to your coffee, it would have tasted good.

Both of these inferences are valid if subjunctive conditionals are strict conditionals. But they don’t sound good.

Exercise 8.6 Suppose \(A \to B\) is assertable. Then \(A\to B\) is known. So \(\mathsf {K} (A \to B)\). In S4, it follows that \(\mathsf {K}\mathsf {K}(A \to B)\). So the epistemically strict conditional \(\mathsf {K}(A \to B)\) is assertable. Conversely, if \(\mathsf {K}(A \to B)\) is assertable, then it is known; so \(\mathsf {K}\mathsf {K}(A \to B)\). In S4, it follows that \(\mathsf {K}(A \to B)\). So \(A \to B\) is assertable.

Exercise 8.7 The ‘or-to-if’ inference is not valid on the assumption that the conditional is epistemically strict. For example, if \(p\) and \(q\) are both true at the actual world and both false at some epistemically accessible world, then ‘\(p\) or \(q\)’ is true but ‘if \(p\) then \(q\)’ is false (on the strict analysis).

The inference might nonetheless look reasonable because it would normally be inappropriate to assert a disjunction ‘\(p\) or \(q\)’ unless the disjunction is known – unless it is true at all epistemically accessible worlds. And if \(p \lor q\) is true at all epistemically accessible worlds then \(\neg p \to q\) is also true at all epistemically accessible worlds, and so \(\Box (\neg p \to q)\) is true. Thus the conclusion of or-to-if is true in any situation in which the premise is assertable. If the logic of knowledge validates the (4)-schema, we can go further and say that the conclusion is assertable in any situation in which the premise is assertable.

Exercise 8.8 Assume that \(R\) is asymmetric and quasi-connected. We want to show that \(R\) is transitive. So assume we have \(xRy\) and \(yRz\). By quasi-connectedness, \(yRz\) implies that either \(yRx\) or \(xRz\). By asymmetry, we can’t have \(yRx\), since we have \(xRy\). So \(xRz\).

Exercise 8.9 We have the following equivalences (using ‘\(\mathfrak {L}eftrightarrow\)’ to mean that the expressions on either side are equivalent): \[ u \npreceq _w v \mathfrak {L}eftrightarrow \neg (u \preceq _w v) \mathfrak {L}eftrightarrow \neg (v \nprec _w u) \mathfrak {L}eftrightarrow v \prec _w u. \] So you can simply replace every instance of \(\omega \prec _{w} \nu \) in the conditions by \(\nu \npreceq _{w} \omega \), and every instance of \(\omega \nprec _{w} \nu \) by \(\nu \preceq _{w} \omega \).

Asymmetry thereby turns into: if \(u \npreceq _{w} v\) then \(v \preceq _{w} u\). Equivalently: either \(u \preceq _{w} v\) or \(v \preceq _{w} u\). This property of relations is called completeness. Notice that it entails reflexivity.

Quasi-connectedness turns into: if \(u \npreceq _{w} v\) then for all \(t\), either \(t \npreceq _{w} v\) or \(u \npreceq _{w} t\). This is equivalent to transitivity for \(\preceq \).

The Limit Assumption turns into: for any non-empty set of worlds \(X\) and world \(w\) there is a \(v\in X\) such that there is no \(u \in X\) with \(v \npreceq _{w} u\). Equivalently, for any non-empty set of worlds \(X\) and world \(w\) there is a \(v\in X\) such that \(v \preceq _{w} u\) for all \(u\in X\).

Exercise 8.10 No. We don’t want \(A\) and \(\mathsf {O}(B/A)\) to entail \(B\). Semantically, we don’t want to assume that every world is among the best worlds relative to its own norms.

Exercise 8.11 Suppose \(A \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow B\) is true at some world \(w\) in some model \(M\). So \(B\) is true at all the closest \(A\)-worlds to \(w\). Now either \(A\) is true at \(w\) or \(A\) is false at \(w\). If \(A\) is false at \(w\), then \(A\to B\) is true at \(w\). If \(A\) is true at \(w\), then \(w\) is one of the closest \(A\)-worlds to \(w\), by Weak Centring; so \(B\) is true at \(w\); and so \(A\to B\) is true at \(w\). Either way, then, \(A\to B\) is true at \(w\).

Exercise 8.12 If \(A\) is true at no worlds, then \(\mathrm {Min}^{\prec _w}(\{u: M,u\models A\})\) is the empty set. So it is vacuously true that \(M,v \models B\) for all \(v \in \mathrm {Min}^{\prec _w}(\{ u: M,u \models A \})\).

Exercise 8.13 (E1) is an inference from \(q\) to \(p \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow q\). To show that this is invalid, we need to give a model in which \(q\) is true at some world (\(w\)) while \(p \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow q\) is false (at \(w\)).

This model also shows that (E2) and (E3) are invalid. (E2) is an inference from \(\neg p\) to \(p \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow q\). In the model, \(\neg p\) is true at \(w\) but \(p \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow q\) is false. (E3) is an inference from \(\neg (p \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow q)\) to \(p\). In the model, \(\neg (p \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow q)\) is true at \(w\) but \(p\) is false.

(E4) is an inference from \(p \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow q\) to \(\neg q \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow \neg p\). In the following model, the premise is true at \(w\) and the conclusion false.

Exercise 8.14 Frances has never learnt a foreign language, although she would have loved to learn French. If Frances had been given a choice between learning French and learning Italian, she would have chosen French. If Frances had learned French or Italian then she would have learned French. It does not follow that if Frances had learned Italian then she would have learned French.

The same style of example works for indicative conditionals.

Exercise 8.15

(a)

Assume \(A\land B\) is true at some world \(w\) in some model \(M\). By Centring, \(w\) is among the closest \(A\)-worlds to \(w\). By connectedness, \(w\) is the unique closest \(A\)-world to \(w\). So \(B\) is true at all closest \(A\)-worlds to \(w\).

(b)

Assume \(A \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow (B\lor C)\) is true at some world \(w\) in some model \(M\). So all the closest \(A\)-worlds to \(w\) are \((B\lor C)\)-worlds. If there are no \(A\)-worlds then \(A \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow B\) and \(A \mathrel {\mathop \Box }\mathrel {\mkern -2.5mu}\rightarrow C\) are both true. If there are \(A\)-worlds then Stalnaker’s semantics implies that there is a unique closest \(A\)-world \(v\) to \(w\). Since \(B\lor C\) is true at \(v\), either \(B\) or \(C\) must be true at \(v\). So either \(B\) is true at all closest \(A\)-worlds to \(w\) or \(C\) is true at all closest \(A\)-worlds to \(v\).

Exercise 8.16 ‘All dogs are barking’: \(\forall x(Dx \to Bx)\)
‘Some dogs are barking’: \(\exists x(Dx \land Bx)\)
‘Most dogs are barking’ cannot be translated in terms of \(\mathsf {M} x\). We need a binary quantifier: \(\mathsf {M} x(Bx / Dx)\)

Exercise 8.17 On this proposal, bare indicative conditionals like (8) are material conditionals. If \(p\) is true and \(q\) is false then there is an accessible \(p\)-world at which \(q\) is false, and so \(q\) is not true at all accessible worlds at which \(p\) is true. In all other cases, \(q\) is true at all accessible worlds at which \(p\) is true.

Exercise 8.18 Conditional Excluded Middle is valid iff there is never more than one closest/accessible \(A\)-world. On that assumption, ‘some closest/accessible \(A\)-world is a \(B\)-world’ entails ‘all closest/accessible \(A\)-worlds are \(B\)-worlds’. But (10) does not entail ‘If I had played the lottery, I would have won’.

Exercise 9.1

(a)

\(Srj \land Skj\); \(r\): Keren, \(k\): Keziah, \(j\): Jemima, \(S\): – is a sister of –

(b)

\(\forall x (Mx \to Ox)\); \(M\): – is a myriapod, \(O\): – is oviparous

(c)

\(\exists x (Cx \land Nx \land Hfx)\); \(f\): Fred, \(C\): – is a car, \(N\): – is new, \(H\): – has –

(d)

\(\neg \forall x (Sx \to Lxl)\); \(l\): logic; \(S\): – is a student, \(L\): – loves –

(e)

\(\forall x ((Sx \land Lxl) \to \exists y Lxy)\); \(l\): logic; \(S\): – is a student, \(L\): – loves –

Exercise 9.2 Let the model \(M\) be given by \(D = \{ \text {Rome}, \text {Paris} \}\) and \(V(F) = \{ \text {Rome} \}\). By clause (a) of definition 9.2, \(M,g' \models Fx\) holds for every assignment function \(g'\) that maps \(x\) to Rome, because then \(g'(x) \in V(F)\). By clause (h) it follows that \(M,g \models \exists x Fx\) for every assignment function \(g\). By clause (a) again, \(M, g' \not \models Fx\) for every assignment function \(g'\) that maps \(x\) to Paris. By clause (g), it follows that \(M,g \not \models \forall x Fx\) for every assignment function \(g\). So \(\exists x Fx\) is true (in \(M\)) relative to every assignment function while \(\forall x Fx\) is false relative to every assignment function. By clause (e) it follows that \(\exists x Fx \to \forall x Fx\) is false in \(M\) relative to every assignment function.

Exercise 9.3 For both cases, use \(Fx\) as the sentence \(A\), and \(\neg Fx\) as \(B\), and consider a model in which \(F\) applies to some but not to all individuals. Both \(Fx\) and \(\neg Fx\) are then true relative to some assignment functions and false relative to others. So neither sentence is true in the model. But \(Fx \lor \neg Fx\) is true relative to every assignment function.

Exercise 9.4 (a) There are many non-reflexive models in which \(\Box p \to p\) is true at some world – for example, any non-reflexive model in which \(p\) is false at all worlds.

(b) Let \(M_1\) be a model with a single world that can see itself. Let \(M_{2}\) be a model with two worlds, each of which can see the other but not itself. In both models, all sentence letters are false at all worlds. The very same \(\mathfrak {L}_M\)-sentences are true at all worlds in these models (as a simple proof by induction shows). But the first model is reflexive and the second isn’t. So there is no \(\mathfrak {L}_{M}\)-question that is true at a world in a model iff the model’s accessibility relation is reflexive.

Exercise 9.5 Use umsu.de/trees/.

Exercise 9.6 If a sentence is valid (in first-order predicate logic) then a fully expanded tree for the sentence will close and show that the sentence is valid. But if a sentence is not valid, the tree might grow forever. There is no algorithm for detecting whether a tree will grow forever.

Exercise 9.7

(a)

\(\Box Fa\)
\(a\): John, \(F\): – is hungry.
(Might be classified as either de re or de dicto.)

(b)

\(\Box \forall x(Fx \to Gx)\)
\(F\): – is a cyclist, \(G\): – has legs.
This is de dicto. Also correct (but different in meaning) is the de re translation \(\forall x (Fx \to \Box Gx)\). Close but incorrect (and de re): \(\forall x \Box (Fx \to Gx)\).

(c)

\(\forall x (Fx \to \Diamond Gx)\)
\(F\): – is a day, \(G\): – is our last day.
Better: \(\forall x (Fx \to \Diamond (Hx \land \neg \exists y(Fy \land Lyx \land Hy)))\)
\(F\): – is a day, \(L\): – is later than –, \(H\): We are alive on –.

Both de re. The English sentence could also be understood de dicto, as \(\Diamond \forall x (Fx \to Gx)\), but that would be a very strange thing to say.

(d)

I would translate this as \(\forall x \mathsf {O}(Fx \to Gx)\)
\(F\): – wants to leave early, \(G\): – leaves quietly.
Even better, if we can use the conditional obligation operator: \(\forall x \mathsf {O}(Gx / Fx)\). Also defensible are \(\forall x (Fx \to \mathsf {O} Gx)\) and \(\mathsf {O}\forall x(Fx \to Gx)\).

All of these are de re.

(e)

\(\forall x (\exists y (Fy \land Hxy) \to \mathsf {P} Gx)\)
\(F\): – is a ticket, \(G\): – enters, \(H\): – bought –.
Perhaps even better: \(\forall x \mathsf {P}(Gx/ \exists y (Fy \land Hxy))\). Both of these are de re.
You could translate ‘bought a ticket’ as a simple predicate here; you could also use a temporal operator to account for the past tense of ‘bought’ (but it’s confusing to use two different kinds of ‘\(\mathsf {P}\)’ in one sentence).

Exercise 9.8 See the previous answer.

Exercise 9.9 Use umsu.de/trees/.

Exercise 9.10 We assume that some branch on a tree contains nodes \(\eta _1=\eta _2\) and \(A\). We have to show that we can add \(A[\eta _1/\!/\eta _2]\) without using the second version of Leibniz’ Law.

Exercise 9.11

(a)

\begin {align*} 1. \quad & a=a &&\text { (SI)}\\ 2. \quad & \forall x\, x\not = a \to a\not = a &&\text { (UI)}\\ 3. \quad & \neg \forall x\, x\not =a &&\text { (1, 2, CPL)}\\ 4. \quad & \neg \exists x\, x=a \leftrightarrow \forall x \, x\not =a &&\text { ($\forall \exists $)}\\ 5. \quad & \exists x\, x=a &&\text { (3, 4, CPL)}\\ 6. \quad & \Box \exists x\, x=a &&\text { (5, Nec)} \end {align*}

(b)

There are many correct answers. For example: historians debate whether Homer ever existed. If \(a\) translates ‘Homer’ then \(\exists x\, x=a\) is arguably false if Homer isn’t a real person. Since the available evidence is compatible with \(\neg \exists x\, x=a\), the sentence \(\Box \exists x\, x=a\) is false on an epistemic interpretation of the box.

Where does the proof go wrong? Each of steps 1, 2, and 6 might be blamed.

Exercise 9.12

(a)

\(\exists x \exists y(Fx \land Fy \land x\not =y \land \forall z(Fz \to (z=x \lor z=y)))\)

(b)

\(\forall x \forall y\forall z\forall v(Fx \land Fy \land Fz \land Fv \to (x=y \lor x=z \lor x=v \lor y=z \lor y=v \lor z=v))\)

Exercise 9.13 The de dicto reading of (a) can be translated as \begin {equation*} \Diamond \exists x (Px \land \forall y(Py \to x\!=\!y) \land x\!=\!c), \end {equation*} where ‘\(P\)’ translates ‘– is 45th US President’ and ‘\(c\)’ denotes Hillary Clinton. The de re reading can be translated as \begin {equation*} \exists x (Px \land \forall y(Py \to x\!=\!y) \land \Diamond x\!=\!c). \end {equation*} The answers to (b) and (c) are analogous.

Exercise 10.1 (a), (b), (d), and (f) are true; (c) and (e) are false.

Exercise 10.2 Use umsu.de/trees/. Note that the website uses slightly different identity rules: instead of the Self-Identity rule, it has a rule for closing any branch that contains a statement of the form \(\tau \not = \tau \).

Exercise 10.3

(a)

\(W=\{ w \}\), \(wRw\), \(D = \{ \text {Alice} \}\), \(V(F,w) = \{ \text {Alice} \}\), \(V(G,w) = \emptyset \)

(b)

\(W=\{ w,v \}\), \(wRw\) and \(wRv\), \(D = \{ \text {Alice}, \text {Bob} \}\), \(V(F,w) = \{ \text {Alice} \}\), \(V(F,v) = \{ \text {Bob} \}\)

(c)

\(W=\{ w,v \}\), \(wRw\) and \(wRv\), \(D = \{ \text {Alice}, \text {Bob} \}\), \(V(F,w) = \{ \text {Alice} \}\), \(V(F,v) = \emptyset \)

(d)

\(W=\{ w,v \}\), \(wRw\) and \(wRv\), \(D = \{ \text {Alice}, \text {Bob} \}\), \(V(P,w) = \{ \text {Alice} \}\), \(V(P,v) = \emptyset \), \(V(Q,w) = \{ \text {Alice} \}\), \(V(Q,v) = \emptyset \)

Exercise 10.4 \(\Box \forall x \exists y\, x\!=\!y \to \forall x \Box \exists y\, x\!=\!y\) is an instance of the Converse Barcan Formula. If we read the box as a relevant kind of circumstantial necessity, and Loafy could have failed to exist, then the consequent of this conditional is false. But the antecedent is true.

Exercise 10.5 (1) is equivalent to the Barcan Formula, (3) to the Converse Barcan Formula. (2) is highly implausible. (1) and (3) are often regarded as implausible, for the reasons I discuss in the text.

Curiously, (4) seems to be equivalent to the Converse Barcan Formula: it, too, is valid on a frame iff the frame has increasing domains. It also rules out scenarios in which individuals at one world may fail to exist at an accessible world.

Exercise 10.6

(a)

(b)

DIY. The tree has four branches. I can’t typeset it.

(c)

(d)

(e)

Exercise 10.7 In the definition of a model, we could allow the interpretation function to be undefined for some names. We might also allow the sets \(D_{w}\) to be empty. In the truth definition 10.4, we only need to clarify that \(M,w,g \not \models A\) for every atomic sentence \(A\) that contains a term \(\tau \) for which \([\tau ]^{M,g}\) is undefined.

Exercise 10.8 In the Superman case, Clark Kent and Superman are the same person, but Lois Lane doesn’t know that they are. So we appear to have \(c\!=\!s\) but not \(\Box \, c\!=\!s\). Similarly, in the Julius case, Julius and Whitcomb L. Judson are the same person, but one may well not know that they are. In the Goliath case, we have Lumpl = Goliath without it being metaphysically necessary that Lumpl = Goliath, as there are worlds in which Lumpl is a bowl and Goliath is not.

Exercise 10.9 ‘Lumpl’ might express a concept that maps every world \(w\) to a certain piece of clay at \(w\), where that piece is perhaps individuated by its matter or origin. The piece’s shape doesn’t matter. ‘Goliath’ might instead express a concept that maps every world \(w\) to a certain statue at \(w\), where the statue is perhaps individuated by its shape and origin.

Exercise 10.10 If we treat ’my body’ as a name, the premises are \(\Box \exists x\, x\!=\!i\) and \(\neg \Box \exists x\, x\!=\!b\). The conclusion is \(i\not =\!b\). This argument is CK-valid and VK-valid. (It is not valid in individual concept semantics.) It might be better to translate ’my body’ as a description. This would make the argument CK-invalid and VK-invalid.

Exercise 10.11 Translation: \(\exists x (Tx \land Wx \land \neg K Wx \land \neg K \neg Wx)\), where \(T\) translates ‘– is a ticket’ and ‘– will win’.

If variables are directly referential, then this sentence is true in any scenario in which I don’t know which ticket will win.

Exercise 10.12 To render \(\forall x \forall y (x\!=\!y \to \Box x\!=\!y)\) valid, we can restrict the eligible individual concepts in a model as follows. For any (eligible) individual concepts \(f\) and \(g\) and worlds \(w\) and \(v\), if \(wRv\) and \(f(w)=g(w)\) then \(f(v)=g(w)\). (We do not stipulate that if \(wRv\) and \(f(v)=g(v)\) then \(f(w)=g(w)\), which would render the necessity of distinctness valid.)