Characterizations of monadic NIP
HTML articles powered by AMS MathViewer
- by Samuel Braunfeld and Michael C. Laskowski;
- Trans. Amer. Math. Soc. Ser. B 8 (2021), 948-970
- DOI: https://doi.org/10.1090/btran/94
- Published electronically: November 2, 2021
- HTML | PDF
Abstract:
We give several characterizations of when a complete first-order theory $T$ is monadically NIP, i.e. when expansions of $T$ by arbitrary unary predicates do not have the independence property. The central characterization is a condition on finite satisfiability of types. Other characterizations include decompositions of models, the behavior of indiscernibles, and a forbidden configuration. As an application, we prove non-structure results for hereditary classes of finite substructures of non-monadically NIP models that eliminate quantifiers.References
- Hans Adler and Isolde Adler, Interpreting nowhere dense graph classes as a classical notion of model theory, European J. Combin. 36 (2014), 322–330. MR 3131898, DOI 10.1016/j.ejc.2013.06.048
- J. T. Baldwin and S. Shelah, Second-order quantifiers and the complexity of theories, Notre Dame J. Formal Logic 26 (1985), no. 3, 229–303. MR 796638, DOI 10.1305/ndjfl/1093870870
- Achim Blumensath, Simple monadic theories and partition width, MLQ Math. Log. Q. 57 (2011), no. 4, 409–431. MR 2832649, DOI 10.1002/malq.201010019
- Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé, Twin-width IV: low complexity matrices, preprint, arXiv:2102.03117 (2021).
- Peter Cameron, Thomas Prellberg, and Dudley Stark, Asymptotics for incidence matrix classes, Electron. J. Combin. 13 (2006), no. 1, Research Paper 85, 19. MR 2255427, DOI 10.37236/1111
- Alfred Dolich, John Goodrick, and David Lippel, Dp-minimality: basic facts and examples, Notre Dame J. Form. Log. 52 (2011), no. 3, 267–288. MR 2822489, DOI 10.1215/00294527-1435456
- Frank Gurski, Linear layouts measuring neighbourhoods in graphs, Discrete Math. 306 (2006), no. 15, 1637–1650. MR 2251098, DOI 10.1016/j.disc.2006.03.048
- H. D. Macpherson, Infinite permutation groups of rapid growth, J. London Math. Soc. (2) 35 (1987), no. 2, 276–286. MR 881516, DOI 10.1112/jlms/s2-35.2.276
- Dugald Macpherson, A survey of homogeneous structures, Discrete Math. 311 (2011), no. 15, 1599–1634. MR 2800979, DOI 10.1016/j.disc.2011.01.024
- Michael Morley, Categoricity in power, Trans. Amer. Math. Soc. 114 (1965), 514–538. MR 175782, DOI 10.1090/S0002-9947-1965-0175782-0
- Saharon Shelah, Monadic logic: Hanf numbers, Around classification theory of models, Lecture Notes in Math., vol. 1182, Springer, Berlin, 1986, pp. 203–223. MR 850059, DOI 10.1007/BFb0098511
- S. Shelah, Classification theory and the number of nonisomorphic models, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam, 1990. MR 1083551
- Pierre Simon, A guide to NIP theories, Lecture Notes in Logic, vol. 44, Association for Symbolic Logic, Chicago, IL; Cambridge Scientific Publishers, Cambridge, 2015. MR 3560428, DOI 10.1017/CBO9781107415133
- Pierre Simon, A note on stability and NIP in one variable, preprint, arXiv:2103.15799 (2021).
- Pierre Simon and Szymon Toruńczyk, Ordered graphs of bounded twin-width, preprint arXiv:2102.06881 (2021).
Bibliographic Information
- Samuel Braunfeld
- MR Author ID: 1197349
- Michael C. Laskowski
- MR Author ID: 110500
- Received by editor(s): May 3, 2021
- Received by editor(s) in revised form: August 5, 2021
- Published electronically: November 2, 2021
- Additional Notes: The second author was partially supported by NSF grant DMS-1855789
- © Copyright 2021 by the authors under Creative Commons Attribution 3.0 License (CC BY 3.0)
- Journal: Trans. Amer. Math. Soc. Ser. B 8 (2021), 948-970
- MSC (2020): Primary 03C45
- DOI: https://doi.org/10.1090/btran/94
- MathSciNet review: 4334194