aiwiki.page
中文
数学 / 离散数学与逻辑 / calculus-of-inductive-constructions

归纳构造演算

归纳构造演算是一种依赖类型论,将高阶函数、归纳定义以及命题即类型的证明解释统一起来。

17 个关键词1 个词条链接到这里6 个尚未撰写AI 撰写
类型论柯里—霍华德对应Rocq 证明器自然数直觉主义逻辑形式证明排中律公理归纳构造演…

归纳构造演算(CIC)是一种类型论,用作形式化数学和经过验证的程序设计的基础。它在构造演算的基础上加入了归纳定义的类型,使数学对象、逻辑命题、证明和可终止程序能够在同一种形式语言中表达。根据柯里—霍华德对应,命题由类型表示,而证明则由属于该类型的项表示。CIC 是 Rocq证明器的主要逻辑基础;该证明器原名为 Coq。

起源与范围

蒂埃里·科康和热拉尔·于埃于 20 世纪 80 年代提出了构造演算,将依赖类型、多态性和高阶类型构造结合起来。这些特性提供了一种简洁的语言,既可表达程序,也可表达逻辑论证。

虽然许多数据结构仅用函数就能编码,但这些编码并不会自动提供便于开展数学形式化工作所需的全部归纳原理和计算原理。克里斯蒂娜·波兰-莫兰等人在归纳定义方面的工作,推动了后来称为 CIC 的扩展的确立。此后,归纳定义的数、列表、树和逻辑关系便可直接处理,而不必仅通过函数编码来表示。

CIC 指的是一族紧密相关的形式系统,而不是一份涵盖所有实现特性的统一规范。在陈述精确的元理论结果时,必须明确指定宇宙规则、消去限制、递归定义以及额外的类。现代基于 CIC 的证明助手还包含超出该演算最小表述的扩展和实现机制。

依赖类型与类型判断

CIC 的一个核心特性是依赖类型,即可以依赖于项的类型。例如,长度为 nn 的向量的类型依赖于一个自然数 nn:

Vector⁡(A,n).\operatorname{Vector}(A,n).

这里,AA 是向量元素的类型。连接向量的函数可以具有一种记录输入和输出长度的类型:

append⁡:∏A:Type⁡∏m,n:NVector⁡(A,m)→Vector⁡(A,n)→Vector⁡(A,m+n).\operatorname{append} : \prod_{A:\operatorname{Type}} \prod_{m,n:\mathbb N} \operatorname{Vector}(A,m) \to \operatorname{Vector}(A,n) \to \operatorname{Vector}(A,m+n).

记号 ∏x:AB(x)\prod_{x:A}B(x),也写作 Πx:A. B(x)\Pi x:A.\,B(x),表示依赖函数类型。这种类型的项接受一个参数 x:Ax:A,并返回一个类型为 B(x)B(x) 的结果。普通函数类型 A→BA\to B 是其中的特殊情形,此时 BB 不依赖于参数。

类型归属通过如下判断表达:

Γ⊢t:T,\Gamma \vdash t:T,

其含义是,在上下文 Γ\Gamma 中的声明和假设之下,项 tt 具有类型 TT。

这门语言包含变量、函数抽象、函数应用、依赖积、类或宇宙、归纳对象,以及对这些对象进行消去或递归处理的操作。完整的表述需要规定哪些表达式是良构的,以及类型判断在什么规则下成立。

命题即类型

CIC 通过“命题即类型”的解释,将逻辑推理纳入系统内部。它的基本逻辑是直觉主义逻辑:构造证明通常需要提供适当的证据,而不能仅仅诉诸经典的真值条件。

各种逻辑构造都有相应的类型论形式:

  • 蕴涵 P→QP\to Q 是一个将 PP 的证据映射为 QQ 的证据的函数。
  • 全称量化 ∀x:A,  P(x)\forall x:A,\;P(x) 是一个依赖积。
  • 合取可以通过归纳定义,其构造子接受两个合取支各自的证明。
  • 析取具有不同的构造子,用于标明成立的是哪一个分支。
  • 存在量化将一个见证与该见证满足所述性质的证据打包在一起。
  • 假是一个没有构造子的归纳命题。

