0
$\begingroup$

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!

$\endgroup$
4
  • 2
    $\begingroup$ 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.) $\endgroup$ Jul 5 '19 at 21:35
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 5 '19 at 22:40
  • $\begingroup$ Are you suggesting this claim is supposed to be proven? Maybe Löwenheim–Skolem theorem? $\endgroup$ Jul 5 '19 at 23:18
  • $\begingroup$ Yes, the claim follows from the downward Löwenheim–Skolem theorem. $\endgroup$ Jul 6 '19 at 18:05
1
$\begingroup$

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.

$\endgroup$

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.