Algebras on fully supported systems
Lax369799.SupportedAlgebras · concepts/Lax369799/SupportedAlgebras.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Evaluation is defined on the systems of Definition 6, with every output reachable. Restriction of an algebra on arbitrary deterministic systems preserves its algebra laws, unfolding invariance, and recognition. Evaluation commutes with surjective output renaming.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.SupportedSystems |
| 2 | import Lax369799.Algebras |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Algebras on fully supported systems |
| 7 | type: theorem |
| 8 | --- |
| 9 | Evaluation is defined on the systems of Definition 6, with every output |
| 10 | reachable. Restriction of an algebra on arbitrary deterministic systems |
| 11 | preserves its algebra laws, unfolding invariance, and recognition. Evaluation commutes with surjective output renaming. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax369799.SupportedAlgebras |
| 15 | open RankedSystems (RankedSet RankedMap RankwiseFinite) |
| 16 | open SupportedSystems Morphisms |
| 17 | |
| 18 | structure Algebra (A : RankedSet) where |
| 19 | eval : ∀ n, System A n → A n |
| 20 | isomorphic : ∀ n (S T : System A n), Isomorphic S.val.val T.val.val → eval n S = eval n T |
| 21 | unit : ∀ n (a : A n), eval n (atomic a) = a |
| 22 | associative : ∀ n (S : System (System A) n) (T : System A n), |
| 23 | Flattening.SystemFlattening (forgetPattern S) T.val → |
| 24 | eval n (relabel eval S) = eval n T |
| 25 | |
| 26 | def UnfoldInvariant {A : RankedSet} (E : Algebra A) : Prop := |
| 27 | ∀ n (S T : System A n), UnfoldEquivalent S.val.val T.val.val → E.eval n S = E.eval n T |
| 28 | |
| 29 | def Recognizes {A B : RankedSet} (E : Algebra B) (η : RankedMap A B) |
| 30 | (F : Set (B 0)) (L : Algebras.Language A) : Prop := |
| 31 | ∀ T : System A 0, T.val ∈ L ↔ E.eval 0 (relabel η T) ∈ F |
| 32 | |
| 33 | def Recognizable {A : RankedSet} (L : Algebras.Language A) : Prop := |
| 34 | ∃ (B : RankedSet) (E : Algebra B) (η : RankedMap A B) (F : Set (B 0)), |
| 35 | RankwiseFinite B ∧ Recognizes E η F L |
| 36 | |
| 37 | def restrict {A : RankedSet} (E : Algebras.Algebra A) : Algebra A where |
| 38 | eval := fun n S => E.eval n S.val |
| 39 | isomorphic := fun n S T h => E.isomorphic n S.val T.val h |
| 40 | unit := E.unit |
| 41 | associative := fun n S T h => E.associative n (forgetPattern S) T.val h |
| 42 | |
| 43 | axiom restrict_invariant {A : RankedSet} (E : Algebras.Algebra A) |
| 44 | (hE : Algebras.UnfoldInvariant E) : UnfoldInvariant (restrict E) |
| 45 | |
| 46 | axiom legacy_recognizable {A : RankedSet} (L : Algebras.Language A) |
| 47 | (hL : Algebras.Recognizable L) : Recognizable L |
| 48 | |
| 49 | axiom rename_evaluation {A : RankedSet} (E : Algebra A) |
| 50 | {m n : ℕ} (σ : Fin m → Fin n) (hσ : Function.Surjective σ) (S : System A m) : |
| 51 | E.eval n (rename σ hσ S) = E.eval n (rename σ hσ (atomic (E.eval m S))) |
| 52 | |
| 53 | end Lax369799.SupportedAlgebras |
| 54 | |
| 55 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments