AFTD Auto-Formalizing Theoretical Domains

Cslib.MachineLearning.PACLearning.HasFiniteVCDim

defimported Lean

A binary concept class C has *finite VC dimension* if there is a uniform upper bound on the cardinalities of finite sets it shatters. This is the hypothesis under which vcDim C is mathematically meaningful (otherwise vcDim returns 0 for unbounded shattered families via sSup on ℕ).

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Set in
variable {α : Type*} in
def Cslib.MachineLearning.PACLearning.HasFiniteVCDim (C : ConceptClass α Bool) : Prop
Defined in
CSLib, `Cslib.MachineLearning.PACLearning.HasFiniteVCDim`
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.
Verified
08 Oct 2026
Axioms
none listed
Built on 2
Used by 1

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Set in
variable {α : Type*} in
/-- A binary concept class `C` has *finite VC dimension* if there is a uniform upper bound on the cardinalities of finite sets it shatters. This is the hypothesis under which `vcDim C` is mathematically meaningful (otherwise `vcDim` returns `0` for unbounded shattered families via `sSup` on `ℕ`). -/
def Cslib.MachineLearning.PACLearning.HasFiniteVCDim (C : ConceptClass α Bool) : Prop :=
  BddAbove {n : ℕ | ∃ W : Finset α, W.card = n ∧ SetShatters C (↑W)}
See it in the graphDiscuss this resultChallenge it