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

Root entries in substituted presentations

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

    To observe the roots of a substitution, give every outer vertex a separate starting copy whose inner roots become initial. Subsequent outer transitions go to ordinary copies, where inner initial vertices remain initial. Outer roots also start at their ordinary copies. All root marks in the expanded presentation are removed. This preserves root observations even at vertices that were unreachable in the original outer presentation.

    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 2 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax369799.FinitePresentations
    2import Lax369799.PresentationCovers
    3
    4/-!
    5---
    6title: Root entries in substituted presentations
    7type: theorem
    8---
    9To observe the roots of a substitution, give every outer vertex a separate
    10starting copy whose inner roots become initial. Subsequent outer transitions
    11go to ordinary copies, where inner initial vertices remain initial. Outer
    12roots also start at their ordinary copies. All root marks in the expanded
    13presentation are removed. This preserves root observations even at vertices
    14that were unreachable in the original outer presentation.
    15-/
    16namespace Lax369799.RootExpansion
    17open RankedSystems FinitePresentations
    18
    19def startAtRoots {A : RankedSet} {n : ℕ} {V : Type} (G : Presentation A n V) :
    20 Presentation A n V := { G with initial := G.root, root := ∅ }
    21
    22def component {A : RankedSet} {n : ℕ} (S : FiniteSystem A n) (start : Bool) : FiniteSystem A n where
    23 size := S.size
    24 graph := { S.graph with initial := if start then S.graph.root else S.graph.initial, root := ∅ }
    25
    26def pattern {A : RankedSet} {n : ℕ} {V : Type}
    27 (P : Presentation (FiniteSystem A) n V) : Presentation (FiniteSystem A) n (Bool × V) where
    28 label := fun v => ⟨(P.label v.2).1, component (Inner P v.2) v.1⟩
    29 initial := fun v => if v.1 then True else P.root v.2
    30 root := ∅
    31 edge := fun v d t => ∃ s, P.edge v.2 d s ∧ t = Sum.map (fun w => (false, w)) id s
    32 direction_valid := by rintro v d t ⟨s, hs, _⟩; exact P.direction_valid _ _ _ hs
    33
    34axiom expansion_cover {A : RankedSet} {n : ℕ} {V : Type}
    35 (P : Presentation (FiniteSystem A) n V) :
    36 Nonempty (PresentationCovers.Cover (flattenPresentation (pattern P))
    37 (startAtRoots (flattenPresentation P)))
    38
    39axiom expansion_folding {A : RankedSet} {n : ℕ} {V : Type}
    40 (P : Presentation (FiniteSystem A) n V) :
    41 ∃ f : PresentationCovers.Cover (flattenPresentation (pattern P))
    42 (startAtRoots (flattenPresentation P)), Function.Surjective f.toFun
    43
    44end Lax369799.RootExpansion
    45
    Show ProofShow Proof

    Discussion

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

    Loading discussion…