Cslib.MachineLearning.PACLearning.hasFiniteVCDim_iff
theoremverifiedformalizationimported Lean
A class has finite VC dimension iff there is a uniform bound on the cardinality of every shattered finite set.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Set in variable {α : Type*} in theorem Cslib.MachineLearning.PACLearning.hasFiniteVCDim_iff {C : ConceptClass α Bool} : HasFiniteVCDim C ↔ ∃ N : ℕ, ∀ W : Finset α, SetShatters C ↑W → W.card ≤ N
- Formalizes
- CSLib, `Cslib.MachineLearning.PACLearning.hasFiniteVCDim_iff`
- 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.hasFiniteVCDim_iff← Cslib.MachineLearning.PACLearning.hasFiniteVCDim_iff (Cslib/MachineLearning/PACLearning/VCDimension.lean:123): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.HasFiniteVCDimA binary concept class
Chas *finite VC dimension* if there is a uniform upper bound on the cardinalities of finite sets it shatters.…
- Cslib.MachineLearning.PACLearning.ConceptClassA *concept class* over domain
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Set in variable {α : Type*} in /-- A class has finite VC dimension iff there is a uniform bound on the cardinality of every shattered finite set. -/ theorem Cslib.MachineLearning.PACLearning.hasFiniteVCDim_iff {C : ConceptClass α Bool} : HasFiniteVCDim C ↔ ∃ N : ℕ, ∀ W : Finset α, SetShatters C ↑W → W.card ≤ N := ⟨fun ⟨N, hN⟩ => ⟨N, fun W hW => hN ⟨W, rfl, hW⟩⟩, fun ⟨N, hN⟩ => ⟨N, fun _ ⟨W, hWc, hW⟩ => hWc ▸ hN W hW⟩⟩