Remote Access Transactions of the American Mathematical Society
Green Open Access

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

Abstract | References | Similar Articles | Additional Information


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?)

  • 1. S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
  • 2. A.K. Ailamazyan, M.M. Gilula, A.P. Stolboushkin and G.F. Shvarts. Reduction of a relational model with infinite domains to the finite-domain case, Dokl. Akad. Nauk SSSR 286 (1996), 308-311. MR 87h:68022.
  • 3. J. T. Baldwin. Fundamentals of Stability Theory. Springer-Verlag, 1988. MR 89k:03002
  • 4. O.Belegradek, A. Stolboushkin, M. Tsaitlin. Extended order-generic queries. Annals of Pure and Applied Logic 97 (1999), 85-125. CMP 99:10
  • 5. O.Belegradek, Ya'acov Peterzil, Frank Wagner. Quasi $O$-minimal groups. Manuscript. To appear J. Symbolic Logic.
  • 6. M. Benedikt, G. Dong, L. Libkin, L. Wong. Relational expressive power of constraint query languages. J. ACM 45 (1998), 1-34. MR 99e:68028
  • 7. M. Benedikt and L. Libkin. On the structure of queries in constraint query languages. In Proceedings of 11th IEEE Symposium on Logic in Computer Science, New Brunswick, New Jersey, 1996. CMP 97:16
  • 8. M. Benedikt and L. Libkin. Languages for Relational Databases over Interpreted Structures. In Proceedings of 16th ACM Symposium on Principles of Database Systems, Tuscon Arizona, June 1996.
  • 9. E. Casanovas and M. Ziegler. Stable theories with a new predicate. Preprint.
  • 10. C.C. Chang and H.J. Keisler. Model Theory. Third edition, North-Holland, Elsevier, 1990. MR 91c:03026
  • 11. A. Dawar, S. Lindell, S. Weinstein. First order logic, fixed point logic, and linear order. In Computer Science Logic '95, LNCS vol. 1092, 1996, pages 161-177. MR 98c:03078
  • 12. H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1995. CMP 97:01
  • 13. J. Flum. Characterizing logics. In Model-Theoretic Logics, edited by J. Barwise and S. Feferman, pages 77-120, Springer-Verlag, 1985. CMP 18:06
  • 14. J.Flum and M. Ziegler. Pseudo-finite Homogeneity and Saturation. Preprint. 1997.
  • 15. E. Grädel and Y. Gurevich. Metafinite model theory. In Proceedings of Logic and Comput. Complexity, LNCS vol. 960, 1994, pages 313-366. CMP 97:12
  • 16. S. Grumbach and J. Su. First-order definability over constraint databases. In Proc. Conf. on Constr. Progr. '95, Lecture Notes in Comput. Sci., 976, Springer-Verlag, 199, pages 121-136. CMP 98:02
  • 17. L. Hella,P. Kolaitis, and K.Luosto. Almost Everywhere Equivalence of Logics Bulletin of Symbolic Logic 2 (1996), 422-443. MR 98c:03079
  • 18. W. Hodges. Model Theory. Cambridge University Press, 1993. MR 94e:03002
  • 19. W. Hodges and A. Pillay. Cohomology of Structures and some problems of Ahlbrandt and Ziegler J. London Math. Soc., 50 (1994) 1-16. MR 95i:03073
  • 20. R. Hull and J. Su. Domain independence and the relational calculus. Acta Informatica 31:513-524, 1994. MR 95h:68120
  • 21. P. Kanellakis, G. Kuper, and P. Revesz. Constraint query languages. JCSS 51 (1995), 26-52. MR 96m:68041
  • 22. H.J. Keisler. Finite Approximation of Infinitely Long Formulas. In The Theory of Models Addison, Henkin, and Tarski,eds. North-Holland, 1965, pp. 158-169. MR 34:2464
  • 23. H.J. Keisler. Measures and Forking. Annals of Pure and Applied Logic 34 (1987), no. 2, 119-169. MR 88i:03052
  • 24. H. Kikyo and A. Tsuboi. On reduction properties. The Journal of Symbolic Logic 59 (1994), 900-911. MR 95m:03074
  • 25. M. C. Laskowski. Vapnik-Chervonenkis classes of definable sets. Journal of the London Mathematical Society. Vol. 45 (1992), no. 2, 377-384. MR 93d:03039
  • 26. D. Macpherson and C. Steinhorn. On variants of $o$-minimality. Ann. Pure Appl. Logic 79 (1996), 165-209. MR 97e:03050
  • 27. C. Marker and C. Steinhorn. Definable types in $O$-minimal theories. The Journal of Symbolic Logic 59 (1994), 185-198. MR 95d:03056
  • 28. M. Otto and J. Van den Bussche. First-order queries on databases embedded in an infinite structure. Information Processing Letters, 60 (1996), no. 1, 37-41. MR 97g:68056
  • 29. J. Paredaens, J. Van den Bussche, and D. Van Gucht. First-order queries on finite structures over the reals. SIAM J. Comput. 27 (1998), 1747-1763. MR 99g:68050
  • 30. A. Pillay. Definability of types and pairs of O-minimal structures. The Journal of Symbolic Logic 59 (1994) 1400-1409. MR 95m:03076
  • 31. A. Pillay and S. Shelah. Classification theory over a predicate I. Notre Dame Journal of Formal Logic 26 (1985), 361-376. MR 87d:03095
  • 32. Bruno Poizat, Cours de theories de modéles Villeurbanne: Nur al-Mantiq wal-Ma'rifah. MR 87f:03084
  • 33. Bruno Poizat. Paires de structure stables. The Journal of Symbolic Logic 48 (1983), 239-249. MR 84h:03082
  • 34. S. Shelah. Classification Theory and the Number of Nonisomorphic Models. North-Holland, 1978. MR 81a:03030

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

Michael Benedikt
Affiliation: Bell Laboratories, 1000 E. Warrenville Rd., Naperville, Illinois 60566

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

American Mathematical Society