在 Coq 中生成一个函数，输出每个见证到存在唯一性公理

Question

所以，我很确定这应该是没有选择的可能。也许我错了。

这是我正在尝试做的一个最小的可重现示例：

Record MRE :=
{ set : Prop
; elem : set
; op : set -> set -> set
; subset : Prop
; subset_incl : subset -> set
; exist_axiom : forall (f : subset -> set), exists (x : set), f = fun y => op (subset_incl y) x
; uniq_axiom : forall (f : subset -> set), forall (x : set),
  f = (fun y => op (subset_incl y) x) -> x = ex_proj1 (exist_axiom f)
}.

我在这里使用了“内涵”平等，我不确定这是否使它过于严格。或许在唯一性公理的假设中需要使用“外延”等式才能做我想做的事情。

本质上，我们有这个结构的一个子集，因此从子集到结构的任何函数都可以使用内部操作 op 表示。很强属性，确实。由于这种表示是唯一的，因此应该有一种方法可以产生从结构到自身的任何给定函数的“导数”。这就是我的意思：

Definition witness_fcn : forall (M : MRE),
  forall (f : set M -> set M),
  exists (fn : set M -> set M),
  forall (x : subset M),
  (fun y => f (op M (subset_incl M x) y)) = (fun y => op M (subset_incl M x) (fn y)).
Proof.
intros M f.
pose (fn0 := fun y => exist_axiom M (fun x => f (op M (subset_incl M x) y))).
exists (fun y => ex_proj1 (fn0 y)).
intros x.
unfold fn0.

我完全不确定如何从那里继续证明，或者我是否正确地开始了它。

This question asks something similar, but without the assumption of uniqueness. The question is answered ，但并没有真正详细说明如何在证明中使用这样的唯一性属性。

假设，至少在常规数学中，它应该直接遵循 fn0 的定义，但我不确定如何表达。

Answer 1

在您提到的两个链接中，问题是 Coq 在命题（类型 Prop 的类型）和其他类型（类型 Set 或 [=14= 的类型）之间强制执行的隔离]), 其想法是运行的程序不需要证明。然而，在你的情况下 set M 和 subset M 都是命题，所以这种分离不是问题：正如你在定义 fn0 时看到的那样，Coq 非常乐意使用你的第一个组件存在类型来构建您正在寻找的功能。这是构造性数学的一个很好的观点：对 Prop 和 Type 之间的间隔取模，选择就是正确的！

而是问题出在证明的第二部分，即函数相等性的证明。 Coq 的一个微妙问题是函数相等不是外延的，即下面的公理通常不能被证明

Axiom fun_ext : forall {A B : Type} {f g : A -> B}, (forall x, f x = g x) -> f = g.

我的直觉是，Coq 中的函数相等性比输出相等性更细粒度，因为它区分了以不同方式计算相同输出的函数。这有点明智，因为您可能希望区分具有不同复杂性的函数。然而，这通常被认为是一个缺陷，Coq 类型理论中的各种 extensions/variations 试图提供该公理为真的系统。

使用这个公理，你的定理变得非常直接可证明（并不是说唯一性不起作用，只有存在性起作用）：

Definition witness_fcn : forall (M : MRE),
  forall (f : set M -> set M),
  exists (fn : set M -> set M),
  forall (x : subset M),
  (fun y => f (op M (subset_incl M x) y)) = (fun y => op M (subset_incl M x) (fn y)).
Proof.
intros M f.
pose (fn0 := fun y => exist_axiom M (fun x => f (op M (subset_incl M x) y))).
exists (fun y => ex_proj1 (fn0 y)).
intros x.
unfold fn0.
eapply fun_ext.
intros z.
destruct (fn0 z).
cbn.
etransitivity.
1: change (f (op M (subset_incl M x) z)) with ((fun x' => f (op M (subset_incl M x') z)) x) ; rewrite e.
all: reflexivity.
Defined.

我不完全确定你的定理在没有函数可扩展性的情况下无法证明，但对我来说这似乎很有可能。如果你想避免它，你应该尝试摆脱函数的相等性。通常的做法是直接使用逐点相等，即将 f = g 替换为 forall x, f x = g x.

在 Coq 中生成一个函数，输出每个见证到存在唯一性公理

Produce a function in Coq which outputs every witness to an existence-uniqueness axiom

proof

theorem-proving

coq