Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Stability theory, permutations of indiscernibles, and embedded finite models


Authors: John Baldwin and Michael Benedikt
Journal: Trans. Amer. Math. Soc. 352 (2000), 4937-4969
MSC (2000): Primary 03C45; Secondary 68P15, 03C40
Published electronically: July 21, 2000
MathSciNet review: 1776884
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

We show that the expressive power of first-order logic 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 in the setting of embedded finite models. These results depend on several results in infinite model theory. Let $I$ be a set of indiscernibles in a model $M$and suppose $(M,I)$ is elementarily equivalent to $(M_1,I_1)$ where $M_1$ is $\vert I_1\vert^+$-saturated. If $M$ is stable and $(M,I)$ is saturated, then every permutation of $I$extends to an automorphism of $M$ and the theory of $(M,I)$ is stable. Let $I$ be a sequence of $<$-indiscernibles in a model $M$, which does not have the independence property, and suppose $(M,I)$ is elementarily equivalent to $(M_1,I_1)$ where $(I_1,<)$ is a complete dense linear order and $M_1$ is $\vert I_1\vert^+$-saturated. Then $(M,I)$-types over $I$are order-definable and if $(M,I)$ is $\aleph_1$-saturated, every order preserving permutation of $I$ can be extended to a back-and-forth system.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03C45, 68P15, 03C40

Retrieve articles in all journals with MSC (2000): 03C45, 68P15, 03C40


Additional Information

John Baldwin
Affiliation: Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607
Email: jbaldwin@math.uic.edu

Michael Benedikt
Affiliation: Bell Laboratories, 1000 E. Warrenville Rd., Naperville, Illinois 60566
Email: benedikt@research.bell-labs.com

DOI: http://dx.doi.org/10.1090/S0002-9947-00-02672-6
PII: S 0002-9947(00)02672-6
Received by editor(s): March 17, 1998
Published electronically: July 21, 2000
Additional Notes: The first author was partially supported by DMS-9803496
Article copyright: © Copyright 2000 American Mathematical Society