Prove or disprove a claim about sentences in first order logic

Question

Let $A,B$ be two statements (i.e. WFFs without free variables) in first order logic.

Prove or disprove: if $A$ and $B$ are satisfied in the same countable models, then $A\equiv B$.

So my intuition tells me this is wrong, and we wish to disprove it. So we wish to find $A$ such that it is satisfied in every countable model, and $B$ such that it is valid (i.e. satisfied by every model). I have no idea how to find such statement $A$.

I thought maybe $A$ would formulate the concept of existence of a bijection $f:D^M \rightarrow \mathbb{N}$, or that its domain is finite, then for every countable model $M$, $M\models A$. Then let $B\cong \forall x (x=x \lor x\neq x)$ and so obviously every model $M$,countable or not, $M \models B$. Therefore $A,B$ are satisfies in the same countable models (all of them) yet are not logically equivalent, for example if $D^m \cong \mathbb{R}$ then obviously $M \not\models A$ yet $M \models B$ regadless of $I^M[=]$.

But I am not sure how to formulate $A$ in $FOL$, or even if my counter-example holds. Any hints or guidance are appreciated!

Answer 1

I'm turning my comment into an answer to move this question off the "unanswered" queue.

Quantifying over functions is second-order, not first-order, so the idea you suggest won't work. (That idea can, however, show that the statement in question fails for second-order logic.)

At this point it's a good idea to step back and think: what general theorems do you know about countable vs. uncountable models in the context of first-order logic?

The upwards and downwards Lowenheim-Skolem theorems.

One of these results lets you "shrink" structures, and in particular implies that if a sentence $X$ is satisfiable then it has a countable model. Now, do you see how this leads to an answer to your question?

Consider "$A\wedge\neg B$" and "$B\wedge\neg A$." If $A\not\equiv B$, then (at least) one of these is satisfiable, and hence satisfiable in some countable model. But that countable model satisfies one but not both of $A$ and $B$, so $A$ and $B$ don't in fact have the same countable models.

Meanwhile, the other of the two cardinality results above similarly implies that we can replace "countable" with "of cardinality $\kappa$" for any fixed infinite $\kappa$ ... under the additional assumption that neither $A$ nor $B$ have any finite models.