Density of compressible types and some consequences

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.

v2: New corollary 6.34 on stable reducts; minor fixes elsewhere; numbering changed in section 6. v3: Minor revisions; numbering changed in section 6; accepted for publication in JEMS