In the book modal logic for open minds by johan van benthem there is on page 169 a statement that the sentence the first formula bellow is valid and the second one is invalid (* means iteration)

So why is this valid: $[ (R\lor S)^* ] \phi \rightarrow [R^*]\phi \land [S^*] \phi$

And why is this one invalid: $[ (R\lor S)^* ] \phi \leftarrow [R^*]\phi \land [S^*] \phi$


1 Answer 1


I will give a hand-wavy general argument for the contraposition of the first validity: $\langle R^\ast\rangle \phi \vee \langle S^\ast \rangle \phi \rightarrow \langle (R \vee S)^\ast \rangle \phi$. The main thing to notice is that the set of $R-S$-paths $(R\vee S)^\ast$ includes the sets of $R$-paths and $S$-paths. So, if some $\phi$-state is reachable via an $R$-path, then it is trivially reachable via an $R-S$-path. The same holds for a $\phi$-state reachable via an $S$-path. In general, $\langle R^\ast\rangle \phi \rightarrow \langle (R \vee S)^\ast \rangle \phi$ is valid.

Now, let us consider the contraposition of the second formula: $\langle (R \vee S)^\ast \rangle \phi \rightarrow \langle R^\ast \rangle \phi \vee \langle S^\ast \rangle \phi$. In order to demonstrate that this formula is invalid, it is enough to notice that even though there is an $R-S$-path that reaches a $\varphi$-state, it may be neither $R$- nor $S$-path (i.e. the path alternate $R$ and $S$). A simple counterexample would be a three-state model, where a $p$-state is reachable via two steps, one $R$- and one $S$-step, and the initial and the intermediate states have $\neg p$.

  • $\begingroup$ What does $R-S$-paths mean? And why did you change the box with label to diamond with label inside it? $\endgroup$ Mar 12, 2019 at 15:07
  • 1
    $\begingroup$ By an $R-S$-path I mean any sequence of $R$- and $S$-arrows in a model. I changed box to diamond because I think that using the contrapositive ($\phi \rightarrow \psi \leftrightarrow \neg \psi \rightarrow \neg \phi$) of the presented formulas makes reasoning more straightforward. So, $[R^\ast] \phi \wedge [S^\ast] phi \rightarrow [(R \vee S)^\ast]\phi$ is equivalent to $\langle (R \vee S)^\ast \rangle \neg \phi \rightarrow \langle R^\ast \rangle \neg \phi \vee \langle S^\ast \rangle \neg \phi$. Note that box and diamond are duals. Anyway, the reasoning and counterxample work for both cases. $\endgroup$ Mar 12, 2019 at 17:27

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.