我如何在 Coq 中从头开始证明 'S x > 0'？

Question

我如何证明这个简单的事实

forall x:nat, S x > 0.

?

我的逻辑是

对于任何 nat n，n > 0 或 n = 0。
S x = 0 导致矛盾。

我的主要问题是我无法记住所有这些关于 nat 的琐碎 theorems/lemma，而且我不太了解搜索命令。

我试过 'destruct gt' 或 '>' 构造函数，或对 'gt' 进行一些反转。但我无法弄清楚语法或者这是否是正确的方向。

非常感谢任何帮助（除了 omega 之类的重物）。

Answer 1

这里有一些命令可能会对您有所帮助：

Unset Printing Notations.是为了能够看到
Print ID. 查看标识符 ID 是什么
unfold ID. 以其定义

ID

SearchAbout (ID (CON ?m) ?n) 查找涉及 ID 的结果适用于子项的 CON 和任何其他子项（如果您重复使用相同的 ?m占位符，搜索将仅 return 结果匹配相应的子词）。

例如，在您的情况下，这可能会导致此交互式会话：

Unset Printing Notations.
Goal forall x:nat, S x > 0.
intro x.
Print gt.
unfold gt.
Print lt.
unfold lt.
Print le.
SearchAbout (le (S ?m) (S ?n)).
apply le_n_S.
SearchAbout (le 0 ?m).
apply le_0_n.
Qed.

Answer 2

这是另一种方法（基于您对自然数的观察）。

首先，我们需要导入一个包含许多关于自然数的事实的模块（没有这个导入 Search 将找不到我们要查找的内容）：

Require Import Coq.Arith.Arith.

现在，让我们寻找引理，它指出任何 nat 要么是 0 要么大于 0:

Search ({_ = 0} + {_}).

此搜索结果

zerop: forall n : nat, {n = 0} + {0 < n},

这是 Coq 对先前观察到的事实的说法。

使用那个 zerop 引理我们最终可以证明我们的目标：

Goal forall x:nat, S x > 0.
  intros x. 
  destruct (zerop (S x)).

(* subcase S x = 0 *)
  discriminate.             (* deals with the contradiction *)

(* subcase S x > 0 *)
  assumption.
Qed.

顺便说一句，标准库中有一个引理（从 Coq v8.5 开始），它和你的引理完全一样：

Search (S _ > 0).

这导致 gt_Sn_O: forall n : nat, S n > 0，您可以在标准库中查看此引理的实现（它又使用了几个引理）。

Answer 3

我提出了一个基于 < 运算符的计算编码的替代解决方案：

From mathcomp
Require Import ssreflect ssrbool ssrfun eqtype ssrnat.

Lemma test n : 0 < n.+1.
Proof. by []. Qed.

这是如何工作的？事实上，这是可行的，因为我们将 < 操作定义为一个函数：

(m < n) = (m.+1 <= n) = (m.+1 - n == 0)

当应用于你的引理时，它变成：

(0 < n.+1) = (0.+1 <= n.+1) = (1 - n.+1 == 0) = (0 - n == 0) = (0 == 0) = true

我如何在 Coq 中从头开始证明 'S x > 0'？

How do I prove 'S x > 0' from scratch in Coq?

coq

coq-tactic