Density of compressible types and some consequences
Preprint
Abstract
We study compressible types in the context of (local and global) NIP. By extending a result in machine learning theory (the existence of a bound on the recursive teaching dimension), we prove density of compressible types. Using this, we obtain explicit uniform honest definitions for NIP formulas (answering a question of Eshel and the second author), and build compressible models in countable NIP theories.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- On uniform definability of types over finite sets for NIP formulasJournal of Mathematical Logic, 2020
- Remarks on generic stability in independent theoriesAnnals of Pure and Applied Logic, 2020
- Invariant types in NIP theoriesJournal of Mathematical Logic, 2015
- Externally definable sets and dependent pairs IITransactions of the American Mathematical Society, 2015
- On uniform definability of types over finite setsThe Journal of Symbolic Logic, 2012
- On NIP and invariant measuresJournal of the European Mathematical Society, 2011
- Dependent first order theories, continuedIsrael Journal of Mathematics, 2009
- On generically stable types in dependent theoriesThe Journal of Symbolic Logic, 2009
- Bounded VC-Dimension Implies a Fractional Helly TheoremDiscrete & Computational Geometry, 2003
- Canonical forms for definable subsets of algebraically closed and real closed valued fieldsThe Journal of Symbolic Logic, 1995