fiber_family_eq_empty_of_card_gt
Let 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} is empty.
Statement
theorem fiber_family_eq_empty_of_card_gt {α : Type*} [Fintype α] [DecidableEq α] {ℱ : Finset (Finset α)} {J S : Finset α} {d : ℕ} (hVC : ℱ.vcDim ≤ d) (hS : S ⊆ J) (hSd : d < S.card) : finset_fiber_family ℱ J S = ∅
- Source
- arXiv:2611.06860 Lemma 2.4
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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
Let α be a finite type with decidable equality. Let ℱ be a finite family of finite subsets of α (ℱ : Finset (Finset α)), let J and S be finite subsets of α, and let d be a natural number. If:
1. The VC dimension of ℱ is at most d (ℱ.vcDim ≤ d),
2. S ⊆ J, and
3. The cardinality of S is strictly greater than d (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 proof proceeds by contradiction. If the fiber family R_{J,S} were nonempty, it would shatter the empty set ∅. By the lifting property of fiber families (shatters_union_of_shatters_fiber_family), the original family ℱ would then shatter S ∪ ∅ = S, implying |S| ≤ VC(ℱ). But this contradicts the hypotheses that VC(ℱ) ≤ d and |S| > d.
Assuming the fiber family is nonempty, it shatters the empty set.
We proceed by contradiction and assume that the fiber family is not empty (`h_ne`). By `Finset.nonempty_iff_ne_empty.2`, being distinct from the empty set means the family is nonempty (`h_nonempty`). By `Finset.shatters_empty.2`, any nonempty family of sets shatters the empty set ∅.
uses
Finset.nonempty_iff_ne_empty.2,Finset.shatters_empty.2by_contra h_ne have h_nonempty : (finset_fiber_family ℱ J S).Nonempty := Finset.nonempty_iff_ne_empty.2 h_ne have h_shat_empty : (finset_fiber_family ℱ J S).Shatters ∅ := Finset.shatters_empty.2 h_nonempty
The ambient family ℱ shatters S.
The lemma `shatters_union_of_shatters_fiber_family` states that whenever S ⊆ J and the fiber family R_{J,S} shatters T, the original family ℱ shatters S ∪ T. Applying this with T = ∅ gives that ℱ shatters S ∪ ∅, which simplifies to S via `Finset.union_empty`.
uses
shatters_union_of_shatters_fiber_family,Finset.union_emptyhave h_shat_union := shatters_union_of_shatters_fiber_family hS h_shat_empty rw [Finset.union_empty] at h_shat_union
A contradiction is reached between the cardinality of S and the VC-dimension bound.
Since ℱ shatters S, the cardinality of S cannot exceed the VC-dimension of ℱ by `card_le_vcDim` (giving |S| ≤ VC(ℱ)). But we are given VC(ℱ) ≤ d and d < |S|, which forms an impossible cycle of inequalities |S| ≤ VC(ℱ) ≤ d < |S|; linear arithmetic (`omega`) closes the contradiction.
uses
card_le_vcDimhave h_card_le := h_shat_union.card_le_vcDim omega
Finset.nonempty_iff_ne_empty.2- A finite set is nonempty if it is not equal to the empty set.
Finset.shatters_empty.2- A family of sets shatters the empty set if it is nonempty.
shatters_union_of_shatters_fiber_family- If S ⊆ J and the fiber family R_{J,S} shatters T, then ℱ shatters S ∪ T.
Finset.union_empty- The union of any set with the empty set is the set itself.
card_le_vcDim- If a family shatters a set, the cardinality of that set is at most the VC-dimension of the family.
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.
/-- If |S| > d and VC(F) ≤ d, then the fiber family R_{J,S} is empty. -/theorem fiber_family_eq_empty_of_card_gt {α : Type*} [Fintype α] [DecidableEq α] {ℱ : Finset (Finset α)} {J S : Finset α} {d : ℕ} (hVC : ℱ.vcDim ≤ d) (hS : S ⊆ J) (hSd : d < S.card) : finset_fiber_family ℱ J S = ∅ := by by_contra h_ne have h_nonempty : (finset_fiber_family ℱ J S).Nonempty := Finset.nonempty_iff_ne_empty.2 h_ne have h_shat_empty : (finset_fiber_family ℱ J S).Shatters ∅ := Finset.shatters_empty.2 h_nonempty have h_shat_union := shatters_union_of_shatters_fiber_family hS h_shat_empty rw [Finset.union_empty] at h_shat_union have h_card_le := h_shat_union.card_le_vcDim omega