8
$\begingroup$

It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find a first-order sentence $\varphi$ such that $\varphi$ is not equivalent to any $\forall^*$-sentence even when we restrict attention to finite models, but if $\mathfrak{A}\models\varphi$ is finite and $\mathfrak{B}\subseteq\mathfrak{A}$ then $\mathfrak{B}\models\varphi$.

I'm curious about whether there is anything that could be called a substructure preservation theorem for $\mathsf{FOL}$ in finite model theory:

Is there a computable set of first-order sentences $\Phi$ with the following properties?

  • Whenever $\varphi\in\Phi$ and $\mathfrak{A}\supseteq\mathfrak{B}$ are finite structures, we have $\mathfrak{A}\models\varphi\implies\mathfrak{B}\models\varphi$.

  • Every $\varphi$ satisfying the previous bulletpoint is equivalent over finite structures to some $\psi\in\Phi$.

If the answer is no, can we at least have some such $\Phi$ which is not $\Pi^0_1$-complete? (Since the set of substructure-preserved-in-the-finite sentences is $\Pi^0_1$, this is the weakest nontriviality notion I can think of.)

$^*$This is a really cute argument that I just learned. The key point is that if $B$ is a complete Boolean algebra with set of atoms $X$, then first-order logic over $B$ can implement monadic second-order logic over $X$ ... and every finite Boolean algebra is trivially complete.

Now consider the sentence $\theta$ in the language $\{\le, s\}$ that says

  • $\le$ yields a Boolean algebra (construed as a poset in the usual way);

  • $s$ is not always the identity but $s(x)=x$ for every nonatomic $x$; and

  • $s$ cyclically permutes the atoms ("the only $s$-closed subsets of $X$ are $X$ and $\emptyset$").

This last bulletpoint isn't obviously first-order, but it is monadic second-order over the set of atoms so we're fine per the above. If $\mathcal{M}\models\theta$ and $\mathcal{N}$ is a substructure of $\mathcal{M}$, then $\mathcal{N}$ must contain all or none of the original atoms of $\mathcal{M}$, and in the latter case we won't have $\mathcal{N}\models\theta$. So now let $\varphi$ be any $\{\le\}$-sentence not equivalent to a universal sentence, and consider $\varphi\wedge\theta$.

Improve this question
$\endgroup$
10
  • $\begingroup$ @bof See my edit! Interestingly, while this basic idea kills most preservation theorems in the finite setting, the homomorphism preservation theorem holds: see Rossman. $\endgroup$
    – Noah Schweber
    Commented Jul 7 at 5:10
  • $\begingroup$ Is there a counterexample without function symbols? $\endgroup$
    – bof
    Commented Jul 8 at 9:27
  • $\begingroup$ Do you know if there is a sentence which is preserved, in the finite setting, by homomorphs, substructures and direct products, but is not equivalent to a universally quantified conjunction of atomic formulas? $\endgroup$
    – bof
    Commented Jul 8 at 9:30
  • 1
    $\begingroup$ @bof Oops, sorry - your second comment. I think we can modify the example in my post to work without function symbols; just augment the sentence with "If $R$ is the graph of a function then ..." appropriately, so that the sentence descends vacuously to substructures we don't want. $\endgroup$
    – Noah Schweber
    Commented Jul 11 at 3:31
  • 1
    $\begingroup$ Does that work? Can't a model of $\neg\theta$ be embedded in a larger structure which satisfies $\theta$ "vacuously" because $R$ is no longer the graph of a function? $\endgroup$
    – bof
    Commented Jul 11 at 4:56

0

Reset to default

You must log in to answer this question.