Elementary classes of finite VC-dimension (Q494638)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Elementary classes of finite VC-dimension |
scientific article |
Statements
Elementary classes of finite VC-dimension (English)
0 references
1 September 2015
0 references
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.
0 references
VC-dimension
0 references
externally definable sets
0 references
Lascar invariance
0 references