Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-11T06:25:23.992Z Has data issue: false hasContentIssue false
  • English
  • Français

THICKET DENSITY

Part of: Model theory

Published online by Cambridge University Press:  15 February 2021

SIDDHARTH BHASKAR
SIDDHARTH BHASKAR*
Affiliation:
DEPARTMENT OF COMPUTER SCINECE HAVERFORD COLLEGEHAVERFORD, PA19041, USA and DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF COPENHAGEN COPENHAGEN 2100, DENMARK E-mail: sbhaskar@di.ku.dk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We define a new type of “shatter function” for set systems that satisfies a Sauer–Shelah type dichotomy, but whose polynomial-growth case is governed by Shelah’s two-rank instead of VC dimension. We identify the least exponent bounding the rate of growth of the shatter function, the quantity analogous to VC density, with Shelah’s $\omega $ -rank.

Keywords

model theorystability theoryVC-densityset systems

MSC classification

Primary: 03C45: Classification theory, stability and related concepts
Type
Article
Information
The Journal of Symbolic Logic , Volume 86 , Issue 1 , March 2021 , pp. 110 - 127
Check for updates
Copyright
© The Association for Symbolic Logic 2021

References

REFERENCES

Aschenbrenner, M., Dolich, A., Haskell, D., Macpherson, D. and Starchenko, S., Vapnik-Chervonenkis density in some theories without the independence property, II . Notre Dame Journal of Formal Logic , vol. 54 (2011), pp. 311–363.Google Scholar
Aschenbrenner, M., Dolich, A., Haskell, D., Macpherson, D. and Starchenko, S., Vapnik-Chervonenkis density in some theories without the independence property, I . Transactions of the American Mathematical Society , vol. 368 (2015), pp. 5889–5949.CrossRefGoogle Scholar
Assouad, P., Densite et dimension . Annales de l’Institut Fourier , vol. 33 (1983), no. 3, pp. 233–282.CrossRefGoogle Scholar
Chase, H. and Freitag, J., Model theory and machine learning . The Bulletin of Symbolic Logic , vol. 25 (2019), no. 3, pp. 319–332.CrossRefGoogle Scholar
Chase, H. and Freitag, J., Model theory and combinatorics of banned sequences, 2020.CrossRefGoogle Scholar
Guingona, V. and Hill, C., On a common generalization of Shelah’s 2-rank, dp-rank, and o-minimal dimension . Annals of Pure and Applied Logic , vol. 166 (2013), pp. 502–525.CrossRefGoogle Scholar
Hodges, W., A Shorter Model Theory , Cambridge University Press, New York, 1997.Google Scholar
Laskowski, M. C., Vapnik-chervonenkis classes of definable sets . Journal of the London Mathematical Society , vol. s2–45 (1992), no. 2, pp. 377–384.CrossRefGoogle Scholar
Lynch, N. A. and Blum, E. K., Relative complexity of operations on numeric and bit-string algebras . Mathematical Systems Theory , vol. 13 (1980), pp. 187–207.CrossRefGoogle Scholar
Pillay, A., An Introduction to Stability Theory , Clarendon Press, Oxford, 1983.Google Scholar
Shelah, S., Classification Theory , Elsevier Science Publishers, Amsterdam, 1978.Google Scholar
Tiuryn, J., A simplified proof of $DDL< DL$ . Information and Computation , vol. 81 (1989), no. 1, pp. 1–12.CrossRefGoogle Scholar
Vapnik, V. N. and Ya Chervonenkis, A. Y., The uniform convergence of frequencies of the appearance of events to their probabilities . Theory of Probability and Its Applications , vol. 16 (1971), pp. 264–280.CrossRefGoogle Scholar