While this submission is a draft, it cannot be used by other submissions.

Quotients by polynomial acceptance tests

Lax369799.PolynomialQuotient · concepts/Lax369799/PolynomialQuotient.lean · lax-369799

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Testing all closed polynomial contexts against an accepting set defines an algebra congruence. Evaluation descends to the quotient, the quotient preserves recognition, and finite sorts remain finite.

    Concept map
    6 concepts; 2 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.PolynomialContexts
    2
    3/-!
    4---
    5title: Quotients by polynomial acceptance tests
    6type: theorem
    7---
    8Testing all closed polynomial contexts against an accepting set defines
    9an algebra congruence. Evaluation descends to the quotient, the quotient
    10preserves recognition, and finite sorts remain finite.
    11-/
    12namespace Lax369799.PolynomialQuotient
    13open RankedSystems Algebras PolynomialContexts
    14
    15abbrev Carrier {B : RankedSet} (E : Algebra B) (F : Set (B 0)) : RankedSet :=
    16 fun n => Quot (@Equivalent B E F n)
    17
    18def classMap {B : RankedSet} (E : Algebra B) (F : Set (B 0)) : RankedMap B (Carrier E F) :=
    19 fun _ => Quot.mk _
    20
    21def Accepting {B : RankedSet} (E : Algebra B) (F : Set (B 0)) (a : Carrier E F 0) : Prop :=
    22 ∃ b, classMap E F 0 b = a ∧ b ∈ F
    23
    24axiom algebra {B : RankedSet} (E : Algebra B) (F : Set (B 0)) :
    25 ∃ Q : Algebra (Carrier E F), ∀ n (S : System B n),
    26 Q.eval n (relabelSystem (classMap E F) S) = classMap E F n (E.eval n S)
    27
    28axiom finite_carrier {B : RankedSet} (E : Algebra B) (F : Set (B 0))
    29 (hB : RankwiseFinite B) : RankwiseFinite (Carrier E F)
    30
    31axiom accepting_class {B : RankedSet} (E : Algebra B) (F : Set (B 0)) (b : B 0) :
    32 Accepting E F (classMap E F 0 b) ↔ b ∈ F
    33
    34axiom recognition {A B : RankedSet} (E : Algebra B) (F : Set (B 0))
    35 (Q : Algebra (Carrier E F))
    36 (hQ : ∀ n (S : System B n), Q.eval n (relabelSystem (classMap E F) S) = classMap E F n (E.eval n S))
    37 (η : RankedMap A B) (L : Language A) (hL : Recognizes E η F L) :
    38 Recognizes Q (fun n a => classMap E F n (η n a)) (Accepting E F) L
    39
    40end Lax369799.PolynomialQuotient
    41
    Show ProofShow ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…