Normalisation of values
Lax149335.ValueNormalisation · concepts/Lax149335/ValueNormalisation.lean · lax-149335
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Lemma
Lemma 5.3 (Normalisation of values). Every value is provably equivalent to a value built from the identity on using the following constructors: and for values of co-products, for values of products, and , and for values of list types.
Concept map
Lean source view on GitHub
| 1 | import Lax149335.EquationalTheory |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Normalisation of values |
| 6 | type: lemma |
| 7 | --- |
| 8 | **Lemma 5.3 (Normalisation of values).** Every value is provably equivalent to a |
| 9 | value built from the identity on using the following constructors: |
| 10 | and for values of co-products, for |
| 11 | values of products, and , and for values of list types. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax149335.ValueNormalisation |
| 15 | |
| 16 | open Lax149335.Types Lax149335.Terms Lax149335.Terms.Term Lax149335.DerivedTerms |
| 17 | Lax149335.DerivedTerms.Term Lax149335.EquationalTheory |
| 18 | |
| 19 | /-- Values in normal form. -/ |
| 20 | inductive NormalValue : {A : Ty} → Value A → Prop |
| 21 | /-- The identity on the unit type. -/ |
| 22 | | id : NormalValue (Term.id Ty.unit) |
| 23 | /-- A co-product value `v; Left`. -/ |
| 24 | | inl {A B : Ty} {v : Value A} : NormalValue v → NormalValue (v ⨟ Term.inl A B) |
| 25 | /-- A co-product value `v; Right`. -/ |
| 26 | | inr {A B : Ty} {v : Value B} : NormalValue v → NormalValue (v ⨟ Term.inr A B) |
| 27 | /-- A product value `(v, w)`. -/ |
| 28 | | pair {A B : Ty} {v : Value A} {w : Value B} : |
| 29 | NormalValue v → NormalValue w → NormalValue (pairR v w) |
| 30 | /-- The concatenation `v · w` of two list values. -/ |
| 31 | | dot {A : Ty} {v w : Value A⋆} : NormalValue v → NormalValue w → NormalValue (dotL v w) |
| 32 | /-- A singleton list value `[v]`. -/ |
| 33 | | sing {A : Ty} {v : Value A} : NormalValue v → NormalValue (sing v) |
| 34 | /-- The empty list value `[]`. -/ |
| 35 | | nil {A : Ty} : NormalValue (nilT A) |
| 36 | |
| 37 | /-- **Lemma 5.3.** Every value is provably equivalent to a value in normal form. -/ |
| 38 | axiom normalisation_of_values {A : Ty} (v : Value A) : ∃ u : Value A, NormalValue u ∧ v ≡ₜ u |
| 39 | |
| 40 | end Lax149335.ValueNormalisation |
| 41 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments