Morphisms of unpruned finite presentations
Lax369799.FiniteMorphisms · concepts/Lax369799/FiniteMorphisms.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Morphisms preserve labels, marks, and transitions, including at unreachable vertices. They lift through substitution in a fixed context. Since they preserve yields on reachable restrictions, they reverse acceptance and the contextual preorder defined by yield acceptance.
Concept map
Evidence
This concept declares 6 statements. Each proof establishes one of them relative to its assumptions.
1 accepting_morphism proven
2 contextual_cover proven
3 contextual_morphism proven
4 sum_idempotent proven
5 sum_lower proven
6 sum_meet proven
Lean source view on GitHub
| 1 | import Lax369799.FiniteAcceptance |
| 2 | import Lax369799.PresentationCovers |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Morphisms of unpruned finite presentations |
| 7 | type: theorem |
| 8 | --- |
| 9 | Morphisms preserve labels, marks, and transitions, including at unreachable |
| 10 | vertices. They lift through substitution in a fixed context. Since they |
| 11 | preserve yields on reachable restrictions, they reverse acceptance and |
| 12 | the contextual preorder defined by yield acceptance. |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.FiniteMorphisms |
| 16 | open RankedSystems (RankedSet) |
| 17 | open FinitePresentations FiniteContexts FiniteContextualOrder FiniteAcceptance |
| 18 | |
| 19 | structure Morphism {A : RankedSet} {n : ℕ} (S T : FiniteSystem A n) where |
| 20 | toFun : S.Vertex → T.Vertex |
| 21 | initial : ∀ v, S.graph.initial v → T.graph.initial (toFun v) |
| 22 | root : ∀ v, S.graph.root v → T.graph.root (toFun v) |
| 23 | label : ∀ v, T.graph.label (toFun v) = S.graph.label v |
| 24 | edge : ∀ v d t, S.graph.edge v d t → T.graph.edge (toFun v) d (Sum.map toFun id t) |
| 25 | |
| 26 | axiom accepting_morphism {A : RankedSet} (L : Algebras.Language A) |
| 27 | {S T : FiniteSystem A 0} (f : Morphism S T) : Accepting L T → Accepting L S |
| 28 | |
| 29 | axiom contextual_morphism {A : RankedSet} (L : Algebras.Language A) {n : ℕ} |
| 30 | {S T : FiniteSystem A n} (f : Morphism S T) : Below (Accepting L) T S |
| 31 | |
| 32 | axiom sum_lower {A : RankedSet} (L : Algebras.Language A) {n : ℕ} |
| 33 | (S T : FiniteSystem A n) : |
| 34 | Below (Accepting L) (sum S T) S ∧ Below (Accepting L) (sum S T) T |
| 35 | |
| 36 | axiom contextual_cover {A : RankedSet} (L : Algebras.Language A) {n : ℕ} |
| 37 | {S T : FiniteSystem A n} (f : PresentationCovers.Cover S.graph T.graph) : |
| 38 | Equivalent (Accepting L) S T |
| 39 | |
| 40 | axiom sum_idempotent {A : RankedSet} (L : Algebras.Language A) {n : ℕ} |
| 41 | (S : FiniteSystem A n) : Equivalent (Accepting L) (sum S S) S |
| 42 | |
| 43 | axiom sum_meet {A : RankedSet} (L : Algebras.Language A) {n : ℕ} |
| 44 | (R S T : FiniteSystem A n) : |
| 45 | Below (Accepting L) R (sum S T) ↔ |
| 46 | Below (Accepting L) R S ∧ Below (Accepting L) R T |
| 47 | |
| 48 | end Lax369799.FiniteMorphisms |
| 49 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments