fiber_family_vc_dim_le
Let F be a family of subsets with VC-dimension at most d on a finite ground set, and let S ⊆ J. Then the VC-dimension of the fiber family R_{J,S} is at most d - |S|.
Statement
theorem fiber_family_vc_dim_le {α : Type*} [Fintype α] [DecidableEq α] {ℱ : Finset (Finset α)} {J S : Finset α} {d : ℕ} (hVC : ℱ.vcDim ≤ d) (hS : S ⊆ J) : (finset_fiber_family ℱ J S).vcDim ≤ d - S.card
- Source
- arXiv:2611.06860 Lemma 2.4
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- shatters_union_of_shatters_fiber_familyLet F be a family of subsets on a finite ground set, S ⊆ J, and let R_{J,S} be the fiber family. If T is shattered by R_{J,S}, then S ∪ T…
- finset_fiber_familyGiven a family of sets F on a finite universe, a subset J, and a subset S of J, the fiber family R_{J,S} consists of all subsets U of the…
- finset_restricted_familyGiven a family of sets F and sets J and U, the restricted family F_{J,U} consists of all subsets A of J such that A ∪ U is in F.
- Used by 1
- finset_shatters_and_vc_dim_restricted_fiber_familyLet F be a family of subsets of a finite ground set with VC-dimension at most d, and let S ⊆ J. If T ⊆ Jᶜ is shattered by the fiber family…
Read back from the Lean
For any finite type α with decidable equality, any family of finsets ℱ : Finset (Finset α), any finsets J, S : Finset α, and any natural number d: if the VC dimension of ℱ is at most d (ℱ.vcDim ≤ d) and S ⊆ J, then the VC dimension of finset_fiber_family ℱ J S is at most d - S.card (under natural number subtraction).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the VC-dimension of the fiber family R_{J,S} is at most d - |S|, it suffices to show that any set T shattered by R_{J,S} has |T| ≤ d - |S|. Because every member of the fiber family is contained in the complement of J, the shattered set T is disjoint from J, and hence disjoint from S. The lemma shatters_union_of_shatters_fiber_family then guarantees that the original family ℱ shatters S ∪ T. Since ℱ has VC-dimension at most d, we have |S| + |T| = |S ∪ T| ≤ d, from which |T| ≤ d - |S| follows.
To bound the VC-dimension, it suffices to show that any set T shattered by the fiber family has cardinality at most d - |S|.
By definition, the VC-dimension is the maximum cardinality of a shattered set. Applying Finset.sup_le, we consider an arbitrary set T in the shatterer of the fiber family, which by mem_shatterer means that the fiber family shatters T.
uses
Finset.sup_le,mem_shattererapply Finset.sup_le intro T hT have hT_shatt : (finset_fiber_family ℱ J S).Shatters T := mem_shatterer.mp hT
S and T are disjoint.
Because the fiber family shatters T, choosing the subset T ⊆ T (via subset_refl) provides an element u in the fiber family such that T ∩ u = T. Since T ∩ u ⊆ u by inter_subset_right, we have T ⊆ u. By definition of the fiber family (via mem_filter and mem_powerset), every such u is contained in Jᶜ. Hence T ⊆ Jᶜ, so J and T are disjoint by disjoint_of_subset_right and disjoint_compl_right. Since S ⊆ J, it follows that S and T are disjoint as well.
uses
subset_refl,mem_filter,mem_powerset,inter_subset_right,disjoint_of_subset_right,disjoint_compl_righthave h_disj : Disjoint S T := by obtain ⟨u, hu, hTu⟩ := hT_shatt (subset_refl T) have hu_mem : u ∈ Jᶜ.powerset := (mem_filter.mp hu).1 rw [mem_powerset] at hu_mem have hTu_sub : T ⊆ u := by rw [← hTu] exact inter_subset_right have hTJ : Disjoint J T := disjoint_of_subset_right (hTu_sub.trans hu_mem) disjoint_compl_right exact hTJ.mono_left hS
The original family ℱ shatters S ∪ T.
By shatters_union_of_shatters_fiber_family, whenever S ⊆ J and the fiber family shatters T, the ambient family ℱ shatters the union S ∪ T.
uses
shatters_union_of_shatters_fiber_familyhave h_shatt : ℱ.Shatters (S ∪ T) := shatters_union_of_shatters_fiber_family hS hT_shattThe cardinality |T| is at most d - |S|, concluding the proof.
Because ℱ shatters S ∪ T, its cardinality |S ∪ T| is at most the VC-dimension of ℱ (by card_le_vcDim), which is at most d. Since S and T are disjoint, card_union_of_disjoint gives |S ∪ T| = |S| + |T|, so |S| + |T| ≤ d. Linear integer arithmetic (omega) then yields |T| ≤ d - |S|.
uses
card_le_vcDim,card_union_of_disjointhave h_card_le : (S ∪ T).card ≤ d := h_shatt.card_le_vcDim.trans hVC rw [card_union_of_disjoint h_disj] at h_card_le omega
Finset.sup_le- The supremum of a function over a finite set is at most a if and only if its value at every element of the set is at most a.
mem_shatterer- A set belongs to the shatterer of a family if and only if the family shatters it.
subset_refl- Every set is a subset of itself.
mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
mem_powerset- A set belongs to the powerset of t if and only if it is a subset of t.
inter_subset_right- The intersection of two sets is a subset of the second set.
disjoint_of_subset_right- If t ⊆ u and s is disjoint from u, then s is disjoint from t.
disjoint_compl_right- Any set is disjoint from its complement.
shatters_union_of_shatters_fiber_family- If S ⊆ J and the fiber family R_{J,S} shatters T, then the original family ℱ shatters S ∪ T.
card_le_vcDim- If a family shatters a set, the cardinality of that set is at most the VC-dimension of the family.
card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The VC-dimension of the fiber family R_{J,S} is at most d - |S| when VC(F) ≤ d and S ⊆ J. -/theorem fiber_family_vc_dim_le {α : Type*} [Fintype α] [DecidableEq α] {ℱ : Finset (Finset α)} {J S : Finset α} {d : ℕ} (hVC : ℱ.vcDim ≤ d) (hS : S ⊆ J) : (finset_fiber_family ℱ J S).vcDim ≤ d - S.card := open Finset in by apply Finset.sup_le intro T hT have hT_shatt : (finset_fiber_family ℱ J S).Shatters T := mem_shatterer.mp hT have h_disj : Disjoint S T := by obtain ⟨u, hu, hTu⟩ := hT_shatt (subset_refl T) have hu_mem : u ∈ Jᶜ.powerset := (mem_filter.mp hu).1 rw [mem_powerset] at hu_mem have hTu_sub : T ⊆ u := by rw [← hTu] exact inter_subset_right have hTJ : Disjoint J T := disjoint_of_subset_right (hTu_sub.trans hu_mem) disjoint_compl_right exact hTJ.mono_left hS have h_shatt : ℱ.Shatters (S ∪ T) := shatters_union_of_shatters_fiber_family hS hT_shatt have h_card_le : (S ∪ T).card ≤ d := h_shatt.card_le_vcDim.trans hVC rw [card_union_of_disjoint h_disj] at h_card_le omega