Cslib.MachineLearning.PACLearning.SetShatters.subset
theoremverifiedformalizationimported Lean
Shattering is anti-monotone in the shattered set: if C shatters W and V ⊆ W, then C shatters V.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Set in variable {α : Type*} in theorem Cslib.MachineLearning.PACLearning.SetShatters.subset {C : ConceptClass α Bool} {W V : Set α} (hW : SetShatters C W) (hVW : V ⊆ W) : SetShatters C V
- Formalizes
- CSLib, `Cslib.MachineLearning.PACLearning.SetShatters.subset`
- Lean proof
- By Samuel Schlesinger, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2026 Samuel Schlesinger. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.MachineLearning.PACLearning.SetShatters.subset← Cslib.MachineLearning.PACLearning.SetShatters.subset (Cslib/MachineLearning/PACLearning/VCDimension.lean:58): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- Cslib.MachineLearning.PACLearning.ConceptClassA *concept class* over domain
αwith label typeβis a set of functionsα → β. For binary classification (β = Bool), this is… - Cslib.MachineLearning.PACLearning.SetShattersA binary concept class
C*shatters* a setWif for every subsetW' ⊆ W, there exists a conceptc ∈ Cwhose positive set…
- Cslib.MachineLearning.PACLearning.ConceptClassA *concept class* over domain
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Set invariable {α : Type*} in/-- Shattering is anti-monotone in the shattered set: if `C` shatters `W` and `V ⊆ W`, then `C` shatters `V`. -/theorem Cslib.MachineLearning.PACLearning.SetShatters.subset {C : ConceptClass α Bool} {W V : Set α} (hW : SetShatters C W) (hVW : V ⊆ W) : SetShatters C V := by intro V' hV'V obtain ⟨c, hc, hc_eq⟩ := hW (V' ∪ (W \ V)) (union_subset (hV'V.trans hVW) sdiff_subset) refine ⟨c, hc, ?_⟩ rw [show V = W ∩ V from (inter_eq_self_of_subset_right hVW).symm, ← inter_assoc, hc_eq] ext x simp only [mem_inter_iff, mem_union, mem_sdiff] refine ⟨?_, fun h => ⟨Or.inl h, hV'V h⟩⟩ rintro ⟨h1 | ⟨_, h2⟩, h3⟩ · exact h1 · exact absurd h3 h2