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

Variable exits of unary systems

Lax369799.UnarySystems · concepts/Lax369799/UnarySystems.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 deterministic system whose labels have rank at most one follows a single path from its initial vertex. Consequently all its variable exits use the same variable. This is the path property used in the characterization of deterministic algebra elements in Section 5.1.

    Concept map
    3 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.

    2 variable_decomposition proven

    Lean source view on GitHub

    1import Lax369799.Morphisms
    2import Mathlib.Data.Fintype.Prod
    3
    4/-!
    5---
    6title: Variable exits of unary systems
    7type: theorem
    8---
    9A deterministic system whose labels have rank at most one follows a single
    10path from its initial vertex. Consequently all its variable exits use the
    11same variable. This is the path property used in the characterization of
    12deterministic algebra elements in Section 5.1.
    13-/
    14namespace Lax369799.UnarySystems
    15open RankedSystems Morphisms
    16
    17axiom unique_exit {A : RankedSet} {n : ℕ} (S : System A n)
    18 (hS : ∀ v, (S.val.graph.label v).1 ≤ 1)
    19 {v w : S.val.Vertex} {d e : ℕ} {i j : Fin n}
    20 (hi : S.val.graph.edge v d (.inr i)) (hj : S.val.graph.edge w e (.inr j)) : i = j
    21
    22/-- One copy for each variable, retaining only exits to that variable. -/
    23def variablePieces {A : RankedSet} {n : ℕ} {V : Type} (G : Presentation A n V) :
    24 Presentation A n (Fin n × V) where
    25 label := fun v => G.label v.2
    26 initial := fun v => G.initial v.2
    27 root := fun v => G.root v.2
    28 edge := fun v d t => ∃ s, G.edge v.2 d s ∧
    29 (∀ i, s = .inr i → i = v.1) ∧ t = Sum.map (fun w => (v.1, w)) id s
    30 direction_valid := by rintro v d t ⟨s, hs, _, _⟩; exact G.direction_valid _ _ _ hs
    31
    32axiom variable_decomposition {A : RankedSet} {n : ℕ} (hn : 0 < n)
    33 {V : Type} [Fintype V] (G : Presentation A n V)
    34 (hG : ∀ v, (G.label v).1 ≤ 1) :
    35 YieldEquivalent (trim G) (trim (variablePieces G))
    36
    37end Lax369799.UnarySystems
    38
    Show ProofShow Proof

    Discussion

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

    Loading discussion…