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

Unary types preserving explicit choices

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

    Selected unary types must preserve the binary choice operation on closed continuations. This is a necessary restriction for exposing choices as separate branch tests. It is not asserted of all unary algebra elements. Finite words of such types preserve choices, and finite expressions built from them can be tested path by path. Existence of suitable selected types and extension to cyclic presentations are separate obligations.

    Concept map
    8 concepts; 8 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

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

    Lean source view on GitHub

    1import Lax369799.FiniteBranchWords
    2
    3/-!
    4---
    5title: Unary types preserving explicit choices
    6type: theorem
    7---
    8Selected unary types must preserve the binary choice operation on closed
    9continuations. This is a necessary restriction for exposing choices as
    10separate branch tests. It is not asserted of all unary algebra elements.
    11Finite words of such types preserve choices, and finite expressions built
    12from them can be tested path by path. Existence of suitable selected types
    13and extension to cyclic presentations are separate obligations.
    14-/
    15namespace Lax369799.ChoicePreservingUnary
    16open RankedSystems (RankedSet)
    17open FiniteSyntacticAlgebra FiniteBranchWords
    18
    19def PreservesChoices {A : RankedSet} (E : Algebra A) (b : A 1) : Prop :=
    20 ∀ c d : A 0, act E b (sumValue E c d) = sumValue E (act E b c) (act E b d)
    21
    22/-- The eligible unary types, retaining their proof of choice preservation. -/
    23def TypeSet {A : RankedSet} (E : Algebra A) := {b : A 1 // PreservesChoices E b}
    24
    25inductive Expression (A : RankedSet) where
    26 | leaf : A 0 → Expression A
    27 | step : A 1 → Expression A → Expression A
    28 | choice : Expression A → Expression A → Expression A
    29
    30def Expression.eval {A : RankedSet} (E : Algebra A) : Expression A → A 0
    31 | .leaf a => a
    32 | .step b t => act E b (t.eval E)
    33 | .choice s t => sumValue E (s.eval E) (t.eval E)
    34
    35def Expression.Eligible {A : RankedSet} (E : Algebra A) : Expression A → Prop
    36 | .leaf _ => True
    37 | .step b t => PreservesChoices E b ∧ t.Eligible E
    38 | .choice s t => s.Eligible E ∧ t.Eligible E
    39
    40def Expression.paths {A : RankedSet} : Expression A → List (List (A 1) × A 0)
    41 | .leaf a => [([], a)]
    42 | .step b t => t.paths.map (fun p => (b :: p.1, p.2))
    43 | .choice s t => s.paths ++ t.paths
    44
    45axiom word_preserves_choices {A : RankedSet} (E : Algebra A)
    46 (w : List (A 1)) (hw : ∀ b ∈ w, PreservesChoices E b) (c d : A 0) :
    47 value E w (sumValue E c d) = sumValue E (value E w c) (value E w d)
    48
    49axiom finite_branch_test {A : RankedSet} (E : Algebra A) (F : Set (A 0))
    50 (hF : ∀ c d, sumValue E c d ∈ F ↔ c ∈ F ∧ d ∈ F)
    51 (t : Expression A) (ht : t.Eligible E) :
    52 t.eval E ∈ F ↔ ∀ p ∈ t.paths, value E p.1 p.2 ∈ F
    53
    54axiom finite_types {A : RankedSet} (E : Algebra A) [Finite (A 1)] : Finite (TypeSet E)
    55
    56end Lax369799.ChoicePreservingUnary
    57
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…