Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — Bridges_ToposTheoreticML_Foundations

Definition
Bridges_ToposTheoreticML_Foundations

by raver1975 · Sep 16, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogbridges

Definition bundle for the Aether Catalog module Bridges.ToposTheoreticML.Foundations, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.

Definition code
-- Def bundle generated from Bridges/ToposTheoreticML/Foundations.lean by skeleton subtraction
import Mathlib

/-! # 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 Finset

/-! ## Concept families, shattering and VC dimension -/

/-- A **concept family** on `α` is a nonempty collection of subsets of `α`
(the *concepts*), presented by their membership predicate `mem`. -/
structure ConceptFamily (α : Type*) where
  /-- `mem c` holds when `c` is one of the concepts of the family. -/
  mem : Set α → Prop
  /-- A concept family contains at least one concept. -/
  nonempty : ∃ c, mem c

namespace ConceptFamily

variable {α : Type*}

/-- A finite set `S` is **shattered** by the family if every subset `T ⊆ S` is cut
out on `S` by some concept: there is a concept `c` with `c ∩ S = T`. -/
def shatters (C : ConceptFamily α) (S : Finset α) : Prop :=
  ∀ T ⊆ S, ∃ c, C.mem c ∧ ∀ x ∈ S, (x ∈ c ↔ x ∈ T)

/-- `C.vcDimBound d` states that the VC dimension of `C` is at most `d`: no set of
cardinality exceeding `d` is shattered. -/
def vcDimBound (C : ConceptFamily α) (d : ℕ) : Prop :=
  ∀ S : Finset α, C.shatters S → S.card ≤ d

end ConceptFamily

/-- `CompactRank C n` records that `n` is the *compact rank* of the family `C`:
it bounds every shattered set and is either `0` or attained by some shattered set.
This is the learning-theoretic incarnation of a compact subobject rank. -/
def CompactRank {α : Type*} (C : ConceptFamily α) (n : ℕ) : Prop :=
  (∀ S : Finset α, C.shatters S → S.card ≤ n) ∧
    (n = 0 ∨ ∃ S : Finset α, C.shatters S ∧ S.card = n)

/-- A **cryptographic hardness witness** at level `k`: a shattered set of exactly
`k` points, certifying that learning the family is at least as hard as
distinguishing all `2^k` labelings of those points. -/
structure CryptoHardnessWitness {α : Type*} (C : ConceptFamily α) (k : ℕ) where
  /-- The shattered witness set. -/
  witness : Finset α
  /-- The witness set is shattered by the family. -/
  witness_shattered : C.shatters witness
  /-- The witness set has exactly `k` elements. -/
  witness_card : witness.card = k

/-! ## The Sauer–Shelah growth function -/

/-- The **Sauer–Shelah bound** `∑_{i ≤ d} C(m, i)`, the maximal number of distinct
labelings a family of VC dimension `d` can realize on `m` points. -/
def sauerShelahBound (m d : ℕ) : ℕ :=
  ∑ i ∈ Finset.range (d + 1), m.choose i


/-! ## Sample complexity -/

/-- An abstract **sample-complexity functional** `d / ε² · log(1/δ)`, capturing the
standard dependence on VC dimension `d`, accuracy `ε`, and confidence `δ`. -/
noncomputable def sampleComplexityBound (d : ℕ) (ε δ : ℝ) : ℝ :=
  (d : ℝ) / ε ^ 2 * Real.log (1 / δ)



/-! ## Sieves on a preorder and their lattice structure -/

/-- A **sieve on `d`** in a preorder `α`: a downward-closed set of elements, all of
which lie below the target `d`.  Sieves are the topos-theoretic classifiers used to
encode downward-closed concepts. -/
structure SieveOn (α : Type*) [Preorder α] (d : α) where
  /-- The underlying set of the sieve. -/
  carrier : Set α
  /-- Sieves are closed downward under the order. -/
  downward_closed : ∀ x y, x ∈ carrier → y ≤ x → y ∈ carrier
  /-- Every element of a sieve lies below the target. -/
  below_target : ∀ x, x ∈ carrier → x ≤ d

namespace SieveOn

variable {α : Type*} [Preorder α] {d : α}


/-- Sieves on `d` form a partial order under inclusion of carriers. -/
instance : PartialOrder (SieveOn α d) where
  le s t := s.carrier ⊆ t.carrier
  le_refl _ := subset_rfl
  le_trans _ _ _ h1 h2 := subset_trans h1 h2
  le_antisymm a b h1 h2 := by
    cases a with
    | mk ca _ _ =>
      cases b with
      | mk cb _ _ =>
        have hc : ca = cb := Set.Subset.antisymm h1 h2
        subst hc
        rfl

/-- The empty sieve. -/
def empty (d : α) : SieveOn α d where
  carrier := ∅
  downward_closed := by intro _ _ hx _; exact absurd hx (by simp)
  below_target := by intro _ hx; exact absurd hx (by simp)

/-- The maximal sieve on `d`, consisting of everything below `d`. -/
def maximal (d : α) : SieveOn α d where
  carrier := {x | x ≤ d}
  downward_closed := fun _ _ hx hle => le_trans hle hx
  below_target := fun _ hx => hx



end SieveOn

/-! ## Transfer morphisms -/

/-- A **transfer morphism** between concept families records the Lipschitz constant
governing how accuracy inflates when transporting a learner from one family to
another. -/
structure TransferMorphism {α β : Type*} (C₁ : ConceptFamily α)
    (C₂ : ConceptFamily β) where
  /-- The Lipschitz constant of the transfer map. -/
  lipschitzConst : ℝ

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me