Coq

Question

我试图使用 Coq 的 listSet 来创建 nats 的 set。但是，我运行在向集合中添加成员时遇到了问题。

这是我运行宁的代码。

Require Import ListSet Nat.

Axiom eq_dec : forall x y : nat, {x = y} + {x <> y}.

Compute (set_add eq_dec 0 (set_add eq_dec 0 nil)).

当运行时，输出为

= if eq_dec 0 0 then (0 :: nil)%list else (0 :: 0 :: nil)%list : set nat

现在，我知道为什么 我在输出中得到 if-else 语句。这是因为我只告诉 Coq nats 上的相等性是可判定的，但与评估相等性无关。我也知道如何比较两个 nats。代码如下。

Fixpoint nats_equal (m n : nat) : bool :=
  match m, n with
    | 0, 0 => true
    | 0, _ => false
    | _, 0 => false
    | S m', S n' => nats_equal m' n'
  end.

但是，我无法将两者串在一起以获得所需的输出，即

(0 :: nil)%list : set nat

我将不胜感激。

Answer 1

您的函数 nats_equal 实际上并不是您编写的 eq_dec 公理的实现，因为它 returns 是一个没有相关证明的布尔值。您可以将公理转化为定义，使用 Coq 的策略来创建定义。把 Defined. 放在最后意味着定义是透明的，这样 Coq 就可以用它来计算，但除此之外，这与你开始一个 Theorem，证明它，并以 [= 结束它是一样的16=].

Definition eq_dec : forall x y : nat, {x = y} + {x <> y}.
  decide equality.
Defined.

在这种情况下，证明很容易，因为 Coq 有一个内置的策略来证明可判定的相等性，它甚至适用于递归类型。

也就是说，nats 的可判定相等性已经在标准库中，因此您无需自己定义它：

(* how to even search for the type in eq_dec? *)
Locate "{".
(* Notation
"{ A } + { B }" := sumbool A B : type_scope (default interpretation)
*)

(* now we know what the notation means and can search for it: *)
Search sumbool nat.
(* PeanoNat.Nat.eq_dec: forall n m : nat, {n = m} + {n <> m} *)

(* alternately, we can use some more specific searches: *)
Search (forall (_ _:nat), {_ = _} + {_ <> _}).
Search ({@eq nat _ _} + {_ <> _}).
(* same as above, but use special notation for equality at a specific type *)
Search ({_ = _ :> nat} + {_ <> _}).

如果您导入 PeanoNat，您可以使用更好的名称来引用它 Nat.eq_dec。

Coq - 压倒平等的概念来添加元素到集合

Coq - overriding notion of equality to add elements to set