Contexts over finite presentations
Lax369799.FiniteContexts · concepts/Lax369799/FiniteContexts.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A context has one distinguished hole vertex, with no restriction on its marks, incident edges, or reachability. Composition and substitution retain all vertices, so an unreachable hole remains available for a later substitution that contributes roots.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.FinitePresentations |
| 2 | import Lax369799.Flattening |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Contexts over finite presentations |
| 7 | type: definition |
| 8 | --- |
| 9 | A context has one distinguished hole vertex, with no restriction on its |
| 10 | marks, incident edges, or reachability. Composition and substitution retain |
| 11 | all vertices, so an unreachable hole remains available for a later |
| 12 | substitution that contributes roots. |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.FiniteContexts |
| 16 | open RankedSystems FinitePresentations |
| 17 | open Flattening (WithHole IsHole) |
| 18 | |
| 19 | structure Context (A : RankedSet) (k n : ℕ) where |
| 20 | system : FiniteSystem (WithHole A k) n |
| 21 | one_hole : ∃! v, IsHole (system.graph.label v) |
| 22 | |
| 23 | def substitution {A : RankedSet} {k : ℕ} (S : FiniteSystem A k) : |
| 24 | RankedMap (WithHole A k) (FiniteSystem A) := |
| 25 | fun _ a => match a with |
| 26 | | .inl a => FinitePresentations.atomic a |
| 27 | | .inr ⟨h⟩ => h ▸ S |
| 28 | |
| 29 | noncomputable def plug {A : RankedSet} {k n : ℕ} (C : Context A k n) |
| 30 | (S : FiniteSystem A k) : FiniteSystem A n := |
| 31 | flatten (FinitePresentations.relabel (substitution S) C.system) |
| 32 | |
| 33 | def insertion {A : RankedSet} {k n : ℕ} (C : Context A k n) : |
| 34 | RankedMap (WithHole A n) (FiniteSystem (WithHole A k)) := |
| 35 | fun _ a => match a with |
| 36 | | .inl a => FinitePresentations.atomic (Sum.inl a) |
| 37 | | .inr ⟨h⟩ => h ▸ C.system |
| 38 | |
| 39 | noncomputable def compositionSystem {A : RankedSet} {k n m : ℕ} |
| 40 | (D : Context A n m) (C : Context A k n) : FiniteSystem (WithHole A k) m := |
| 41 | flatten (FinitePresentations.relabel (insertion C) D.system) |
| 42 | |
| 43 | def interpretation {A B : RankedSet} {k : ℕ} |
| 44 | (f : RankedMap B (FiniteSystem A)) (S : FiniteSystem A k) : |
| 45 | RankedMap (WithHole B k) (FiniteSystem A) := |
| 46 | fun _ a => match a with |
| 47 | | .inl b => f _ b |
| 48 | | .inr ⟨h⟩ => h ▸ S |
| 49 | |
| 50 | /-- Replace each ordinary label by its assigned finite presentation. -/ |
| 51 | axiom extension {A B : RankedSet} (f : RankedMap B (FiniteSystem A)) |
| 52 | {k n : ℕ} (C : Context B k n) : |
| 53 | ∃ D : Context A k n, ∀ S, |
| 54 | Isomorphic (plug D S) (flatten (FinitePresentations.relabel (interpretation f S) C.system)) |
| 55 | |
| 56 | axiom composition {A : RankedSet} {k n m : ℕ} |
| 57 | (D : Context A n m) (C : Context A k n) : |
| 58 | ∃ E : Context A k m, E.system = compositionSystem D C ∧ |
| 59 | ∀ S, FinitePresentations.Isomorphic (plug E S) (plug D (plug C S)) |
| 60 | |
| 61 | end Lax369799.FiniteContexts |
| 62 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments