Submission date: 12 July 2021

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.

Mathematics Subject Classification: 03C45 (Primary) 03C95, 03C50 (Secondary)

Keywords and phrases:

Full text arXiv 2107.05197: pdf, ps.