Cofinal families of finite VC-dimension

Omer Ben-Neria, Itay Kaplan, George Peterzil · 2025

Read Cofinal families of finite VC-dimension by Omer Ben-Neria, Itay Kaplan, George Peterzil (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-24744.txt.

Introduction

Omer Ben-Neria, Itay Kaplan, and George Peterzil ask how simple a complete family of small sets can be in this 2025 paper. The families must reach every size below a given bound. Simplicity is measured by a learning-theory number, the VC-dimension. For the smallest bound case, they show the floor can be met. That answer holds under standard set theory assumptions. For larger bounds, the answer splits sharply by whether the bound is singular or regular. Related and generalized versions are settled for the singular case.

Catalog record

CREATOROmer Ben-Neria, Itay Kaplan, George Peterzil
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-24744

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cofinal families of finite VC-dimension Thanks: The first author would like to thank the Israel Science Foundation for partial support of this research (Grant 1302/23). The second author would like to thank the Israel Science Foundation for partial support of this research (Grant no. 804/22). Omer Ben-Neria, Itay Kaplan, George Peterzil Abstract . Given infinite cardinals θ ≤ κ \theta\leq\kappa , we ask for the minimal VC-dimension of a cofinal family ℱ ⊆ [ κ ] < θ \mathcal{F}\subseteq[\kappa]^{<\theta} . We show that for θ = ω \theta=\omega and κ = ℵ n \kappa=\aleph_{n} it is consistent with ZFC that there exists such a family of VC-dimension n + 1 n+1 , which is known to be the lower bound. For θ > ω \theta>\omega we answer this question completely, demonstrating a strong dichotomy between the case of singular and regular θ \theta . We furthermore answer some relative and generalized versions of the above question for singular θ \theta , and answer a related question which appears in [ BBKS24 ] . 2020 Mathematics Subject Classification 03E35, 03E55, 05D99 1. Introduction Suppose that X is an infinite set of size \kappa and that \mathcal{F} is a family of subsets, each of cardinality at most \theta for \theta\leq\kappa . Consider two possible properties: (1) The family \mathcal{F} is cofinal: every set of cardinality <\theta is contained in a member of \mathcal{F} . (2) The family \mathcal{F} has finite VC-dimension, meaning that there is some n<\omega such that given any subset s of X of size n , there is some t\subseteq s such that t is not of the form s\cap A for some A\in\mathcal{F} , see 2.2 . Observe that ( 1 ) pulls \mathcal{F} towards having many sets while ( 2 ) pulls \mathcal{F} towards having few sets. This precise tension is the center of this paper. Generalizing ( 1 ) we may introduce a third cardinal \lambda\leq\theta and ask that \mathcal{F} is \lambda -cofinal, meaning that every set of size <\lambda is contained in a member of \mathcal{F} . This leads us to: Question 1.1 . Given cardinals \lambda\leq\theta\leq\kappa , what is the minimal VC-dimension of a \lambda -cofinal family \mathcal{F}\subseteq[\kappa]^{<\theta} (where [\kappa]^{<\theta} is the set of all subsets of \kappa of cardinality <\theta )? Consider the family of proper initial segments of \omega . Every finite subset of the natural numbers is contained in such an initial segment, and it can be seen to have VC-dimension 1. Thus, we have that for \lambda=\kappa=\theta=\omega , the answer to 1.1 is 1. In [ BBKS24 ] , Bays, Simon and the first two authors, motivated by questions in model theory, considered a version of 1.1 . Generalizing the example of initial segments of \omega , they proved: Fact 1.2 . [ BBKS24 , Theorem 3.8] There is an \omega -cofinal family \mathcal{F}\subseteq[\omega_{1}]^{<\omega} with \VC(\mathcal{F})=2 . The following result in their paper demonstrates that the VC-dimension for such families cannot be smaller, and more generally gives a lower bound for a possible answer to 1.1 . Fact 1.3 . [ BBKS24 , Proposition 3.3 and Remark 3.7] For n<\omega , a cardinal \kappa and a family \mathcal{F}\subseteq[\kappa^{+n}]^{<\kappa} which is (n+2) -cofinal we have \VC(\mathcal{F})\geq n+1 . Remark 1.4 . 1.3 does not appear exactly in this form in [ BBKS24 ] : there, the family is required to cover every finite subset of \kappa^{+n} , not just those of size n+1 . However, the proof there gives this stronger formulation. In this paper, we attempt to continue this project. In particular, we ask when the bound of 1.3 is optimal. The following is the first result proved. Theorem 1.5 ( 6.1 ( 2 , 4 )) . Fix infinite cardinals \lambda\leq\theta\leq\kappa . (1) If \theta is regular and uncountable, then there is a \lambda -cofinal \mathcal{F}\subseteq[\kappa]^{<\theta} with \VC(\mathcal{F})\leq n if and only if \kappa<\theta^{+n} . (2) If \theta is singular and \cof(\theta)<\lambda , then every \lambda -cofinal \mathcal{F}\subseteq[\kappa]^{<\theta} has \VC(\mathcal{F})=\infty . In light of 1.2 , 1.3 and 1.5 , the following two questions are therefore natural: Question 1.6 . (1) What can we say for \theta=\omega and \kappa=\omega_{n} for n>1 ? (2) What can we say for singular \theta , \kappa=\theta^{+n} and \lambda\leq\cof(\theta) ? Regarding those two questions, we get the following consistency results. Theorem 1.7 ( 6.1 ( 3 , 5 )) . (1) For every n<\omega , it is consistent with ZFC that there is an \omega -cofinal \mathcal{F}\subseteq[\omega_{n}]^{<\omega} with \VC(\mathcal{F})=n+1 . (2) Relative to the existence of a measurable cardinal, it is consistent that there is a singular cardinal \theta of countable cofinality such that for every n<\omega there is some \omega -cofinal \mathcal{F}\subseteq[\theta^{+n}]^{<\theta} such that \VC(\mathcal{F})=n+1 . The notion of VC-dimension is important in machine learning, where it corresponds to PAC learnability (see [ SB14 ] ), and also has a model theoretic counterpart, namely the NIP/IP dichotomy, which we will not go into here, but see [ Sim15 ] for more. An interesting application is the existence of a plethora of examples of 2-sorted structures with IP, whose language each has a single binary NIP relation. In their paper, the following was also proved: Fact 1.8 . [ BBKS24 , Theorem 4.1] Suppose \theta is an infinite cardinal, X a set with |X|\geq\theta^{+} and \mathcal{F}\subseteq[X]^{<\theta} is \omega -cofinal, then the structure \mathcal{M}=(X,\mathcal{F},\in) has IP , i.e., there is some definable family in \mathcal{M} with IP (see 2.2 ). Since the structure (X,\mathcal{F},\in) is interpretable in every structure in which \mathcal{F} is definable, 1.5 and 1.7 together with 1.8 give us a family of examples (consistently) of NIP families of sets which are not definable in any NIP structure, which would hopefully give us more understanding of local NIP phenomena, and perhaps serve as a source for counterexamples to conjectures regarding such formulas. This work is part of the third author’s master’s thesis. The complementary work towards this thesis was written in [ PS25 ] together with Johanna Steinmeyer, in it a finitary analogue of the above question is considered. The third author would like to thank the first two authors for guiding him towards the completion of this thesis, and to Uri Abraham for refereeing the thesis with great care, leading to improvements in its presentation, and therefore in the presentation of this paper. A bit on the proofs. The main construction throughout this paper is that of an n -ordering system, see 2.8 . The idea is to construct systems of compatible well-orders on a cardinal and its initial segments (and each of their initial segments, etc.) and considering sets which are closed relative to these systems, in a certain precise sense (see 2.13 ). This idea originated in [ BBKS24 , Theorem 3.8] where this was done for n=1 . Having this general definition forces us to prove many properties by induction on n . Accordingly, we made an effort to find the correct definitions so that the proofs are as simple as possible. 2. Preliminaries and ordering systems 2.1. VC dimension and cofinal families of sets Definition 2.1 . Given a set X and a cardinal \theta , write [X]^{<\theta} for the collection of subsets of X of size less

Read the complete text