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

Derived terms

Lax149335.DerivedTerms · concepts/Lax149335/DerivedTerms.lean · lax-149335

definition

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

    Definition

    The following terms are derived from the atomic functions and combinators of Definition 3.1. They are used to state the axioms of Section 4 and the results of the completeness proof.

    • The unique term A→1A \to 1, co-pairing ⟨f1,f2⟩=(f1+f2);codiag\langle f_1, f_2 \rangle = (f_1 + f_2) \mathbin{;} \mathsf{codiag}, commutativity and associativity of co-products.
    • The list notation of Section 4.6: the empty list [ ]:1→A∗[\,] : 1 \to A^*, prepend:A×A∗→A∗\mathsf{prepend} : A \times A^* \to A^*, append:A∗×A→A∗\mathsf{append} : A^* \times A \to A^*, pure:A→A∗\mathsf{pure} : A \to A^*, binconcat:A∗×A∗→A∗\mathsf{binconcat} : A^* \times A^* \to A^*, the homomorphism combinator hom f=f∗;concat\mathrm{hom}\, f = f^* \mathbin{;} \mathsf{concat}, and the concatenation f⊙g=(f×g);binconcatf \odot g = (f \times g) \mathbin{;} \mathsf{binconcat} of two terms with list outputs.
    • The inverses of distributivity, undistL\mathsf{undistL} and undistR\mathsf{undistR} (Section 4.4).
    • Definition 5.1 (Value). A value is a term of type 1→A1 \to A. For a list value ww, the terms w⋅fw \cdot f and f⋅wf \cdot w prepend or append the output of ww to the output of ff (Section 5.2), and headw:A∗→A\mathsf{head}_w : A^* \to A returns the first element of a list, or the output of ww for the empty list.
    • Concatenation maps (Section 5.1). For a type constructor FF with one parameter, built from the parameter, 11, ×\times, ++ and (−)∗(-)^*, the concatenation map F(A)↣A∗F(A) \rightarrowtail A^* lists all the elements of AA occurring in the input, from left to right. Similarly for type constructors with two parameters, with outputs in (A+B)∗(A + B)^*. In particular, unsplit:A∗×(B×A∗)∗→(A+B)∗\mathsf{unsplit} : A^* \times (B \times A^*)^* \to (A + B)^* is a concatenation map.
    • The terms shift:(A×B)∗→1+A×(B×A)∗×B\mathsf{shift} : (A \times B)^* \to 1 + A \times (B \times A)^* \times B and unshift\mathsf{unshift} of Table 1.
    • The inverse unpref\mathsf{unpref} of group prefix multiplication (Section 4.4), which maps [(a1,g1),…,(an,gn)][(a_1, g_1), \ldots, (a_n, g_n)] to [(a1,g0−1g1),…,(an,gn−1−1gn)][(a_1, g_0^{-1} g_1), \ldots, (a_n, g_{n-1}^{-1} g_n)], where g0g_0 is the group identity.
    Concept map
    3 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Lax149335.Terms
    2
    3/-!
    4---
    5title: Derived terms
    6type: definition
    7---
    8The following terms are derived from the atomic functions and combinators of
    9Definition 3.1. They are used to state the axioms of Section 4 and the results of the
    10completeness proof.
    11
    12- The unique term A→1A \to 1, co-pairing ⟨f1,f2⟩=(f1+f2);codiag\langle f_1, f_2 \rangle = (f_1 + f_2) \mathbin{;} \mathsf{codiag}
    13, commutativity and associativity of co-products.
    14- The list notation of Section 4.6: the empty list [ ]:1→A∗[\,] : 1 \to A^*, prepend:A×A∗→A∗\mathsf{prepend} : A \times A^* \to A^*
    15, append:A∗×A→A∗\mathsf{append} : A^* \times A \to A^*, pure:A→A∗\mathsf{pure} : A \to A^*
    16, binconcat:A∗×A∗→A∗\mathsf{binconcat} : A^* \times A^* \to A^*, the homomorphism combinator
    17 hom f=f∗;concat\mathrm{hom}\, f = f^* \mathbin{;} \mathsf{concat}, and the concatenation
    18 f⊙g=(f×g);binconcatf \odot g = (f \times g) \mathbin{;} \mathsf{binconcat} of two terms with list outputs.
    19- The inverses of distributivity, undistL\mathsf{undistL} and undistR\mathsf{undistR} (Section 4.4).
    20- **Definition 5.1 (Value).** A *value* is a term of type 1→A1 \to A. For a list value ww,
    21 the terms w⋅fw \cdot f and f⋅wf \cdot w prepend or append the output of ww to the output
    22 of ff (Section 5.2), and headw:A∗→A\mathsf{head}_w : A^* \to A returns the first element of a
    23 list, or the output of ww for the empty list.
    24- *Concatenation maps* (Section 5.1). For a type constructor FF with one parameter, built
    25 from the parameter, 11, ×\times, ++ and (−)∗(-)^*, the concatenation map
    26 F(A)↣A∗F(A) \rightarrowtail A^* lists all the elements of AA occurring in the input, from left
    27 to right. Similarly for type constructors with two parameters, with outputs in
    28 (A+B)∗(A + B)^*. In particular, unsplit:A∗×(B×A∗)∗→(A+B)∗\mathsf{unsplit} : A^* \times (B \times A^*)^* \to (A + B)^*
    29 is a concatenation map.
    30- The terms shift:(A×B)∗→1+A×(B×A)∗×B\mathsf{shift} : (A \times B)^* \to 1 + A \times (B \times A)^* \times B and
    31 unshift\mathsf{unshift} of Table 1.
    32- The inverse unpref\mathsf{unpref} of group prefix multiplication (Section 4.4), which maps
    33 [(a1,g1),…,(an,gn)][(a_1, g_1), \ldots, (a_n, g_n)] to [(a1,g0−1g1),…,(an,gn−1−1gn)][(a_1, g_0^{-1} g_1), \ldots, (a_n, g_{n-1}^{-1} g_n)],
    34 where g0g_0 is the group identity.
    35
    36# Formalization notes
    37
    38The paper only asserts that a term for unpref\mathsf{unpref} exists. Here it is defined
    39explicitly, following the appendix, by case analysis on the letters of the finite alphabet
    40that carries the group (`caseL`, `caseR`, `constFin`).
    41-/
    42
    43namespace Lax149335.DerivedTerms
    44
    45open Lax149335.Types Lax149335.Terms
    46
    47namespace Term
    48
    49open Lax149335.Terms.Term
    50
    51/-- The unique function into the unit type, `A → 1`. -/
    52def toUnit (A : Ty) : Term A Ty.unit := unitL A ⨟ fst Ty.unit A
    53
    54/-- Co-pairing, a derived combinator: `either f₁ f₂ = (f₁ + f₂); codiag`. -/
    55def either {A₁ A₂ B : Ty} (f₁ : Term A₁ B) (f₂ : Term A₂ B) : Term (A₁ ⊕' A₂) B :=
    56 sumF f₁ f₂ ⨟ codiag B
    57
    58/-- Commutativity of the co-product, a derived term. -/
    59def comm (A B : Ty) : Term (A ⊕' B) (B ⊕' A) := either (inr B A) (inl B A)
    60
    61/-- Associativity of the co-product, from left to right. -/
    62def sumAssocR (A B C : Ty) : Term ((A ⊕' B) ⊕' C) (A ⊕' (B ⊕' C)) :=
    63 either (either (inl A (B ⊕' C)) (inl B C ⨟ inr A (B ⊕' C))) (inr B C ⨟ inr A (B ⊕' C))
    64
    65/-- Associativity of the co-product, from right to left. -/
    66def sumAssocL (A B C : Ty) : Term (A ⊕' (B ⊕' C)) ((A ⊕' B) ⊕' C) :=
    67 either (inl A B ⨟ inl (A ⊕' B) C)
    68 (either (inr A B ⨟ inl (A ⊕' B) C) (inr (A ⊕' B) C))
    69
    70/-- The empty list `[] : 1 → A*`, defined as `Left; cons`. -/
    71def nilT (A : Ty) : Term Ty.unit A⋆ := inl Ty.unit (A ⊗ A⋆) ⨟ cons A
    72
    73/-- `prepend : A × A* → A*`, defined as `Right; cons`. -/
    74def prepend (A : Ty) : Term (A ⊗ A⋆) A⋆ := inr Ty.unit (A ⊗ A⋆) ⨟ cons A
    75
    76/-- `append : A* × A → A*`, defined as `Right; snoc`. -/
    77def append (A : Ty) : Term (A⋆ ⊗ A) A⋆ := inr Ty.unit (A⋆ ⊗ A) ⨟ snoc A
    78
    79/-- `pure : A → A*`, defined as `(id,1); id × []; prepend`. -/
    80def pureT (A : Ty) : Term A A⋆ :=
    81 unitR A ⨟ prodF (Term.id A) (nilT A) ⨟ prepend A
    82
    83/-- `binconcat : A* × A* → A*`, defined as `(id × pure); prepend; concat`. -/
    84def binconcat (A : Ty) : Term (A⋆ ⊗ A⋆) A⋆ :=
    85 prodF (Term.id A⋆) (pureT A⋆) ⨟ prepend A⋆ ⨟ concat A
    86
    87/-- The homomorphism combinator `hom f = f*; concat`. -/
    88def homT {A B : Ty} (f : Term A B⋆) : Term A⋆ B⋆ := listF f ⨟ concat B
    89
    90/-- Concatenation of two functions with list outputs, `f ⊙ g = (f × g); binconcat`. -/
    91def fdot {A₁ A₂ B : Ty} (f : Term A₁ B⋆) (g : Term A₂ B⋆) : Term (A₁ ⊗ A₂) B⋆ :=
    92 prodF f g ⨟ binconcat B
    93
    94/-- Notation `f ⊙ g` for the concatenation of two terms with list outputs. -/
    95infixl:65 " ⊙ " => Term.fdot
    96
    97/-- The inverse of distributivity on the right,
    98`undistR = either (id × Left) (id × Right)`. -/
    99def undistR (A B C : Ty) : Term ((A ⊗ B) ⊕' (A ⊗ C)) (A ⊗ (B ⊕' C)) :=
    100 either (prodF (Term.id A) (inl B C)) (prodF (Term.id A) (inr B C))
    101
    102/-- The inverse of distributivity on the left. -/
    103def undistL (A B C : Ty) : Term ((A ⊗ C) ⊕' (B ⊗ C)) ((A ⊕' B) ⊗ C) :=
    104 either (prodF (inl A B) (Term.id C)) (prodF (inr A B) (Term.id C))
    105
    106-- Values and concatenation with values (Section 5.2)
    107
    108/-- **Definition 5.1 (Value).** A value is a term of type `1 → A`. -/
    109abbrev Value (A : Ty) : Type := Term Ty.unit A
    110
    111/-- Pairing a value on the left with an arbitrary term: `(v,f) = (1,id); (v × f)`. -/
    112def pairL {A B C : Ty} (v : Value C) (f : Term A B) : Term A (C ⊗ B) :=
    113 unitL A ⨟ prodF v f
    114
    115/-- Pairing a value on the right with an arbitrary term: `(f,v) = (id,1); (f × v)`. -/
    116def pairR {A B C : Ty} (f : Term A B) (v : Value C) : Term A (B ⊗ C) :=
    117 unitR A ⨟ prodF f v
    118
    119/-- Concatenation of a list value on the left with a term with list outputs, `w · f`. -/
    120def dotL {A B : Ty} (w : Value B⋆) (f : Term A B⋆) : Term A B⋆ :=
    121 pairL w f ⨟ binconcat B
    122
    123/-- Concatenation of a term with list outputs with a list value on the right, `f · w`. -/
    124def dotR {A B : Ty} (f : Term A B⋆) (w : Value B⋆) : Term A B⋆ :=
    125 pairR f w ⨟ binconcat B
    126
    127/-- The singleton list value `[v] = v; pure`. -/
    128def sing {A : Ty} (v : Value A) : Value A⋆ := v ⨟ pureT A
    129
    130/-- The *head term for `w`*: the first element of a list, or the value `w` if the list is
    131empty. -/
    132def headT {A : Ty} (w : Value A) : Term A⋆ A :=
    133 uncons A ⨟ either w (fst A A⋆)
    134
    135-- Concatenation maps (Section 5.1)
    136
    137/-- Type constructors with one parameter, used to define concatenation maps. -/
    138inductive TyF : Type
    139 /-- The parameter itself. -/
    140 | param : TyF
    141 /-- The unit type. -/
    142 | unit : TyF
    143 /-- Product of two type constructors. -/
    144 | prod : TyF → TyF → TyF
    145 /-- Co-product of two type constructors. -/
    146 | sum : TyF → TyF → TyF
    147 /-- List of a type constructor. -/
    148 | list : TyF → TyF
    149
    150/-- The type `F(A)` obtained by substituting the type `A` for the parameter of `F`. -/
    151def TyF.app : TyF → Ty → Ty
    152 | .param, A => A
    153 | .unit, _ => Ty.unit
    154 | .prod F G, A => (F.app A) ⊗ (G.app A)
    155 | .sum F G, A => (F.app A) ⊕' (G.app A)
    156 | .list F, A => (F.app A)⋆
    157
    158/-- **Concatenation maps** (Section 5.1): the term `F(A) ↣ A*` that concatenates all the
    159elements of the input into a single list, defined by induction on `F`. -/
    160def TyF.concatMap : (F : TyF) → (A : Ty) → Term (F.app A) A⋆
    161 | .param, A => pureT A
    162 | .unit, A => nilT A
    163 | .prod F G, A => (F.concatMap A) ⊙ (G.concatMap A)
    164 | .sum F G, A => either (F.concatMap A) (G.concatMap A)
    165 | .list F, A => homT (F.concatMap A)
    166
    167/-- The type constructor `A ↦ Aᵏ`, the `k`-fold product of the parameter with itself. -/
    168def TyF.pow : ℕ → TyF
    169 | 0 => .unit
    170 | (k + 1) => .prod .param (TyF.pow k)
    171
    172/-- The type constructor `A ↦ A⁰ + A¹ + ⋯ + Aᵏ`, i.e. `A^{<k+1}` in the notation of the
    173paper. -/
    174def TyF.lt : ℕ → TyF
    175 | 0 => TyF.pow 0
    176 | (k + 1) => .sum (TyF.lt k) (TyF.pow (k + 1))
    177
    178/-- Type constructors with two parameters, used for the concatenation maps with values in
    179`(A + B)*` that occur in Axiom 15 and in the definition of `unsplit`. -/
    180inductive TyF2 : Type
    181 /-- The first parameter. -/
    182 | p1 : TyF2
    183 /-- The second parameter. -/
    184 | p2 : TyF2
    185 /-- The unit type. -/
    186 | unit : TyF2
    187 /-- Product of two type constructors. -/
    188 | prod : TyF2 → TyF2 → TyF2
    189 /-- Co-product of two type constructors. -/
    190 | sum : TyF2 → TyF2 → TyF2
    191 /-- List of a type constructor. -/
    192 | list : TyF2 → TyF2
    193
    194/-- The type `F(A,B)`. -/
    195def TyF2.app : TyF2 → Ty → Ty → Ty
    196 | .p1, A, _ => A
    197 | .p2, _, B => B
    198 | .unit, _, _ => Ty.unit
    199 | .prod F G, A, B => (F.app A B) ⊗ (G.app A B)
    200 | .sum F G, A, B => (F.app A B) ⊕' (G.app A B)
    201 | .list F, A, B => (F.app A B)⋆
    202
    203/-- The concatenation map `F(A,B) ↣ (A+B)*`, which injects the elements of `A` and of `B`
    204into the co-product `A + B` and concatenates all of them. -/
    205def TyF2.concatMap : (F : TyF2) → (A B : Ty) → Term (F.app A B) (A ⊕' B)⋆
    206 | .p1, A, B => inl A B ⨟ pureT (A ⊕' B)
    207 | .p2, A, B => inr A B ⨟ pureT (A ⊕' B)
    208 | .unit, A, B => nilT (A ⊕' B)
    209 | .prod F G, A, B => (F.concatMap A B) ⊙ (G.concatMap A B)
    210 | .sum F G, A, B => either (F.concatMap A B) (G.concatMap A B)
    211 | .list F, A, B => homT (F.concatMap A B)
    212
    213/-- The inverse of `split`: it injects `A` and `B` into the co-product `A + B` and then
    214concatenates all resulting lists. -/
    215def unsplit (A B : Ty) : Term (A⋆ ⊗ (B ⊗ A⋆)⋆) (A ⊕' B)⋆ :=
    216 TyF2.concatMap (.prod (.list .p1) (.list (.prod .p2 (.list .p1)))) A B
    217
    218-- The terms `shift` and `unshift` of Table 1
    219
    220/-- The lift `shift : (A × B)* ⊸ 1 + A × (B × A)* × B`, obtained by composing `uncons`,
    221`assocR` and `shiftL`. -/
    222def shift (A B : Ty) : Term ((A ⊗ B)⋆) (Ty.unit ⊕' (A ⊗ ((B ⊗ A)⋆ ⊗ B))) :=
    223 uncons (A ⊗ B) ⨟
    224 sumF (Term.id Ty.unit) (assocR A B ((A ⊗ B)⋆) ⨟ prodF (Term.id A) (shiftL B A))
    225
    226/-- The drop `unshift : 1 + A × (B × A)* × B ⇒ (A × B)*`, the inverse of `shift`. -/
    227def unshift (A B : Ty) : Term (Ty.unit ⊕' (A ⊗ ((B ⊗ A)⋆ ⊗ B))) ((A ⊗ B)⋆) :=
    228 sumF (Term.id Ty.unit) (prodF (Term.id A) (shiftR B A) ⨟ assocL A B ((A ⊗ B)⋆)) ⨟ cons (A ⊗ B)
    229
    230-- Terms for finite alphabets and the inverse of the group prefix operation
    231
    232/-- The value `1 → 1 + ⋯ + 1` that picks out a given letter of a finite alphabet. -/
    233def constFin : {n : ℕ} → ⟦Ty.finAlph n⟧ → Value (Ty.finAlph n)
    234 | 0, _ => Term.id Ty.unit
    235 | (_ + 1), .inl _ => inl Ty.unit _
    236 | (_ + 1), .inr g => constFin g ⨟ inr Ty.unit _
    237
    238/-- Case analysis on a letter of a finite alphabet that appears as the right component of a
    239product; it is derived using distributivity and co-pairing. -/
    240def caseR : {n : ℕ} → {A B : Ty} → (⟦Ty.finAlph n⟧ → Term A B) → Term (A ⊗ Ty.finAlph n) B
    241 | 0, A, _, t => fst A Ty.unit ⨟ t ()
    242 | (n + 1), A, _, t =>
    243 distR A Ty.unit (Ty.finAlph n) ⨟
    244 either (fst A Ty.unit ⨟ t (.inl ())) (caseR (fun g => t (.inr g)))
    245
    246/-- Case analysis on a letter of a finite alphabet that appears as the left component of a
    247product. -/
    248def caseL : {n : ℕ} → {A B : Ty} → (⟦Ty.finAlph n⟧ → Term A B) → Term (Ty.finAlph n ⊗ A) B
    249 | 0, A, _, t => snd Ty.unit A ⨟ t ()
    250 | (n + 1), A, _, t =>
    251 distL Ty.unit (Ty.finAlph n) A ⨟
    252 either (snd Ty.unit A ⨟ t (.inl ())) (caseL (fun g => t (.inr g)))
    253
    254/-- The term `(a,g) ↦ (g,(a,g))`, admissible because the group is a finite alphabet. -/
    255def grepeat (A : Ty) (n : ℕ) : Term (A ⊗ Ty.finAlph n) (Ty.finAlph n ⊗ (A ⊗ Ty.finAlph n)) :=
    256 caseR (fun g => pairL (constFin g) (pairR (Term.id A) (constFin g)))
    257
    258/-- The term `(h,(g,a)) ↦ (a, h⁻¹ · g)`, admissible because the group is a finite
    259alphabet. -/
    260def gdiv (A : Ty) {n : ℕ} (G : Group ⟦Ty.finAlph n⟧) :
    261 Term (Ty.finAlph n ⊗ (Ty.finAlph n ⊗ A)) (A ⊗ Ty.finAlph n) :=
    262 caseL (fun h => caseL (fun g => pairR (Term.id A) (constFin (letI := G; h⁻¹ * g))))
    263
    264/-- The unprefixing operation, the inverse of the group prefix multiplication:
    265`[(a₁,g₁),…,(aₙ,gₙ)] ↦ [(a₁,g₀⁻¹g₁),(a₂,g₁⁻¹g₂),…,(aₙ,gₙ₋₁⁻¹gₙ)]`, where `g₀` is the group
    266identity. -/
    267def unpref (A : Ty) {n : ℕ} (G : Group ⟦Ty.finAlph n⟧) :
    268 Term ((A ⊗ Ty.finAlph n)⋆) ((A ⊗ Ty.finAlph n)⋆) :=
    269 listF (grepeat A n) ⨟
    270 listF (assocL (Ty.finAlph n) A (Ty.finAlph n)) ⨟
    271 pairL (constFin (letI := G; (1 : ⟦Ty.finAlph n⟧))) (Term.id _) ⨟
    272 shiftL (Ty.finAlph n) (Ty.finAlph n ⊗ A) ⨟
    273 fst _ _ ⨟ listF (gdiv A G)
    274
    275end Term
    276
    277end Lax149335.DerivedTerms
    278
    Formalization notes

    The paper only asserts that a term for unpref\mathsf{unpref} exists. Here it is defined explicitly, following the appendix, by case analysis on the letters of the finite alphabet that carries the group (caseLcaseL, caseRcaseR, constFinconstFin).

    Discussion

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

    Loading discussion…