了解 coq 中证据的归纳

Question

我正在研究 IndProp.v of Software Foundations (Vol 1: Logical Foundations) 中的定理 ev_ev__ev。

Theorem ev_ev__ev : forall n m,
  even (n+m) -> even n -> even m.
Proof.
  intros n m Enm En. induction En as [| n' Hn' IHn'].
  - (* En: ev_0 *) simpl in Enm. apply Enm.
  - (* En: ev_SS n' Hn': even n' 
              with IHn': even (n' + m) -> even m *)
    apply IHn'. simpl in Enm. inversion Enm as [| n'm H]. apply H.
Qed.

其中 even 定义为：

Inductive even : nat -> Prop :=
| ev_0 : even 0
| ev_SS (n : nat) (H : even n) : even (S (S n)).

第二个子弹点-，上下文和目标如下：

m, n' : nat
Enm : even (S (S n') + m)
Hn' : even n'
IHn' : even (n' + m) -> even m
______________________________________(1/1)
even m

我理解m, n', Enm, Hn'中的上下文是如何生成的。但是，IHn'是怎么生成的呢？

Answer 1

归纳假设是针对同一类型族中的构造函数的前提系统地创建的。因此，您可以独立查看每个构造函数。

假设您有一个以以下开头的类型的归纳定义：

Inductive arbitraryName : A -> B -> Prop :=

将创建一个称为 arbitraryName_ind 的归纳原理，它首先对通常称为 P 的具有相同类型

的任意谓词进行量化

forall P : A -> B -> Prop,

现在，如果您有一个构造函数

arbitrary_constructor : forall x y, arbitraryName x y -> ...

对于这个构造函数，归纳原则将有一个 sub-clause，它以对构造函数中所有变量的相同量化、相同假设以及依赖于 arbitraryName 的前提的归纳假设开始。

forall x y, arbitraryName x y -> P x y -> ...

最后，归纳定义的每个构造函数都必须以定义的类型族的应用程序结束（在本例中 arbitraryName）。此构造函数子句的末尾将函数 P 应用于同一参数。

让我们回到 arbitrary_constructor 并假设它具有以下完整类型：

arbitrary_constructor : forall x y, arbitraryName x y -> arbitraryName (g x y) (h x y)

在那种情况下，归纳原则中的子句是：

 (forall x y, arbitraryName x y -> P x y -> P (g x y) (h x y))

在 even 的情况下，有一个具有以下形状的构造函数 ev_SS：

ev_SS : forall x, even x -> even (S (S x))

因此生成的子句具有以下形状：

(forall x, even x -> P x -> P (S (S x)))

归纳假设IHn'正好对应子句中的这个P。

完整的归纳原理具有以下形状。

forall P : nat -> Prop, P 0 -> 
   (forall x, even x -> P x -> P (S (S x))) ->
   forall n, even n -> P n

当您键入 induction En 时，将应用此定理。假设 even n，其中 n 是普遍量化的，与当时目标中 En 的文本相匹配。事实证明，该假设的陈述是 even n（这里的 n 在目标中是固定的）所以普遍量化的 n 是用来自局部 n 实例化的目标上下文。然后，该策略尝试在 n 出现的上下文中找到所有假设。在这种情况下，有Enm，所以这个假设用来定义归纳原理将被实例化的P。从某种意义上说，发生的事情是将 Enm 放回到目标的结论中，就好像执行了 revert Enm.

我们需要 P n 与 even (n + m) -> even m 相同。最自然的解决方案是 P 等于函数 fun x => even (x + m) -> even m

所以在归纳证明的第二种情况下，引入一个新的n'并将P应用于n'，给出归纳假设的内容：

(even (n' + m) -> even m)

和P应用于S (S n')得到最终目标的内容。

 even (S (S n') + m) -> even m

现在，在调用 induction 策略时，假设 Enm 在上下文中，因此语句 even (S (S n') + m) 在道德上是 [=39 的后代=] 以相同的名称放回上下文中。请注意，另一个目标中已经有一个名为 Enm 的假设，但声明再次不同。

你对这个归纳假设是如何产生的有疑问是正常的，因为实际上发生的事情涉及几个操作。

了解 coq 中证据的归纳

Understanding the induction on evidence in coq

coq

theorem-proving

coq-tactic

induction