如何在 Coq 中将“+ 1”（加一）重写为 "S"（succ）？

Question

我有以下证明不完整的引理：

Lemma s_is_plus_one : forall n:nat, S n = n + 1.
Proof.
  intros.
  reflexivity.
Qed.

此证明失败

Unable to unify "n + 1" with "S n".

似乎 eq_S 可以证明这一点，但我无法应用它（它无法将 n + 1 识别为 S n：Error: Unable to find an instance for the variable y.).我也试过 ring，但找不到关系。当我使用 rewrite 时，它只是减少到相同的最终目标。

我怎样才能完成这个证明？

Answer 1

这与(+)的定义方式有关。您可以通过关闭符号来访问 (+) 的底层定义（在 View > Display notations 中的 CoqIDE 中），看到符号 (+) 对应于函数 Nat.add 然后调用 Print Nat.add 这给你：

Nat.add = 
fix add (n m : nat) {struct n} : nat :=
  match n with
  | O => m
  | S p => S (add p m)
  end

你可以看到 (+) 是通过匹配它的第一个参数来定义的，在 n + 1 中是变量 n。因为 n 不是以 O 或 S 开头（它不是 "constructor-headed"），所以 match 不能减少。这意味着你不能仅仅通过说这两个东西计算出相同的范式（这就是 reflexivity 所声称的）来证明相等性。

相反，您需要向 coq 解释为什么对于任何 n 等式都成立。对于像 Nat.add 这样的递归函数，一个经典的做法是通过 induction 进行证明。它确实在这里完成了工作：

Lemma s_is_plus_one : forall n:nat, S n = n + 1.
Proof.
intros. induction n.
 - reflexivity.
 - simpl. rewrite <- IHn. reflexivity.
Qed.

你可以做的另一件事是注意 1 另一方面是以构造函数为首的，这意味着只有你有 1 + n 而不是 n + 1 才会触发匹配。好吧，我们很幸运，因为在标准库中有人已经证明 Nat.add 是可交换的，所以我们可以直接使用它：

Lemma s_is_plus_one : forall n:nat, S n = n + 1.
Proof.
intros.
rewrite (Nat.add_comm n 1).
reflexivity.
Qed.

最后一个替代方案：使用 SearchAbout (?n + 1)，我们可以找到所有关于某个变量 ?n 的模式 ?n + 1 的定理（这里的问号很重要）。第一个结果是真正相关的引理：

Nat.add_1_r: forall n : nat, n + 1 = S n

如何在 Coq 中将“+ 1”（加一）重写为 "S"（succ）？

How can I rewrite "+ 1" (plus one) to "S" (succ) in Coq?

coq

coq-tactic

successor-arithmetics