I am working through Fitting and Mendelsohn's First Order Modal Logic and have come across the following exercise:

Prove that a frame $\langle \mathcal{G}, \mathcal{R} \rangle$ is transitive if and only if every formula of the form $\Box P \supset \Box \Box P$ is valid in it.

I can prove the left to right direction, but can't even get started on the right to left proof. Any ideas/hints? I know it should be a relatively simple proof but would appreciate any help.

  • $\begingroup$ For those not familiar with the notation, the superset symbol refers to material implication. $\endgroup$ – nick Aug 4 '15 at 10:43

Assume that $\mathcal R$ is not transitive, i.e. $x \mathcal R y$ and $y \mathcal R z$ but $\lnot (x \mathcal R z)$.

Consider $x \Vdash p$ and $y \Vdash p$ but $z \nVdash p$. We have $x \Vdash \square p$ and $y \nVdash \square p$.

Thus, $x \nVdash \square \square p$ and this contradicts : $\Vdash \square p \to \square \square p$.

  • $\begingroup$ Should have known to try a different proof method, thanks! $\endgroup$ – nick Aug 4 '15 at 21:18

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.