Embedded Finite Models, Stability Theory, and the Impact of Order

We show that the expressive power of the relational calculus over finite models embedded in a model M is determined by stability-theoretic properties of M. In particular, we show that if M is stable, then every class of finite structures that can be defined by embedding the structures in M, can be defined in pure first-order logic. We also show that if M does not have the independence property, then any class of finite structures that can be defined by embedding the structures in M, can be defined in first-order logic over a dense linear order. This extends known results on the definability of classes of finite structures and ordered finite structures to the setting of embedded finite models, and gives expressive bounds on new constraint query languages. We show that if M is a model of a stabel theory T, I is a set of indiscernibles in T and (m, I) is elementarily equivalent to (M sub 1, I sub 1) where M sub 1 is I sup + sub 1 saturated then every permutation of I extends to an automorphism of M and the theory of (M, I) is stable.