finset_fiber_family
def
Given 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 complement of J such that the restricted family F_{J,U} shatters S.
Statement
def finset_fiber_family {α : Type*} [Fintype α] [DecidableEq α] (ℱ : Finset (Finset α)) (J S : Finset α) : Finset (Finset α)
- Defined in
- arXiv:2611.06860, Section 2.2
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 1
- 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 5
- finset_fiber_family_emptyThe fiber family of the empty family is empty.
- 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…
- 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}…
- 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…
Read back from the Lean
Given a finite type α with decidable equality, a family of sets ℱ : Finset (Finset α), and subsets J, S : Finset α, finset_fiber_family ℱ J S defines the finset of all subsets U ⊆ Jᶜ (i.e., U ∈ Jᶜ.powerset) such that the family finset_restricted_family ℱ J U shatters S.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The fiber family R_{J,S} = {U ⊆ Jᶜ : S is shattered by F_{J,U}}. -/ def finset_fiber_family {α : Type*} [Fintype α] [DecidableEq α] (ℱ : Finset (Finset α)) (J S : Finset α) : Finset (Finset α) := Jᶜ.powerset.filter (fun U => (finset_restricted_family ℱ J U).Shatters S)