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

Polynomial contexts of a system algebra

Lax369799.PolynomialContexts · concepts/Lax369799/PolynomialContexts.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

    Polynomial contexts are functions obtained from a variable and constants by system evaluation. They may use the variable at several vertices. Testing all closed polynomial contexts against an accepting set gives a congruence for evaluation. This construction does not presume unfolding invariance.

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

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

    Lean source view on GitHub

    1import Lax369799.Algebras
    2
    3/-!
    4---
    5title: Polynomial contexts of a system algebra
    6type: theorem
    7---
    8Polynomial contexts are functions obtained from a variable and constants by
    9system evaluation. They may use the variable at several vertices. Testing
    10all closed polynomial contexts against an accepting set gives a congruence
    11for evaluation. This construction does not presume unfolding invariance.
    12-/
    13namespace Lax369799.PolynomialContexts
    14open RankedSystems Algebras
    15
    16abbrev Shape := System (fun _ => Unit)
    17
    18def withLabels {A B : RankedSet} {n : ℕ} (P : System A n)
    19 (f : ∀ v, B (P.val.graph.label v).1) : System B n :=
    20 ⟨{ P.val with graph := { P.val.graph with label := fun v => ⟨(P.val.graph.label v).1, f v⟩ } }, P.property⟩
    21
    22inductive Polynomial {B : RankedSet} (E : Algebra B) (k : ℕ) : ∀ n, (B k → B n) → Prop
    23 | variable : Polynomial E k k id
    24 | constant (n : ℕ) (b : B n) : Polynomial E k n (fun _ => b)
    25 | evaluation {n : ℕ} (P : Shape n) (f : ∀ v, B k → B (P.val.graph.label v).1)
    26 (hf : ∀ v, Polynomial E k (P.val.graph.label v).1 (f v)) :
    27 Polynomial E k n (fun x => E.eval n (withLabels P (fun v => f v x)))
    28
    29def Equivalent {B : RankedSet} (E : Algebra B) (F : Set (B 0)) {n : ℕ} (a b : B n) : Prop :=
    30 ∀ p : B n → B 0, Polynomial E n 0 p → (p a ∈ F ↔ p b ∈ F)
    31
    32axiom composition {B : RankedSet} (E : Algebra B) {k m n : ℕ}
    33 {f : B m → B n} {g : B k → B m} (hf : Polynomial E m n f) (hg : Polynomial E k m g) :
    34 Polynomial E k n (f ∘ g)
    35
    36axiom evaluation_congruence {A B : RankedSet} (E : Algebra B) (F : Set (B 0))
    37 {n : ℕ} (P : System A n) (q r : ∀ v, B (P.val.graph.label v).1)
    38 (h : ∀ v, Equivalent E F (q v) (r v)) :
    39 Equivalent E F (E.eval n (withLabels P q)) (E.eval n (withLabels P r))
    40
    41end Lax369799.PolynomialContexts
    42
    Show ProofShow Proof

    Discussion

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

    Loading discussion…