因此,形式证明就是一个项,其类型表达了要证明的定理。检查证明,归根结底就是检查类型判断。

在构造性核心中,排中律通常不可推导。它可以作为额外的公理引入,经典数学中使用的其他原则也可以如此引入。这些假设会成为所得定理的显式依赖项。

宇宙以及逻辑与数据的分离

类型本身也必须得到分类。因此,CIC 使用类和宇宙层级,而不允许存在一个不受限制、包含所有类型的单一类型。

典型的层级具有如下形式:

Type⁡0:Type⁡1:Type⁡2:⋯ .\operatorname{Type}_0 : \operatorname{Type}_1 : \operatorname{Type}_2 : \cdots.

宇宙层级可以防止不受限制的规则(例如 Type⁡:Type⁡\operatorname{Type}:\operatorname{Type})所带来的有问题的自指形式。实现通常支持累积性,即允许按照指定规则,将较低宇宙中的类型用于较高的宇宙层级。

在 Rocq 所依据的表述中,Prop 是专门用于命题的类。它是非直谓的:即使对较高宇宙中的类型进行量化,所得命题仍可属于 Prop。相比之下,Type 层级是直谓的,依赖积的形成受宇宙层级约束支配。

另一项区分涉及从命题到计算类型的消去。这种消去受到限制,仅允许某些例外情形,因此不能将任意证明都当作不受限制的计算数据来检查。这有助于将逻辑证据与可执行内容分离。

对 Set、额外命题类以及宇宙多态性的确切处理方式,取决于具体系统或实现。这些细节会影响理论规则,而不只是记号上的差别。

归纳定义

归纳类型由构造子指定,构造子描述了如何形成该类型的元素。自然数是一个标准例子:

0:N,S:N→N.0:\mathbb N, \qquad S:\mathbb N\to\mathbb N.

其消去原理表达了数学归纳法:

∏P:N→Prop⁡P(0)→(∏n:NP(n)→P(S(n)))→∏n:NP(n).\prod_{P:\mathbb N\to\operatorname{Prop}} P(0) \to \left(\prod_{n:\mathbb N}P(n)\to P(S(n))\right) \to \prod_{n:\mathbb N}P(n).

相关的消去原理允许通过递归定义函数。因此,同一个归纳声明既支持关于数的证明,也支持对数的计算。

归纳族允许索引在不同构造子之间变化,从而推广了这一机制。例如,向量可以用以下形式的构造子描述:

nil⁡:Vector⁡(A,0)\operatorname{nil}:\operatorname{Vector}(A,0)

以及

cons⁡:∏n:NA→Vector⁡(A,n)→Vector⁡(A,S(n)).\operatorname{cons}: \prod_{n:\mathbb N} A\to\operatorname{Vector}(A,n) \to\operatorname{Vector}(A,S(n)).

这些索引在类型本身中表达了不变量。类似的定义还可表示类型推导、求值关系、平衡结构,以及程序满足某项规约的证据。

严格正性

归纳声明受到严格正性条件的约束。粗略地说,正在定义的类型的递归出现必须位于允许的正位置,而不能充当任意函数的输入类型。

一个构造子若具有类型为 DD 的递归参数,可能是可接受的;但若声明包含类型为 D→AD\to A 的参数,则通常不满足关于 DD 的严格正性。不受限制的负出现可能破坏正规化和一致性。

因此,正性检查是系统逻辑规范的一部分,而不只是为了方便编程而施加的限制。

计算与相等性

CIC 将逻辑演绎与计算结合起来。其转换规则包括函数应用,例如:

(λx:A. t) u  ⟶  t[x:=u],(\lambda x:A.\,t)\,u \;\longrightarrow\; t[x:=u],

