Coq 子类型

Question

我尝试在Coq中练习subtypes，并使用ssreflect来简化事情。但是我在重写子类型时总是运行遇到一些问题。例如：

Require Import Omega.
From mathcomp Require Import ssreflect ssrfun ssrbool ssrnat eqtype.

(* a type A to build X *)
Inductive A: Set :=
| mkA: nat -> A.

Definition getNat_A (a: A) :=
match a with
| mkA n => n
end.

Inductive X: Set :=
| r1 : A -> X.

(* subtype of X that satisfying some property *)
Definition Instantiated_X (x : X) : bool :=
  match x with
  | r1 a => (getNat_A a) > 10
end.

Definition iX : Set := {x:X | (Instantiated_X x)}.

(* rewrite constructor of X, stating the fact of elements of A, under certain condition creates element of iX *)
Program Definition r1_rewrite : A -> option iX :=
fun a: A =>
 match (Instantiated_X (r1 a)) with 
 | true => Some (exist _ (r1 a) _)
 | false => None
 end.

(* try to prove r1_rewrite is surjective *)
Example r1_rewrite_surj: 
forall t : iX, exists (a : A),
 match (r1_rewrite a) with
 | None => True
 | Some e => eq t e
 end.
 Proof.
  intros.
  destruct t eqn: caseiX.
  destruct x eqn: caseX.
  exists a.
  destruct (r1_rewrite a) eqn: r_res.
   - destruct (10 < getNat_A a) eqn: guard.
     destruct i0.
     destruct x0.
     unfold r1_rewrite in r_res.
     simpl in r_res.
     rewrite <- guard in r_res. (* <- stuck *)
Abort.

我不明白为什么它卡在那里。错误消息说：

Error: Abstracting over the term "true" leads to a term: ... 
which is ill-typed.

我认为 Coq 会在 r_res 中用 true 替换每次出现的 (10 < getNat_A a)，这会导致类似：

Some (exist (fun x : X => Instantiated_X x) (r1 a)
          (r1_rewrite_obligation_1 a Heq_anonymous) =
Some (exist (fun x : X => Instantiated_X x) (r1 a0) i0)

以及 proof irrelevance 和 r1 injectivity，让我的证明得以通过。所以，我想知道我能否得到一些关于如何在这种情况下按摩 r_res 以便于重写的指示。

编辑：删除 Eq 类型 class 及其实例以使示例更简洁

Answer 1

你的证明尝试的问题是你必须小心重写。这是一个可能的解决方案。

Example r1_rewrite_surj:
forall t : iX, exists (a : A),
 match (r1_rewrite a) with
 | None => True
 | Some e => eq t e
 end.
Proof.
move=> [[a] Pa]; exists a; rewrite /r1_rewrite.
move: (erefl _); rewrite {1 3}Pa.
by move=> e; rewrite (eq_irrelevance (r1_rewrite_obligation_1 _ _) Pa).
Qed.

看这里发生了什么有点棘手。在第一行之后，证明状态如下所示：

  a : A
  Pa : Instantiated_X (r1 a)
  ============================
  match
    (if Instantiated_X (r1 a) as b return b = Instantiated_X (r1 a) -> option iX
     then
      fun H : true = Instantiated_X (r1 a) =>
      Some (exist (fun x : X => Instantiated_X x) (r1 a) (r1_rewrite_obligation_1 a H))
     else fun _ : false = Instantiated_X (r1 a) => None) (erefl (Instantiated_X (r1 a)))
  with
  | Some e => exist (fun x : X => Instantiated_X x) (r1 a) Pa = e
  | None => True
  end

如果我们尝试在以下任何情况下用 Pa 重写，我们将得到类型错误。例如：

如果我们尝试替换第一次出现的 Instantiated_X (r1 a)，Coq 将不允许我们将 if 的结果应用到 (erefl (Instantiated_X (r1 a))。
我们可以通过用 true 替换第一次、第二次和第六次（erefl 上出现的 Instantiated_X (r1 a) 来解决上述问题。这也行不通，因为它会使 r1_rewrite_obligation_1 的应用程序类型错误。

解决方案是对 erefl 进行泛化（调用 move: (erefl _)），导致以下证明状态：

  forall e : Instantiated_X (r1 a) = Instantiated_X (r1 a),
  match
    (if Instantiated_X (r1 a) as b return b = Instantiated_X (r1 a) -> option iX
     then
      fun H : true = Instantiated_X (r1 a) =>
      Some (exist (fun x : X => Instantiated_X x) (r1 a) (r1_rewrite_obligation_1 a H))
     else fun _ : false = Instantiated_X (r1 a) => None) e
  with
  | Some e0 => exist (fun x : X => Instantiated_X x) (r1 a) Pa = e0
  | None => True
  end

可能不容易看到，但此时可以安全地用 Pa 重写以替换第一次和第三次出现的 Instantiated_X (r1 a)，并允许 if减少。然后我们可以通过诉诸证明布尔相等性的无关性来得出结论。

不用说，以这种方式推理打字问题是一场噩梦。正如 ejgallego 指出的那样，在这种情况下重用 ssreflect 的子类型化机制要容易得多。例如：

(* Other definitions remain the same *)
Definition r1_rewrite a : option iX := insub (r1 a).

Example r1_rewrite_surj:
forall t : iX, exists (a : A),
 match (r1_rewrite a) with
 | None => True
 | Some e => eq t e
 end.
Proof.
by move=> [[a] Pa]; exists a; rewrite /r1_rewrite insubT.
Qed.

insub 函数是 r1_rewrite 的通用版本。它检查定义子类型的属性是否成立，如果成立，则将该对象与相应的证明配对。 insubT 引理说 insub returns 一个 Some 当属性成立时。

Coq 子类型

Subtype with Coq

subtype

coq