使用“依赖归纳”策略在进行归纳时保留信息

Question

我刚刚运行研究了 Coq induction 的问题，在阅读来自 here 的证明时丢弃了有关构造项的信息。

作者使用了类似的东西：

remember (WHILE b DO c END) as cw eqn:Heqcw.

在实际归纳induction H之前重写一个假设H。我真的不喜欢必须引入微不足道的平等的想法，因为它看起来像黑魔法。

SO 中的一些搜索表明 remember 技巧实际上是必要的。然而，一个答案 here 指出新的 dependent induction 可用于避免 remember 技巧。这很好，但是 dependent induction 本身现在看起来有点神奇。

我很难理解 dependent induction 的工作原理。 documentation 给出了一个需要 dependent induction 的例子：

Lemma le_minus : forall n:nat, n < 1 -> n = 0.

我可以验证 induction 是如何失败的，而 dependent induction 在这种情况下是如何工作的。但是我不能使用 remember 技巧来复制 dependent induction 结果。

到目前为止，我尝试模仿 remember 的技巧是：

Require Import Coq.Program.Equality.

Lemma le_minus : forall n:nat, n < 1 -> n = 0.
intros n H. (* dependent induction H works*) 
remember (n < 1) as H0. induction H.

但这行不通。任何人都可以根据 remember-ing?

来解释 dependent induction 在这里是如何工作的

Answer 1

你可以做到

Require Import Coq.Program.Equality.

Lemma le_minus : forall n:nat, n < 1 -> n = 0.
Proof.
intros n H.
remember 1 as m in H. induction H.
- inversion Heqm. reflexivity.
- inversion Heqm. subst m.
  inversion H.
Qed.

如 here 所述，问题在于 Coq 无法跟踪出现在您正在归纳的事物类型中的术语的形状。换句话说，对 "less than" 关系进行归纳会指示 Coq 尝试证明有关通用上限的某些内容，而不是您正在考虑的特定上限 (1).

请注意，在没有 remember 或 dependent induction 的情况下，始终可以通过稍微概括您的结果来证明此类目标：

Lemma le_minus_aux :
  forall n m, n < m ->
    match m with
    | 1 => n = 0
    | _ => True
    end.
Proof.
intros n m H. destruct H.
- destruct n; trivial.
- destruct H; trivial.
Qed.

Lemma le_minus : forall n, n < 1 -> n = 0.
Proof.
intros n H.
apply (le_minus_aux n 1 H).
Qed.

使用“依赖归纳”策略在进行归纳时保留信息

Using `dependent induction` tactic to keep information while doing induction

coq

induction

coq-tactic