Homework 2

Note that when a problem asks you to “explain/justify” something, that is not asking for an answer as rigorous as when you are asked to “show/prove” something. And as we’ve discussed in class, when you are asked to prove something, we don’t expect it to be in a strict formal proof calculus, unless/until that’s what we specifically request. The kinds of proofs we’ve been doing on the board (with the steps made explicit enough), or that you’d submit for homework in a math class, are usually adequate.

Also, if two sentences are ever equivalent as a matter of propositional logic, you can simply say that. We don’t expect you to provide any further justification. Just be sure you’ve verified it for yourself.

Prove that if □ obeys a normal modal logic including axioms D and 4, then the “omissive Moore sentence” p ∧ ¬□p cannot be necessary (i.e. believed).

Suppose for reductio that □(p ∧ ¬□p). By Axiom M it follows that □p ∧ □¬□p. From the first conjunct and Axiom 4 we get □□p. But that and the second conjunct □¬□p violate Axiom D. So our supposition cannot be true.

Prove that in any normal modal logic containing Axiom 5, from the premise □(q ⊃ □q), it follows that ◊q ⊃ □q. Hints: Show that the premise is true iff □(¬□q ⊃ ¬q). Help yourself to the propositional tautology that □q ∨ ¬□q. Work from there to establising □q ∨ □¬q. Work from there to the conclusion. This problem comes from reconstructions of Anselm’s “ontological proof” that God exists.

Since it’s a theorem that (q ⊃ □q) iff (¬□q ⊃ ¬q), the Rule of Equivalents tells us that □(q ⊃ □q) iff □(¬□q ⊃ ¬q). Our premise is the left-hand side of this, the right-hand side is □(¬□q ⊃ ¬q).

We assume the disjunctive tautology □q ∨ ¬□q. From the second disjunct and Axiom 5, it follows that □¬□q. That plus the result of the previous paragraph and Axiom K would imply □¬q.

So our disjunctive tautology implies □q ∨ □¬q. This is logically equivalent to ¬□¬q ⊃ □q, that is to ◊q ⊃ □q.

We explained in class that some premises are counted as entailing a conclusion in a normal modal logic just in case for every model and every world in that model, if the premises are all true then so too is the conclusion. So to disprove an entailment, we find a model and world where the premises are all true but the conclusion is false. Disprove the following entailments:

□p ⊨ p (it should be clear from our discussions that the accessibility relation in your model will have to fail to be reflexive)

Let w1 be a world where p is false, and w2 a world where p is true. Suppose that w1 can see w2 but not itself. (For the purposes of Problem 17b, let’s also say that w2 can see w1 but not itself.) In this model, w1 is a world where □p is true but p is false.
p ⊨ □p

Consider the same model as in Problem 17a. In that model, w2 is a world where p is true but □p is false.
q ⊃ □q ⊨ ◊q ⊃ □q (if your counter-model has a right-Euclidean accessibility relation, it will show that the initial □ was essential to the proof in Problem 16)

Here’s one possibility. w1 has q false, and can access w2 and w3, which can each access themself and the other. In w2 q is true and in w3 q is false. In w1, the premise q ⊃ □q is true because q is false. At the same time, in w1 ◊q is true and □q is false, so the conclusion ◊q ⊃ □q is false.

Here’s another possibility. w1 has q false, and can access itself and w2, where q is true. w2 can access itself and w1. In w1, the premise q ⊃ □q is again true because q is false. At the same time, in w1 ◊q is true (because w2 is accessible) and □q is false (because w1 can access itself).

In both of these examples the accessibility relation happens to be right-Euclidean.

Your neighbor sees your solution to Problem 17b and says “Wait a minute, I thought it’s a rule for all normal modal logics that when you’ve got p as a theorem, you could then infer □p as another theorem. How is that compatible with what you just did?” How would you answer their question and resolve their confusion?

In Problem 17b, we were treating p as a sentence letter, so it wasn’t a theorem. The rule that when you’ve got some φ as a theorem (derivable from no premises), you can then infer □φ as a theorem, does not imply that when you merely have φ as a premise you can then infer □φ. Our counter-model showed that the latter inference is invalid when φ is a mere sentence letter.

