0
$\begingroup$

As I'm new to modal logic, I wanted to check whether my counter examples for the given formula is right.

$$ \Box A \rightarrow \Diamond B \Rightarrow \Box(\Box A \rightarrow \Diamond B) $$

First I tried to create a proof tree to find a counterexample, but that got very complicated to comprehend very quickly. However the procedure yielded the following: $\langle W, R, V \rangle$ with $W=\{ w_0, w_1, w_2, w_3\}$, $R=\{ (w_0, w_1), (w_0, w_2), (w_0, w_3)\}$ and $V_{\neg A} = \{ w_0, w_2, w_3\}$, $V_{A} = \{w_1\}$, $V_{\neg B} = \{ w_0, w_2, w_3\}$, $V_{B} = \{w_1\}$. Could anyone who is more familiar with the concepts provide me any guidance as to whether this constitutes a proper counter example?

Secondly, I came up with another one and would like to know if I'm right in my assumption that I could simply create a one-world counter example: $\langle W, R, V \rangle$ with $W=\{ w_0, w_1\}$, $R=\{\}$ and $V_{\neg A} = \{w_0 \}$, $V_{A} = \{\}$, $V_{\neg B} = \{w_0\}$, $V_{B} = \{\}$. If I'm correct, this means that since the negation of A is true, $\Box A$ is false and the first part of the implication is true. Now the same counts for inner part on the right side. However, since there is no $w_0Rw_1$ as $R$ is empty, the right side is not true in all worlds. Thus the implication is false. Is this a proper counter example?

$\endgroup$
  • $\begingroup$ What is the intended value of $A$ in $w_1$ in your example? (The usual approach is to specify an assignment of propositions to each world.) $\endgroup$ – Fabio Somenzi Jan 19 '18 at 20:16
2
$\begingroup$

We write $(M,w) \models \varphi$ to say that $\varphi$ holds in world $w$ of model $M$.

To show that $\psi$ is a logical consequence of $\varphi$ (written $\varphi \Rightarrow \psi$) we need to show that in every possible world $w$ of every Kripke model $M$, if $(M,w) \models \varphi$, then $(M,w) \models \psi$.

A counterexample to $\varphi \Rightarrow \psi$ consists of a world $w$ of model $M$ such that $(M,w) \models \varphi$, but $(M,w) \not\models \psi$.

If the accessibility relation of model $M$ is empty, the definition of $\Box$ implies that $(M,w) \models \Box \varphi$ for every world $w$ of $M$, because universal quantification is over the empty set of worlds accessible from $w$. Since our $\psi$ starts with a $\Box$, we better choose a nonempty accessibility relation.

Another way to see why we need a nonempty accessibility relation is that for our counterexample to $\varphi \Rightarrow \Box\varphi$ we need a world $w$ such that $(M,w) \models \varphi$, from which we can access a world $w'$ such that $(M,w') \not\models \varphi$. This argument also makes it clear that we need at least two worlds: a model with a single world accessible from itself won't do.

A simple model that satisfies these requirements, and that works when $\varphi$ is $\Box A \rightarrow \Diamond B$, consists of two worlds, $w_0$ and $w_1$, has the accessibility relation

$$ \{\,(w_0,w_0), (w_0,w_1), (w_1,w_1) \,\} \enspace, $$

and is such that $A$ is true in both worlds, but $B$ is only true in $w_0$. We can verify that $(M,w_0) \models \Box A$, $(M,w_1) \models \Box A$, $(M,w_0) \models \Diamond B$, and $(M,w_1) \not\models \Diamond B$. Hence $(M,w_0) \models \varphi$, $(M,w_1) \not\models \varphi$, and finally $(M,w_0) \not\models \Box\varphi$.


Of course, once we found one model, we can find many variations. In particular, we can choose a model $M'$ with accessibility relation

$$ \{\,(w_0,w_1) \,\} $$

and stipulate that $A$ and $B$ are both true at $w_1$. Now $(M',w_1) \models \Box A$ vacuously, but $(M',w_1) \not\models \Diamond B$. So, we have another counterexample.

However, it is often assumed that the accessibility relation is both reflexive and transitive, and our first example remains valid under those assumptions, while the second doesn't. That is, $\Box(\Box A \rightarrow \Diamond B)$ is not a logical consequence of $\Box A \rightarrow \Diamond B$ even in the stronger logics (like $\mathbf S_4$) that assume reflexive and transitive models.

Can you see what happens if we assume symmetry of the accessibility relation?


Let's finally take a look at your first, four-world counterexample. The only world $w$ for which $(M,w) \models \Diamond B$ is $w_0$. For all worlds except $w_0$ we have $(M,w) \models \Box A$ (vacuously in all three cases).

So, $(M,w_0) \models \Box A \rightarrow \Diamond B$ (in fact, vacuously), but $(M,w_0) \not\models \Box(\Box A \rightarrow \Diamond B)$. Hence $w_0$ is a counterexample. We can also see that our second counterexample above is a pruned version of this one: worlds $w_2$ and $w_3$ can be dispensed with.

If you revisit your proof tree, you may find where the extra worlds crept in, but the good news is that you still got a valid counterexample.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.