AFTD Auto-Formalizing Theoretical Domains

shatters_union_of_shatters_fiber_family

theoremverified

Let 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 is shattered by F.

Statement

theorem shatters_union_of_shatters_fiber_family {α : Type*} [Fintype α] [DecidableEq α] {ℱ : Finset (Finset α)} {J S T : Finset α} (hS : S ⊆ J) (hT : (finset_fiber_family ℱ J S).Shatters T) : ℱ.Shatters (S ∪ T)
Source
arXiv:2611.06860 Lemma 2.4
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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 3
  • 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}…
  • 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

Let $α$ be a finite type with decidable equality. Let $\mathcal{F}$ be a family of finite subsets of $α$ (Finset (Finset α)), and let $J, S, T$ be finite subsets of $α$ (Finset α). Assume: 1. $S \subseteq J$, and 2. the fiber family of $\mathcal{F}$ with respect to $J$ and $S$ shatters $T$, where the fiber family consists of all subsets $U \subseteq J^c$ such that the restricted family $\{A \subseteq J \mid A \cup U \in \mathcal{F}\}$ shatters $S$. Then $\mathcal{F}$ shatters $S \cup T$.

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 prove that ℱ shatters S ∪ T, we take an arbitrary subset Z ⊆ S ∪ T and construct a witness in ℱ tracing Z. Because T is shattered by the fiber family R_{J,S}, every element of T must lie in Jᶜ, making T disjoint from J and thus from S ⊆ J. We first pick a fiber U ∈ R_{J,S} tracing Z ∩ T on T, and then pick A ⊆ J tracing Z ∩ S on S such that A ∪ U ∈ ℱ. Because A ⊆ J is disjoint from T ⊆ Jᶜ and U ⊆ Jᶜ is disjoint from S ⊆ J, the cross-intersections vanish, yielding (S ∪ T) ∩ (A ∪ U) = (S ∩ A) ∪ (T ∩ U) = (Z ∩ S) ∪ (Z ∩ T) = Z.

  1. To show that ℱ shatters S ∪ T, fix an arbitrary subset Z ⊆ S ∪ T; first, T is disjoint from J (that is, T ⊆ Jᶜ).

    Let Z ⊆ S ∪ T be arbitrary. Before finding a witness for Z, we establish that T ⊆ Jᶜ. For any x ∈ T, because the fiber family R_{J,S} shatters T, tracing T onto itself (T ⊆ T) gives some fiber U ∈ R_{J,S} such that T ∩ U = T. By definition of the fiber family, every member U satisfies U ⊆ Jᶜ. Since x ∈ T = T ∩ U, x belongs to U and therefore to Jᶜ.

    lines 3–9

    uses Finset.Subset.refl, Finset.mem_powerset.mp, Finset.mem_filter.mp, Finset.mem_of_mem_inter_right

      intro Z hZ
      have hT_compl : T ⊆ Jᶜ := by
        intro x hx
        obtain ⟨U, hU, hTU⟩ := hT (Finset.Subset.refl T)
        have hU_sub : U ⊆ Jᶜ := Finset.mem_powerset.mp (Finset.mem_filter.mp hU).1
        have : x ∈ T ∩ U := by rw [hTU]; exact hx
        exact hU_sub (Finset.mem_of_mem_inter_right this)
  2. There exists a fiber U ⊆ Jᶜ such that T ∩ U = Z ∩ T and whose restricted family ℱ_{J,U} shatters S.

    Since Z ∩ T ⊆ T and the fiber family R_{J,S} shatters T, there is some U ∈ R_{J,S} such that T ∩ U = Z ∩ T. Unfolding the definition of the fiber family, this means U ⊆ Jᶜ and the restricted family ℱ_{J,U} shatters S.

    lines 10–13

    uses Finset.inter_subset_right, finset_fiber_family, Finset.mem_filter, Finset.mem_powerset

      have hX_sub : Z ∩ T ⊆ T := Finset.inter_subset_right
      obtain ⟨U, hU, hTU⟩ := hT hX_sub
      rw [finset_fiber_family, Finset.mem_filter, Finset.mem_powerset] at hU
      rcases hU with ⟨hU_sub, hU_shatters⟩
  3. There exists a set A ⊆ J such that S ∩ A = Z ∩ S and A ∪ U ∈ ℱ.

    Since Z ∩ S ⊆ S and ℱ_{J,U} shatters S, there is a set A in the restricted family such that S ∩ A = Z ∩ S. Unfolding the definition of the restricted family, this means A ⊆ J and A ∪ U ∈ ℱ.

    lines 14–17

    uses Finset.inter_subset_right, finset_restricted_family, Finset.mem_filter, Finset.mem_powerset

      have hY_sub : Z ∩ S ⊆ S := Finset.inter_subset_right
      obtain ⟨A, hA, hSA⟩ := hU_shatters hY_sub
      rw [finset_restricted_family, Finset.mem_filter, Finset.mem_powerset] at hA
      rcases hA with ⟨hA_sub, hAU_in_F⟩
  4. The set A ∪ U ∈ ℱ is our candidate witness, reducing the goal to showing (S ∪ T) ∩ (A ∪ U) = Z.

    We supply A ∪ U as the witness in ℱ. By set extensionality, it suffices to prove that an element x belongs to (S ∪ T) ∩ (A ∪ U) if and only if x ∈ Z.

    lines 18–21

    uses Finset.mem_inter, Finset.mem_union

      use A ∪ U, hAU_in_F
      ext x
      simp only [Finset.mem_inter, Finset.mem_union]
      constructor
  5. Forward inclusion: (S ∪ T) ∩ (A ∪ U) ⊆ Z.

    Assume x ∈ S ∪ T and x ∈ A ∪ U. We split into cases: - If x ∈ S: - If x ∈ A, then x ∈ S ∩ A = Z ∩ S, so x ∈ Z. - If x ∈ U, then x ∈ J (since S ⊆ J) and x ∈ Jᶜ (since U ⊆ Jᶜ), a contradiction. - If x ∈ T: - If x ∈ A, then x ∈ Jᶜ (since T ⊆ Jᶜ) and x ∈ J (since A ⊆ J), a contradiction. - If x ∈ U, then x ∈ T ∩ U = Z ∩ T, so x ∈ Z. In all non-contradictory cases, x ∈ Z.

    lines 22–41

    uses Finset.mem_inter.mpr, Finset.mem_inter.mp, Finset.mem_compl

      · rintro ⟨hxST, hxAU⟩
        rcases hxST with hxS | hxT
        · rcases hxAU with hxA | hxU
          · have : x ∈ S ∩ A := Finset.mem_inter.mpr ⟨hxS, hxA⟩
            rw [hSA] at this
            exact (Finset.mem_inter.mp this).1
          · exfalso
            have hxJ := hS hxS
            have hxJc := hU_sub hxU
            rw [Finset.mem_compl] at hxJc
            exact hxJc hxJ
        · rcases hxAU with hxA | hxU
          · exfalso
            have hxJc := hT_compl hxT
            rw [Finset.mem_compl] at hxJc
            have hxJ := hA_sub hxA
            exact hxJc hxJ
          · have : x ∈ T ∩ U := Finset.mem_inter.mpr ⟨hxT, hxU⟩
            rw [hTU] at this
            exact (Finset.mem_inter.mp this).1
  6. Reverse inclusion: Z ⊆ (S ∪ T) ∩ (A ∪ U), completing the proof that ℱ shatters S ∪ T.

    Assume x ∈ Z. Since Z ⊆ S ∪ T, we already have x ∈ S ∪ T. It remains to show x ∈ A ∪ U: - If x ∈ S, then x ∈ Z ∩ S = S ∩ A, so x ∈ A ⊆ A ∪ U. - If x ∈ T, then x ∈ Z ∩ T = T ∩ U, so x ∈ U ⊆ A ∪ U. In either case x ∈ A ∪ U, so x ∈ (S ∪ T) ∩ (A ∪ U). This proves (S ∪ T) ∩ (A ∪ U) = Z.

    lines 42–55

    uses Finset.mem_union.mp, Finset.mem_inter.mpr, Finset.mem_inter.mp

      · intro hxZ
        have hxST := Finset.mem_union.mp (hZ hxZ)
        refine ⟨hxST, ?_⟩
        rcases hxST with hxS | hxT
        · left
          have : x ∈ S ∩ A := by
            rw [hSA]
            exact Finset.mem_inter.mpr ⟨hxZ, hxS⟩
          exact (Finset.mem_inter.mp this).2
        · right
          have : x ∈ T ∩ U := by
            rw [hTU]
            exact Finset.mem_inter.mpr ⟨hxZ, hxT⟩
          exact (Finset.mem_inter.mp this).2
