茶年 · 中文维基百科

直觉类型论

Wikipedia · 2025-08-07 维基百科 👁 1 阅读

直觉类型论（），也可简称类型论，此外也有构造类型论（）或马汀-洛夫类型论（，缩写 MLTT）称呼，是基于数学构造主义的一种类型论，也可作为公理集合论以外的另一种数学基础。

直觉类型论由瑞典数学家和哲学家佩尔·马丁-洛夫于1972年提出。马丁提出了多个版本，先是非直谓性的而后是直谓性的，先是外延的而后是内涵的类型论变体。

直觉类型论基于柯里-霍华德同构而提出，后者指的是计算机程序的类型和逻辑系统之间的一一对应关系。而且在先前类型理论的基础上，直觉类型论进一步实现了谓词逻辑的对应：依赖类型。类型论内在化了鲁伊兹·布劳威尔、阿兰德·海廷和安德雷·柯爾莫哥洛夫提议的布劳威尔-海廷-柯尔莫哥洛夫释义的直觉逻辑释义。类型论的类型扮演了类似于集合在集合论的角色，不同之处在于在类型论中的函数总是可计算的。
类型论的连结词
在类型论的语境中，连结词是使用已给定的类型而构造类型的一种方式。类型论的基本连结词有:

\Pi-类型
\Pi-类型，也叫做依赖函数类型，一般化了普通的函数空间，建模其结果的类型可以随它们的输入而变化的函数，比如，对实数的 n-元组写为 \mbox{Vec}({\mathbb R},n)，则\Pi n:{\mathbb N}.\mbox{Vec}({\mathbb R},n) 表示对给定的自然数返回这个大小的实数元组的函数的类型。在值域类型实际上不依赖于输入的时候，普通函数空间作为特殊情况出现，比如 \Pi n:{\mathbb N}.{\mathbb R} 是从自然数到实数的函数的类型，它也写为 {\mathbb N}\to{\mathbb R}。使用 Curry-Howard同构，\Pi-类型还充当建模蕴涵和全称量化: 比如，具有类型 \Pi m,n:{\mathbb N}.m+n = n+m 的一个项，是对任何一对自然数的函数指派加法对这个数对是交换性的证明，并因此可以被当作加法对于所有自然数是交换性的一个证明。

\Sigma-类型
\Sigma-类型，也叫做依赖乘积类型，一般化了普通的笛卡尔积，建模第二个构件的类型依赖于第一个构件的有序对，比如类型 \Sigma n:{\mathbb N}.\mbox{Vec}({\mathbb R},n) 表示自然数和这个大小的实数的元组的有序对的类型，就是说，这个类型可以用来建模任意长度的序列(通常叫做列表)。在第二个构件的类型实际上不依赖于第一个构件的时候，常规的笛卡尔积类型作为特殊情况出现，比如 \Sigma n:{\mathbb N}.{\mathbb R} 是自然数和实数的有序对的类型，它也写为 {\mathbb N}\times{\mathbb R}。再次使用 Curry-Howard同构，\Sigma-类型也充当建模合取和存在量化。

有限类型
特别重要的是 0 (空类型)、1 (单位类型)和 2 (布尔值或真值)。再次用到 Curry-Howard同构，0 表示假而 1 表示真。

使用有限类型，我们可以定义否定为 \neg A = A \to 0，服从Curry-Howard同构，不相交并集也表示析取，它可以定义为 A+B = \Sigma b:2.\mbox{if}\,b\,\mbox{then}\,A\,\mbox{else}\, B。

等式类型
给定 a,b : A，则 a = b 是 a 等于 b 的等式证明。只有一个(规范的) a = b 的居留，并且这是自反性 \mbox{refl} : \Pi a:A.a = a 的证明。

归纳类型
归纳类型的基本例子是自然数 \mathbb N 的类型，它是通过 0 : {\mathbb N} 和 \mbox{succ} :{\mathbb N} \to {\mathbb N} 生成的。命题为类型原理的一个重要应用是通过对用 n:{\mathbb N} 索引的给定类型 P(n) 的一个消除常量: {\mathbb N}-\mbox{elim} : P(0) \to (\Pi n:{\mathbb N}.P(n)\to P(\mbox{succ}(n)))\to\Pi n:{\mathbb N}.P(n) 来把(依赖的)原始递归和归纳同一起来的。在一般的归纳类型中可以被定义为 W-类型，它是良基的树的类型。

一类重要的归纳类型是像上面提及的向量 \mbox{Vec}(A,n) 的归纳类型家族，它们是归纳生成自构造子 \mbox{vnil}:\mbox{Vec}(A,0) 和 \mbox{vcons}:A\to\Pi n:{\mathbb N}.\mbox{Vec}(A,n)\to\mbox{Vec}(A,\mbox{succ}(n))。再次用到Curry-Howard同构，归纳类型家族对应于归纳定义的关系。

全集
全集的一个例子是 U_0，它是所有小类型的全集，它包含前面介绍的所有类型的名字。对于每个名字 a:U_0 我们关联上一个类型 El(a)，这是它的外延或意义。标准上是假定全集的一个直谓性等级: 对于每个自然数 n:{\mathbb N} 的 U_n，这里的全集 U_{n+1} 包含以前的全集的一个代码，就是说，我们通过 El(u_n)=U_n 而有 u_n:U_{n+1}。这个等级经常被假定为是累积性的，就是说来自 U_n 的代码被嵌入了 U_{n+1}。

已经研究了更强的全集原理，比如超全集和 Mahlo 全集。在 1992 年 Huet 和 Coquand 介入了构造演算，它是带有非直谓性全集的类型论，从而把类型论同 Girard 的系统F 合并起来了。这个扩展不被直觉主义者所普遍接受，因为它允许非直谓性的，就是循环的构造，这经常用经典推理来识别。

类型论的形式化
类型论通常表示为依赖的有类型 lambda 演算，使用判断:

  • \vdash \Gamma\, \mbox{Context}，\Gamma类型假定的良好形成的上下文。
  • \Gamma\vdash \sigma\, \mbox{Type}，\sigma 在上下文 \Gamma 中的良好形成的类型。
  • \Gamma\vdash t : \sigma，t 是在上下文 \Gamma 中的类型\sigma 的良好形成的项。
  • \Gamma\vdash \sigma\equiv\tau，\sigma 和 \tau 是在上下文 \Gamma 中的等于类型。
  • \Gamma\vdash t \equiv u: \sigma，t 和 u 是在上下文 \Gamma 中的类型 \sigma 的相等项。

特别重要的是转换规则，它声称给定 \Gamma\vdash t : \sigma 和 \Gamma\vdash \sigma\equiv\tau 则 \Gamma\vdash t : \tau。

外延和内涵
一个基本区别是外延和内涵的类型论。在外延类型论中定义性(就是计算性)等式不区别于需要证明的命题性等式。作为结论类型检查成为不可判定性的。相反的，在内涵类型论中，类型检查是可判定性的，但是很多数学概念的表达是不标准的，因为缺乏外延推理。这是目前对这种折中是否是不可避免的和在内涵类型论中缺乏外延原理是一个特色还是一个缺陷的讨论的一个主题。

类型论的实现
类型论已经被用做很多证明助理的基础，比如 NuPRL、LEGO、Coq 和 Agda。最近，依赖类型也作为编程语言设计的特征，比如Dependent ML 和 Epigram。

参见

  • 直觉主义
  • BHK释义
  • 经典逻辑
  • 中间逻辑
  • 线性逻辑
  • 构造性证明
  • Curry-Howard对应
  • 可计算性逻辑
  • 博弈语义
  • 有类型 lambda 演算
  • Curry-Howard同构
  • 直觉逻辑
  • 构造演算
  • Per Martin-Löf
  • 类型论

外部链接

#數理邏輯 #类型论

评论 (0)

  • 还没有评论，来抢沙发吧。