For a (first-order) theory $T$, let the preservability degrees over $T$ be the following preorder $\mathsf{Pr}(T)$:
-
Elements of $\mathsf{Pr}(T)$ are finite sets of formulas in the language of $T$.
-
We set $\{\varphi_1(\overline{x}),…,\varphi_n(\overline{x})\}\sqsupseteq\{\psi_1(\overline{x}),…,\psi_k(\overline{x})\}$ iff for every pair of models $\mathcal{A},\mathcal{B}\models T$, every homomorphism $f:\mathcal{A}\rightarrow\mathcal{B}$ which preserves each $\varphi_i$ also preserves each $\psi_j$.
Here a homomorphism $h:\mathcal{X}\rightarrow\mathcal{Y}$ preserves a formula $\theta$ iff for all appropriate-length tuples $a_1,…,a_k\in \mathcal{X}$ we have $$\mathcal{X}\models\theta(a_1,…,a_k)\quad\implies\quad \mathcal{Y}\models\theta(h(a_1),…,h(a_k)).$$
There are a number of questions I'm interested in about $\mathsf{Pr}(T)$, but to start with I'm curious whether we ever have meets in $\mathsf{Pr}(T)$, ignoring relatively-boring cases:
Is there a theory $T$ such that every finite subset of $\mathsf{Pr}(T)$ has a greatest lower bound, but $\mathsf{Pr}(T)$ is not linearly ordered?
A couple quick observations:
-
Due to compactness we won't lose much by considering only finite sets of formulas: if every homomorphism preserving each $\varphi_i$ ($i\in\mathbb{N}$) also preserves $\psi$, then $\{\varphi_i:i\le n\}\sqsupseteq\{\psi\}$ for some $n$.
-
Even if $T$ is complete, $\mathsf{Pr}(T)$ could still be complicated. For example, if $\mathcal{A}$ is any nonstandard model of true arithmetic then there will be lots of homomorphisms out of $\mathcal{A}$ which fail to preserve even $\Pi_1$ properties.
Best Answer
Let me make some very general observations first.
A formula is preserved by all homomorphisms (between models of $T$) if and only if it is equivalent (modulo $T$) to a positive existential formula: one built up from atomic formulas and $\top$ and $\bot$ by $\land$, $\lor$, and $\exists$.
Given a set $F$ of formulas, a homomorphism preserving all the formulas in $F$ is the same as an ordinary homomorphism in the expanded language $L_F$ where we introduce a new relation symbol for each formula in $F$ (and expand $T$ to $T_F$ by axioms definining each new relation symbol). It follows that a formula $\psi$ is preserved by all homomorphisms preserving $F$ if and only if $\psi$ is equivalent (modulo $T_F$) to a positive existential $L_F$-formula.
Let's say a set of formulas $F$ is a preservation class if whenever $\psi$ is preserved by all homomorphisms preserving $F$, already $\psi\in F$. Equivalently, when $F$ is closed under positive existential definability in the sense described in the last paragraph.
Now the set of preservation classes, ordered by inclusion, is obviously a lattice: the meet of two preservation classes is their intersection, and the join of two preservation classes is the preservation class generated by their union.
The preorder you are interested in maps to the lattice of preservation classes in an obvious way, with range the finitely generated preservation classes. So your question can be rephrased to ask about the situation where the intersection of two finitely generated preservation classes is always finitely generated, but the preservation classes are not linearly ordered.
One way to arrange this is to make $T$ so trivial that every preservation class is finitely generated, while still having two incomparable formulas, i.e. formulas where neither is definable in terms of the other.
Consider the language with unary predicates $P,Q,R,S$, and a binary relation $\neq$. Let $T$ say that $P$ and $Q$ form a partition, $R$ defines an infinite and coinfinite subset of $P$, $S$ defines an infinite and coinfinite subset of $Q$, and $\neq$ is interpreted in the natural way. Note that $T$ is complete and has quantifier elimination.
Now I believe that there are only $4$ preservation classes: those generated by $\varnothing$ (the positive existential formulas), by $\lnot R$, by $\lnot S$, and by both $\lnot R$ and $\lnot S$ (all formulas). The lattice structure is a diamond, with $\lnot R$ and $\lnot S$ incomparable. If you like, I can try to write out a proof of these claims.