Preservation results in abstract logics

Question

For readability, I've put the definitions of algebraic operation and preservation at the end of the question.

An old theme in logic is:

Given some algebraic operation, we can give a syntactic characterization of the sentences preserved by this operation.

For example, the sentences preserved by Cartesian products are the Horn sentences, and the sentences preserved by taking substructures are the universal sentences.

Of course, there are a couple caveats:

• First, these characterizations are only up to logical equivalence. E.g. $$\mbox{"$\exists x(x\not=x)\vee \forall x(R(x, x))$"}$$ is not a universal sentence, but is preserved by taking substructures.

• Second, and more importantly, these characterizations are logic-dependent! For example, there is a sentence $\varphi$ in second-order logic which is true in exactly the finite structures: $$\forall F((\forall x, y(F(x)=F(y)\iff x=y))\implies \forall x\exists y(F(y)=x)).$$ Clearly $\varphi$ is preserved under taking substructures, but it isn't universal (even allowing second-order universal quantifiers).

I would like to know what is known beyond the first-order context.

Question 1. What kinds of preservation results are known, or can we hope for, for logics other than first-order logic?

I'm particularly interested in second-order logic, infinitary logics, and first-order logics with cofinality quantifiers.

---

Now, this is a painfully broad question; so let me ask a more focused sub-question. There are several reasonable candidates, but here's my favorite:

Second-order logic is, to put it mildly, terrible: not only does it lack the Compactness, Lowenheim-Skolem, and Interpolation properties (not to mention basically all the other nice properties), its set of validities isn't even set-theoretically absolute. However, I don't know for a fact that it's bad from a preservation perspective! That is, I don't know of any reason why we can't give reasonable descriptions (up to equivalence) of the sentences of second-order logic preserved under various algebraic operations. Now of course these characterizations would be of dubious value, since equivalence of second-order sentences is incredibly complicated; but it would still be really neat if they existed!

Here's an attempt to precisely define what such a characterization should look like:

