Due on Fri Oct 13.

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).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.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)`p ⊨ □p`

`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)

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?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.**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.

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.

- If
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.- Preservation: If
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`

.~~The~~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})`

.Originally we had omitted the underlined formula, and the subset that was listed was not maximal. This doesn’t change the problem’s solution, though; the difference gets washed out when you expand by

`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`

.- Will the
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`

If

`C ⊑ A`

and`C ⊑ B`

then`C ⊑ (A ∧ B)`

`B ⊑ A`

iff`B ⊑ (A ∧ B)`

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.