VC Dimension of o-Minimal Families

93 Views Asked by At

I'm not a model-theoretic person, I'm looking at Laskowski (1992), "VC Classes of Definable Sets". Have I understood correctly that the following true: If A is an o-minimal subset of $\mathbb{R}^n \times \mathbb{R}^m$, then the collection $\{ A_y \mid y \in \mathbb{R}^n \}$, where $A_y = \{ x \in \mathbb{R}^m \mid (y,x) \in A \}$ is the fibre of A at y, has finite VC dimension?

Excert from Laskowski (1992)

1

There are 1 best solutions below

0
On BEST ANSWER

"$A$ is an o-minimal subset" doesn't make any sense. You mean "$A\subseteq \mathbb{R}^{n+m}$ is a definable subset for an o-minimal structure on $\mathbb{R}$".

But yes, your reading of Laskowski is correct. More generally, a complete first-order theory $T$ is called NIP (not independence property) if for every model $M$, every family of fibers for a definable set in $M$ has finite VC dimension. And o-minimal theories are primary examples of NIP theories.