Polynomial contexts of a system algebra
Lax369799.PolynomialContexts · concepts/Lax369799/PolynomialContexts.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Evidence
Lean source view on GitHub
| 1 | import Lax369799.Algebras |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Polynomial contexts of a system algebra |
| 6 | type: theorem |
| 7 | --- |
| 8 | Polynomial contexts are functions obtained from a variable and constants by |
| 9 | system evaluation. They may use the variable at several vertices. Testing |
| 10 | all closed polynomial contexts against an accepting set gives a congruence |
| 11 | for evaluation. This construction does not presume unfolding invariance. |
| 12 | -/ |
| 13 | namespace Lax369799.PolynomialContexts |
| 14 | open RankedSystems Algebras |
| 15 | |
| 16 | abbrev Shape := System (fun _ => Unit) |
| 17 | |
| 18 | def 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 | |
| 22 | inductive 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 | |
| 29 | def 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 | |
| 32 | axiom 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 | |
| 36 | axiom 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 | |
| 41 | end Lax369799.PolynomialContexts |
| 42 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments