Context decomposition with hole boundary data
Lax369799.ContextDecomposition · concepts/Lax369799/ContextDecomposition.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A hole is an ordinary vertex: it may be initial, a root, and the target of its own outgoing edges. Cutting a closed context into unary pieces must retain these three kinds of boundary information. The entry piece starts at the original non-hole initial vertices; piece i+1 starts at non-hole successors in direction i. All pieces retain the non-hole roots, and edges into the hole become edges to the sole variable.
Recomposition takes a separate copy of every piece, redirects variable edges to a fresh hole, restores its initial and root marks, and restores its self-loops. Unreachable vertices are removed after recomposition. The resulting set-system covers the original context and is therefore unfold-equivalent to it.
This records explicitly the boundary information omitted by the literal construction preceding in Section 2.8 of arXiv:2407.12677v6. The pieces are presented over the extended alphabet, but no piece contains a vertex labelled by the hole. Presentations retain unreachable vertices until the final restriction.
Concept map
Evidence
This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.
1 decomposition_cover proven
2 decomposition_equivalence proven
3 piece_has_no_hole proven
Lean source view on GitHub
| 1 | import Lax369799.Flattening |
| 2 | import Lax369799.PresentationCovers |
| 3 | import Mathlib.Data.Fintype.Option |
| 4 | import Mathlib.Data.Fintype.Prod |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Context decomposition with hole boundary data |
| 9 | type: theorem |
| 10 | --- |
| 11 | A hole is an ordinary vertex: it may be initial, a root, and the target of |
| 12 | its own outgoing edges. Cutting a closed context into unary pieces must |
| 13 | retain these three kinds of boundary information. The entry piece starts |
| 14 | at the original non-hole initial vertices; piece i+1 starts at non-hole |
| 15 | successors in direction i. All pieces retain the non-hole roots, and |
| 16 | edges into the hole become edges to the sole variable. |
| 17 | |
| 18 | Recomposition takes a separate copy of every piece, redirects variable |
| 19 | edges to a fresh hole, restores its initial and root marks, and restores |
| 20 | its self-loops. Unreachable vertices are removed after recomposition. |
| 21 | The resulting set-system covers the original context and is therefore |
| 22 | unfold-equivalent to it. |
| 23 | |
| 24 | This records explicitly the boundary information omitted by the literal |
| 25 | construction preceding `lemma:context-decomposition` in Section 2.8 of |
| 26 | arXiv:2407.12677v6. The pieces are presented over the extended alphabet, |
| 27 | but no piece contains a vertex labelled by the hole. Presentations retain |
| 28 | unreachable vertices until the final restriction. |
| 29 | -/ |
| 30 | |
| 31 | namespace Lax369799.ContextDecomposition |
| 32 | open RankedSystems Morphisms Flattening |
| 33 | |
| 34 | noncomputable def holeVertex {A : RankedSet} {k : ℕ} (C : SetContext A k 0) : |
| 35 | C.system.Vertex := Classical.choose C.one_hole |
| 36 | |
| 37 | abbrev BodyVertex {A : RankedSet} {k : ℕ} (C : SetContext A k 0) := |
| 38 | {v : C.system.Vertex // v ≠ holeVertex C} |
| 39 | |
| 40 | structure Boundary (k : ℕ) where |
| 41 | initial : Prop |
| 42 | root : Prop |
| 43 | loops : Set (Fin k) |
| 44 | |
| 45 | noncomputable def boundary {A : RankedSet} {k : ℕ} (C : SetContext A k 0) : Boundary k where |
| 46 | initial := holeVertex C ∈ C.system.graph.initial |
| 47 | root := holeVertex C ∈ C.system.graph.root |
| 48 | loops := {d | C.system.graph.edge (holeVertex C) d.val (.inl (holeVertex C))} |
| 49 | |
| 50 | noncomputable def piece {A : RankedSet} {k : ℕ} (C : SetContext A k 0) |
| 51 | (i : Fin (k + 1)) : Presentation (WithHole A k) 1 (BodyVertex C) where |
| 52 | label := fun v => C.system.graph.label v.val |
| 53 | initial := fun v => (i = 0 ∧ v.val ∈ C.system.graph.initial) ∨ |
| 54 | ∃ d : Fin k, i = d.succ ∧ C.system.graph.edge (holeVertex C) d.val (.inl v.val) |
| 55 | root := fun v => v.val ∈ C.system.graph.root |
| 56 | edge := fun v d t => match t with |
| 57 | | .inl w => C.system.graph.edge v.val d (.inl w.val) |
| 58 | | .inr _ => C.system.graph.edge v.val d (.inl (holeVertex C)) |
| 59 | direction_valid := by |
| 60 | intro v d t ht |
| 61 | cases t with |
| 62 | | inl w => exact C.system.graph.direction_valid v.val d _ ht |
| 63 | | inr i => exact C.system.graph.direction_valid v.val d _ ht |
| 64 | |
| 65 | abbrev CopyVertex (k : ℕ) (V : Type) := Option (Fin (k + 1) × V) |
| 66 | |
| 67 | /-- `none` is the new hole; `some (i,v)` is vertex v in piece i. -/ |
| 68 | def recomposePresentation {A : RankedSet} {k : ℕ} {V : Type} |
| 69 | (B : Boundary k) (P : Fin (k + 1) → Presentation (WithHole A k) 1 V) : |
| 70 | Presentation (WithHole A k) 0 (CopyVertex k V) where |
| 71 | label := fun v => match v with |
| 72 | | none => ⟨k, Sum.inr ⟨rfl⟩⟩ |
| 73 | | some (i, v) => (P i).label v |
| 74 | initial := fun v => match v with |
| 75 | | none => B.initial |
| 76 | | some (i, v) => i = 0 ∧ v ∈ (P i).initial |
| 77 | root := fun v => match v with |
| 78 | | none => B.root |
| 79 | | some (i, v) => v ∈ (P i).root |
| 80 | edge := fun v d t => match t with |
| 81 | | .inr j => Fin.elim0 j |
| 82 | | .inl w => match v, w with |
| 83 | | none, none => ∃ i : Fin k, d = i.val ∧ i ∈ B.loops |
| 84 | | none, some (j, w) => ∃ i : Fin k, d = i.val ∧ j = i.succ ∧ w ∈ (P j).initial |
| 85 | | some (i, v), none => (P i).edge v d (.inr 0) |
| 86 | | some (i, v), some (j, w) => i = j ∧ (P i).edge v d (.inl w) |
| 87 | direction_valid := by |
| 88 | intro v d t ht |
| 89 | cases t with |
| 90 | | inr j => exact Fin.elim0 j |
| 91 | | inl w => |
| 92 | cases v with |
| 93 | | none => |
| 94 | cases w with |
| 95 | | none => obtain ⟨i, rfl, _⟩ := ht; exact i.isLt |
| 96 | | some w => obtain ⟨i, rfl, _, _⟩ := ht; exact i.isLt |
| 97 | | some v => |
| 98 | cases w with |
| 99 | | none => exact (P v.1).direction_valid v.2 d _ ht |
| 100 | | some w => exact (P v.1).direction_valid v.2 d _ ht.2 |
| 101 | |
| 102 | noncomputable def recompose {A : RankedSet} {k : ℕ} (C : SetContext A k 0) : |
| 103 | SetSystem (WithHole A k) 0 := by |
| 104 | classical |
| 105 | exact trim (recomposePresentation (boundary C) (piece C)) |
| 106 | |
| 107 | axiom piece_has_no_hole {A : RankedSet} {k : ℕ} (C : SetContext A k 0) |
| 108 | (i : Fin (k + 1)) (v : BodyVertex C) : ¬ IsHole ((piece C i).label v) |
| 109 | |
| 110 | axiom decomposition_cover {A : RankedSet} {k : ℕ} (C : SetContext A k 0) : |
| 111 | UnfoldsTo C.system (recompose C) |
| 112 | |
| 113 | axiom decomposition_equivalence {A : RankedSet} {k : ℕ} (C : SetContext A k 0) : |
| 114 | UnfoldEquivalent C.system (recompose C) |
| 115 | |
| 116 | end Lax369799.ContextDecomposition |
| 117 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments