While this submission is a draft, it cannot be used by other submissions.

Finite presentations without reachability pruning

Lax369799.FinitePresentations · concepts/Lax369799/FinitePresentations.lean · lax-369799

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    2 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

    This concept declares 5 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.RankedSystems
    2
    3/-!
    4---
    5title: Finite presentations without reachability pruning
    6type: definition
    7---
    8Finite presentations retain every vertex during substitution. Reachability
    9is an additional property, rather than a restriction on intermediate
    10presentations. This distinction is needed for associativity when labels
    11may themselves contain roots: an intermediate unreachable vertex may
    12carry a label with a root that becomes visible at the next substitution.
    13-/
    14
    15namespace Lax369799.FinitePresentations
    16open RankedSystems
    17
    18structure FiniteSystem (A : RankedSet) (n : ℕ) where
    19 size : ℕ
    20 graph : Presentation A n (Fin size)
    21
    22abbrev FiniteSystem.Vertex {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) := Fin S.size
    23
    24def Reachable {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) : Prop :=
    25 ∀ v, S.graph.Reachable v
    26
    27def ofSetSystem {A : RankedSet} {n : ℕ} (S : SetSystem A n) : FiniteSystem A n :=
    28 ⟨S.size, S.graph⟩
    29
    30def atomic {A : RankedSet} {n : ℕ} (a : A n) : FiniteSystem A n :=
    31 ofSetSystem (RankedSystems.atomic a)
    32
    33def 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
    41noncomputable 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
    45def 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
    59noncomputable 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. -/
    63def 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. -/
    73def 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. -/
    78def 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
    89abbrev 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. -/
    93abbrev FlattenedVertex {A : RankedSet} {n : ℕ} {V : Type}
    94 (P : Presentation (FiniteSystem A) n V) := (v : V) × (Inner P v).Vertex
    95
    96def 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
    115noncomputable def flatten {A : RankedSet} {n : ℕ}
    116 (S : FiniteSystem (FiniteSystem A) n) : FiniteSystem A n :=
    117 enumerate (flattenPresentation S.graph)
    118
    119def 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
    129def 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
    139structure 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
    147def Isomorphic {A : RankedSet} {n : ℕ} (S T : FiniteSystem A n) : Prop :=
    148 Nonempty (PresentationIso S.graph T.graph)
    149
    150axiom 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
    154axiom outer_atomic {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) :
    155 Isomorphic (flatten (atomic S)) S
    156
    157axiom inner_atomic {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) :
    158 Isomorphic (flatten (relabel (fun _ a => atomic a) S)) S
    159
    160axiom 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
    164axiom flatten_binary {A : RankedSet} {n : ℕ} (S T : FiniteSystem A n) :
    165 Isomorphic (flatten (binary S T)) (sum S T)
    166
    167end Lax369799.FinitePresentations
    168
    Show ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…