1

Let $A$ and $B$ be closed formulas in first order logic language. Assume that for any finite structure $M$: $$ M\models A \iff M\models B $$Prove or disprove: $A$ and $B$ are logically equivalent.

I know that this claim is not true, but I cannot find a counter example. Any suggestions?

Shlomi
  • 811

2 Answers2

3

Let $A$ be the axioms defining "linear order". Let $B$ be the conjunction of $A$ with "there is a smallest element".

Andreas Blass
  • 71,833
  • but in those axioms we have to interpret the sign '=' as the equal relation, no? could you give more details? – Shlomi Aug 03 '14 at 23:45
  • @Shlomi: Yes. I assumed the standard semantics for first-order logic. But it seems easy to modify the example to not even mention equality. Let $A$ assert that the relation $<$ is irreflexive and transitive, and let $B$ assert that and, in addition, that there is an $x$ such that no $y$ satisfies $y<x$. – Andreas Blass Aug 03 '14 at 23:49
  • I do not understand what $B$ is. Can you formalize it? – Shlomi Aug 03 '14 at 23:58
  • @Shlomi $B$ is the conjunction of $(\forall x),\neg(x<x)$ and $(\forall x,y,z),((x<y\land y<z)\to(x<z))$ and $(\exists x)(\forall y),\neg(y<x)$. And $A$ is the conjunction of the first two of these three. – Andreas Blass Aug 04 '14 at 00:02
1

Edit: First answer was incorrect. I misread the question.

Fix our language $\mathscr{L} = \{f\}$ where $f$ is a unary function symbol.

Consider the following sentences:

  1. $\phi_1 \equiv (\forall x)(\forall y)((f(x)=f(y)) \to x=y)$

  2. $\phi_2 \equiv (\forall y)(\exists x)(f(x)=y)$

Now, let $A = \phi_1$ and $B =\phi_2$. $A$ is the statement that $f$ is injective and $B$ is that statement that $f$ is surjective. If $M$ is a finite, then $M \models A \iff M \models B$. However, clearly this is not true for infinite models. Consider $(\mathbb{N};S)$ where $S$ is the successor function. This function is injective but not surjective.

Kyle Gannon
  • 6,363