AFTD Auto-Formalizing Theoretical Domains

fiber_family_vc_dim_le

theoremverified

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

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.

  1. 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.

    lines 3–5

    uses Finset.sup_le, mem_shatterer

      apply Finset.sup_le
      intro T hT
      have hT_shatt : (finset_fiber_family ℱ J S).Shatters T := mem_shatterer.mp hT
  2. 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.

    lines 6–14

    uses subset_refl, mem_filter, mem_powerset, inter_subset_right, disjoint_of_subset_right, disjoint_compl_right

      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
  3. 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.

    line 15

    uses shatters_union_of_shatters_fiber_family

      have h_shatt : ℱ.Shatters (S ∪ T) := shatters_union_of_shatters_fiber_family hS hT_shatt
  4. The 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|.

    lines 16–18

    uses card_le_vcDim, card_union_of_disjoint

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it