formulas such that either "$\mathcal{M} \vDash \phi$, then $\mathcal{M} \vDash \psi$" or "$\mathcal{M} \vDash \phi \rightarrow \psi$"

Question

I'd appreciate your help with the following: I am looking for formulas $\phi$ and $\psi$ (in any suitable language $\mathcal{L}$) such that in the following exactly one condition is fulfilled, the other not:

a) For all $\mathcal{L}$-structures $\mathcal{M}$: if $\mathcal{M} \vDash \phi$, then $\mathcal{M} \vDash \psi\\$.

b) For all $\mathcal{L}$-structures $\mathcal{M}$: $\mathcal{M} \vDash \phi \rightarrow \psi \\ \\$

($\mathcal{M} \vDash \phi$ means that the formula $\phi$ is valid in $\mathcal{M}$)

I am looking forward to your replies!

Answer 1

Using the same convention that Mauro does:

We assume the "usual" convention that, if $\phi$ has a free variable $x$, then $\mathcal M \vDash \phi$ iff $\mathcal M \vDash (\forall x) \phi$.

a first-order example that actually works is:

• $\mathcal L$ consists of a single binary predicate $<$.
• $\phi$ is $x<y$
• $\psi$ is $y<x$.

It is clear that (a) holds: For every $\mathcal M$ such that $\mathcal M\vDash(\forall x)(\forall y)\,x<y$ we also have $\mathcal M\vDash(\forall x)(\forall y)\,y<x$.

But (b) does not hold: There is an $\mathcal M$ such that $\mathcal M \not\vDash (\forall x)(\forall y)(x<y \to y<x)$. Namely, $\mathcal M$ can be taken to be any set with a non-symmetric binary relation.

Answer 2

The issue is that $\vDash (\phi \to \psi)$ implies "if $\vDash \phi$, then $\vDash \psi$" but not vice versa.

A simple example with propositional logic.

We have that :

$\nvDash [(P \to Q) \land (P \lor R)] \to (P \to R)$.

We can check with an assignment $v$ such that : $v(P)=v(Q)=\text T$ and $v(R)=\text F$.

But we have that :

"if $\vDash (P \to Q) \land (P \lor R)$, then $\vDash(P \to R)$" holds,

because the antecedent : $\vDash (P \to Q) \land (P \lor R)$, is false.

---

A lilttle bit tricky example with FOL is the following :

let $\phi$ be $(0 < x)$ and $\psi$ be $(1 < x)$

and consider the structure $\mathbb N$.

We assume the "usual" convention that, if $\phi$ has a free variable $x$, then $\mathcal M \vDash \phi$ iff $\mathcal M \vDash (\forall x) \phi$.

Thus, we have that :

$\mathbb N \nvDash (0 < x) \to (1 < x)$.

But again, we have that :

"if $\mathbb N \vDash (0 < x)$, then $\mathbb N \vDash (1 < x)$" holds,

because the antecedent is false.

---

In the same way, we can easily manufacture a suitable counter-example for the case with all structures $\mathcal M$ [see Hemming's answer below].