Elementary classes of finite VC-dimension (Q494638): Difference between revisions

The main result of this paper is as follows: Let \({\mathcal U}\) be a saturated model of inaccessible cardinality. For \(D\subseteq{\mathcal U}\), let \(e(D)\) be the collection of \(C\subseteq{\mathcal U}\) such that \(\langle{\mathcal U},C\rangle\equiv\langle{\mathcal U},D\rangle\). Then, \(D\) is externally definable when \(e(D)\) is of finite VC-dimension. In general, these two conditions are not equivalent; but they are if the theory is NIP (non-independence property). \(D\) is externally definable, by definition, if \(D= \{a\in{\mathcal U}\mid \phi(x,a)\in p\}\) with some type \(p\) over \({\mathcal U}\), and a formula \(\phi(x,z)\). \(e(D)\) is of finite VC-dimension means, by definition, that there is some \(n<\omega\) such that every subset \(B\subseteq{\mathcal U}\) of size \(n\) has a subset that is not \(B\cap C\) for any \(C\in e(D)\). (`VC' stands for `Vapnik-Chervonenkis'.) The author obtained ``loosely connected'' results, touching on Lascar invariance, dividing, and second-order language with one relation variable. A number of characterizations of Lascar invariance are proved.