Finset.Subset.refl
Every set is a subset of itself: s ⊆ s.
Finset.mem_powerset.mp
If a set belongs to the powerset of t, then it is a subset of t: s ∈ 𝒫(t) implies s ⊆ t.
Finset.mem_filter.mp
If an element belongs to a filtered set, then it belongs to the base set and satisfies the predicate.
Finset.mem_of_mem_inter_right
If an element belongs to s₁ ∩ s₂, then it belongs to s₂.
Finset.inter_subset_right
The intersection s₁ ∩ s₂ is a subset of s₂.
finset_fiber_family
The definition of the fiber family R_{J,S}: the family of subsets U ⊆ Jᶜ whose restricted family shatters S.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the condition: a ∈ filter p s ↔ a ∈ s ∧ p a.
Finset.mem_powerset
A set belongs to the powerset of t if and only if it is a subset of t: s ∈ powerset t ↔ s ⊆ t.
finset_restricted_family
The definition of the restricted family ℱ_{J,U}: the family of subsets A ⊆ J such that A ∪ U ∈ ℱ.
Finset.mem_inter
An element belongs to s₁ ∩ s₂ if and only if it belongs to s₁ and s₂: a ∈ s₁ ∩ s₂ ↔ a ∈ s₁ ∧ a ∈ s₂.
Finset.mem_union
An element belongs to s ∪ t if and only if it belongs to s or t: a ∈ s ∪ t ↔ a ∈ s ∨ a ∈ t.
Finset.mem_inter.mpr
If an element belongs to s₁ and s₂, then it belongs to s₁ ∩ s₂.
Finset.mem_inter.mp
If an element belongs to s₁ ∩ s₂, then it belongs to s₁ and s₂.
Finset.mem_compl
An element belongs to the complement sᶜ if and only if it does not belong to s: a ∈ sᶜ ↔ a ∉ s.
Finset.mem_union.mp
If an element belongs to s ∪ t, then it belongs to s or t.

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

