卡在一个很简单的函数的构造中

Question

我正在学习 Coq。我被困在一个很愚蠢的问题上（没有动机，真的很愚蠢）。我想构建一个从 ]2,+oo] 到映射 x 到 x-3 的整数集的函数。这应该很简单...在我知道的任何语言中，它很简单。但不是在 Coq 中。首先，我写（我解释了很多细节，以便有人可以解释我在 Coq 的行为中不理解的地方）

Definition f : forall n : nat, n > 2 -> nat.

我有一个子目标

  ============================
   forall n : nat, n > 2 -> nat

这意味着 Coq 想要一个从 n>2 的证明到整数集的映射。美好的。所以我想告诉它 n = 3 + p 对于某个整数 p，然后 return 整数 p。我写：

intros n H.

然后我得到 context/subgoal

  n : nat
  H : n > 2
  ============================
   nat

然后我想我已经通过

证明了某个整数 p 的 n = 3 + p

cut(exists p, 3 + p = n).

我得到 context/subgoal

  n : nat
  H : n > 2
  ============================
   (exists p : nat, 3 + p = n) -> nat

subgoal 2 (ID 6) is:
 exists p : nat, 3 + p = n

我将上下文中的假设移动

intro K.

我得到：

  n : nat
  H : n > 2
  K : exists p : nat, 3 + p = n
  ============================
   nat

subgoal 2 (ID 6) is:
 exists p : nat, 3 + p = n

稍后我会证明p的存在。现在我想通过精确的 p 来完成证明。所以我需要先做一个

destruct K as (p,K).

我收到错误消息

Error: Case analysis on sort Set is not allowed for inductive definition ex.

我卡住了。

Answer 1

你完全正确！用任何合理的编程语言编写这个函数应该很容易，幸运的是，Coq 也不例外。

在你的情况下，通过简单地忽略你提供的证明参数来定义你的函数要容易得多：

Definition f (n : nat) : nat := n - 3.

您可能会想 "but wait a second, the natural numbers aren't closed under subtraction, so how can this make sense?"。好吧，在 Coq 中，自然数的减法并不是真正的减法：它实际上是 truncated。例如，如果您尝试从 2 中减去 3，您将得到 0 作为答案：

Goal 2 - 3 = 0. reflexivity. Qed.

这在实践中意味着您始终可以 "subtract" 两个自然数并得到一个自然数，但是为了使这种减法有意义，第一个参数需要大于第二。然后我们得到如下引理（在 standard library 中可用）：

le_plus_minus_r : forall n m, n <= m -> n + (m - n) = m

在大多数情况下，使用部分正确的函数（例如减法的这个定义）就足够了。但是，如果您愿意，可以限制 f 的域以使其属性更令人愉悦。我冒昧地使用 ssreflect 库执行以下脚本，这使得编写此类函数更加容易：

Require Import Ssreflect.ssreflect Ssreflect.ssrfun Ssreflect.ssrbool.
Require Import Ssreflect.ssrnat Ssreflect.eqtype.

Definition f (n : {n | 2 < n}) : nat :=
  val n - 3.

Definition finv (m : nat) : {n | 2 < n} :=
  Sub (3 + m) erefl.

Lemma fK : cancel f finv.
Proof.
move=> [n Pn] /=; apply/val_inj=> /=.
by rewrite /f /= addnC subnK.
Qed.

Lemma finvK : cancel finv f.
Proof.
by move=> n; rewrite /finv /f /= addnC addnK.
Qed.

现在，f 将大于 2 的自然数 n 作为参数（{x : T | P x} 形式是 [=19= 的语法糖] 标准库中的类型，用于形成像子集一样工作的类型）。通过限制参数类型，我们可以编写一个反函数 finv 接受任意 nat 和 returns 另一个大于 2 的数字。然后，我们可以证明引理 fK 和 finvK，它们断言 fK 和 finvK 是互逆的。

在f的定义中，我们使用了val，这是ssreflect的习惯用法，用于从{n | 2 < n}等类型的成员中提取元素。 finv 上的 Sub 函数则相反，将自然数 n 与 2 < n 的证明打包并返回 {n | 2 < n} 的元素。在这里，我们关键地依赖于 < 在 ssreflect 中表示为布尔计算这一事实，因此 Coq 可以使用其计算规则来检查 erefl，true = true 的证明，也是 2 < 3 + m.

的有效证明

总而言之，您最后收到的神秘错误消息与 Coq 管理计算类型的规则有关，在 Type 中存在，命题类型在 Prop 中存在。 Coq 的规则禁止您使用命题证明来构建具有计算内容（例如自然数）的元素，除非在非常特殊的情况下。如果你愿意，你仍然可以使用 {p | 3 + p = n} 而不是 exists p, 3 + p = n 来完成你的定义——两者的意思相同，除了前者位于 Type 而后者位于 Prop.

卡在一个很简单的函数的构造中

Stuck in the construction of a very simple function

coq