陷入无限反转循环 Coq

Question

我有一个归纳关系，如下所示，标题为后缀。我试图证明相关定理 suffix_app。我的一般想法是使用 后缀 xs ys 的事实来表明 xs 等于 ys 或者它是一系列元素 cons进入ys。

Require Import Coq.Lists.List.
Import ListNotations.

Inductive suffix {X : Type} : list X -> list X -> Prop :=
  | suffix_end : forall xs,
          suffix xs xs
  | suffix_step : forall x xs ys,
          suffix xs ys ->
          suffix (x :: xs) ys.

Theorem suffix_app : forall (X: Type) (x:X) (xs ys: list X),
  suffix xs ys -> 
  exists ws, xs = ws ++ ys.
Proof.
  intros.
  inversion H.
  - exists []. reflexivity.
  -

但是，当我使用反转时，实际上没有办法 "arriving" 等于 ys 的项。因此，我停留在代码中当前看到的位置。

Answer 1

您的证明只需对任何结构进行归纳，例如：

Theorem suffix_app (X: Type) (xs ys: list X) :
  suffix xs ys -> exists ws, xs = ws ++ ys.
Proof.
induction 1 as [|x xsp ysp hs [zs zeq]]; [now exists []|].
now exists (x :: zs); rewrite zeq.
Qed.

出于实际原因，您可能希望使用不同的计算版本的后缀。

陷入无限反转循环 Coq

Stuck in infinite inversion loop Coq

coq

theorem-proving