# Why are these PDL formulas valid and invalid

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

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$$.
• What does $R-S$-paths mean? And why did you change the box with label to diamond with label inside it? Mar 12, 2019 at 15:07
• 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. Mar 12, 2019 at 17:27