Stability theory, permutations of indiscernibles, and embedded finite models
HTML articles powered by AMS MathViewer
- by John Baldwin and Michael Benedikt
- Trans. Amer. Math. Soc. 352 (2000), 4937-4969
- DOI: https://doi.org/10.1090/S0002-9947-00-02672-6
- Published electronically: July 21, 2000
- PDF | Request permission
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 $|I_1|^+$-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 $|I_1|^+$-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
- S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
- A. K. Aĭlamazyan, M. M. Gilula, A. P. Stolboushkin, and G. F. Shvarts, Reduction of a relational model with infinite domains to the case of finite domains, Dokl. Akad. Nauk SSSR 286 (1986), no. 2, 308–311 (Russian). MR 823391
- John T. Baldwin, Fundamentals of stability theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1988. MR 918762, DOI 10.1007/978-3-662-07330-8
- O. Belegradek, A. Stolboushkin, M. Tsaitlin. Extended order-generic queries. Annals of Pure and Applied Logic 97 (1999), 85-125.
- O. Belegradek, Ya’acov Peterzil, Frank Wagner. Quasi $O$-minimal groups. Manuscript. To appear J. Symbolic Logic.
- Michael Benedikt, Guozhu Dong, Leonid Libkin, and Limsoon Wong, Relational expressive power of constraint query languages, J. ACM 45 (1998), no. 1, 1–34. MR 1616484, DOI 10.1145/273865.273870
- 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.
- 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.
- E. Casanovas and M. Ziegler. Stable theories with a new predicate. Preprint.
- C. C. Chang and H. J. Keisler, Model theory, 3rd ed., Studies in Logic and the Foundations of Mathematics, vol. 73, North-Holland Publishing Co., Amsterdam, 1990. MR 1059055
- Anuj Dawar, Steven Lindell, and Scott Weinstein, First order logic, fixed point logic and linear order, Computer science logic (Paderborn, 1995) Lecture Notes in Comput. Sci., vol. 1092, Springer, Berlin, 1996, pp. 161–177. MR 1461875, DOI 10.1007/3-540-61377-3_{3}7
- H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1995.
- J. Flum. Characterizing logics. In Model-Theoretic Logics, edited by J. Barwise and S. Feferman, pages 77–120, Springer-Verlag, 1985.
- J.Flum and M. Ziegler. Pseudo-finite Homogeneity and Saturation. Preprint. 1997.
- E. Grädel and Y. Gurevich. Metafinite model theory. In Proceedings of Logic and Comput. Complexity, LNCS vol. 960, 1994, pages 313–366.
- 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.
- Lauri Hella, Phokion G. Kolaitis, and Kerkko Luosto, Almost everywhere equivalence of logics in finite model theory, Bull. Symbolic Logic 2 (1996), no. 4, 422—443. MR 1460316, DOI 10.2307/421173
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
- Wilfrid Hodges and Anand Pillay, Cohomology of structures and some problems of Ahlbrandt and Ziegler, J. London Math. Soc. (2) 50 (1994), no. 1, 1–16. MR 1277750, DOI 10.1112/jlms/50.1.1
- Richard Hull and Jianwen Su, Domain independence and the relational calculus, Acta Inform. 31 (1994), no. 6, 513–524. MR 1300053, DOI 10.1007/BF01213204
- Paris C. Kanellakis, Gabriel M. Kuper, and Peter Z. Revesz, Constraint query languages, J. Comput. System Sci. 51 (1995), no. 1, 26–52. Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Nashville, TN, 1990). MR 1347942, DOI 10.1006/jcss.1995.1051
- H. Jerome Keisler, Finite approximations of infinitely long formulas, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 158–169. MR 0202602
- H. Jerome Keisler, Measures and forking, Ann. Pure Appl. Logic 34 (1987), no. 2, 119–169. MR 890599, DOI 10.1016/0168-0072(87)90069-8
- Hirotaka Kikyo and Akito Tsuboi, On reduction properties, J. Symbolic Logic 59 (1994), no. 3, 900–911. MR 1295977, DOI 10.2307/2275916
- Michael C. Laskowski, Vapnik-Chervonenkis classes of definable sets, J. London Math. Soc. (2) 45 (1992), no. 2, 377–384. MR 1171563, DOI 10.1112/jlms/s2-45.2.377
- Dugald Macpherson and Charles Steinhorn, On variants of o-minimality, Ann. Pure Appl. Logic 79 (1996), no. 2, 165–209. MR 1396850, DOI 10.1016/0168-0072(95)00037-2
- David Marker and Charles I. Steinhorn, Definable types in $\scr O$-minimal theories, J. Symbolic Logic 59 (1994), no. 1, 185–198. MR 1264974, DOI 10.2307/2275260
- Martin Otto and Jan Van den Bussche, First-order queries on databases embedded in an infinite structure, Inform. Process. Lett. 60 (1996), no. 1, 37–41. MR 1420326, DOI 10.1016/S0020-0190(96)00140-8
- Jan Paredaens, Jan Van den Bussche, and Dirk Van Gucht, First-order queries on finite structures over the reals, SIAM J. Comput. 27 (1998), no. 6, 1747–1763. MR 1622649, DOI 10.1137/S009753979629766
- Anand Pillay, Definability of types, and pairs of O-minimal structures, J. Symbolic Logic 59 (1994), no. 4, 1400–1409. MR 1312317, DOI 10.2307/2275712
- Anand Pillay and Saharon Shelah, Classification theory over a predicate. I, Notre Dame J. Formal Logic 26 (1985), no. 4, 361–376. MR 799506, DOI 10.1305/ndjfl/1093870929
- Bruno Poizat, Cours de théorie des modèles, Bruno Poizat, Lyon, 1985 (French). Une introduction à la logique mathématique contemporaine. [An introduction to contemporary mathematical logic]. MR 817208
- Bruno Poizat, Paires de structures stables, J. Symbolic Logic 48 (1983), no. 2, 239–249 (French). MR 704080, DOI 10.2307/2273543
- Saharon Shelah, Classification theory and the number of nonisomorphic models, Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam-New York, 1978. MR 513226
Bibliographic 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
- Received by editor(s): March 17, 1998
- Published electronically: July 21, 2000
- Additional Notes: The first author was partially supported by DMS-9803496
- © Copyright 2000 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 352 (2000), 4937-4969
- MSC (2000): Primary 03C45; Secondary 68P15, 03C40
- DOI: https://doi.org/10.1090/S0002-9947-00-02672-6
- MathSciNet review: 1776884