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

Algebras on fully supported systems

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

    Evaluation is defined on the systems of Definition 6, with every output reachable. Restriction of an algebra on arbitrary deterministic systems preserves its algebra laws, unfolding invariance, and recognition. Evaluation commutes with surjective output renaming.

    Concept map
    10 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.SupportedSystems
    2import Lax369799.Algebras
    3
    4/-!
    5---
    6title: Algebras on fully supported systems
    7type: theorem
    8---
    9Evaluation is defined on the systems of Definition 6, with every output
    10reachable. Restriction of an algebra on arbitrary deterministic systems
    11preserves its algebra laws, unfolding invariance, and recognition. Evaluation commutes with surjective output renaming.
    12-/
    13
    14namespace Lax369799.SupportedAlgebras
    15open RankedSystems (RankedSet RankedMap RankwiseFinite)
    16open SupportedSystems Morphisms
    17
    18structure Algebra (A : RankedSet) where
    19 eval : ∀ n, System A n → A n
    20 isomorphic : ∀ n (S T : System A n), Isomorphic S.val.val T.val.val → eval n S = eval n T
    21 unit : ∀ n (a : A n), eval n (atomic a) = a
    22 associative : ∀ n (S : System (System A) n) (T : System A n),
    23 Flattening.SystemFlattening (forgetPattern S) T.val →
    24 eval n (relabel eval S) = eval n T
    25
    26def UnfoldInvariant {A : RankedSet} (E : Algebra A) : Prop :=
    27 ∀ n (S T : System A n), UnfoldEquivalent S.val.val T.val.val → E.eval n S = E.eval n T
    28
    29def Recognizes {A B : RankedSet} (E : Algebra B) (η : RankedMap A B)
    30 (F : Set (B 0)) (L : Algebras.Language A) : Prop :=
    31 ∀ T : System A 0, T.val ∈ L ↔ E.eval 0 (relabel η T) ∈ F
    32
    33def Recognizable {A : RankedSet} (L : Algebras.Language A) : Prop :=
    34 ∃ (B : RankedSet) (E : Algebra B) (η : RankedMap A B) (F : Set (B 0)),
    35 RankwiseFinite B ∧ Recognizes E η F L
    36
    37def restrict {A : RankedSet} (E : Algebras.Algebra A) : Algebra A where
    38 eval := fun n S => E.eval n S.val
    39 isomorphic := fun n S T h => E.isomorphic n S.val T.val h
    40 unit := E.unit
    41 associative := fun n S T h => E.associative n (forgetPattern S) T.val h
    42
    43axiom restrict_invariant {A : RankedSet} (E : Algebras.Algebra A)
    44 (hE : Algebras.UnfoldInvariant E) : UnfoldInvariant (restrict E)
    45
    46axiom legacy_recognizable {A : RankedSet} (L : Algebras.Language A)
    47 (hL : Algebras.Recognizable L) : Recognizable L
    48
    49axiom rename_evaluation {A : RankedSet} (E : Algebra A)
    50 {m n : ℕ} (σ : Fin m → Fin n) (hσ : Function.Surjective σ) (S : System A m) :
    51 E.eval n (rename σ hσ S) = E.eval n (rename σ hσ (atomic (E.eval m S)))
    52
    53end Lax369799.SupportedAlgebras
    54
    55
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…