Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — Bridges_GraphTheory_SemanticQuotientExtraction

Definition
Bridges_GraphTheory_SemanticQuotientExtraction

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

aether-catalogbridges

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

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

/-!
# Semantic Quotient Extraction: Non-Convergent Soundness

## Overview

This file establishes that **extraction correctness is a manifestation of semantic quotient
invariance**, and therefore survives far beyond the classical boundaries of convergent rewriting.
We formalize the principle that equality saturation is sound because quotient semantics is sound,
not because rewriting converges.

## Mathematical Contribution

The central insight: an e-graph extractor is sound whenever the rewrite relation preserves
denotation under each step. No confluence, no termination, no orientation is required.
We formalize this in three settings:

1. **Abstract rewrite systems** — semantic invariance of equivalence closure (Theorem 1)
2. **Extraction soundness** — any extractor from the same e-class preserves semantics (Theorem 2)
3. **Compositional term languages** — context closure preserves soundness (Theorems 3–4)
4. **SK combinator calculus** — a non-confluent, non-normalizing bridge domain (Theorem 5)

## New Definitions

- `EGraphSound`: a class capturing step-soundness of a rewrite relation w.r.t. a denotation
- `SemanticsInvariant`: semantic invariance under equivalence closure
- `QuotientSoundExtractor`: an extractor that is sound via quotient semantics
- `ContextClosure`: closure of a relation under term constructors
- `SKTerm`, `SKStep`: SK combinator syntax and rewrite rules
- `SKDenote`: denotation of SK terms into function spaces

## Lineage

Builds on `Catalog/Pythagorean/EqualitySaturationExtraction.lean`:
- `extraction_semantics_preserved`
- `extract_eqvGen`
-/

open Relation

universe u v

/-! ## Part I: Core Definitions -/

/-- A semantics is e-graph sound if every rewrite step preserves denotation. -/
class EGraphSound
    {α : Type u} {σ : Type v}
    (denote : α → σ)
    (step : α → α → Prop) : Prop where
  sound_step : ∀ {a b}, step a b → denote a = denote b

/-- Semantic invariance under the equivalence closure generated by a rewrite relation. -/
def SemanticsInvariant
    {α : Type u} {σ : Type v}
    (denote : α → σ)
    (R : α → α → Prop) : Prop :=
  ∀ ⦃a b : α⦄, EqvGen R a b → denote a = denote b

/-- An extractor is quotient-sound if it always returns a representative
    semantically equal to the original term whenever it returns a term in the same e-class. -/
def QuotientSoundExtractor
    {α : Type u} {σ : Type v}
    (denote : α → σ)
    (R : α → α → Prop)
    (extract : α → α) : Prop :=
  ∀ a, EqvGen R a (extract a) ∧ denote (extract a) = denote a

/-! ## Part II: Theorem 1 — Semantic Invariance Without Convergence -/

/-
**Theorem 1: Semantic invariance of equivalence closure needs no convergence.**

The semantic content of equality saturation lives in the equivalence closure,
not in any normalization theorem.

> Confluence is sufficient for canonical forms, but unnecessary for semantic soundness.

This is proved by induction on `EqvGen`, handling reflexivity, symmetry, transitivity,
and the forward step case using the step-soundness hypothesis.
-/
theorem eqvGen_semantics_preserved_of_step_sound
    {α : Type u} {σ : Type v}
    (denote : α → σ)
    (R : α → α → Prop)
    (hR : ∀ ⦃a b : α⦄, R a b → denote a = denote b) :
    ∀ ⦃a b : α⦄, EqvGen R a b → denote a = denote b := by
  intro a b;
  intro hab
  induction' hab with a b hab ih;
  · grind +qlia;
  · rfl;
  · grind;
  · grind

/-
Step soundness implies full semantic invariance.
-/

/-! ## Part III: Theorem 2 — Extraction Soundness Without Confluence -/

/-
**Theorem 2: Extraction soundness for arbitrary non-confluent rewrite systems.**

If an extractor returns any representative from the same e-class,
and the e-class relation is semantically sound, then extraction is sound.
No confluence, termination, or orientation hypotheses appear.
-/

/-
Constructing a `QuotientSoundExtractor` from step soundness and class membership.
-/

/-- The denotation factors through the quotient by `EqvGen R` when step soundness holds. -/
noncomputable def denoteLiftQuotient
    {α : Type u} {σ : Type v}
    (denote : α → σ)
    (R : α → α → Prop)
    (hR : ∀ ⦃a b : α⦄, R a b → denote a = denote b) :
    Quot (EqvGen R) → σ :=
  Quot.lift denote (eqvGen_semantics_preserved_of_step_sound denote R hR)

/-
The quotient lift agrees with direct evaluation.
-/

/-! ## Part IV: Theorem 3 — Context Closure for Compositional Languages -/

/-- A simple arithmetic term language. -/
inductive Term where
  | var : Nat → Term
  | const : Int → Term
  | add : Term → Term → Term
  | mul : Term → Term → Term
  deriving Repr, BEq

/-- Denotation of terms into integers given an environment. -/
def Term.denote (ρ : Nat → Int) : Term → Int
  | .var n => ρ n
  | .const k => k
  | .add t₁ t₂ => t₁.denote ρ + t₂.denote ρ
  | .mul t₁ t₂ => t₁.denote ρ * t₂.denote ρ

/-- Contextual closure of a relation `R` under the term constructors.
This captures the idea of rewriting inside subterms. -/
inductive ContextClosure (R : Term → Term → Prop) : Term → Term → Prop where
  | base (a b : Term) : R a b → ContextClosure R a b
  | add_left (a b c : Term) : ContextClosure R a b → ContextClosure R (Term.add a c) (Term.add b c)
  | add_right (a b c : Term) : ContextClosure R a b → ContextClosure R (Term.add c a) (Term.add c b)
  | mul_left (a b c : Term) : ContextClosure R a b → ContextClosure R (Term.mul a c) (Term.mul b c)
  | mul_right (a b c : Term) : ContextClosure R a b → ContextClosure R (Term.mul c a) (Term.mul c b)

/-
**Lemma: Context closure preserves denotation if the base relation does.**

If every base rewrite step preserves denotation, then rewriting anywhere
inside a term also preserves denotation. This uses induction on the
`ContextClosure` derivation.
-/

/-
**Theorem 3: Context closure preserves semantic soundness under equivalence closure.**

Soundness survives compositional embedding into larger programs. This is essential
if the abstract theorems are to justify real optimizers rather than isolated equation provers.
-/

/-
Extraction soundness for the compositional term language.
-/

/-! ## Part V: Theorem 4 — SK Combinator Bridge (Non-Confluent Domain) -/

/-- SK combinator terms — a famously non-normalizing calculus. -/
inductive SKTerm where
  | S : SKTerm
  | K : SKTerm
  | app : SKTerm → SKTerm → SKTerm
  deriving Repr, BEq

/-- One-step SK reduction rules.
- K x y → x
- S x y z → (x z) (y z)
These are non-confluent and non-normalizing in general. -/
inductive SKStep : SKTerm → SKTerm → Prop where
  | K_red (x y : SKTerm) : SKStep (SKTerm.app (SKTerm.app SKTerm.K x) y) x
  | S_red (x y z : SKTerm) : SKStep
      (SKTerm.app (SKTerm.app (SKTerm.app SKTerm.S x) y) z)
      (SKTerm.app (SKTerm.app x z) (SKTerm.app y z))
  | app_left (a b c : SKTerm) : SKStep a b → SKStep (SKTerm.app a c) (SKTerm.app b c)
  | app_right (a b c : SKTerm) : SKStep a b → SKStep (SKTerm.app c a) (SKTerm.app c b)

/-- An SK model provides a type and interpretation of S and K combinators. -/
structure SKModel where
  carrier : Type
  sk_S : carrier
  sk_K : carrier
  sk_app : carrier → carrier → carrier
  /-- K x y = x -/
  K_law : ∀ x y, sk_app (sk_app sk_K x) y = x
  /-- S x y z = (x z) (y z) -/
  S_law : ∀ x y z, sk_app (sk_app (sk_app sk_S x) y) z =
    sk_app (sk_app x z) (sk_app y z)

/-- Denotation of SK terms into a model. -/
def SKTerm.denote (M : SKModel) : SKTerm → M.carrier
  | .S => M.sk_S
  | .K => M.sk_K
  | .app t u => M.sk_app (t.denote M) (u.denote M)

/-
Each SK reduction step preserves denotation in any model.
-/

/-
**Theorem 4 (Cross-domain bridge): SK combinator equivalence preserves denotation
without normalization.**

The SK combinator calculus is famously non-normalizing — many terms have no normal form,
and the rewrite system is non-confluent modulo evaluation order. Yet semantic soundness
of extraction holds by the quotient principle alone.
-/

/-
Extraction soundness for SK combinators: any extractor returning an equivalent
term preserves semantics, even though normal forms may not exist.
-/

/-! ## Part VI: General Composition Theorem -/

/-
**Composition of sound extractors.**

If two extraction steps are each quotient-sound, their composition is also sound.
This enables modular optimizer pipelines where each pass may use a different
non-confluent rewrite system.
-/

/-! ## Part VII: Concrete Non-Confluent Example -/

/-- A concrete non-confluent rewrite system on arithmetic terms:
both `x + 0 → x` and `x → x + 0` are valid rewrites,
creating non-confluence and non-termination. -/
inductive NonConfluentArithStep : Term → Term → Prop where
  | add_zero_elim (t : Term) : NonConfluentArithStep (Term.add t (Term.const 0)) t
  | add_zero_intro (t : Term) : NonConfluentArithStep t (Term.add t (Term.const 0))
  | comm_add (a b : Term) : NonConfluentArithStep (Term.add a b) (Term.add b a)

/-
The non-confluent arithmetic rewrites preserve denotation.
-/

/-
Even with non-confluent, non-terminating rewrites, equivalence closure
preserves semantics for arithmetic terms.
-/

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