Finite presentations without reachability pruning
Lax369799.FinitePresentations · concepts/Lax369799/FinitePresentations.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Finite presentations retain every vertex during substitution. Reachability is an additional property, rather than a restriction on intermediate presentations. This distinction is needed for associativity when labels may themselves contain roots: an intermediate unreachable vertex may carry a label with a root that becomes visible at the next substitution.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax369799.RankedSystems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Finite presentations without reachability pruning |
| 6 | type: definition |
| 7 | --- |
| 8 | Finite presentations retain every vertex during substitution. Reachability |
| 9 | is an additional property, rather than a restriction on intermediate |
| 10 | presentations. This distinction is needed for associativity when labels |
| 11 | may themselves contain roots: an intermediate unreachable vertex may |
| 12 | carry a label with a root that becomes visible at the next substitution. |
| 13 | -/ |
| 14 | |
| 15 | namespace Lax369799.FinitePresentations |
| 16 | open RankedSystems |
| 17 | |
| 18 | structure FiniteSystem (A : RankedSet) (n : ℕ) where |
| 19 | size : ℕ |
| 20 | graph : Presentation A n (Fin size) |
| 21 | |
| 22 | abbrev FiniteSystem.Vertex {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) := Fin S.size |
| 23 | |
| 24 | def Reachable {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) : Prop := |
| 25 | ∀ v, S.graph.Reachable v |
| 26 | |
| 27 | def ofSetSystem {A : RankedSet} {n : ℕ} (S : SetSystem A n) : FiniteSystem A n := |
| 28 | ⟨S.size, S.graph⟩ |
| 29 | |
| 30 | def atomic {A : RankedSet} {n : ℕ} (a : A n) : FiniteSystem A n := |
| 31 | ofSetSystem (RankedSystems.atomic a) |
| 32 | |
| 33 | def reindex {A : RankedSet} {n : ℕ} {V W : Type} |
| 34 | (G : Presentation A n V) (e : V ≃ W) : Presentation A n W where |
| 35 | label := fun w => G.label (e.symm w) |
| 36 | initial := fun w => G.initial (e.symm w) |
| 37 | root := fun w => G.root (e.symm w) |
| 38 | edge := fun w d t => G.edge (e.symm w) d (Sum.map e.symm id t) |
| 39 | direction_valid := fun _ d _ h => G.direction_valid _ d _ h |
| 40 | |
| 41 | noncomputable def enumerate {A : RankedSet} {n : ℕ} {V : Type} [Fintype V] |
| 42 | (G : Presentation A n V) : FiniteSystem A n := |
| 43 | ⟨Fintype.card V, reindex G (Fintype.equivFin V)⟩ |
| 44 | |
| 45 | def sumPresentation {A : RankedSet} {n : ℕ} {V W : Type} |
| 46 | (G : Presentation A n V) (H : Presentation A n W) : Presentation A n (V ⊕ W) where |
| 47 | label := Sum.elim G.label H.label |
| 48 | initial := Sum.elim G.initial H.initial |
| 49 | root := Sum.elim G.root H.root |
| 50 | edge := fun v d t => match v with |
| 51 | | .inl v => ∃ s, G.edge v d s ∧ t = Sum.map Sum.inl id s |
| 52 | | .inr w => ∃ s, H.edge w d s ∧ t = Sum.map Sum.inr id s |
| 53 | direction_valid := by |
| 54 | intro v d t h |
| 55 | cases v with |
| 56 | | inl v => obtain ⟨s, hs, _⟩ := h; exact G.direction_valid v d s hs |
| 57 | | inr w => obtain ⟨s, hs, _⟩ := h; exact H.direction_valid w d s hs |
| 58 | |
| 59 | noncomputable def sum {A : RankedSet} {n : ℕ} (S T : FiniteSystem A n) : FiniteSystem A n := |
| 60 | enumerate (sumPresentation S.graph T.graph) |
| 61 | |
| 62 | /-- The presentation with no vertices. -/ |
| 63 | def empty (A : RankedSet) (n : ℕ) : FiniteSystem A n where |
| 64 | size := 0 |
| 65 | graph := { |
| 66 | label := Fin.elim0 |
| 67 | initial := ∅ |
| 68 | root := ∅ |
| 69 | edge := fun _ _ _ => False |
| 70 | direction_valid := fun v => Fin.elim0 v } |
| 71 | |
| 72 | /-- Turn all initial vertices into roots without deleting vertices. -/ |
| 73 | def plant {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) : FiniteSystem A n where |
| 74 | size := S.size |
| 75 | graph := { S.graph with initial := ∅, root := S.graph.root ∪ S.graph.initial } |
| 76 | |
| 77 | /-- A two-component pattern for disjoint union. -/ |
| 78 | def binary {A : RankedSet} {n : ℕ} (a b : A n) : FiniteSystem A n where |
| 79 | size := 2 |
| 80 | graph := { |
| 81 | label := Fin.cases ⟨n, a⟩ (fun _ => ⟨n, b⟩) |
| 82 | initial := Set.univ |
| 83 | root := ∅ |
| 84 | edge := fun _ d t => ∃ i : Fin n, d = i.val ∧ t = .inr i |
| 85 | direction_valid := by |
| 86 | rintro v d t ⟨i, rfl, _⟩ |
| 87 | exact Fin.cases i.isLt (fun _ => i.isLt) v } |
| 88 | |
| 89 | abbrev Inner {A : RankedSet} {n : ℕ} {V : Type} |
| 90 | (P : Presentation (FiniteSystem A) n V) (v : V) := (P.label v).2 |
| 91 | |
| 92 | /-- A vertex of a flattened presentation retains its outer and inner positions. -/ |
| 93 | abbrev FlattenedVertex {A : RankedSet} {n : ℕ} {V : Type} |
| 94 | (P : Presentation (FiniteSystem A) n V) := (v : V) × (Inner P v).Vertex |
| 95 | |
| 96 | def flattenPresentation {A : RankedSet} {n : ℕ} {V : Type} |
| 97 | (P : Presentation (FiniteSystem A) n V) : |
| 98 | Presentation A n (FlattenedVertex P) where |
| 99 | label := fun v => (Inner P v.1).graph.label v.2 |
| 100 | initial := fun v => P.initial v.1 ∧ (Inner P v.1).graph.initial v.2 |
| 101 | root := fun v => (Inner P v.1).graph.root v.2 ∨ |
| 102 | (P.root v.1 ∧ (Inner P v.1).graph.initial v.2) |
| 103 | edge := fun v d t => |
| 104 | (∃ w, (Inner P v.1).graph.edge v.2 d (.inl w) ∧ t = .inl ⟨v.1, w⟩) ∨ |
| 105 | (∃ i : Fin (P.label v.1).1, (Inner P v.1).graph.edge v.2 d (.inr i) ∧ |
| 106 | ((∃ w : (v : V) × (Inner P v).Vertex, |
| 107 | P.edge v.1 i.val (.inl w.1) ∧ (Inner P w.1).graph.initial w.2 ∧ t = .inl w) ∨ |
| 108 | (∃ j, P.edge v.1 i.val (.inr j) ∧ t = .inr j))) |
| 109 | direction_valid := by |
| 110 | intro v d t h |
| 111 | rcases h with ⟨w, hw, _⟩ | ⟨i, hi, _⟩ |
| 112 | · exact (Inner P v.1).graph.direction_valid _ d _ hw |
| 113 | · exact (Inner P v.1).graph.direction_valid _ d _ hi |
| 114 | |
| 115 | noncomputable def flatten {A : RankedSet} {n : ℕ} |
| 116 | (S : FiniteSystem (FiniteSystem A) n) : FiniteSystem A n := |
| 117 | enumerate (flattenPresentation S.graph) |
| 118 | |
| 119 | def relabel {A B : RankedSet} (f : RankedMap A B) {n : ℕ} |
| 120 | (S : FiniteSystem A n) : FiniteSystem B n where |
| 121 | size := S.size |
| 122 | graph := { |
| 123 | label := fun v => ⟨(S.graph.label v).1, f _ (S.graph.label v).2⟩ |
| 124 | initial := S.graph.initial |
| 125 | root := S.graph.root |
| 126 | edge := S.graph.edge |
| 127 | direction_valid := S.graph.direction_valid } |
| 128 | |
| 129 | def withLabels {A B : RankedSet} {n : ℕ} (P : FiniteSystem B n) |
| 130 | (q : ∀ v : P.Vertex, A (P.graph.label v).1) : FiniteSystem A n where |
| 131 | size := P.size |
| 132 | graph := { |
| 133 | label := fun v => ⟨(P.graph.label v).1, q v⟩ |
| 134 | initial := P.graph.initial |
| 135 | root := P.graph.root |
| 136 | edge := P.graph.edge |
| 137 | direction_valid := P.graph.direction_valid } |
| 138 | |
| 139 | structure PresentationIso {A : RankedSet} {n : ℕ} {V W : Type} |
| 140 | (G : Presentation A n V) (H : Presentation A n W) where |
| 141 | vertex : V ≃ W |
| 142 | label : ∀ v, H.label (vertex v) = G.label v |
| 143 | initial : ∀ v, H.initial (vertex v) ↔ G.initial v |
| 144 | root : ∀ v, H.root (vertex v) ↔ G.root v |
| 145 | edge : ∀ v d t, H.edge (vertex v) d (Sum.map vertex id t) ↔ G.edge v d t |
| 146 | |
| 147 | def Isomorphic {A : RankedSet} {n : ℕ} (S T : FiniteSystem A n) : Prop := |
| 148 | Nonempty (PresentationIso S.graph T.graph) |
| 149 | |
| 150 | axiom flatten_associative {A : RankedSet} {n : ℕ} |
| 151 | (S : FiniteSystem (FiniteSystem (FiniteSystem A)) n) : |
| 152 | Isomorphic (flatten (flatten S)) (flatten (relabel (fun _ T => flatten T) S)) |
| 153 | |
| 154 | axiom outer_atomic {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) : |
| 155 | Isomorphic (flatten (atomic S)) S |
| 156 | |
| 157 | axiom inner_atomic {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) : |
| 158 | Isomorphic (flatten (relabel (fun _ a => atomic a) S)) S |
| 159 | |
| 160 | axiom flatten_natural {A B : RankedSet} (f : RankedMap A B) {n : ℕ} |
| 161 | (S : FiniteSystem (FiniteSystem A) n) : |
| 162 | relabel f (flatten S) = flatten (relabel (fun _ T => relabel f T) S) |
| 163 | |
| 164 | axiom flatten_binary {A : RankedSet} {n : ℕ} (S T : FiniteSystem A n) : |
| 165 | Isomorphic (flatten (binary S T)) (sum S T) |
| 166 | |
| 167 | end Lax369799.FinitePresentations |
| 168 |
Builds on
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments