*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

syntacticcharacterization 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})$.

Borelset of $L_{\omega_1\omega}$-sentences, $B_m$, each of which is preserved under $m$, such that every $L_{\omega_1\omega}$-sentence preserved under $m$ is equivalent to a (possibly uncountable) conjunction of sentences in $B_m$. $\endgroup$ – Noah Schweber Nov 17 '16 at 22:24Question 3) go through to $L_{\infty\omega}$. $\endgroup$ – Pedro Sánchez Terraf Nov 17 '16 at 23:55