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$.