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

Context decomposition with hole boundary data

Lax369799.ContextDecomposition · concepts/Lax369799/ContextDecomposition.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

    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 lemma:context−decompositionlemma:context-decomposition 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
    5 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.Flattening
    2import Lax369799.PresentationCovers
    3import Mathlib.Data.Fintype.Option
    4import Mathlib.Data.Fintype.Prod
    5
    6/-!
    7---
    8title: Context decomposition with hole boundary data
    9type: theorem
    10---
    11A hole is an ordinary vertex: it may be initial, a root, and the target of
    12its own outgoing edges. Cutting a closed context into unary pieces must
    13retain these three kinds of boundary information. The entry piece starts
    14at the original non-hole initial vertices; piece i+1 starts at non-hole
    15successors in direction i. All pieces retain the non-hole roots, and
    16edges into the hole become edges to the sole variable.
    17
    18Recomposition takes a separate copy of every piece, redirects variable
    19edges to a fresh hole, restores its initial and root marks, and restores
    20its self-loops. Unreachable vertices are removed after recomposition.
    21The resulting set-system covers the original context and is therefore
    22unfold-equivalent to it.
    23
    24This records explicitly the boundary information omitted by the literal
    25construction preceding `lemma:context-decomposition` in Section 2.8 of
    26arXiv:2407.12677v6. The pieces are presented over the extended alphabet,
    27but no piece contains a vertex labelled by the hole. Presentations retain
    28unreachable vertices until the final restriction.
    29-/
    30
    31namespace Lax369799.ContextDecomposition
    32open RankedSystems Morphisms Flattening
    33
    34noncomputable def holeVertex {A : RankedSet} {k : ℕ} (C : SetContext A k 0) :
    35 C.system.Vertex := Classical.choose C.one_hole
    36
    37abbrev BodyVertex {A : RankedSet} {k : ℕ} (C : SetContext A k 0) :=
    38 {v : C.system.Vertex // v ≠ holeVertex C}
    39
    40structure Boundary (k : ℕ) where
    41 initial : Prop
    42 root : Prop
    43 loops : Set (Fin k)
    44
    45noncomputable 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
    50noncomputable 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
    65abbrev 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. -/
    68def 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
    102noncomputable 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
    107axiom 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
    110axiom decomposition_cover {A : RankedSet} {k : ℕ} (C : SetContext A k 0) :
    111 UnfoldsTo C.system (recompose C)
    112
    113axiom decomposition_equivalence {A : RankedSet} {k : ℕ} (C : SetContext A k 0) :
    114 UnfoldEquivalent C.system (recompose C)
    115
    116end Lax369799.ContextDecomposition
    117
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…