Unary types preserving explicit choices
Lax369799.ChoicePreservingUnary · concepts/Lax369799/ChoicePreservingUnary.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Evidence
This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.
1 finite_branch_test proven
2 finite_types proven
3 word_preserves_choices proven
Lean source view on GitHub
| 1 | import Lax369799.FiniteBranchWords |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Unary types preserving explicit choices |
| 6 | type: theorem |
| 7 | --- |
| 8 | Selected unary types must preserve the binary choice operation on closed |
| 9 | continuations. This is a necessary restriction for exposing choices as |
| 10 | separate branch tests. It is not asserted of all unary algebra elements. |
| 11 | Finite words of such types preserve choices, and finite expressions built |
| 12 | from them can be tested path by path. Existence of suitable selected types |
| 13 | and extension to cyclic presentations are separate obligations. |
| 14 | -/ |
| 15 | namespace Lax369799.ChoicePreservingUnary |
| 16 | open RankedSystems (RankedSet) |
| 17 | open FiniteSyntacticAlgebra FiniteBranchWords |
| 18 | |
| 19 | def 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. -/ |
| 23 | def TypeSet {A : RankedSet} (E : Algebra A) := {b : A 1 // PreservesChoices E b} |
| 24 | |
| 25 | inductive 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 | |
| 30 | def 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 | |
| 35 | def 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 | |
| 40 | def 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 | |
| 45 | axiom 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 | |
| 49 | axiom 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 | |
| 54 | axiom finite_types {A : RankedSet} (E : Algebra A) [Finite (A 1)] : Finite (TypeSet E) |
| 55 | |
| 56 | end Lax369799.ChoicePreservingUnary |
| 57 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments