Root entries in substituted presentations
Lax369799.RootExpansion · concepts/Lax369799/RootExpansion.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
To observe the roots of a substitution, give every outer vertex a separate starting copy whose inner roots become initial. Subsequent outer transitions go to ordinary copies, where inner initial vertices remain initial. Outer roots also start at their ordinary copies. All root marks in the expanded presentation are removed. This preserves root observations even at vertices that were unreachable in the original outer presentation.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FinitePresentations |
| 2 | import Lax369799.PresentationCovers |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Root entries in substituted presentations |
| 7 | type: theorem |
| 8 | --- |
| 9 | To observe the roots of a substitution, give every outer vertex a separate |
| 10 | starting copy whose inner roots become initial. Subsequent outer transitions |
| 11 | go to ordinary copies, where inner initial vertices remain initial. Outer |
| 12 | roots also start at their ordinary copies. All root marks in the expanded |
| 13 | presentation are removed. This preserves root observations even at vertices |
| 14 | that were unreachable in the original outer presentation. |
| 15 | -/ |
| 16 | namespace Lax369799.RootExpansion |
| 17 | open RankedSystems FinitePresentations |
| 18 | |
| 19 | def startAtRoots {A : RankedSet} {n : ℕ} {V : Type} (G : Presentation A n V) : |
| 20 | Presentation A n V := { G with initial := G.root, root := ∅ } |
| 21 | |
| 22 | def component {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) (start : Bool) : FiniteSystem A n where |
| 23 | size := S.size |
| 24 | graph := { S.graph with initial := if start then S.graph.root else S.graph.initial, root := ∅ } |
| 25 | |
| 26 | def pattern {A : RankedSet} {n : ℕ} {V : Type} |
| 27 | (P : Presentation (FiniteSystem A) n V) : Presentation (FiniteSystem A) n (Bool × V) where |
| 28 | label := fun v => ⟨(P.label v.2).1, component (Inner P v.2) v.1⟩ |
| 29 | initial := fun v => if v.1 then True else P.root v.2 |
| 30 | root := ∅ |
| 31 | edge := fun v d t => ∃ s, P.edge v.2 d s ∧ t = Sum.map (fun w => (false, w)) id s |
| 32 | direction_valid := by rintro v d t ⟨s, hs, _⟩; exact P.direction_valid _ _ _ hs |
| 33 | |
| 34 | axiom expansion_cover {A : RankedSet} {n : ℕ} {V : Type} |
| 35 | (P : Presentation (FiniteSystem A) n V) : |
| 36 | Nonempty (PresentationCovers.Cover (flattenPresentation (pattern P)) |
| 37 | (startAtRoots (flattenPresentation P))) |
| 38 | |
| 39 | axiom expansion_folding {A : RankedSet} {n : ℕ} {V : Type} |
| 40 | (P : Presentation (FiniteSystem A) n V) : |
| 41 | ∃ f : PresentationCovers.Cover (flattenPresentation (pattern P)) |
| 42 | (startAtRoots (flattenPresentation P)), Function.Surjective f.toFun |
| 43 | |
| 44 | end Lax369799.RootExpansion |
| 45 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments