Solutions to the Exercises from Session 3

Exercises

The following are a bit harder puzzles for the courageous.

1. We have just shown that \(\mathsf{O} (\mathsf{O}p \rightarrow p)\) holds in Anderson’s system with reflexive accessibility relation. Does it hold in SDL? If yes, give an argument. If no, find a counter-model.

2. What about \(\mathsf{O}\mathsf{O}p \rightarrow \mathsf{O}p\)?

3. In view of the distribution principle

   • \(\mathsf{O}(p \rightarrow q) \rightarrow (\mathsf{O}p \rightarrow \mathsf{O} q)\)

   \(\mathsf{O}(\mathsf{O}p \rightarrow p)\) implies \(\mathsf{O}\mathsf{O}p \rightarrow \mathsf{O}p\). Do you see how this is so?

4. Is there an SDL models where \(\mathsf{O}\mathsf{O}p \rightarrow \mathsf{O}p\) holds but \(\mathsf{O}(\mathsf{O}p \rightarrow p)\) not?

Solutions

Ad 1

No it doesn’t. We give a counter-model \(M = \langle \{w_{1}, w_{2}\}, R, v, w_{1} \rangle\). The accessibility relation is given in the following graph:

Our assignment is as follows:

world	\(p\)
\(w_1\)	1
\(w_2\)	0

Then: \(M,w_1 \models \neg \mathsf{O}(\mathsf{O}p \rightarrow p)\). The reason is that \(M,w_2 \models \mathsf{O}p \wedge \neg p\).

Additional information: the principle \(\mathsf{O}(\mathsf{O}p \rightarrow p)\) can be warranted if we impose secondary or step reflexivity on the accessibility relation. It says: for all \(w\) and \(w’\), if \(w R w^{\prime}\) then \(w^{\prime} R w^{\prime}\).

Ad 2

In the previous model we have:

• \(M,w_1 \models \mathsf{O} \mathsf{O} p\) but
• \(M,w_1 \models \neg \mathsf{O} p\) since \(M,w_2 \models \neg p\).

Additional information: the principle \(\mathsf{O}\mathsf{O}p \rightarrow \mathsf{O}p\) can be warrented if we impose density on the accessibility relation. It says: for all \(w\) and \(w^{\prime}\), if \(w R w^{\prime}\) then there is a \(w^{\prime\prime}\) for which \(wRw^{\prime\prime}\) and \(w^{\prime\prime} R w^{\prime}\).

Ad 3

In SDL the distribution principle holds for \(\mathsf{O}\). So, for any formulas \(A\) and \(B\),

• \(\mathsf{O}(A \rightarrow B) \rightarrow (\mathsf{O} A \rightarrow \mathsf{O} B)\).

If we now set \(A = \mathsf{O}p\) and \(B= p\) then:

• \(\mathsf{O}(\mathsf{O}p \rightarrow p) \rightarrow ( \mathsf{O} \mathsf{O} p \rightarrow \mathsf{O}p)\).

Ad 4

No it doesn’t. We give a counter-model \(M = \langle \{w_{1}, w_{2}, w_3\}, R, v, w_{1} \rangle\). The accessibility relation is given in the following graph:

Our assignment is as follows:

world	\(p\)
\(w_1\)	1
\(w_2\)	0
\(w_3\)	1

We have:

• \(M, w_1 \models \mathsf{O}\mathsf{O}p \rightarrow \mathsf{O}p\) since \(M,w_1 \models \neg \mathsf{O} \mathsf{O} p\). However,
• \(M, w_1 \models \neg \mathsf{O}(\mathsf{O}p \rightarrow p)\) since \(M, w_2 \models \mathsf{O}p \wedge \neg p\).