Show that there is always a proposition between two propositions logic Suppose we define the following relationship of ordering between propositions in PROP:
$$
\phi < \psi := (\models \phi \rightarrow \psi \land \lnot(\models \psi \rightarrow \phi) )
$$
Show that if exists $\phi$ and $\psi$ such that:
$$
\phi < \psi
$$
Then there is a $\sigma$ such that:
$$
\phi < \sigma < \psi
$$
I have tried to use valuation to find what $\sigma$ could possibly be, so for all valuations v:

*

*If $v(\phi)=0$ and $v(\psi)=0$ then, since $\models \sigma \rightarrow \psi$, $v(\sigma)=0$


*If $v(\phi)=1$ and $v(\psi)=1$ then, since $\models \phi \rightarrow \sigma$, $v(\sigma)=1$


*It is impossible that $v(\phi)=1$ and $v(\psi)=0$ since $\models \phi \rightarrow \psi$


*If $v(\phi)=1$ and $v(\psi)=0$ then $v(\sigma)$ could be either 0 or 1, and it would satisfy the tautologies, but if:

*

*$v(\sigma)=0$, then the valuation of $\sigma$ would be equal to valuation of $\psi$ for all valuations and thus $\models \psi \rightarrow \sigma$, which is a contraditcion;

*$v(\sigma)=1$, then the valuation of $\sigma$ would be equal to valuation of $\phi$ for all valuations and thus $\models \sigma \rightarrow \phi$, which is a contraditcion.



 A: I assume that this is a question about classical propositional logic.
Given $\varphi < \psi$, pick a variable $q$ not occuring in $\varphi$ or $\psi$. Then
$$
\varphi < (\varphi\land q)\lor(\psi\land\lnot q) < \psi.
$$

Let's go through the things we have to check. If $v(\varphi)=1$ then also $v(\psi)=1$ because $\models \varphi\rightarrow\psi$ by assumption, and so either $v(\varphi\land q)=1$ (if $v(q)=1$) or $v(\psi\land\lnot q)=1$ (if $v(q)=0$). Hence $\models \varphi\rightarrow (\varphi\land q)\lor(\psi\land\lnot q)$. On the other hand, if it were the case that $\models (\varphi\land q)\lor(\psi\land\lnot q)\rightarrow \varphi$, then in particular it would follow that $\models(\psi\land\lnot q)\rightarrow \varphi$, which in turn implies $\models \psi\rightarrow \varphi$ as $q$ does not in $\varphi$ and $\psi$. But this is ruled out as we assumed $\varphi <\psi$. We have now established $\varphi < (\varphi\land q)\lor(\psi\land\lnot q)$. For the second part, $\models (\varphi\land q)\lor(\psi\land\lnot q) \rightarrow \psi$ follows from $\models \varphi\rightarrow\psi$. And if it were the case that $\models\psi\rightarrow (\varphi\land q)\lor(\psi\land\lnot q)$, then we'd again have $\models\psi\rightarrow \varphi$ because $q$ does not appear in $\varphi$ and $\psi$, but this was ruled out because $\varphi<\psi$. We therefore conclude $(\varphi\land q)\lor(\psi\land\lnot q) < \psi$.

[EDIT: I just saw the question is tagged "first-order logic". The argument above also works in the first-order setting, one only has to replace the propositional variable $q$ by the formula $\exists x Q(x)$ where $Q$ is a new relation symbol.]
