如何为 Coq 中的 sigma 类型证明更短的 nat 比较，如 10000 > 1？

Question

目前我有：

Require Import Coq.Init.Specif.
Require Import Coq.Arith.Arith. 

Definition Test(s: {x : nat | x > 1}) := True.

Lemma pTwoGt1 : 2 > 1. apply gt_Sn_n. Qed.

Eval compute in Test (exist _ 2 pTwoGt1).

我如何证明随机高数，例如：10000 > 1？
如何简化此 sigma 类型的值创建？目前我必须有单独的几行代码来证明，甚至要给它起个名字。

Answer 1

您可以阅读本书的第 7 章 https://zenodo.org/record/4457887#.Ydbktdso-cM，其中介绍了如何在 Math Comp 库中形式化序数。

关键要素是使用 >

的计算定义

Answer 2

我不确定这是 Enrico 的想法，但这是一种可能的方法，使用 mathcomp 有限类型（支持计算）而不是 nat 和 ssreflect 战术语言。请注意，I_n.+1 是大小为 n+1 的有限类型的序数，即从 0 到 n 的自然数。

From mathcomp Require Import all_ssreflect.

Definition Test n (s : exists x : 'I_n.+1, x > 1) := true.

Lemma exists_gt_1 n (lt1n : 1 < n) : exists x : 'I_n.+1, x > 1.
Proof. by exists ord_max. Qed.

Eval compute in @Test 2 (exists_gt_1 2 is_true_true).
Eval compute in @Test 10000 (exists_gt_1 10000 is_true_true).

Answer 3

对于 (1)，您不必一直递归 10000 的一元定义：您只需执行两步即可：

Lemma pLotsGt1 : 10000 > 1.
Proof.
  apply le_n_S, le_n_S, Nat.le_0_l.
Qed.

不幸的是，证明项仍然相当大：

pLotsGt1 = 
le_n_S 1 (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (...)))))))))))))))))))))))
  (le_n_S 0 (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (...))))))))))))))))))))))
     (Nat.le_0_l (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (...)))))))))))))))))))))))
     : Init.Nat.of_num_uint
         (Number.UIntDecimal (Decimal.D1 (Decimal.D0 (Decimal.D0 (Decimal.D0 (Decimal.D0 Decimal.Nil)))))) >
       1

因为 le_n_S 将（一元编码的）大数作为其参数之一。

编辑：进一步观察，我注意到 Coq 实际上将像这样的大数字表示为数字列表。你可以在上面看到它，我们在基本上是列表 [1, 0, 0, 0, 0] 的地方调用 of_num_uint。展开一点，of_num_uint 归结为对 Init.Nat.tail_addmul 的调用，它有一个规范引理：

Nat.tail_addmul_spec: forall r n m : nat, Nat.tail_addmul r n m = r + n * m

因此您实际上可以使用数字列表上的决策过程来处理您的示例，这将避免在任何时候必须构建大的一元扩展。

当然，这首先取决于您的“随机”数字的来源。大概不是来自源代码中的数字文字，所以您可能无论如何都是从 nat 开始的。

如何为 Coq 中的 sigma 类型证明更短的 nat 比较，如 10000 > 1？

How to prove shorter nat comparisons like 10000 > 1 for sigma types in Coq?

coq