# Prove or disprove a claim about sentences in first order logic

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!

• 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 probably 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? (I'm leaving this as a comment since I don't see a good way to make a hint good enough to be an answer but also not give away the problem entirely.) Jul 5 '19 at 21:35
• One of the main things about FOL is you cannot formulate $A$ in FOL. As Noah indicates, there is a 'big theorem' to this effect. Jul 5 '19 at 22:40
• Are you suggesting this claim is supposed to be proven? Maybe Löwenheim–Skolem theorem? Jul 5 '19 at 23:18
• Yes, the claim follows from the downward Löwenheim–Skolem theorem. Jul 6 '19 at 18:05

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.