Exercise 1.8.2 in Fitting and Mendelson's "First Order Logic" asks to show that $\mathcal{M} \models \Box \phi \rightarrow \Box \Box \phi$ for all $\phi$ if and only if the accessibility relation of $\mathcal{M}$ is transitive. This is reiterated in the answer to this question but I have been unable to prove the only if part and believe I have a counterexample:

Let the universe of $\mathcal{M}$ be $\{\Gamma_i: I\in\mathbb{N}\}$ with relation $R = \{(i,i+1): i \in \mathbb{N}\}$. Clearly, $R$ is not transitive. Let $\Vdash$ be identical for each $\Gamma_i$. Then, each for each $i,j,\phi$ we have that $\Gamma_i \Vdash \phi$ if and only if $\Gamma_j \Vdash \phi$, so $\Box \phi \rightarrow \Box\Box \phi$ is valid in $\mathcal{M}$. The proof uses standard induction on height of $\phi$.

What am I missing here?


I realized the problem 30 seconds after posting: The definition of validity in a Frame requires truth across all valuations. Here is the proof:

Fix $\Gamma,\Delta,\Omega$ in the universe if $\mathcal{M}$ with $\Gamma R \Delta$ and $\Delta R \Omega$. Pick a valuation $\Vdash$ so that for $\Gamma R \Lambda$, $\Lambda \Vdash P$ and for $\Gamma \not\text{R} \Lambda$, $\Lambda \not\Vdash P$ for some Propositional Variable $P$. Then, $\Gamma \Vdash \Box P$, so $\Gamma \Vdash \Box\Box P$, so $\Omega \Vdash P$. By construction of $\Vdash$, $\Gamma R\Omega$.


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.