Aether Catalog definitions — Bridges_ProofAutomatonDuality
DefinitionBridges_ProofAutomatonDualityaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.ProofAutomatonDuality, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/ProofAutomatonDuality.lean by skeleton subtraction
import Mathlib
import Definitions.Def_Bridges_TropicalAlgebra_SpectralProofSpace
/-
Copyright (c) 2025 Harmonic. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
# Proof Automaton Duality: Stone-Type Reconstruction
This file establishes the duality between finite proof automata over
idempotent monoids and their prime spectra. The key results are:
1. **Proof automaton structure**: States, transitions, acceptance.
2. **Spectral reconstruction**: Recovering automaton structure from spectral data.
3. **Duality lemmas**: The round-trip (automaton → spectrum → automaton)
preserves all structure up to isomorphism.
## Main definitions
* `FiniteProofAutomaton` — Finite-state proof automaton over an idempotent monoid
* `AutomatonHomomorphism` — Structure-preserving maps between automata
* `SpectralReconstruction` — Reconstructed automaton from spectral data
* `DualityWitness` — Witness of the round-trip isomorphism
* `VerificationCertificate` — Spectral certificate for automaton properties
Bridge: connects automata theory to spectral topology and certified_robustness.
-/
set_option maxHeartbeats 800000
universe u
open SpectralProofSpace
namespace ProofAutomatonDuality
variable {S : Type u} [IdempotentAddMonoid S]
/-! ## Section 1: Finite Proof Automata -/
/-- A finite proof automaton over an idempotent additive monoid.
States form a finite set, transitions are driven by monoid elements,
and acceptance is determined by a language.
Bridge: connects automata theory (state machines) to algebraic geometry
(each state corresponds to a prime congruence on the monoid).
Computational bound: transition function is O(1) per step. -/
structure FiniteProofAutomaton (S : Type u) [IdempotentAddMonoid S] where
/-- The state type -/
State : Type u
/-- States are finite -/
[stateFintype : Fintype State]
/-- States have decidable equality -/
[stateDecEq : DecidableEq State]
/-- Initial state -/
initial : State
/-- Transition function: given current state and monoid element, produce next state -/
transition : State → S → State
/-- Acceptance predicate -/
accept : State → Prop
/-- Acceptance is decidable -/
[acceptDec : DecidablePred accept]
/-- Idempotent transition: transitioning by a+a = transitioning by a -/
transition_idem : ∀ q : State, ∀ a : S,
transition (transition q a) a = transition q a
attribute [instance] FiniteProofAutomaton.stateFintype
FiniteProofAutomaton.stateDecEq FiniteProofAutomaton.acceptDec
namespace FiniteProofAutomaton
variable (A : FiniteProofAutomaton S)
/-- Run the automaton on a list of inputs from the initial state. -/
def run (inputs : List S) : A.State :=
inputs.foldl A.transition A.initial
/-- Run from a given state. -/
def runFrom (q : A.State) (inputs : List S) : A.State :=
inputs.foldl A.transition q
/-- The Myhill-Nerode congruence: two elements are equivalent if they
lead to the same state from every starting state.
Bridge: connects automata minimization to prime congruences. -/
def myhillNerodeRel (a b : S) : Prop :=
∀ q : A.State, A.transition q a = A.transition q b
end FiniteProofAutomaton
/-! ## Section 2: Automaton Homomorphisms -/
/-- A homomorphism between proof automata: a state map that preserves
transitions, initial state, and acceptance.
Bridge: connects automata morphisms to continuous spectral maps. -/
structure AutomatonHomomorphism (A B : FiniteProofAutomaton S) where
/-- The state map -/
stateMap : A.State → B.State
/-- Preserves initial state -/
map_initial : stateMap A.initial = B.initial
/-- Preserves transitions -/
map_transition : ∀ q a, stateMap (A.transition q a) = B.transition (stateMap q) a
/-- Preserves acceptance -/
map_accept : ∀ q, A.accept q → B.accept (stateMap q)
namespace AutomatonHomomorphism
end AutomatonHomomorphism
/-! ## Section 3: State Congruence from Automaton -/
/-- The state-equivalence congruence: two monoid elements are equivalent
if they produce the same state from every starting point.
This is a refinement of Myhill-Nerode. -/
def stateEquivRel (A : FiniteProofAutomaton S) (a b : S) : Prop :=
∀ q : A.State, A.transition q a = A.transition q b
/-! ## Section 4: Spectral Reconstruction -/
/-- Given a set of prime congruences (spectral points), reconstruct
an acceptance predicate by checking if any accepted element
remains distinguished from all rejected elements.
Bridge: connects sheaf theory to automaton reconstruction.
Computational bound: O(|S|²) for reconstruction. -/
def spectralAcceptance (L : AcceptanceLanguage S)
(C : MonoidCongruence S) : Prop :=
∃ a : S, L.accepts a ∧ ∀ b : S, ¬L.accepts b → ¬C.rel a b
/-! ## Section 5: Duality Witnesses -/
/-- A duality witness records the correspondence between automaton
states and spectral points (prime congruences).
Bridge: connects Stone duality to proof compression —
the witness is the "dictionary" translating between algebraic
and topological descriptions of the same proof system. -/
structure DualityWitness (A : FiniteProofAutomaton S)
(L : AcceptanceLanguage S) where
/-- Map from states to congruences -/
stateToCongruence : A.State → MonoidCongruence S
/-- The congruence at a state identifies elements with the same successor state -/
cong_compat : ∀ q : A.State, ∀ a b : S,
(stateToCongruence q).rel a b →
A.transition q a = A.transition q b
/-- Distinct states give distinct congruences -/
injectivity : ∀ q₁ q₂ : A.State, q₁ ≠ q₂ →
∃ a b : S, (stateToCongruence q₁).rel a b ∧
¬(stateToCongruence q₂).rel a b
/-! ## Section 6: Verification Certificates -/
/-! ## Section 7: Complexity Bounds -/
/-! ## Section 8: Reconstruction Theorems -/
/-! ## Section 9: Minimality via Spectral Separation -/
/-- An automaton is minimal if distinct states have distinct behaviors.
Bridge: connects automaton minimization to spectral T₀ separation. -/
def IsMinimal (A : FiniteProofAutomaton S) : Prop :=
∀ q₁ q₂ : A.State, q₁ ≠ q₂ →
∃ inputs : List S, A.accept (A.runFrom q₁ inputs) ≠ A.accept (A.runFrom q₂ inputs)
/-! ## Section 10: Tropical and Crypto Bridges -/
/-! ## Section 11: Category-Theoretic Structure -/
/-! ## Section 12: Summary Theorem -/
end ProofAutomatonDuality