Externally definable sets and dependent pairs II

Chernikov, Artem; Simon, Pierre

doi:10.1090/S0002-9947-2015-06210-2

Externally definable sets and dependent pairs II
HTML articles powered by AMS MathViewer

by Artem Chernikov and Pierre Simon PDF

Trans. Amer. Math. Soc. 367 (2015), 5217-5235 Request permission

Abstract:

We continue investigating the structure of externally definable sets in $\mathrm {NIP}$ theories and preservation of $\mathrm {NIP}$ after expanding by new predicates. Most importantly: types over finite sets are uniformly definable; over a model, a family of non-forking instances of a formula (with parameters ranging over a type-definable set) can be covered with finitely many invariant types; we give some criteria for the boundedness of an expansion by a new predicate in a distal theory; naming an arbitrary small indiscernible sequence preserves $\mathrm {NIP}$, while naming a large one doesn’t; there are models of $\mathrm {NIP}$ theories over which all 1-types are definable, but not all $n$-types.

References

Hans Adler, Introduction to theories without the independence property, to appear in Archive Math. Logic (2008).
Noga Alon and Daniel J. Kleitman, Piercing convex sets and the Hadwiger-Debrunner $(p,q)$-problem, Adv. Math. 96 (1992), no. 1, 103–112. MR 1185788, DOI 10.1016/0001-8708(92)90052-M
Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson, and Sergei Starchenko, Vapnik-chervonenkis density in some theories without the independence property, I, Preprint, arXiv: 1109.5438 (2011).
John Baldwin and Michael Benedikt, Stability theory, permutations of indiscernibles, and embedded finite models, Trans. Amer. Math. Soc. 352 (2000), no. 11, 4937–4969. MR 1776884, DOI 10.1090/S0002-9947-00-02672-6
Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
Enrique Casanovas and Martin Ziegler, Stable theories with a new predicate, J. Symbolic Logic 66 (2001), no. 3, 1127–1140. MR 1856732, DOI 10.2307/2695097
Artem Chernikov and Itay Kaplan, Forking and dividing in $\textrm {NTP}_2$ theories, J. Symbolic Logic 77 (2012), no. 1, 1–20. MR 2951626, DOI 10.2178/jsl/1327068688
Artem Chernikov and Pierre Simon, Externally definable sets and dependent pairs, Israel J. Math. 194 (2013), no. 1, 409–425. MR 3047077, DOI 10.1007/s11856-012-0061-9
Sarah Cotter and Sergei Starchenko, Forking in VC-minimal theories, J. Symbolic Logic 77 (2012), no. 4, 1257–1271. MR 3051624, DOI 10.2178/jsl.7704110
Françoise Delon, Définissabilité avec paramètres extérieurs dans $\textbf {Q}_p$ et $\textbf {R}$, Proc. Amer. Math. Soc. 106 (1989), no. 1, 193–198 (French, with English summary). MR 953003, DOI 10.1090/S0002-9939-1989-0953003-8
Vincent Guingona, On uniform definability of types over finite sets, J. Symbolic Logic 77 (2012), no. 2, 499–514. MR 2963018, DOI 10.2178/jsl/1333566634
Ehud Hrushovski and Anand Pillay, On NIP and invariant measures, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 4, 1005–1061. MR 2800483, DOI 10.4171/JEMS/274
H. R. Johnson and M. C. Laskowski, Compression schemes, stable definable families, and o-minimal structures, Discrete Comput. Geom. 43 (2010), no. 4, 914–926. MR 2610477, DOI 10.1007/s00454-009-9201-3
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
Michael C. Laskowski and Anand Pillay, Uncountable categoricity for gross models, Proc. Amer. Math. Soc. 132 (2004), no. 9, 2733–2742. MR 2054800, DOI 10.1090/S0002-9939-04-07451-9
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
Jiří Matoušek, Bounded VC-dimension implies a fractional Helly theorem, Discrete Comput. Geom. 31 (2004), no. 2, 251–255. MR 2060639, DOI 10.1007/s00454-003-2859-z
Anand Pillay, Stable embeddedness and $NIP$, J. Symbolic Logic 76 (2011), no. 2, 665–672. MR 2830421, DOI 10.2178/jsl/1305810769
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
Saharon Shelah, Dependent first order theories, continued, Israel J. Math. 173 (2009), 1–60. MR 2570659, DOI 10.1007/s11856-009-0082-1
Saharon Shelah and Pierre Simon, Adding linear orders, J. Symbolic Logic 77 (2012), no. 2, 717–725. MR 2963031, DOI 10.2178/jsl/1333566647
Pierre Simon, Distal and non-distal NIP theories, Ann. Pure Appl. Logic 164 (2013), no. 3, 294–318. MR 3001548, DOI 10.1016/j.apal.2012.10.015