On the shatter functions of semilinear families

Seminar series

Logic Seminar

Date

Thu, 23 Feb 2023
17:00

Location

Speaker

Chieu-Minh Tran

Organisation

National University of Singapore

Toward a characterization of modularity using shatter functions, we show that an o-minimal expansion of the real ordered additive group $(\mathbb{R}; 0, +,<)$ does not define restricted multiplication if and only if the shatter function of every definable family is asymptotic to a polynomial. Our result implies that vc-density can only take integer values in $(\mathbb{R}; 0, +,<)$ confirming a special case of a conjecture by Chernikov. (Joint with Abdul Basit.)