是否可以在不使用反演的情况下在 Coq 中证明 `forall n: nat, le n 0 -> n = 0.`？

Question

在official coq tutorial中，他们定义了以下小于或等于的归纳定义：

Inductive le (n : nat) : nat -> Prop :=
          | le_n : le n n
          | le_S : forall m : nat, le n m -> le n (S m).

我的理解是它定义了两个类型构造函数：

le_n 取任意自然数并构造 le n n.
le_S 取任意自然数 m，证明 le n m 并构造 le n (S m)

到目前为止一切顺利。然而，他们随后继续引入以下引理和证明

Lemma tricky : forall n:nat, le n 0 -> n = 0.
Proof.
  intros n0 H.
  inversion H.
  trivial.
Qed.

'inversion' 这一步让我感到困惑。我知道除非 n 等于 0，否则无法构造 le n 0，因为 0 没有后继者，但我不确定反转策略如何解决这个问题。

为了尝试更好地理解它在哪些方面做得更好，我尝试在不使用倒置策略的情况下证明这个引理。然而，到目前为止我的所有尝试（即在 n0 上使用 elim，在 H 上，试图使用 forall n : nat, 0 <> S n. 等事实）都失败了。

虽然我的 'Computer science' 大脑完全可以接受这个推理，但我的 'mathematician brain' 有点难以接受这个，因为没有假设这就是只有种方式来构建 le 的居民。这让我想到也许使用反转策略是做到这一点的唯一方法。

是否可以不用反转策略来证明这个引理？如果可以，怎么办？

Answer 1

这个引理可以不用反演来证明：重点是对合适的目标做归纳（消元）。

首先请注意，当您将 elim 应用于 le n 0 类型的假设时，下面发生的事情是 Coq 将应用与 le 相关的消除原理。这里那个消元原理叫做le_ind，可以查询它的类型：

forall (n : nat) (P : nat -> Prop),
       P n ->
       (forall m : nat, n <= m -> P m -> P (S m)) ->
       forall n0 : nat, n <= n0 -> P n0

这可能有点吓人，但重要的一点是，为了从假设 n <= n0 中证明目标 P n0，您需要考虑两种情况，一种用于 le.

那么这对您的问题有何帮助？假设 n <= 0，这意味着您的目标应该是 P(n0) 和 n0 := 0 的形状。现在考虑要证明 n = 0，P 的形状应该是什么？您可以尝试采用最简单的解决方案 P(n0) := n = 0（如果您在代码中直接调用 elim H，这实际上就是 Coq 正在做的事情）但是您无法证明这两种情况中的任何一种。问题是，选择 P(n0) := n = 0 时，您忘记了 n0 的值，因此您不能使用它等于 0。那个问题的解决方法就是记住n0是0，也就是设置P(n0) := n0 = 0 -> n = 0.

我们如何在实践中做到这一点？这是一种解决方案：

Goal forall n, le n 0 -> n = 0.
Proof.
  intros n H.
  remember 0 as q eqn: Hq. (* change all the 0s to a new variable q and add the equation Hq : q = 0 *)
  revert Hq. (* now the goal is of the shape q = 0 -> n = 0 and H : le n q *)
  elim H.
  - intros; reflexivity. (* proves n = n *)
  - intros; discriminate. (* discriminates S m = 0 *)
Qed.

所有这些概括 0 的工作实际上是 inversion 试图为您做的。

请注意，我提出的谓词 P 并不是唯一可能的解决方案。另一个有趣的解决方案是基于 match（关键字是小规模反演）和 P(n0) := match n0 with 0 => n = 0 | S _ => True end。此外，战术最终总是会产生裸露的 gallina 术语，因此您总是可以（至少在理论上）写出一个术语来证明与任何战术相同的东西。下面是一个使用 Coq 强大但冗长的模式匹配的示例：

Definition pf : forall n, le n 0 -> n = 0 :=
  fun n H =>
    match H
          in le _ q
          return match q return Prop with
                 | 0 => n = q
                 | S _ => True
                 end
    with
    | le_n _ => match n with 0 => eq_refl | S _ => I end
    | le_S _ _ _ => I
    end.

编辑：使用remember 策略简化策略脚本。最初的提议是手动重新实现 remember：

set (q := 0). (* change all the 0s in the goal into q and add it as hypothesis *)
  intro H.
  generalize (eq_refl : q = 0). (* introduce q = 0 *)
  revert H.
  generalize q ; clear q.  (* generalizes q *)
  (* Now the goal is of the shape
     forall q : nat, n <= q -> q = 0 -> n = q
     and we can apply elim *)
  intros q H ; elim H.

Answer 2

问题是 induction 或 elim 策略 忘记了 le n 0 中的第二个参数是 0。可能有两种情况，要么 le n 0 的证明是 le_n，要么证明是 le_S。事实上，第二种情况是不可能的，因为 0 <> S n 但策略不会知道。

inversion 更接近 destruct 而不是 induction 因为它不会给你任何归纳假设。它会查看你给它的命题的所有构造函数，看看哪些可以导致它。而这一次，它很聪明，它发现 le_S 仅在您有 0 <> S n 时才适用并丢弃它。

一种手动完成的方法是简单地强制 Coq 记住第二个参数是 0.

Lemma tricky : forall n, le n 0 -> n = 0.
Proof.
  assert (h : forall n m, m = 0 -> le n m -> n = 0).
  { intros n m e h.
    induction h.
    - assumption.
    - discriminate.
  }
  intros n hyp.
  eapply h.
  - reflexivity.
  - assumption.
Qed.

如您所见，我通过添加等式来概括引理。 discriminate 策略允许您从荒谬的假设中得出目标，例如 0 = S n.

Answer 3

可以设计一个使用 SSReflect 的简短证明，遵循 Théo 的方法，同时交换 h 的两个假设：

Lemma tricky n (len0 : le n 0) : n = 0.
Proof.
  have h m : le n m -> m = 0 -> n = 0 by elim. 
  exact: (h 0).
Qed.

Answer 4

当你 destruct 假设 n <= 0 时，Coq 忘记了右边的值是 0 并要求你证明任意值的第二步 m .

因此，您必须 remember 该值实际上是 0。那么你将有足够的信息来得到第二种情况下的矛盾假设“S m = 0”。

Goal forall n, n <= 0 -> n = 0.
  remember 0 as m. 
  destruct 1. 
  - reflexivity.
  - pose proof (I : match S m with S _ => True | 0 => False end) as HF.
    rewrite Heqm in HF.
    apply False_ind, HF.
Qed.

是否可以在不使用反演的情况下在 Coq 中证明 `forall n: nat, le n 0 -> n = 0.`？

Is it possible to prove `forall n: nat, le n 0 -> n = 0.` in Coq without using inversion?

coq

coq-tactic