颠倒一个明显不正确的假设并不能证明错误

Question

我正在尝试证明一个微不足道的引理，它是我在另一点发现自己的情况的再现。

Lemma Sn_neq_n: forall n, S n <> n.

证明看起来很简单：

Proof. unfold not. intros.

现在我的目标状态显示：

n : nat
H : S n = n
===================
 False

嗯，很明显S n和n不能统一，所以我应该可以把这个假设倒过来：

inversion H.

但是我的状态现在没有解决目标，而是显示：

n : nat
H : S n = n
H0 : S n = n
===================
 False

嗯？我现在只是在一个无限循环中。我可以 inversion H0 并且我只得到一个 H1，等等

我能够通过归纳法证明引理：

unfold not. intros. induction n.
Case "n = 0". inversion H.
Case "n > 0". inversion H. apply IHn. apply H1.

但这有点傻，因为可以想象，首先允许自反平等有意义的统一算法不应该能够将 S n 与 n 统一。

这是怎么回事？

Answer 1

要了解为什么 inversion 无法自行解决这个目标，我们需要更详细地了解它在做什么。

当您反转（共）归纳类型的假设时，粗略地说，Coq 所做的是从中提取尽可能多的信息仅使用模式匹配（请记住，Coq 策略总是在幕后产生证明项）。因此，当通过反转证明 1 <> 0 时，Coq 将产生如下所示的项：

Definition one_neq_zero (p : 1 = 0) : False :=
  match p in _ = n return match n with
                          | 0 => False
                          | _ => True
                          end
  with
  | eq_refl => I (* "I" is the only constructor of the True proposition *)
  end.

match 语句中的 return 批注对此至关重要。这里发生的事情本质上是这样的：

我们需要匹配等式证明 p 才能使用它。
为了能够在对其证明进行模式匹配时讨论该等式的右侧，我们必须为我们的匹配添加一个 return 注释。
遗憾的是，此 return 注释不能直接提及 0。相反，它需要为 generic n、 工作，即使我们知道该元素实际上是 0。这只是因为模式匹配在 Coq 中的工作方式。
在return注解上，我们在Coq上打了一个"trick"：我们说我们会returnFalse在我们真正关心的情况下（即, n = 0), 但说我们会 return 在其他分支上做些别的事情。
要对 match 进行类型检查，每个分支必须 return 某些出现在 return 子句中的类型，但在替换 实际值之后 个绑定在 in 子句上的变量。
在我们的例子中，相等类型只有一个构造函数，eq_refl。在这里，我们知道 n = 1。在我们的 return 类型中用 1 代替 n，我们得到 True，所以我们必须 return 类型 True 的东西。
最后，由于 p 的右边是 0，Coq 知道整个匹配的类型是 False，所以整个定义进行类型检查。

最后一步之所以有效，是因为 0 是一个构造函数，因此 Coq 能够简化 return 类型的匹配，从而意识到我们 return 是对的。这个是尝试反转S n = n时失败的地方：因为n是一个变量，所以不能简化整个匹配。

我们可以尝试翻转等式并反转 n = S n，这样 Coq 就可以稍微简化 return 类型。不幸的是，出于类似的原因，这也行不通。例如，如果您尝试用 in _ = m return match m with 0 => True | _ => False end 注释匹配项，在 eq_refl 中我们将不得不 return 类型为 match n with 0 => True | _ => False end 的内容，但我们不能这样做。

最后我要提一下 Coq 内部的统一算法不能像你提到的那样使用 "negatively"，因为该理论只定义了 可证明的东西 ，并且不是哪些东西是可以反驳的。特别是，当我们证明一个否定命题如 S n <> n 时，类型检查器总是在测试某些统一问题是否有解决方案，而不是测试它们是否有 no 解决方案.例如，假设 n = m 是一件非常好的事情，并且不会导致任何矛盾，即使 n 和 m 是 而不是 统一。另请注意，如果 nat 被声明为 co-inductive 类型，则 S n = n 是 而不是 一个矛盾的假设，两者之间的区别只是在这种情况下我们无法对 n.

进行归纳

颠倒一个明显不正确的假设并不能证明错误

Inverting an obviously untrue hypothesis does not prove falsehood

coq

inversion