Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)
share|improve this question
    
1. The link to wikipedia is broken 2. Possibly related: mathoverflow.net/questions/51654/… ? –  Pasha Zusmanovich Jun 12 '11 at 15:19
    
@Pasha: thanks for pointing this out, fixed the link. –  András Salamon Jun 14 '11 at 0:05

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
The Feferman paper uses restricted quantification as a key concept. This seems highly relevant: thanks for the pointer! –  András Salamon Jun 16 '11 at 17:45
    
@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. –  Ali Enayat Jun 16 '11 at 18:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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