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

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!

## 2 Answers

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
• $$\psi$$ is $$y.

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

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

• Thank you for your example, Henning! But I seem to not get the whole thing since I still don't see how Mauros example is false. What do you mean by the $\{<, 0, 1\}$-structure? Is there one binary relation < and two constants 0,1 in the language? Or is $\{0,1\}$ a specific universe of some specific structure that reveals the incorrectness of his example? Nov 12, 2018 at 15:55
• @Studentu: Since Mauro suggests the formulas $0<x$ and $1<x$, his language must contain constant symbols $0$ and $1$ and a binary predicate $<$, so I'm assuming that his $\mathcal L$ is $\{{<},0,1\}$. Where his example becomes not-an-example is that he tries to specify the particular $\mathcal L$-structure $\mathbb N$, whereas your question was about properties that were phrased as "for all $\mathcal L$-structures $\mathcal M$. Nov 12, 2018 at 20:09
• I know from Mauro's answers to other questions that his understanding of mathematical logic is excellent, so I can only assume that he must have misread the question and thought you were looking for an example of $\phi$ and $\psi$ together with a particular $\mathcal M$. Nov 12, 2018 at 20:13
• @Studentu: As I said in my comment to Mauro's answer, it is an example of $\phi$ and $\psi$, such that your (a) is false and your (b) is also false. Since you asked for an example where exactly one of them is true, that doesn't work. Which of that do you disagree with? Nov 12, 2018 at 20:19
• @Studentu: I described one such structure in my comment under Mauro's answer. Perhaps more explicitly: the universe of $\mathcal M$ is $\{a,b\}$; the constants are interpreted as $0^{\mathcal M}=a$, $1^{\mathcal M}=b$; and $<^{\mathcal M}$ is the relation $\{(a,a),(a,b)\}$. Nov 12, 2018 at 22:59

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].

• Note that the (a) part of the question explicitly quantifies over all structures. So I don't think there can be a propositional example. It's conceivable that we can have first-order examples due to the "invisible universal closure" but I don't think yours is one if we quantify over all $\{{<},0,1\}$-structures. Nov 9, 2018 at 12:54
• @Henning Makholm: Thanks for your comment. But I don't understand what you mean. Am I correct that both the (a) and the (b) - part quantify over all structures? Anyways, I was looking for an example in FOL, not in prop. logic. The example with $(\mathbb{N}, <)$ as a structure looks just fine to me. Where do you see the problem there? What do you mean by quantifying over all $\{<, 0, 1\}$-structures? Nov 10, 2018 at 17:06
• @Mauro ALLEGRANZA: Thanks for your answer! It was very confusion to me that such formulas can exist, but now it makes sense to me what the main point is. Nov 10, 2018 at 17:51
• @Studentu - you are welcome :-) The propositional example has only a "pedagocical" value : to show the "subtle" point about $\vDash$. Nov 10, 2018 at 17:56
• @Studentu: Mauro's FOL example is not an example of what you want. Both of your conditions (a) and (b) are false for that example. An $\mathcal M$ that witnesses the falsehood of either of them is the structure with two individuals $0$ and $1$, and whose $<$ relation makes $0<0$ and $0<1$ true but $1<0$ and $1<1$ false. Nov 11, 2018 at 5:22