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)

Request Permissions   Purchase Content 
 
 

 

Externally definable sets and dependent pairs II


Authors: Artem Chernikov and Pierre Simon
Journal: Trans. Amer. Math. Soc. 367 (2015), 5217-5235
MSC (2010): Primary 03C45, 03C50; Secondary 05D99, 68R05
DOI: https://doi.org/10.1090/S0002-9947-2015-06210-2
Published electronically: February 20, 2015
MathSciNet review: 3335415
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Hans Adler, Introduction to theories without the independence property, to appear in Archive Math. Logic (2008).
  • [2] 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 (93m:52008), https://doi.org/10.1016/0001-8708(92)90052-M
  • [3] 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).
  • [4] 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 (2001d:03088), https://doi.org/10.1090/S0002-9947-00-02672-6
  • [5] Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1978. MR 506522 (80a:05120)
  • [6] Enrique Casanovas and Martin Ziegler, Stable theories with a new predicate, J. Symbolic Logic 66 (2001), no. 3, 1127-1140. MR 1856732 (2002k:03050), https://doi.org/10.2307/2695097
  • [7] Artem Chernikov and Itay Kaplan, Forking and dividing in $ {\rm NTP}_2$ theories, J. Symbolic Logic 77 (2012), no. 1, 1-20. MR 2951626, https://doi.org/10.2178/jsl/1327068688
  • [8] Artem Chernikov and Pierre Simon, Externally definable sets and dependent pairs, Israel J. Math. 194 (2013), no. 1, 409-425. MR 3047077, https://doi.org/10.1007/s11856-012-0061-9
  • [9] Sarah Cotter and Sergei Starchenko, Forking in VC-minimal theories, J. Symbolic Logic 77 (2012), no. 4, 1257-1271. MR 3051624, https://doi.org/10.2178/jsl.7704110
  • [10] Françoise Delon, Définissabilité avec paramètres extérieurs dans $ {\bf Q}_p$ et $ {\bf R}$, Proc. Amer. Math. Soc. 106 (1989), no. 1, 193-198 (French, with English summary). MR 953003 (90d:03060), https://doi.org/10.2307/2047391
  • [11] Vincent Guingona, On uniform definability of types over finite sets, J. Symbolic Logic 77 (2012), no. 2, 499-514. MR 2963018, https://doi.org/10.2178/jsl/1333566634
  • [12] Ehud Hrushovski and Anand Pillay, On NIP and invariant measures, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 4, 1005-1061. MR 2800483 (2012e:03069), https://doi.org/10.4171/JEMS/274
  • [13] 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 (2011j:03087), https://doi.org/10.1007/s00454-009-9201-3
  • [14] Michael C. Laskowski, Vapnik-Chervonenkis classes of definable sets, J. London Math. Soc. (2) 45 (1992), no. 2, 377-384. MR 1171563 (93d:03039), https://doi.org/10.1112/jlms/s2-45.2.377
  • [15] Michael C. Laskowski and Anand Pillay, Uncountable categoricity for gross models, Proc. Amer. Math. Soc. 132 (2004), no. 9, 2733-2742. MR 2054800 (2005h:03068), https://doi.org/10.1090/S0002-9939-04-07451-9
  • [16] David Marker and Charles I. Steinhorn, Definable types in $ \mathcal {O}$-minimal theories, J. Symbolic Logic 59 (1994), no. 1, 185-198. MR 1264974 (95d:03056), https://doi.org/10.2307/2275260
  • [17] Jiří Matoušek, Bounded VC-dimension implies a fractional Helly theorem, Discrete Comput. Geom. 31 (2004), no. 2, 251-255. MR 2060639 (2005d:52011), https://doi.org/10.1007/s00454-003-2859-z
  • [18] Anand Pillay, Stable embeddedness and $ NIP$, J. Symbolic Logic 76 (2011), no. 2, 665-672. MR 2830421 (2012k:03092), https://doi.org/10.2178/jsl/1305810769
  • [19] 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 (91k:03085)
  • [20] Saharon Shelah, Dependent first order theories, continued, Israel J. Math. 173 (2009), 1-60. MR 2570659 (2011j:03077), https://doi.org/10.1007/s11856-009-0082-1
  • [21] Saharon Shelah and Pierre Simon, Adding linear orders, J. Symbolic Logic 77 (2012), no. 2, 717-725. MR 2963031, https://doi.org/10.2178/jsl/1333566647
  • [22] Pierre Simon, Distal and non-distal NIP theories, Ann. Pure Appl. Logic 164 (2013), no. 3, 294-318. MR 3001548, https://doi.org/10.1016/j.apal.2012.10.015

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03C45, 03C50, 05D99, 68R05

Retrieve articles in all journals with MSC (2010): 03C45, 03C50, 05D99, 68R05


Additional Information

Artem Chernikov
Affiliation: Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Edmond J. Safra Campus, Givat Ram, 91904 Jerusalem, Israel
Address at time of publication: Équipe de Logique Mathématique, IMJ - PRG, Université Paris Diderot Paris 7, UFR de Mathématiques, case 7012, 75205 Paris Cedex 13, France
Email: artem.chernikov@imj-prg.fr

Pierre Simon
Affiliation: Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Edmond J. Safra Campus, Givat Ram, 91904 Jerusalem, Israel
Address at time of publication: Université Claude Bernard - Lyon 1, Institut Camille Jordan, 43 boulevard du 11 novembre 1918, 69622 Villeurbanne Cedex, France
Email: simon@math.univ-lyon1.fr

DOI: https://doi.org/10.1090/S0002-9947-2015-06210-2
Keywords: NIP, UDTFS, externally definable sets, VC-dimension, elementary pairs
Received by editor(s): April 10, 2012
Received by editor(s) in revised form: May 16, 2013
Published electronically: February 20, 2015
Additional Notes: The first author was supported by the Marie Curie Initial Training Network in Mathematical Logic - MALOA - From Mathematical Logic to Applications, PITN-GA-2009-238381
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society