您的位置:首页 > 房产 > 建筑 > LEAN 赋型唯一性(Unique Typing)之 κ 简化 (κ reduction)

LEAN 赋型唯一性(Unique Typing)之 κ 简化 (κ reduction)

2025/1/31 11:02:10 来源:https://blog.csdn.net/sinat_36821938/article/details/142204393  浏览:    关键词:LEAN 赋型唯一性(Unique Typing)之 κ 简化 (κ reduction)

        在《赋型唯一性的证明过程简介》 提及到,κ 简化 (κ reduction)概念的引入,是为了证明,在不考虑 证据不区分(Proof Irrelevance)的情况,表达式具备唯一常态(Unique normal form),这使得 Church-Rosser 定理 得以证明,从而证明 n-provability是定义上方向(Definitional Inversion),最终,证明 赋型唯一性(Unique Typing)。

一、简化规则回顾

        κ 简化 (κ reduction),可以简单地看作 β δ ζ ι 简化的统称。先回顾一下LEAN定义的简化规则,有:

β 简化(beta reduction):

δ 简化(Delta reduction):

ζ 简化(Zeta reduction):

 ι 简化(Iota reduction):

另有,不属于 K 简化的 η 简化,( Eta reduction):

二、简化规则的选择 与 rec 常态 (rec-normal form)

通过对相等类型(Equality Type)使用函数的简化,来体现LEAN是如何规范简化规则的选择的。有:

相等类型(Equality Type)定义:

        相等类型的使用函数(Recursor of Equality Type):

                其中:

                动机函数(Motive function) C : (a: α) → {eqₐ a} → Uᵤ

                次要函数组(Minors) C a:Uᵤ

                主要作用对象(major)∀b: a = b

                结果 C b:Uᵤ

        那么,对于 表达式

λh:a = a. recₐ₌ C e a h

        即,给入 a = a 的证明 h,输出结果 e。

        但此时,有两种计算方式(Reduction)可以选择,即 η 简化(eta reduction)和 ι 简化(iota reduction)。有:

        其中,在做 η 简化(eta reduction)后,表达式 为 recₐ₌ C e a,与含义不符这就要求LEAN在选择计算规则是,需要约束其只能选择体现原含义的计算规则。即,LEAN 要求 使用函数 rec 的参数个数必须得到满足,即表达式 recₐ₌ C e a 不被允许,因此,表达式 λh:a = a. recₐ₌ C e a h 只能选 ι 简化(iota reduction)。

        下图是LEAN 对简化规则使用的正式说明:

        注:商类型(Quotient Type)的使用函数 lift 在 介绍 商类型(Quotient Type)时提及过,后续会有文章,进行详细讨论。

        其中,第一点说明了,当 使用函数 rec 后跟着的参数个数少于其要求的参数个数是,其表达式的形态为 λx :: α. rec e x,即,上述的 recₐ₌ C e a ,不允许存在。

        第三点说明,如果满足参数个数的要求,会先使用 η 简化(eta reduction),也叫 η 扩展(eta expanse),这个就是等式的解析,从左到右看或从右到左看了。

        此时,满足 rec 参数要求的表达式,称为 rec 常态 (rec-normal form)。

三、rec 常态 (rec-normal form)的属性

                

四、K 简化(K Reduction)定义

其实,就是将把 β δ ζ ι 简化 定义在 rec-normal form 上,统称为 K 简化(K Reduction)。

五、证据不区分(Proof Relevance)关系

        证据不区分(Proof Relevance)会导致 表达式没有唯一的常态,但是,如果两个表达式间有证据不区分(Proof Relevance)关系,那么,实际意义上,两表达式是定义上相等的。由此,通过下面定义指示,两个表达式在证据不区分(Proof Relevance)的情况下,定义上相等(Definitional Equal),记,≡ₚ ,即 对于具备证据不区分(Proof Relevance)关系的两表达式的简化规则(Reduction Rule)。

        上述 ≡ₚ 定义的推演规则,说明,如果表达式中带有 p: P,那么基于证据不区分(Proof Relevance),其形变应遵从 ≡ₚ 定义的推演规则。

六、小结

        至此,简化规则就包括 K简化(K Reduction)和 针对具备证据不区分(Proof Relevance)关系的简化规则,具备后续推导 Church-Rosser 定理 的准备。另外,简化规则有下面属性:

     

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com