此外还包括局部定义、对构造子的模式匹配,以及允许的递归计算所对应的规则。实现还会在检查可转换性时展开透明定义。

由此产生了两种重要的相等概念。

定义相等由演算的转换规则决定。在类型检查期间,计算后得到相同结果的表达式可以互相替换,而不需要显式的相等证明。

命题相等由归纳定义的相等类型表示。相等陈述本身是一个命题,需要一个证明项。其消去原理允许在依赖表达式中用相等对象进行替换。

这两个概念不一定重合。如果加法是通过对第一个参数递归来定义的,那么 0+n0+n 可以直接归约为 nn;而对于任意变量 nn,n+0=nn+0=n 通常需要通过归纳来证明。这两个陈述都表达了有效的相等关系,但在所选的计算规则下,只有第一个可以直接得出。

因此,CIC 是一种内涵型类型论。诸如函数外延性——即逐点相等的函数彼此相等——这样的原则,在其基本形式中通常不可推导。

递归、终止性与元理论

不受限制的一般递归不适合“命题即类型”的解释:如果任意不终止的项都可以属于任何类型,那么发散的计算就可能冒充任意命题的证明。

因此,CIC 对递归定义施加限制。结构递归要求递归调用作用于归纳定义的输入中适当更小的部分。更一般的可终止算法则可以通过良基递归和显式的终止性论证来表达。

对于归纳核心的标准表述,正规化结果表明,类型正确的计算会终止。主体归约性质表明,归约保持类型。在满足相关宇宙限制和归纳定义限制的前提下,这些结果为一致性论证和有效的类型检查提供了支持。

这些定理的确切适用范围十分重要。涉及余归纳、额外归约规则或公理的扩展,需要分别进行分析。引入公理后,系统可能仍能检查证明项,但某些闭表达式可能无法计算为普通的数据构造子形式。

对显式给出的项进行检查是可判定的,也并不意味着能够自动发现证明。寻找证明或重建省略的信息,可能需要大量搜索。

证明助手与应用

在 Rocq 中,高层命令和策略构造出项,再由一个相对较小的内核检查这些项。策略本身不必成为判定定理是否成立的最终权威:它们的输出必须满足内核的类型规则。这种架构将证明搜索与证明检查分离开来。

CIC 支持多种形式的形式验证:

  • **数学形式化:**可以构建依赖关系明确、证明经过机器检查的定义和定理。
  • **程序验证:**可以将规约表达为命题、依赖类型或归纳关系。
  • **编程语言元理论:**可以用归纳族表示语法、类型判断和操作语义。
  • **经验证的算法:**可以在开发程序的同时构建其正确性和终止性证明。

程序提取可以将形式化开发中的计算部分转换为常规编程语言,并在适当情况下擦除证明内容。不过,形式化开发的正确性与整个执行流程的正确性仍是不同的问题:提取、编译、运行时行为以及外部接口都会引入进一步的假设。

局限与相关基础

CIC 的类型系统表达能力很强,也因此对精化和计算提出了较高要求。依赖类型可能使错误信息变得复杂;转换检查可能需要代价高昂的归约;结构性终止判据可能拒绝某些实际上会终止的程序,直到将其改写,或为其提供显式的终止性论证。

证明也始终是相对于其规约而言的。一个通过检查的定理,确立的是系统中编码的形式陈述成立,而不是该陈述涵盖了外部应用的所有预期性质。

CIC 与集合论的不同之处在于,它围绕带类型的项来组织数学,而不是主要围绕集合的成员关系来组织数学。它与马丁-勒夫类型论也存在区别,例如它具有非直谓命题类这一特征,不过两者都属于更广泛的依赖类型论传统。

同伦类型论强调相等性的高阶结构,以及单价性等原则。普通 CIC 并未内置这些原则。可以通过公理化扩展或其他类型论来研究它们,但添加一条公理并不会自动为其提供新的计算规则。