为什么不能对结论中使用的术语进行归纳？

Question

假设以下特定场景。

我们有一个相等的定义：

Inductive eqwal {A : Type} (x : A) : A -> Prop :=
    eqw_refl : eqwal x x.

还有 peano nats：

Inductive nawt : Prop :=
    | zewro : nawt
    | sawc  : nawt -> nawt.

我们在nats上定义加法：

Fixpoint plaws (m n : nawt) : nawt :=
    match m with
      | zewro => n
      | sawc m' => sawc (plaws m' n)
    end.

现在我们要证明零从右到右是中性的。求和：

Theorem neutral_r : forall n : nawt, eqwal (plaws n zewro) n.

可悲的是，以下证明的最后一行说“错误：结论中使用了 n。”。

Proof.
intros.
induction n. - this is the culprit

官方文档中没有太多关于错误的信息，我有点困惑-为什么会出现这个错误？

使用标准库，我可以很容易地证明定理：

Theorem neutral_r : forall n : nat,
  n + 0 = n.
Proof.
  induction n; try reflexivity.
  cbn; rewrite IHn; reflexivity.
Qed.

Answer 1

问题是您定义 nawt 时使用排序 Prop 而不是 Type 或 Set。默认情况下，为命题生成的归纳原理不允许我们证明任何关于这些命题的证明。考虑为 nawt:

生成的默认归纳原理

Check nawt_ind.
> nawt_ind : forall P : Prop, P -> (nawt -> P -> P) -> nawt -> P

因为 nawt_ind 量化超过 Prop，而不是超过 nat -> Prop，我们不能用它来证明你的目标。

解决方案是设置一些选项来更改 Coq 的默认行为，如以下脚本所示。

Inductive eqwal {A : Type} (x : A) : A -> Prop :=
    eqw_refl : eqwal x x.

Unset Elimination Schemes.

Inductive nawt : Prop :=
    | zewro : nawt
    | sawc  : nawt -> nawt.

Scheme nawt_ind := Induction for nawt Sort Prop.

Set Elimination Schemes.

Fixpoint plaws (m n : nawt) : nawt :=
    match m with
      | zewro => n
      | sawc m' => sawc (plaws m' n)
    end.

Theorem eqwal_sym {A : Type} (x y : A) : eqwal x y -> eqwal y x.
Proof. intros H. destruct H. constructor. Qed.

Theorem neutral_r : forall n : nawt, eqwal (plaws n zewro) n.
Proof.
intros. induction n as [|n IH]; simpl.
- constructor.
- apply eqwal_sym in IH. destruct IH. constructor.
Qed.

Elimination Schemes 选项使 Coq 自动生成数据类型和命题的归纳原理。在此脚本中，我只是将其关闭，并使用 Scheme 命令为 nawt 生成正确的归纳原理。为了让 induction 策略起作用，重要的是给这个原则命名 nawt_ind：这是 Coq 生成的默认名称，也是 induction 寻找的那个打电话。

也就是说，我通常建议不要在 Prop 中定义一种自然数，而不是在 Type 中定义，因为 Coq 对如何使用存在于 [=13 中的事物施加了限制=].例如，无法证明 zewro 不同于 sawc zewro。

为什么不能对结论中使用的术语进行归纳？

Why is it impossible to perform induction on a term that is used in conclusion?

coq