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

   1 (*#* #stop file *)
   2
   3 Require lift_gen.
   4 Require subst0_gen.
   5 Require subst0_confluence.
   6 Require subst1_defs.
   7 Require subst1_gen.
   8
   9    Section subst1_confluence. (**********************************************)
  10
  11       Theorem subst1_confluence_neq: (t0,t1,u1:?; i1:?) (subst1 i1 u1 t0 t1) ->
  12                                      (t2,u2:?; i2:?) (subst1 i2 u2 t0 t2) ->
  13                                      ~i1=i2 ->
  14                                      (EX t | (subst1 i2 u2 t1 t) &
  15                                              (subst1 i1 u1 t2 t)
  16                                      ).
  17       Intros until 1; XElim H; Clear t1; Intros.
  18 (* case 1; subst1_refl *)
  19       XEAuto.
  20 (* case 2; subst1_single *)
  21       XElim H0; Intros; Try Subst0Confluence; XEAuto.
  22       Qed.
  23
  24       Theorem subst1_confluence_eq : (t0,t1,u:?; i:?) (subst1 i u t0 t1) ->
  25                                      (t2:?) (subst1 i u t0 t2) ->
  26                                      (EX t | (subst1 i u t1 t) &
  27                                              (subst1 i u t2 t)
  28                                      ).
  29       Intros until 1; XElim H; Intros.
  30 (* case 1; subst1_refl *)
  31       XEAuto.
  32 (* case 2; subst1_single *)
  33       XElim H0; Intros;
  34       Try Subst0Confluence; Try Rewrite H0; XEAuto.
  35       Qed.
  36
  37       Theorem subst1_confluence_lift: (t0,t1,u:?; i:?) (subst1 i u t0 (lift (1) i t1)) ->
  38                                       (t2:?) (subst1 i u t0 (lift (1) i t2)) ->
  39                                       t1 = t2.
  40       Intros until 1; InsertEq H '(lift (1) i t1); XElim H; Clear y; Intros.
  41 (* case 1: subst1_refl *)
  42       Rewrite H in H0; Clear H t0.
  43       Subst1Gen; SymEqual; LiftGen; XEAuto.
  44 (* case 2: subst1_single *)
  45       Rewrite H0 in H; Clear H0 t2.
  46       InsertEq H1 '(lift (1) i t3); XElim H0; Clear y; Intros.
  47 (* case 2.1: subst1_refl *)
  48       Rewrite H0 in H; Clear H0 t0; Subst0Gen.
  49 (* case 2.2: subst1_single *)
  50       Rewrite H1 in H0; Clear H1 t2; Subst0ConfluenceLift; XAuto.
  51       Qed.
  52
  53    End subst1_confluence.
  54
  55       Tactic Definition Subst1Confluence :=
  56          Match Context With
  57             | [ H0: (subst1 ?1 ?2 ?3 (lift (1) ?1 ?4));
  58                 H1: (subst1 ?1 ?2 ?3 (lift (1) ?1 ?5)) |- ? ] ->
  59               LApply (subst1_confluence_lift ?3 ?4 ?2 ?1); [ Clear H0; Intros H0 | XAuto ];
  60               LApply (H0 ?5); [ Clear H0; Intros | XAuto ]
  61             | [ H0: (subst1 ?1 ?2 ?3 ?4);
  62                 H1: (subst1 ?1 ?2 ?3 ?5) |- ? ] ->
  63               LApply (subst1_confluence_eq ?3 ?4 ?2 ?1); [ Clear H0; Intros H0 | XAuto ];
  64               LApply (H0 ?5); [ Clear H0; Intros H0 | XAuto ];
  65               XElim H0; Intros
  66             | [ H0: (subst0 ?1 ?2 ?3 ?4);
  67                 H1: (subst1 ?1 ?2 ?3 ?5) |- ? ] ->
  68               LApply (subst1_confluence_eq ?3 ?4 ?2 ?1); [ Clear H0; Intros H0 | XAuto ];
  69               LApply (H0 ?5); [ Clear H0; Intros H0 | XAuto ];
  70               XElim H0; Intros
  71             | [ H0: (subst1 ?1 ?2 ?3 ?4);
  72                 H1: (subst1 ?5 ?6 ?3 ?7) |- ? ] ->
  73               LApply (subst1_confluence_neq ?3 ?4 ?2 ?1); [ Clear H0; Intros H0 | XAuto ];
  74               LApply (H0 ?7 ?6 ?5); [ Clear H0 H1; Intros H0 | XAuto ];
  75               LApply H0; [ Clear H0; Intros H0 | XAuto ];
  76               XElim H0; Intros
  77             | [ H0: (subst0 ?1 ?2 ?3 ?4);
  78                 H1: (subst1 ?5 ?6 ?3 ?7) |- ? ] ->
  79               LApply (subst1_confluence_neq ?3 ?4 ?2 ?1); [ Clear H0; Intros H0 | XAuto ];
  80               LApply (H0 ?7 ?6 ?5); [ Clear H0 H1; Intros H0 | XAuto ];
  81               LApply H0; [ Clear H0; Intros H0 | XAuto ];
  82               XElim H0; Intros.