Coq - индукция в списках с функцией, примененной к каждому элементу

Question

Пытаюсь доказать, что применение функции f к каждому элементу из двух списков приводит к аналогичным rel_list списки, если они были первоначально связаны. у меня есть rel на элементы списка и доказали лемму Lemma1 что если два элемента находятся в rel, они в rel после того, как функция f применяется к обоим элементам. Я попробовал индукцию в списке и rel_list но после того, как базовый случай решен, я в конечном итоге с xL :: xL0 :: xlL0 = xL0 :: xlL0 или введите цикл. Пожалуйста, кто-нибудь подскажет мне, как закрыть доказательство. Спасибо,

Variable A:Type.    
Variable rel: A -> A -> Prop. 
Variable f: A -> A.

Lemma lemma1: forall n m n' m', 
 rel n m -> 
 n' = f n -> 
 m' = f m  -> 
 rel n' m'.
Proof. 
  ... 
 Qed

Inductive rel_list : list A -> list A -> Prop :=
| rel_list_nil : rel_list nil nil 
| rel_list_cons: forall x y xl yl, 
  rel x y ->  
  rel_list xl yl ->
  rel_list (x::xl) (y::yl).

Fixpoint f_list (xl: list A) : list A :=
 match xl with 
  | nil => xl
  | x :: xl' => f x :: (f_list xl')
 end.

Lemma Lemma2: forall lL lR lL' lR', 
 rel_list lL lR -> 
 lL' = f_list lL -> 
 lR' = f_list lR  -> 
 rel_list lL' lR'.
Proof.
 intros ? ? ? ? Hsim HmL HmR.

Answer 1

Это можно легко показать, выполнив индукцию на вашем rel_list гипотеза. Вот обобщенная версия этого, которая использует функции в стандартной библиотеке:

Require Import Coq.Lists.List.

Section Lists.

Variables A1 A2 B1 B2 : Type.
Variables (RA : A1 -> A2 -> Prop) (RB : B1 -> B2 -> Prop).
Variables (f1 : A1 -> B1) (f2 : A2 -> B2).

Hypothesis parametric : forall a1 a2, RA a1 a2 -> RB (f1 a1) (f2 a2).

Lemma l : forall l1 l2, Forall2 RA l1 l2 ->
                        Forall2 RB (map f1 l1) (map f2 l2).
Proof.
  intros.
  induction H as [|a1 a2 l1 l2 HR H IH]; simpl; constructor; eauto.
Qed.

End Lists.