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!


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.

  • $\begingroup$ 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? $\endgroup$ – Studentu Nov 12 '18 at 15:55
  • 1
    $\begingroup$ @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$. $\endgroup$ – Henning Makholm Nov 12 '18 at 20:09
  • 1
    $\begingroup$ 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$. $\endgroup$ – Henning Makholm Nov 12 '18 at 20:13
  • 1
    $\begingroup$ @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? $\endgroup$ – Henning Makholm Nov 12 '18 at 20:19
  • 1
    $\begingroup$ @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)\}$. $\endgroup$ – Henning Makholm Nov 12 '18 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].

  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Nov 9 '18 at 12:54
  • $\begingroup$ @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? $\endgroup$ – Studentu Nov 10 '18 at 17:06
  • $\begingroup$ @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. $\endgroup$ – Studentu Nov 10 '18 at 17:51
  • 1
    $\begingroup$ @Studentu - you are welcome :-) The propositional example has only a "pedagocical" value : to show the "subtle" point about $\vDash$. $\endgroup$ – Mauro ALLEGRANZA Nov 10 '18 at 17:56
  • 1
    $\begingroup$ @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. $\endgroup$ – Henning Makholm Nov 11 '18 at 5:22

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.