AFTD Auto-Formalizing Theoretical Domains

finset_shatters_and_vc_dim_restricted_fiber_family

theoremverifiedformalization

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

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

    line 3

    uses shatters_union_of_shatters_fiber_family

      ⟨fun _ _ hT => shatters_union_of_shatters_fiber_family hS hT,
  2. 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.

    line 4

    uses fiber_family_vc_dim_le

       fun _ => fiber_family_vc_dim_le hVC hS,
  3. 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.

    line 5

    uses fiber_family_eq_empty_of_card_gt

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

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