finset_shatters_and_vc_dim_restricted_fiber_family
Let 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 R_{J,S}, then S ∪ T is shattered by F. In particular, the VC-dimension of R_{J,S} is at most d - |S| when |S| ≤ d, and R_{J,S} is empty when |S| > d.
Statement
theorem finset_shatters_and_vc_dim_restricted_fiber_family {α : Type*} [Fintype α] [DecidableEq α] (ℱ : Finset (Finset α)) {d : ℕ} (hVC : ℱ.vcDim ≤ d) (J S : Finset α) (hS : S ⊆ J) : (∀ T : Finset α, T ⊆ Jᶜ → (finset_fiber_family ℱ J S).Shatters T → ℱ.Shatters (S ∪ T)) ∧ (S.card ≤ d → (finset_fiber_family ℱ J S).vcDim ≤ d - S.card) ∧ (d < S.card → finset_fiber_family ℱ J S = ∅)
- Formalizes
- arXiv:2611.06860 Lemma 2.4
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- fiber_family_vc_dim_leLet 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…
- fiber_family_eq_empty_of_card_gtLet F be a family of subsets with VC-dimension at most d on a finite ground set, and let S ⊆ J with |S| > d. Then the fiber family R_{J,S}…
- 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…
Read back from the Lean
Let α be a finite type with decidable equality. Let ℱ be a family of finsets of α (i.e., ℱ : Finset (Finset α)), let d : ℕ be a natural number such that the VC-dimension of ℱ is at most d (ℱ.vcDim ≤ d), and let J and S be finsets of α such that S ⊆ J.
Then the following three conditions hold simultaneously:
1. For every finset T of α, if T ⊆ Jᶜ and finset_fiber_family ℱ J S shatters T, then ℱ shatters S ∪ T.
2. If S.card ≤ d, then the VC-dimension of finset_fiber_family ℱ J S is at most d - S.card.
3. If d < S.card, then finset_fiber_family ℱ J S = ∅.
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
The theorem packages three properties of the restricted fiber family R_{J,S} into a conjunction: shattering lifting, a VC-dimension upper bound, and emptiness when S is too large. The proof constructs this 3-way conjunction directly by invoking three previously proven lemmas: `shatters_union_of_shatters_fiber_family`, `fiber_family_vc_dim_le`, and `fiber_family_eq_empty_of_card_gt`.
If T ⊆ Jᶜ is shattered by the fiber family R_{J,S}, then S ∪ T is shattered by ℱ.
Given any subset T ⊆ Jᶜ and a proof that the fiber family R_{J,S} shatters T, applying `shatters_union_of_shatters_fiber_family` with the hypothesis S ⊆ J yields that ℱ shatters S ∪ T.
uses
shatters_union_of_shatters_fiber_family⟨fun _ _ hT => shatters_union_of_shatters_fiber_family hS hT,If |S| ≤ d, the VC-dimension of the fiber family R_{J,S} is at most d - |S|.
The lemma `fiber_family_vc_dim_le` provides the VC-dimension upper bound d - |S| directly from the assumptions that ℱ has VC-dimension at most d and S ⊆ J; the implication's antecedent |S| ≤ d is discarded as the bound holds unconditionally in natural number arithmetic.
uses
fiber_family_vc_dim_lefun _ => fiber_family_vc_dim_le hVC hS,If d < |S|, the fiber family R_{J,S} is empty.
Applying `fiber_family_eq_empty_of_card_gt` with the hypotheses that ℱ has VC-dimension at most d and S ⊆ J shows that once d < |S|, the fiber family cannot contain any subset, so it is empty.
uses
fiber_family_eq_empty_of_card_gtfiber_family_eq_empty_of_card_gt hVC hS⟩
shatters_union_of_shatters_fiber_family- If S ⊆ J and the fiber family of ℱ at (J, S) shatters T, then ℱ shatters S ∪ T.
fiber_family_vc_dim_le- If the VC-dimension of ℱ is at most d and S ⊆ J, then the VC-dimension of the fiber family of ℱ at (J, S) is at most d - |S|.
fiber_family_eq_empty_of_card_gt- If the VC-dimension of ℱ is at most d, S ⊆ J, and d < |S|, then the fiber family of ℱ at (J, S) is empty.
- In step 2 (line 4), the lemma `fiber_family_vc_dim_le` proves the inequality `(finset_fiber_family ℱ J S).vcDim ≤ d - S.card` unconditionally using truncated natural number subtraction, so the premise `S.card ≤ d` is formally ignored (`fun _ => ...`).
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Trace shattering and VC-dimension of restricted fiber families (Lemma 2.4). -/theorem finset_shatters_and_vc_dim_restricted_fiber_family {α : Type*} [Fintype α] [DecidableEq α] (ℱ : Finset (Finset α)) {d : ℕ} (hVC : ℱ.vcDim ≤ d) (J S : Finset α) (hS : S ⊆ J) : (∀ T : Finset α, T ⊆ Jᶜ → (finset_fiber_family ℱ J S).Shatters T → ℱ.Shatters (S ∪ T)) ∧ (S.card ≤ d → (finset_fiber_family ℱ J S).vcDim ≤ d - S.card) ∧ (d < S.card → finset_fiber_family ℱ J S = ∅) := ⟨fun _ _ hT => shatters_union_of_shatters_fiber_family hS hT, fun _ => fiber_family_vc_dim_le hVC hS, fiber_family_eq_empty_of_card_gt hVC hS⟩