Coq 案例分析和重写函数返回子集类型

Question

我正在做这个关于使用子集类型编写认证函数的简单练习。思路是先写一个前驱函数

pred : forall  (n : {n : nat | n > 0}), {m : nat | S m = n.1}.

然后使用这个定义给出一个函数

pred2 : forall (n : {n : nat | n > 1}), {m : nat | S (S m) = n.1}.

第一个没问题。这是我的代码

Program Definition pred (n : {n : nat | n > 0}) : {m : nat | S m = n.1} :=
  match n with
  | O => _
  | S n' => n'
  end.
Next Obligation. elimtype False. compute in H. inversion H. Qed.

但是我无法计算出第二个定义。我试着写这些定义

Program Definition pred2 (n : {n : nat | n > 1}) : {m : nat | S (S m) = n.1} 
:= pred (pred n).

我设法证明了前两项义务

Next Obligation. apply (gt_trans n 1 0). assumption. auto. Qed.
Next Obligation. 
  destruct pred.  
  simpl.
  simpl in e. 
  rewrite <- e in H.
  apply gt_S_n in H; assumption.
Qed.

但是对于最后一项义务，我被卡住了，因为当我尝试对 pred 的 return 类型进行案例分析时，目标中没有重写新的假设。

我尝试了以下策略但没有结果。

destruct (pred (n: pred2_obligation_1 (n ; H))).

destruct (pred (n; pred2_obligation_1 (n ; H))) eqn:?.
rewrite Heqs.

我知道我可以直接写 pred2，但我的想法是使用和组合函数 pred。

Answer 1

之所以destruct没有任何效果，可能是因为您要进行案例分析的目标没有出现在目标中。该术语的隐式参数可能与目标中该术语的隐式参数不匹配。无论哪种方式，您都无法在不使目标类型错误的情况下对该术语进行案例分析。

但您可以通过 n 上的案例分析来证明该义务。

Next Obligation.
destruct n.
inversion H.
destruct n.
inversion H.
subst.
inversion H1.
cbn.
eauto.
Qed.

我也能够证明一些辅助定理，但由于类型依赖性，我无法使用它们。

Theorem T1 : forall s1, S (` (pred s1)) = ` s1.
Proof. intros [[| n1] H1]. inversion H1. cbn. eauto. Qed.

Theorem T2 : forall T1 (P1 : T1 -> Prop) s1 H1, (forall x1 (H1 H2 : P1 x1), H1 = H2) -> exist P1 (` s1) H1 = s1.
Proof. intros ? ? [x1 H1] H2 H3. cbn in *. rewrite (H3 _ H1 H2). eauto. Qed.

我从未见过 destruct 用于函数。我很惊讶 Coq 没有抱怨那个函数不是归纳定义的。

Coq 案例分析和重写函数返回子集类型

Coq case analysis and rewrite with function returning subset types

types

analysis

case

subset

coq