Suppose $\mathcal{L}$ is a logic. Say that an algebraic operation $m$ is syntactic for $\mathcal{L}$ if there is a computable set $P_m$ of $\mathcal{L}$-sentences preserved under $m$, such that every $\mathcal{L}$-sentence which is preserved under $m$ is equivalent to a (possibly infinite) conjunction of ones in $P_m$. (Note that this only makes sense if we have a canonical way of representing $\mathcal{L}$-sentences by natural numbers - so second-order logic is okay, but infinitary logic isn't.) Call such a $P_m$ a syntactic base for $m$ in $L$.

Then we can ask:

Question 2. Are any interesting algebraic operations syntactic for second-order logic? For example, is "substructure of" syntactic for second-order logic?

I suspect "substructure of" is not syntactic - indeed, I suspect that in a precise sense, no nontrivial algebraic operation is syntactic for second-order logic (although pinning down what "nontrivial" means here is nontrivial) - but I don't see how to prove it.

EDIT THE SECOND: It turns out "substructure of" is syntactic for second-order logic - see my answer below. However, this relies on a trick that doesn't appear to generalize to, say, products. So, I suspect the right algebraic operation to focus on is products, and here again I'm in the dark.

Note that really I should ask if any algebraic operations are consistently syntactic for second-order logic - there's no reason to believe that even simple examples can be settled in ZFC alone!

EDIT: A quick comment on this question. The question of whether a second-order sentence is preserved by a given algebraic operation is, in generally, set-theoretically contingent. For instance, let $\Phi$ be any second-order sentence whose validity is undecidable from ZFC (e.g. we may take a $\Phi$ which is valid iff CH holds). Then via standard techniques we can construct a second-order sentence $\hat{\Phi}$ such that for all structures $M$, we have $M\models\hat{\Phi}$ unless $\vert M\vert=2^\kappa$ where $\kappa$ is the smallest cardinality of a model of $\neg\Phi$. Then $\hat{\Phi}$ is preserved under substructures iff $\Phi$ is valid.

However, this does not show that whether a property is syntactic is set-theoretically contingent: note that in case $\hat{\Phi}$ is preserved under substructures, $\hat{\Phi}$ is equivalent to $\top$! So in principle we may have a syntactic base for an algebraic operation - provably in ZFC! - even if the preservation of a fixed sentence under that algebraic operation is set-theoretically contingent.

---

EDIT: Arguably second-order logic is a bridge too far. The other natural logic to try is $L_{\omega_1\omega}$, but here the notion of "syntactic" just doesn't work. Here's a stab at the right question: say that $m$ is "syntactic for $L_{\omega_1\omega}$" if there is a Borel set of reals $B$ whose intersection with the set of real codes for $L_{\omega_1\omega}$-sentences, $B_m$, has the following properties:

• Each $\varphi\in B_m$ is preserved under $m$, and

• Every $L_{\omega_1\omega}$-sentence preserved under $m$ is equivalent to a (possibly uncountable) conjunction of sentences in $B_m$.

Then we can ask, e.g.:

Question 3. Is "substructures of" is syntactic for $L_{\omega_1\omega}$?

---

Definitions.

By an algebraic operation, I mean a method of building new structures from old (here "structure" means "first-order structure"). Formally (and eliding set-theoretic subtleties), an algebraic operation is a function $m$ from classes of structures to classes of structures such that for all $\mathcal{C}$,

• $m(\mathcal{C})$ is closed under isomorphism,

• $\mathcal{C}\subseteq m(\mathcal{C})$, and

• $m(m(\mathcal{C}))=m(\mathcal{C})$.

Some classic examples of algebraic operations are:

• Homomorphic images

• Substructures

• Finite products

• Arbitrary products

• Ultraproducts

• Ultraroots

• And so forth.

Given an algebraic operation $m$ and a property $\mathfrak{P}$, say that $\mathfrak{P}$ is preserved by $m$ if - for every class of structures $\mathcal{C}$ - whenever every element of $\mathcal{C}$ has $\mathfrak{P}$, so does every element of $m(\mathcal{C})$.

Answer 1

This should really be a comment, but it's way too long:

Let $\sigma$ be the substructure operation: $\sigma(\mathcal{C})$ is the class of (structures isomorphic to) substructures of structures in $\mathcal{C}$. I asked, as a sub-question, about $\sigma$-preserving sentences in second-order logic. It turns out this is easier than I thought: $\sigma$ is syntactic for second-order logic, and in fact the proof of this is substantially easier than for first-order logic!

For a sentence $\varphi$ in a logic $\mathcal{L}$, consider the (a priori) informal statement $$\mbox{$\varphi_\sigma\equiv$ "Every substructure of $M$ is a model of $\varphi$."}$$ Then a silly attempt to get a handle on the $\sigma$-preserving sentences of $\mathcal{L}$ might begin by trying to show that $\varphi_\sigma$ is actually an $\mathcal{L}$-sentence, for every $\varphi$. Of course, in first-order logic there is an obvious barrier: the lack of a universal quantifier over sets.

Indeed, this barrier is insurmountable, and $\varphi_\sigma$ fails to be first-order expressible for general first-order $\varphi$: consider the language of linear orders, and the sentence $\varphi\equiv$ "Every element has an immediate successor." Then if $\varphi_\sigma$ were first-order expressible, it would have to hold in a nontrivial ultrapower of $(\mathbb{N}, <)$; but such a structure has descending sequences, so has a substructure isomorphic to $(\{-\infty\}\cup\mathbb{Z}, <)$, which does not satisfy $\varphi$.

In the case of first-order logic, since the silly strategy fails, we then find a more clever strategy using compactness. In second-order logic, though, the silly strategy works, since we can quantify over subsets of the domain! We can indeed express $\varphi_\sigma$ as a second-order sentence, for any second-order sentence $\varphi$. (There's a slight hiccup here, in case the language is infinite; but it's enough to quantify over substructures in the sublanguage of symbols actually used in $\varphi$, which is finite, so this quantification can be done in second-order logic. This issue seems to carry a bit more force if we're working modulo a theory $T$, but that's going beyond what I asked.)

Note that no such obvious "silly" strategy exists for preservation under Cartesian products; so this doesn't suggest in general that preservation results will exist for second-order logic. For this reason, I've changed the sub-question to focus on products, since I think that's actually the right example to begin with. Still, I think this is a neat observation.