shatters_union_of_shatters_fiber_family
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.
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ᶜ.
uses
Finset.Subset.refl,Finset.mem_powerset.mp,Finset.mem_filter.mp,Finset.mem_of_mem_inter_rightintro 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)
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.
uses
Finset.inter_subset_right,finset_fiber_family,Finset.mem_filter,Finset.mem_powersethave 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⟩
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 ∈ ℱ.
uses
Finset.inter_subset_right,finset_restricted_family,Finset.mem_filter,Finset.mem_powersethave 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⟩
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.
uses
Finset.mem_inter,Finset.mem_unionuse A ∪ U, hAU_in_F ext x simp only [Finset.mem_inter, Finset.mem_union] constructor
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.
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).1Reverse 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.
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
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 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