Axiom D states □p ⊃ ¬□¬p, or equivalently, ¬(□p ∧ □¬p). A related sentence sometimes called “Axiom P” says ¬□⊥ (where ⊥ is a sentence logically guaranteed to be false). Prove that any normal modal logic contains Axiom D iff it contains Axiom P.

Proof of Axiom P using Axiom D: Since ⊤ is logically equivalent to ¬⊥, Axiom N plus the Rule of Equivalents gives us □¬⊥. From that and Axiom D, it follows that ¬□⊥.

Proof of Axiom D using Axiom P: Since ⊥ is logically equivalent to p ∧ ¬p, Axiom P plus the Rule of Equivalents gives us ¬□(p ∧ ¬p). Axiom Converse-M says □p ∧ □¬p ⊃ □(p ∧ ¬p). Since the result in the first sentence denied the consequent of this, it follows that ¬(□p ∧ □¬p), which is one of the formulations of Axiom D.

Cheryl’s Birthday. Albert and Bernard just met Cheryl. “When’s your birthday?” Albert asks her. Cheryl thinks a moment and says, “I’m not going to tell you, but I’ll give you some clues.” She writes down a list of ten dates: May 15, May 16, May 19, June 17, June 18, July 14, July 16, August 14, August 15, August 17. She says “My birthday is one of these dates.” Then Cheryl says she’ll whisper in Albert’s ear the month — and only the month — of her birthday, and she does so. Then Cheryl says she’ll whisper in Bernard’s ear the day — and only the day — of her birthday, and she does so.

“Can you figure it out now?” Cheryl asks Albert.

Albert answers, “I don’t know when your birthday is, but I know Bernard doesn’t know either.”

Bernard says, “I didn’t know originally, but now I do.”

Abert says, “Well, then now I know too!”

When is Cheryl’s birthday? Justify and explain your answer.

It’s helpful to make a table, for example with May through August labeling the columns and 14 through 19 labeling the rows. From Cheryl’s first clue, only 10 of the 24 cells are possible.

From Albert’s first answer, we learn that Cheryl didn’t tell him a month with only a single possible cell in it (there are no such months at this point, so that’s not news). We also learn that what Cheryl told him excludes the possibility that Bernard got into a position to know. If Cheryl had told Albert “May,” he couldn’t exclude the possibility that she told Bernard “19” enabling Bernard to deduce the single month with 19 as a possibility. If Cheryl had told Albert “June,” he couldn’t exclude the possibility that she told Bernard “18” enabling Bernard to deduce the single month with 18 as a possibility. Hence we can conclude that Cheryl didn’t tell Albert either of those months. Every date open in July and August is on the same row as another open date in another month, so our reasoning so far leaves open the possibility that Cheryl told Albert one of these months.

All the reasoning we just did, Bernard can also do. But he is able to combine that information with what Cheryl told him, and deduce a single date. That means that Cheryl could not have told him “14,” as that’s an open date in both July and August. She must have instead told him 15 or 17 (two further possibilities in August) or 16 (a further possibility in July).

Now once Albert sees that Bernard knows the answer, he is also able to deduce the answer. But if Cheryl had told Albert August, he wouldn’t at this point be in a position to know whether Bernard had been told 15 or 17. If Cheryl had told Albert July, he would be in a position to know that Bernard must have been told 16.

So Cheryl’s birthday is July 16. She told Albert “July” and she told Bernard “16.”

We asserted two derived rules of System P are:

If G ƕ D and G ƕ Q, then G ƕ D ∧ Q
If G ∧ D ƕ Q, then G ƕ D ⊃ Q

Here’s a proof that rule 7 holds, in any system satisfying the first six postulates for System P. (Maybe there are nicer proofs, this is what we came up with.)

First use Cautious Monotonicity and the assumptions G ƕ D and G ƕ Q to establish that G ∧ Q ƕ D. Then use that result, plus the Reflexive entailment G ∧ Q ∧ D ƕ G ∧ Q ∧ D and Cut to establish G ∧ Q ƕ G ∧ Q ∧ D. By Rule 5 for System P, that result gives us G ∧ Q ƕ Q ∧ D. That plus the initial assumption G ƕ Q and Cut give the desired conclusion that G ƕ Q ∧ D.

