如何证明 Coq 中的证明定义

Question

我目前正在使用 Coq，我遇到了一个我不知道如何解决的问题。

假设我们正在使用给定的类型，我将以 nat 为例，我想使用一个可能会失败的函数 f。为了弥补失败，我们将 f 定义为 nat -> option nat.

类型

现在我有一个给定的假设H: nat -> bool，在这个假设下 f 不会失败，我什至已经证明了引理

Lemma no_error_in_f : forall (n:nat), H n = true -> exists (u:nat), f n = Some u.

我想定义一个函数 g: nat->nat 如果满足 H n 则给出 f 在 n 上的结果，否则只给出 n .这个函数应该定义得很好，但我不知道如何正确定义它。如果我尝试一些天真的事情 Definition g (n:nat) := if H n then f n else n.，打字系统有问题。

有谁知道如何收集所有元素并告诉系统定义是合法的？

Answer 1

你的开发有两个问题。一个是你不能使用 no_error_in_f 在 Coq 中定义 g 而不假设额外的公理，因为 Coq 不允许从证明中提取计算信息（查看 for more details). Another problem is that you can't use H in an if expression, because it returns a Prop instead of a bool (check 了解更多细节）。

Answer 2

我找到了一种方法，如果有人感兴趣，这是我的解决方案：

Definition g (n:nat) :nat := (match (H n) as a return a = H n -> nat with | true => (fun H_true => (match (f n) as b return b = f n -> nat with | Some u => (fun _ => u) | None => (fun H1 => False_rec _ (no_error_in_f H_true H1)) end) (eq_refl f n)) | false => n end) (eq_refl H n).

对于那些想知道它是什么意思的人，False_rec 将 False 的证明作为第二个参数，并证明匹配是不可能的。术语

(match (f n) as b return b = f n -> nat with | Some u => (fun _ => u) | None => (fun H1 => False_rec _ (no_error_in_f H_true H1)) end) (eq_refl f n)) 具有类型 f n = f n-> nat，当我将其应用于证明 eq_refl (f n)（这是 f n = f n 的证明，因此类型为 f n = f n）时，我获得了 nat。这是一个让我获得 H1 的技巧，它是 f n = None 使用相等的自反性和 pattern-matching 获得的证明，我将在 [=] 的证明中使用18=].

另一场比赛也是如此。

Answer 3

我在这里给出了一个解决方案，它与问题中给出的假设相同。

Axiom f : nat -> option nat.
Axiom H : nat -> bool.
Axiom no_error_in_f : forall n,
  H n = true -> exists u, f n = Some u.

Lemma no_error_in_f_bis : forall n,
  H n = true -> f n <> None.
Proof.
  intros. apply no_error_in_f in H0. destruct H0. rewrite H0. discriminate.
Qed.

Definition g n :=
  match H n as b return H n = b -> _ with
  | true => fun H =>
    match f n as f0 return f n = f0 -> _ with
    | Some n0 => fun _ => n0
    | None => fun H0 => match no_error_in_f_bis n H H0 with end
    end eq_refl
  | false => fun _ => n
  end eq_refl.

我用了一个比no_error_in_f更方便证明False的引理。注意这个函数的两个思想（使用[=14=的return构造，破坏False的一个证明来表明分支不可达）在这里解释：http://adam.chlipala.net/cpdt/html/Subset.html.

如何证明 Coq 中的证明定义

How to prove a prove definition in Coq

types

proof

definition

pattern-matching

coq