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

Systems with all output variables reachable

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

    Definition 6 requires every vertex and every output variable to be reachable from the unique initial vertex. The earlier deterministic presentation interface already requires vertex reachability; full support adds occurrence of every variable edge. Relabelling and surjective renaming preserve this condition. Flattening fully supported systems retains all vertices and all output variables (Lemma 33). In rank zero, the support condition is vacuous.

    Concept map
    9 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.FlatteningTheorems
    3import Lax369799.Renaming
    4
    5/-!
    6---
    7title: Systems with all output variables reachable
    8type: theorem
    9---
    10Definition 6 requires every vertex and every output variable to be
    11reachable from the unique initial vertex. The earlier deterministic
    12presentation interface already requires vertex reachability; full support
    13adds occurrence of every variable edge. Relabelling and surjective
    14renaming preserve this condition. Flattening fully supported systems
    15retains all vertices and all output variables (Lemma 33). In rank zero,
    16the support condition is vacuous.
    17-/
    18
    19namespace Lax369799.SupportedSystems
    20open RankedSystems (RankedSet RankedMap)
    21open FinitePresentations
    22
    23def FullySupported {A : RankedSet} {n : ℕ} (S : RankedSystems.System A n) : Prop :=
    24 ∀ i : Fin n, ∃ v d, S.val.graph.edge v d (.inr i)
    25
    26abbrev System (A : RankedSet) (n : ℕ) := {S : RankedSystems.System A n // FullySupported S}
    27
    28def forget {A : RankedSet} : RankedMap (System A) (RankedSystems.System A) := fun _ S => S.val
    29
    30def relabel {A B : RankedSet} (f : RankedMap A B) {n : ℕ} (S : System A n) : System B n :=
    31 ⟨RankedSystems.relabelSystem f S.val, S.property⟩
    32
    33def atomic {A : RankedSet} {n : ℕ} (a : A n) : System A n :=
    34 ⟨RankedSystems.atomicSystem a, fun i => ⟨(0 : Fin 1), i.val, i, rfl, rfl⟩⟩
    35
    36def closedEquiv (A : RankedSet) : System A 0 ≃ RankedSystems.System A 0 where
    37 toFun := Subtype.val
    38 invFun := fun S => ⟨S, fun i => Fin.elim0 i⟩
    39 left_inv := fun _ => rfl
    40 right_inv := fun _ => rfl
    41
    42def rename {A : RankedSet} {m n : ℕ} (σ : Fin m → Fin n)
    43 (hσ : Function.Surjective σ) (S : System A m) : System A n :=
    44 ⟨Renaming.renameSystem σ S.val, fun j => by
    45 obtain ⟨i, rfl⟩ := hσ j
    46 obtain ⟨v, d, hd⟩ := S.property i
    47 exact ⟨v, d, .inr i, hd, rfl⟩⟩
    48
    49def pattern {A : RankedSet} {n : ℕ} (S : System (System A) n) :
    50 FiniteSystem (FiniteSystem A) n :=
    51 FinitePresentations.relabel (fun _ T => ofSetSystem T.val.val) (ofSetSystem S.val.val)
    52
    53def forgetPattern {A : RankedSet} {n : ℕ} (S : System (System A) n) :
    54 RankedSystems.System (RankedSystems.System A) n :=
    55 RankedSystems.relabelSystem forget S.val
    56
    57axiom flatten_reachable {A : RankedSet} {n : ℕ} (S : System (System A) n) :
    58 ∀ v, (flattenPresentation (pattern S).graph).Reachable v
    59
    60axiom flatten_system {A : RankedSet} {n : ℕ} (S : System (System A) n) :
    61 ∃ T : System A n, Flattening.SystemFlattening (forgetPattern S) T.val
    62
    63end Lax369799.SupportedSystems
    64
    Show ProofShow Proof

    Discussion

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

    Loading discussion…