Now you prove that rule 8 holds, in any system satisfying the first six postulates for System P.

Since Q ⊃ (D ⊃ Q) is a deductive theorem, the assumption G ∧ D ƕ Q plus Rule 5 for System P tells us that G ∧ D ƕ D ⊃ Q. Next, take the Reflexive entailment G ∧ ¬D ƕ G ∧ ¬D, and use Rule 5 to get G ∧ ¬D ƕ ¬D. Now since ¬D ⊃ (D ⊃ Q) is a deductive theorem, the result of the last sentence plus Rule 5 give us G ∧ ¬D ƕ D ⊃ Q. Now we’ve shown that D ⊃ Q is a nonmonotonic consequence of each of G ∧ D and G ∧ ¬D. So Rule 4 gives us (G ∧ D) ∨ (G ∧ ¬D) ƕ D ⊃ Q. But since the premise there is deductively equivalent to G, Rule 6 gives us the desired conclusion that G ƕ D ⊃ Q.

Recall our Preservation Postulate for AGM:

Preservation: If A is consistent with the sentences in 𝓚 (that is, ¬A ∉ 𝓚), then 𝓚 ⊆ 𝓚 ★ A.

We said that sometimes the consequent is instead formulated as Cn(𝓚 ∪ {A}) ⊆ 𝓚 ★ A; we said also that given AGM Postulates 1–5, these two consequents are equivalent. Prove that this is so, that is, that:: 𝓚 ⊆ 𝓚 ★ A iff Cn(𝓚 ∪ {A}) ⊆ 𝓚 ★ A

Hint: The right-to-left direction is easy. For the other direction, make use of AGM Success Postulate, and what we called the “alternate formulation” of Monotonicity for deductive consequence.

Here’s a proof of the easy right-to-left direction. From the definition of ∪ it follows that 𝓚 ⊆ 𝓚 ∪ {A}. From the fact that deductive consequence is Reflexive, it follows that 𝓚 ∪ {A} ⊆ Cn(𝓚 ∪ {A}). From those results and the premise that Cn(𝓚 ∪ {A}) ⊆ 𝓚 ★ A and the transitivity of ⊆, we get the desired result that 𝓚 ⊆ 𝓚 ★ A.

Here’s a proof of the left-to-right direction. We assume that 𝓚 ⊆ 𝓚 ★ A, and the Success Postulate implies that {A} ⊆ 𝓚 ★ A. From those two facts, and the definitions of ∪ and ⊆, it follows that 𝓚 ∪ {A} ⊆ 𝓚 ★ A. The “alternate formulation” of Monotonicity for deductive consequence then implies that Cn(𝓚 ∪ {A}) ⊆ Cn(𝓚 ★ A). But we know from the Closure Postulate of AGM that Cn(𝓚 ★ A) is identical to 𝓚 ★ A. So we get the desired result that Cn(𝓚 ∪ {A}) ⊆ 𝓚 ★ A.

This is a question about defining contraction functions in terms of “remainder sets”. Suppose you start with a 𝓚 which is the set Cn({A ⊃ B, B ⊃ C, C ⊃ ¬A}}. Next you learn A. This is inconsistent with your initial beliefs, so you will have to somehow contract by ¬A.

Some maximal subsets of 𝓚 that are compatible with A are: the three sets Cn({A ⊃ B, B ⊃ C}), Cn({A ⊃ B, C ⊃ ¬A, A ∨ (B ⊃ C)}), and Cn({B ⊃ C, C ⊃ ¬A}).

Suppose that you count each of those maximal subsets as equally “best”, and you contract by their intersection. (That is, after contraction, you will accept all and only sentences that are true in each of those maximal subsets.) You then expand the resulting belief set with A.

Will the 𝓚 ★ A you arrive at in this way contain B? Why or why not?
Will it contain C? Why or why not?
Will that 𝓚 ★ A be a subset of Cn({A})? Why or why not?

Hint: for answering these, we found it useful to remember that it’s a deductive theorem that (X ⊃ Q) ∧ (Y ⊃ Q) ∧ (Z ⊃ Q) iff (X ∨ Y ∨ Z) ⊃ Q. Hence, it will be the case that (i) Q is a deductive consequence of X, and also of Y, and also of Z, iff (ii) Q is a deductive consequence of X ∨ Y ∨ Z.