/-- If T is shattered by the fiber family R_{J,S}, then S ∪ T is shattered by F. -/theorem shatters_union_of_shatters_fiber_family {α : Type*} [Fintype α] [DecidableEq α] {ℱ : Finset (Finset α)} {J S T : Finset α} (hS : S ⊆ J) (hT : (finset_fiber_family ℱ J S).Shatters T) : ℱ.Shatters (S ∪ T) := by  intro Z hZ  have hT_compl : T ⊆ Jᶜ := by    intro x hx    obtain ⟨U, hU, hTU⟩ := hT (Finset.Subset.refl T)    have hU_sub : U ⊆ Jᶜ := Finset.mem_powerset.mp (Finset.mem_filter.mp hU).1    have : x ∈ T ∩ U := by rw [hTU]; exact hx    exact hU_sub (Finset.mem_of_mem_inter_right this)  have hX_sub : Z ∩ T ⊆ T := Finset.inter_subset_right  obtain ⟨U, hU, hTU⟩ := hT hX_sub  rw [finset_fiber_family, Finset.mem_filter, Finset.mem_powerset] at hU  rcases hU with ⟨hU_sub, hU_shatters⟩  have hY_sub : Z ∩ S ⊆ S := Finset.inter_subset_right  obtain ⟨A, hA, hSA⟩ := hU_shatters hY_sub  rw [finset_restricted_family, Finset.mem_filter, Finset.mem_powerset] at hA  rcases hA with ⟨hA_sub, hAU_in_F⟩  use A ∪ U, hAU_in_F  ext x  simp only [Finset.mem_inter, Finset.mem_union]  constructor  · rintro ⟨hxST, hxAU⟩    rcases hxST with hxS | hxT    · rcases hxAU with hxA | hxU      · have : x ∈ S ∩ A := Finset.mem_inter.mpr ⟨hxS, hxA⟩        rw [hSA] at this        exact (Finset.mem_inter.mp this).1      · exfalso        have hxJ := hS hxS        have hxJc := hU_sub hxU        rw [Finset.mem_compl] at hxJc        exact hxJc hxJ    · rcases hxAU with hxA | hxU      · exfalso        have hxJc := hT_compl hxT        rw [Finset.mem_compl] at hxJc        have hxJ := hA_sub hxA        exact hxJc hxJ      · have : x ∈ T ∩ U := Finset.mem_inter.mpr ⟨hxT, hxU⟩        rw [hTU] at this        exact (Finset.mem_inter.mp this).1  · intro hxZ    have hxST := Finset.mem_union.mp (hZ hxZ)    refine ⟨hxST, ?_⟩    rcases hxST with hxS | hxT    · left      have : x ∈ S ∩ A := by        rw [hSA]        exact Finset.mem_inter.mpr ⟨hxZ, hxS⟩      exact (Finset.mem_inter.mp this).2    · right      have : x ∈ T ∩ U := by        rw [hTU]        exact Finset.mem_inter.mpr ⟨hxZ, hxT⟩      exact (Finset.mem_inter.mp this).2
See it in the graphDiscuss this resultChallenge it