Characterizations of monadic NIP

Braunfeld, Samuel; Laskowski, Michael

doi:10.1090/btran/94

Characterizations of monadic NIP
HTML articles powered by AMS MathViewer

by Samuel Braunfeld and Michael C. Laskowski HTML | PDF

Trans. Amer. Math. Soc. Ser. B 8 (2021), 948-970

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