在Coq中证明` `forall x xs ys，subseq (x :：xs) ys -> subseq xs‘

Question

我有以下定义

Inductive subseq : list nat -> list nat -> Prop :=
| empty_subseq : subseq [] []
| add_right : forall y xs ys, subseq xs ys -> subseq xs (y::ys)
| add_both : forall x y xs ys, subseq xs ys -> subseq (x::xs) (y::ys)
.

利用这个，我想证明下面的引理

Lemma del_l_preserves_subseq : forall x xs ys, subseq (x :: xs) ys -> subseq xs ys.

所以，我试着通过做subseq (x :: xs) ys来查看destruct H的证据。

Proof.
  intros. induction H.

3 subgoals (ID 209)

  x : nat
  xs : list nat
  ============================
  subseq xs [ ]

subgoal 2 (ID 216) is:
 subseq xs (y :: ys)
subgoal 3 (ID 222) is:
 subseq xs (y :: ys)

为什么第一个子目标要求我证明subseq xs []？destruct的策略难道不应该知道证明不能是形式empty_subseq，因为类型包含x :: xs而不是[]

一般来说，我如何证明我试图证明的引理？

Answer 1

难道毁灭策略不应该知道证明不能是形式empty_subseq，因为类型包含x :：xs而不是[]？

事实上，destruct并不知道那么多。它只是在x :: xs和[]的情况下用[]和[]替换了empty_subseq和[]。特别是，这常常导致上下文中的信息丢失。更好的替代办法：

• 使用inversion而不是destruct。
• 使用remember确保subseq的两种类型索引都是destruct之前的变量。(remember (x :: xs) as xxs in H.)这种更明确的目标管理在induction中也能很好地工作。

Answer 2

李姚的回答其实很有用。这是引理的证明。

Lemma del_l_preserves_subseq : forall x xs ys, subseq (x :: xs) ys -> subseq xs ys.
Proof.
  intros x xs ys.
  induction ys as [|y ys'].
  - intros. inversion H. (* Inversion will detect that no constructor matches the type of H *)
  - intros. inversion H. (* Inversion will automatically discharge the first case *)
    + (* When [subseq (x :: xs) ys'] holds *)
      apply IHys' in H2. now apply add_right.
    + (* When [subseq xs ys'] holds *)
      now apply add_right.
Qed