At full dimension the Sauer–Shelah bound collapses to the exponential `2^k`.
ProvedsauerShelah_fullaether-catalogbridges
At full dimension the Sauer–Shelah bound collapses to the exponential 2^k.
theorem sauerShelah_full(k : ℕ) : sauerShelahBound k k = 2 ^ k := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Bridges/Foundations.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Bridges/ToposTheoreticML/Foundations.lean
import Mathlib
import Definitions.Def_Bridges_ToposTheoreticML_Foundations
/-! # Topos-Theoretic Machine Learning: Foundations
This file develops the shared vocabulary connecting statistical learning theory to
topos-theoretic geometry. It introduces concept families and their shattering /
Vapnik–Chervonenkis dimension, the Sauer–Shelah growth function, an abstract
sample-complexity functional, sieves on a preorder together with their lattice
structure, and the auxiliary data (cryptographic hardness witnesses, transfer
morphisms) used to phrase transfer and lower-bound results.
The downstream file `Bridges/VCCompactness.lean` builds the actual bridge theorems
on top of these definitions.
-/
-- open removed: section is not a namespace
/-! ## Concept families, shattering and VC dimension -/
open ConceptFamily
variable {α : Type*}
/-! ## The Sauer–Shelah growth function -/Formal statement
theorem sauerShelah_full(k : ℕ) : sauerShelahBound k k = 2 ^ k := by sorry
Source