Modal logic assignment

PHI134 Assignment # 2 Completeness and Filtrations

�is assignment consists of two questions, and is worth 25% of your final grade. It is due on Wednesdaythe3rdofJune at 11:59pm.

Question1: (15marks) In this question we will walk through, step by step, the argu- ment showing that if Σ contains the modal formula ♦�A → �♦A, then RΣ is conver- gent in the sense that

If RΣΓ∆ and RΣΓ∆∗ then there exists a Θ such that RΣ∆Θ and RΣ∆∗Θ

To do this we need to show that given (i) �−1Γ ⊆ ∆ and (ii) ♦∆∗ ⊆ Γ, that there exists a complete and consistent set Θ ∈ WΣ such that RΣ∆Θ and RΣ∆∗Θ. Consider the set Θ− where:

Θ− = �−1∆∪�−1∆∗

If this set Θ− is consistent, then there must be a complete Σ-consistent set extending it, and we can let that set be our Θ.

Part (i): Show that if Θ is a complete consistent set extending Θ− that we will have both RΣ∆Θ and RΣ∆∗Θ

All that remains to be done, then, is to show that Θ− is consistent. Suppose, for a contradiction, that it isn’t. �en we must have that Θ− `Σ ⊥. So we must have �D1, . . . , �Dn ∈ ∆ and �S1, . . . , �Sm ∈ ∆∗ for which

D1 ∧ . . . ∧ Dn, S1 ∧ . . . ∧ Sm `Σ ⊥

So by the deduction theorem (Proposition 3.36(4)) we have S1 ∧ . . . ∧ Sm `Σ (D1 ∧ . . . ∧ Dn) → ⊥, and so by (Proposition3.36(5)) and the fact that (A → ⊥) → ¬A is a tautological instance we have

S1 ∧ . . . ∧ Sm `Σ ¬(D1 ∧ . . . ∧ Dn)

So by Lemma4.6 it follows that

�(S1 ∧ . . . ∧ Sm) `Σ �¬(D1 ∧ . . . ∧ Dn)

Part (ii): From the above it follows that:

1. �(D1 ∧ . . . ∧ Dn) ∈ ∆

2. �(S1 ∧ . . . ∧ Sm) ∈ ∆∗

3. �¬(D1 ∧ . . . ∧ Dn) ∈ ∆∗

Explain why.

1

So, as �¬(D1∧. . .∧Dn) ∈ ∆∗ it follows that we must have ♦�¬(D1∧. . .∧Dn) ∈ Γ, and so by the fact that ♦�A → �♦A ∈ Σ, that �♦¬(D1 ∧ . . . ∧ Dn) ∈ Γ. So by the fact that �−1Γ ⊆ ∆ it follows that we must have ♦¬(D1 ∧ . . . ∧ Dn) ∈ ∆. But (as you will show) this means that ∆ is inconsistent.

Part(iii): Explain why the fact that �(D1 ∧ . . . ∧ Dn) ∈ ∆ and ♦¬(D1 ∧ . . . ∧Dn) ∈ ∆ means that ∆ is inconsistent, ideally by providing an appropri- ate derivation.

But ∆, being by hypothesis a world in WΣ must be consistent. And so by reductio ad absurdem it follows that Θ− must also be consistent. So by Lindenbaum’s Lemma there is a complete Σ-consistent set Θ extending it in WΣ, and the result follows by Part (i) above.

Question2(10marks): �is question is about filtrations. Consider the following model M2 = 〈W2, R2, V2〉, where:

• W2 = {0}∪ {na, nb|n ∈ Z+}∪ {n∗, n†|n > 1 and n odd}1

• R2 = {〈0, 1a〉,〈0, 1b〉} ∪ {〈na, ma〉|m = n + 1} ∪ {〈nb, mb〉|m = n + 1} ∪ {〈na, m∗〉|n even and m = n + 1}∪ {〈nb, m†〉|n even and m = n + 1}

• V2(pi) = ∅ for all i

Here’s a picture:

0

1a

1b

2a 3a

3∗

4a 5a

5∗

. . .

2b 3b

3†

4b 5b

5†

. . .

In this question we will be looking at what filtrations of this model through the subformulas of �♦�⊥ look like. We’ll go through this in stages.

1. Give the set Γ of subformulas of �♦�⊥.

2. Let M∗2 be a filtration of M2 through the set of formulas Γ from the previous question. Give W∗2 by describing which worlds in W2 are ≡Γ . Which members of Γ are true in each equivalence class [w]≡Γ in W

∗ 2 ?

1Z+ is the set of all positive integers 1, 2, 3, . . .

2

3. What is the finest filtration of M2 through Γ?

4. What is the coarsest filtration of M2 through Γ?

3