After contraction, you will accept a sentence Q iff it belongs to each of the three sets named above. The sentence ¬A does not belong to any of the three sets, so the result of 𝓚 ★ A will be what you get by taking the union of the contracted set with {A}, and closing under deductive consequence. In other words, Q ∈ 𝓚 ★ A iff Q is an element of each of Cn({A ⊃ B, B ⊃ C, A}}, Cn({A ⊃ B, C ⊃ ¬A, A ∨ (B ⊃ C), A}}, and Cn({B ⊃ C, C ⊃ ¬A, A}}. This will be true iff Q is a consequence of A ∧ B ∧ C, and Q is also a consequence of A ∧ B ∧ ¬C, and Q is also a consequence of A ∧ ¬B ∧ ¬C. This will be true iff Q is a consequence of the disjunction of those three sentences. (This is where the deductive theorem in the hint is useful.) Equivalently, iff Q is a consequence of A ∧ (C ⊃ B). Thus, 𝓚 ★ A = Cn({A, C ⊃ B}).

Now we have enough information to answer the questions.

No, because B is not a consequence of A ∧ (C ⊃ B).
No, because C is not a consequence of A ∧ (C ⊃ B).
No, because some of the sentences in 𝓚 ★ A, such as C ⊃ B, are not consequences of A.

Here are some questions about “entrenchment orderings” as explained in the webnotes as a way to generate contraction functions.

We asserted that Constraints 1–3 on ⊑ entail that ⊑ is a total preorder, that is that ∀ x,y. x ⊑ y ∨ y ⊑ x. Here’s a proof of that assertion.

Constraint 3 tells us that either (i) A ⊑ (A ∧ B) or (ii) B ⊑ (A ∧ B). But Constraint 2 tells us that (iii) (A ∧ B) ⊑ A and (iv) (A ∧ B) ⊑ B. If (i) is the disjunct that holds, that together with (iv) and transitivity entails that A ⊑ B. If (ii) is the disjunct that holds, that together with (iii) and transitivity tells us that B ⊑ A. So in every case, either A ⊑ B or B ⊑ A.

Here are some other properties of ⊑ that we hereby assert are also entailed by Constraints 1–3. Prove those assertions.

If (B ∧ C) ⊑ A then B ⊑ A or C ⊑ A

Constraint 3 tells us that either (i) B ⊑ (B ∧ C) or (ii) C ⊑ (B ∧ C). But the premise says that (B ∧ C) ⊑ A, so by transitivity we have that either B ⊑ A or C ⊑ A, which is the desired conclusion.

If C ⊑ A and C ⊑ B then C ⊑ (A ∧ B)

Constraint 3 tells us that either (i) A ⊑ (A ∧ B) or (ii) B ⊑ (A ∧ B). We take as premises that (iii) C ⊑ A and (iv) C ⊑ B. If (i) is the disjunct that holds, that together with (iii) and transitivity entails that C ⊑ (A ∧ B). If (ii) is the disjunct that holds, that together with (iv) and transitivity entails that C ⊑ (A ∧ B). So in every case, C ⊑ (A ∧ B).

B ⊑ A iff B ⊑ (A ∧ B)

The right-to-left side is easy to prove: assuming B ⊑ (A ∧ B), we have from Constraint 2 that (A ∧ B) ⊑ A, so by transitivity we get the desired conclusion that B ⊑ A.

Here’s a proof of the left-to-right side. We take as a premise that B ⊑ A. By Constraint 2 we have that B ⊑ B. Result (b) tells us it follows that B ⊑ (A ∧ B), which is the desired conclusion.

We also asserted that Constraints 2 and 4 on ⊑ entail that all and only deductive theorems will be greatest with respect to the ⊑ ordering. Prove this assertion.

Suppose some deductive theorem Q is not greatest, that means there must be some P such that P ⊑ Q is false. But if Q is a deductive theorem, then P will deductively entail Q, and so by Constraint 2, P ⊑ Q. So the supposition that Q is not greatest fails. Every deductive theorem will be greatest.

Constraint 4 tells us that only deductive theorems are greatest.

It follows that all and only deductive theorems are greatest.