Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — Bridges_ProofAutomatonDuality

Definition
Bridges_ProofAutomatonDuality

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

aether-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

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