如何证明关于对列表的定理

Question

我试图继续证明那是关于对的列表，但这似乎是不可能的。我应该如何继续解决这个定理？

Require Import List.

Fixpoint split (A B:Set)(x:list (A*B)) : (list A)*(list B) :=
 match x with
   |nil => (nil, nil)
   |cons (a,b) x1 => let (ta, tb) := split A B x1 in (a::ta, b::tb)
 end.

Theorem split_eq_len : 
forall (A B:Set)(x:list (A*B))(y:list A)(z:list B),(split A B x)=(y,z) -> 
length y = length z.
Proof.
intros A B x.
elim x.
simpl.
intros y z.
intros H.
injection H.
intros H1 H2.
rewrite <- H1.
rewrite <- H2.
reflexivity.
intros hx.
elim hx.
intros a b tx H y z.
simpl.
intro.
destruct (split A B tx).

Answer 1

我不想只给你一个证明，但这里有一个提示：

如果你使用 inversion H 而不是 injection H 和 subst 而不是用等式重写（subst 取任何等式 v = expr 其中 v 是一个变量，到处用 expr 代替 v；然后清除变量 v).

Answer 2

让我向您展示几个步骤，您可以采取这些步骤来推进您的证明。您最终处于这种证明状态：

H0 : (a :: l, b :: l0) = (y, z)
============================
length y = length z

此时应该很明显，y和z是一些非空列表。所以 injection H0.（或 Tej Chajed 建议的 inversion H0.）可以帮助你解决这个问题。

那你可以把目标改成

length l = length l0

结合使用简化和重写（这取决于您使用的确切策略，inversion 使它更简单）。您可能还会发现 f_equal 策略非常有用。此时您几乎完成了，因为您现在可以使用您的归纳假设。

如何证明关于对列表的定理

How to prove theorem about list of pairs

coq

coq-tactic