LEAN 类型理论之注解（Annotations of LEAN Type Theory）—— 归纳类型（Inductive Type）的使用规则（Elimination Rule）

        使用规则（Elimination Rule），也叫解构规则（Destruction Rule），与构建规则（Introduction Rule），也叫建构规则（Construction Rule），相对应。

        即，构建规则（Introduction Rule），定义了该类型的正规元素是如何构建出来的；而，使用规则（Elimination Rule），定义了该类型的正规元素是如何被使用的。可以看作，生产（Produce）、消费（consume）关系。

        在定义一个类型，包括归纳类型（Inductive Type），需要四种规则：

1. 类型构建规则（Type Formation Rule），即该类型需要依赖哪些条件来形成。

        如自然数 Nat，就不需要依赖，自成类型；而 流类型 （Stream α）则需要依赖一个 α 类型，来形成最终的 α 流类型，如 α = Int，有 Stream Nat，即自然数流类型，因此，在不考虑类型宇宙多态的情况下，Stream: Type -> Type。

2. 类型元素的构建规则（Introduction Rule），用于构建该类型的正规元素（Canonical Element）。

3. 类型元素的使用规则（Elimination Rule），用与使用该类型的正规元素（Canonical Element）。

4. 类型元素的相等规则（Equality Rule），用于证明其构建的正规元素可以正确被使用。

        在《归纳类型（Inductive Type）的定义》 中，已经介绍归纳类型（Inductive Type）的前两个种规则：

1. 类型构建规则（Type Formation Rule）:

2. 类型元素的构建规则（Introduction Rule）:

        此文将介绍其使用规则（Elimination Rule），即，其递归函数（recursor）的定义:

这里看起来比较复杂，由此，LEAN类型理论给出了一个简化版，即 自然数 Nat 的递归函数的定义：

        此处有：

        1. F ≡ Type

        2. K ≡  zₙ: t + Sₙ: t → t  ≡（ zero : t ） + （ succ (n : t ) : t  ）

        3. P ≡ ℕ ≡ Nat

        4. κ ≡ ℕ → Uᵤ

        5. ∀C:κ ≡ ∀(C: ℕ → Uᵤ)

        6. ∀e::ε ≡ (C:zₙ) → (∀x:ℕ.C x → C (Sₙ x))

        7. ∀a::α. ∀z: P a ≡ ∀n:ℕ （因为 ℕ 没有依赖，因此∀a::α.  不需要）

        8. C a z ≡ C n

        另记：

        1. ∀C:κ ≡ ∀(C: ℕ → Uᵤ) 中的 C:κ ，为类型为 κ 的动机函数（motive）。

        2. ∀e::ε ≡ (C:zₙ) → (∀x:ℕ.C x → C (Sₙ x))中的 e::ε ，为次要函数组（minors），与构建函数一一对应，即，每个构建函数对应的使用函数（eliminator for each constructor）。

        3. ∀a::α. ∀z: P a ≡ ∀n:ℕ 中的 z: P a，为主要作用对象（major），是该使用规则（Elimination），或递归函数（Recursor），的作用对象。该作用对象由其归纳类型的构建规则（Introduction rules），即构建函数（constructor），所产生，因此该作用对象的类型为 ∀a::α. P a 。

        这样一对照来看后，对于归纳类型的使用规则就有很好的理解了。

        总结来说，从归纳类型（Inductive Type）的归纳原理（Inductive Principle ）出发理解，其使用函数（Elimination Rules），主旨是基于其前值（predecessor）、前结果（前结果由使用函数作用于前值得出） 得现结果。每个构建函数（constructor）都有对应的使用函数（eliminator），因此，使用函数作用在一个归纳类型的值（正规元素）时，可以逐步递归，基于最基本的值，通过一步步使用对应使用函数（eliminator），来求得最终对应的结果。

        以下列出，LEAN的正式定义及相关注解（供参考）：

        其中：

        另有：

 注解：

        1. P 指示 正在定义的归纳类型的本身，如 Nat。

        2. K 指示 P 中 一系列的构建函数，即 K 是 P 的归纳规范（Inductive Specification）

        3. c 为构建函数（constructor）。

        4. ∀b::β 为构建函数的所有输入参数，包括递归参数（recursive arguments）和无递归参数（non-recursive arguments）。

        5.  t p[b] 为 构建函数的输出类型（Target Type / Output Type）。

        6. p[b] :: α，即基于 b::β （所有输入参数）中的无递归参数（non-recursive arguments），可以推断出， 正在定义的归纳类型的所有依赖（类型或值），即 p : β → α。

        7. ∀b::β.∀v::δ.C p[b] (c b) ，为每个构建函数对应的使用函数的类型（Type of eliminator for each constructor）。

        8. u::γ ⊆ b::β，指的是，构建函数的所有输入递归参数（recursive arguments）。

        9. γᵢ = ∀x::ξᵢ. P πᵢ[b, x]，指的是，构建函数中第 i 个递归参数的类型。其中，πᵢ[b, x] ::  α，即以来 b::β （所有输入参数）以及该归纳类型的前值（predecessor，x::ξ）。

        10. v::δ ，指的是前结果，即动机函数C 作用于 作用对象（major）的前值（predecessor）的结果，可依赖的多个前结果，如 斐波那契函数（Fibonacci ）。

        11. （uᵢ x）,指的是，对于第 i 个递归参数所需要的前值 （uᵢ x），其中，uᵢ 为 x 给定其宇宙层次。

              口