选项类型下表示"almost Properness"

Question

假设我们有一个类型A，上面有一个等价关系(===) : A -> A -> Prop。

除此之外还有一个函数 f : A -> option A。

正好这个函数f相对于equiv是"almost"Proper。 "almost" 我的意思是：

Lemma almost_proper :
  forall a1 a2 b1 b2 : A,
    a1 === a2 ->
    f a1 = Some b1 -> f a2 = Some b2 ->
    b1 === b2.

换句话说，如果 f 在两个输入上都成功，关系将被保留，但 f 可能仍然在一个上失败而在另一个上成功。我想简洁地表达这个概念，但在尝试这样做时提出了几个问题。

我看到三个问题的解决方案：

保持原样。不要使用 typeclasses，像上面那样证明引理。这看起来不太好，因为像 x = Some y 这样的先决条件的激增，这在证明引理时造成了复杂性。

当equiv_if_Some定义如下时，可以证明Proper ((===) ==> equiv_if_Some) f：

Inductive equiv_if_Some {A : Type} {EqA : relation A} `{Equivalence A EqA} : relation (option A) :=
| equiv_Some_Some : forall a1 a2, a1 === a2 -> equiv_if_Some (Some a1) (Some a2)
| equiv_Some_None : forall a, equiv_if_Some (Some a) None
| equiv_None_Some : forall a, equiv_if_Some None (Some a)
| equiv_None_None : equiv_if_Some None None.

这里的一个问题是这不再是等价关系（它不是传递的）。

如果使用一些合理的Almost_Proper class，可能可以证明Almost_Proper ((===) ==> (===)) f。我不确定那将如何工作。

表达这个概念的最佳方式是什么？我倾向于第二种，但也许还有更多选择？

对于变体 2 和 3，我描述的关系是否有预先存在的通用名称（因此可能是预先定义的）？ (equiv_if_Some 和 Almost_Proper)

Answer 1

2 如果它简化了你的证明。

它不是等价关系这一事实不会破坏交易，但它确实限制了它可以使用的上下文。

equiv_if_Some 定义为蕴涵（类似于它在 almost_proper 引理中出现的方式）可能比归纳类型更好。

您也可以考虑使用其他关系（作为 equiv_if_Some 的替代或结合）：

偏序，只能将 None 关联到 Some 而不能将 Some 关联到 None
部分等价关系，只能关联 Somes。

选项类型下表示"almost Properness"

Expressing "almost Properness" under option type

coq

typeclass

conceptual