5
$\begingroup$

The Łos-Tarski preservation theorem states that a set of formulas $F$ of first-order language $L$ is preserved under substructures for models of theory $T$ in $L$ precisely when $F$ is equivalent modulo $T$ to a set of universal formulas of $L$. The often-seen corollary is that a formula of $L$ is preserved by embeddings between models of $T$ precisely when it is equivalent modulo $T$ to an existential formula of $L$.

Lyndon's preservation theorem has a similar flavour, relating positive formulas and surjective homomorphisms. Moreover, first-order formulas preserved under homomorphisms are precisely those that are equivalent to an existential positive first-order formula with the same quantifier-rank.

These kinds of preservation results use first-order theories. However, some higher-order logics, such as the monadic fragment of second-order logic, are sufficiently restricted that they retain many of the properties of first-order logic. This motivates my question:

Are any preservation results known for logics $L$ and theories $T$ beyond first-order? In other words, are there results such as: a formula of logic $L$ is preserved under embeddings between models of theory $T$ in $L$ precisely when it is equivalent modulo $T$ to an existential formula of $L$?

Pointers or even key phrases would be appreciated. I'm struggling to find relevant references, which may indicate that I have overlooked a trivial reason why such theorems cannot exist: if this is the case then a hint would be appreciated.

References:

  • Wilfrid Hodges, Model Theory, Cambridge University Press, 1993.
  • Benjamin Rossman, Homomorphism preservation theorems, Journal of the ACM 55(3), 2008. doi:10.1145/1379759.1379763 (preprint)
$\endgroup$
2

1 Answer 1

7
$\begingroup$

There are a number of preservation results concerning the infinitary logic $L_{\omega_{1},\omega}$, as well as its so-called admissible fragments. Such results include an analogue of the one you mentioned about existential sentences.

Here are some basic sources in this direction:

H.J. Keisler, Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers. Studies in Logic and the Foundations of Mathematics, Vol. 62. North-Holland Publishing Co., Amsterdam-London, 1971 [see Chapter 7].

The following paper also establishes a preservation theorem for "end extensions" (which were called "outer extensions" in the old days).

S. Feferman, Persistent and invariant formulas for outer extensions. Compositio Math. 20 1968 29–52 (1968).

See this recent paper for survey of related work to Feferman's result.

$\endgroup$
3
  • $\begingroup$ The Feferman paper uses restricted quantification as a key concept. This seems highly relevant: thanks for the pointer! $\endgroup$ Jun 16, 2011 at 17:45
  • $\begingroup$ @András: I am glad to hear that the Feferman paper is of interest; you will find related work on MathSciNet on the page containing the review of Feferman's paper (including Marker's model-theoretic proof of the theorem). I have edited my answer to by inserting a link to a recent survey paper of Feferman that includes a discussion of his result and related work. $\endgroup$
    – Ali Enayat
    Jun 16, 2011 at 18:24
  • $\begingroup$ The link to springerlink.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$ Dec 8, 2022 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.