Stability theory, permutations of indiscernibles, and embedded finite models
John T. Baldwin, Michael Benedikt · Transactions of the American Mathematical Society · 2000
We show that the expressive power of first-order logic over finite models embedded in a model M M is determined by stability-theoretic properties of M M . In particular, we show that if M M is stable, then every class of finite structures that can be defined by embedding the structures in M M , can be defined in pure first-order logic. We also show that if M M does not have the independence property, then any class of finite structures that can be defined by embedding the structures in M 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 in the setting of embedded finite models. These results depend on several results in infinite model theory. Let I I be a set of indiscernibles in a model M M and suppose ( M , I ) (M,I) is elementarily equivalent to ( M 1 , I 1 ) (M_1,I_1) where M 1 M_1 is | I 1 | + |I_1|^+ -saturated. If M M is stable and ( M , I ) (M,I) is saturated, then every permutation of I