helm/coq-contribs/LAMBDA-TYPES/subst1_subst1.v

   1 (*#* #stop file *)
   2
   3 Require subst0_subst0.
   4 Require subst1_defs.
   5
   6    Section subst1_subst1. (**************************************************)
   7
   8       Theorem subst1_subst1: (t1,t2,u2:?; j:?) (subst1 j u2 t1 t2) ->
   9                              (u1,u:?; i:?) (subst1 i u u1 u2) ->
  10                              (EX t | (subst1 j u1 t1 t) & (subst1 (S (plus i j)) u t t2)).
  11       Intros until 1; XElim H; Clear t2.
  12 (* case 1: subst1_refl on first premise *)
  13       XEAuto.
  14 (* case 2: subst1_single on first premise *)
  15       Intros until 2; InsertEq H0 u2; XElim H0; Clear y; Intros.
  16 (* case 2.1: subst1_refl on second premise *)
  17       Rewrite H0; Clear H0 u1; XEAuto.
  18 (* case 2.2: subst1_single on second premise *)
  19       Rewrite H1 in H0; Clear H1 t0; Subst0Subst0; XEAuto.
  20       Qed.
  21
  22       Theorem subst1_subst1_back: (t1,t2,u2:?; j:?) (subst1 j u2 t1 t2) ->
  23                                   (u1,u:?; i:?) (subst1 i u u2 u1) ->
  24                                   (EX t | (subst1 j u1 t1 t) & (subst1 (S (plus i j)) u t2 t)).
  25       Intros until 1; XElim H; Clear t2.
  26 (* case 1: subst1_refl on first premise *)
  27       XEAuto.
  28 (* case 2: subst1_single on first premise *)
  29       Intros until 2; XElim H0; Clear u1; Intros;
  30       Try Subst0Subst0; XEAuto.
  31       Qed.
  32
  33       Theorem subst1_trans: (t2,t1,v:?; i:?) (subst1 i v t1 t2) ->
  34                             (t3:?) (subst1 i v t2 t3) ->
  35                             (subst1 i v t1 t3).
  36       Intros until 1; XElim H; Clear t2.
  37 (* case 1: subst1_refl on first premise *)
  38       XEAuto.
  39 (* case 2: subst1_single on first premise *)
  40       Intros until 2; XElim H0; Clear t3; XEAuto.
  41       Qed.
  42
  43    End subst1_subst1.
  44
  45       Hints Resolve subst1_trans : ltlc.
  46
  47       Tactic Definition Subst1Subst1 :=
  48          Match Context With
  49             | [ H1: (subst1 ?0 ?1 ?2 ?3); H2: (subst1 ?4 ?5 ?6 ?1) |- ? ] ->
  50                LApply (subst1_subst1 ?2 ?3 ?1 ?0); [ Intros H_x | XAuto ];
  51                LApply (H_x ?6 ?5 ?4); [ Clear H_x; Intros H_x | XAuto ];
  52                XElim H_x; Intros
  53             | [ H1: (subst1 ?0 ?1 ?2 ?3); H2: (subst0 ?4 ?5 ?6 ?1) |- ? ] ->
  54                LApply (subst1_subst1 ?2 ?3 ?1 ?0); [ Intros H_x | XAuto ];
  55                LApply (H_x ?6 ?5 ?4); [ Clear H_x; Intros H_x | XAuto ];
  56                XElim H_x; Intros
  57             | [ H1: (subst1 ?0 ?1 ?2 ?3); H2: (subst1 ?4 ?5 ?1 ?6) |- ? ] ->
  58                LApply (subst1_subst1_back ?2 ?3 ?1 ?0); [ Intros H_x | XAuto ];
  59                LApply (H_x ?6 ?5 ?4); [ Clear H_x; Intros H_x | XAuto ];
  60                XElim H_x; Intros.