Aether Catalog definitions — Bridges_VCCompactness
DefinitionBridges_VCCompactnessaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.VCCompactness, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/VCCompactness.lean by skeleton subtraction
import Mathlib
import Definitions.Def_Bridges_ToposTheoreticML_Foundations
/-! # Topos-Theoretic Machine Learning: VC Dimension and Compactness
This file proves core theorems connecting VC dimension (combinatorial learning theory)
to compact subobject rank (topos-theoretic geometry), and establishes the No-Free-Lunch
theorem, sample complexity bounds, transfer learning, and sieve lattice structure.
## Bridge: Combinatorics (shattering) → Learning Theory (VC, PAC, NFL) →
Category Theory (compact rank, presheaf toposes) → Cryptography (lattice_crypto) →
Quantum Information (dagger-symmetric learnability)
-/
noncomputable section
open Finset Real
/-! ## I. Basic Shattering Properties -/
/-! ## II. No-Free-Lunch Theorem (Combinatorial Form) -/
/-! ## III. Sample Lower Bound from Shattering -/
/-! ## IV. Transfer Sample Complexity -/
/-! ## V. Sauer-Shelah Growth Function -/
/-! ## VI. Sieve Lattice Operations -/
/-- Sieve intersection (meet). -/
def sieveIntersection {α : Type*} [Preorder α] {d : α}
(s₁ s₂ : SieveOn α d) : SieveOn α d where
carrier := s₁.carrier ∩ s₂.carrier
downward_closed := fun x y ⟨h₁, h₂⟩ hle =>
⟨s₁.downward_closed x y h₁ hle, s₂.downward_closed x y h₂ hle⟩
below_target := fun x ⟨h₁, _⟩ => s₁.below_target x h₁
/-- Sieve union (join). -/
def sieveUnion {α : Type*} [Preorder α] {d : α}
(s₁ s₂ : SieveOn α d) : SieveOn α d where
carrier := s₁.carrier ∪ s₂.carrier
downward_closed := fun x y hx hle => by
rcases hx with h | h
· exact Or.inl (s₁.downward_closed x y h hle)
· exact Or.inr (s₂.downward_closed x y h hle)
below_target := fun x hx => by
rcases hx with h | h
· exact s₁.below_target x h
· exact s₂.below_target x h
/-! ## VII. Concept-to-Sieve Encoding -/
/-- A downward-closed concept induces a sieve.
Bridge: learning theory → topos theory (sieves). -/
def conceptToSieve {α : Type*} [Preorder α] (c : Set α)
(hdown : ∀ x y, x ∈ c → y ≤ x → y ∈ c) (d : α) : SieveOn α d where
carrier := {x | x ≤ d ∧ x ∈ c}
downward_closed := fun x y ⟨hxd, hxc⟩ hyx =>
⟨le_trans hyx hxd, hdown x y hxc hyx⟩
below_target := fun _ ⟨hxd, _⟩ => hxd
/-! ## VIII. VC Characterizes Learnability -/
end