types - 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 的返回类型进行案例分析时，目标中没有重写新的假设。

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

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 没有提示该函数不是归纳定义的。