matita/matita/contribs/lambdadelta/basic_1/subst1/subst1.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 (* This file was automatically generated: do not edit *********************)
  16
  17 include "Basic-1/subst1/fwd.ma".
  18
  19 include "Basic-1/subst0/subst0.ma".
  20
  21 theorem subst1_subst1:
  22  \forall (t1: T).(\forall (t2: T).(\forall (u2: T).(\forall (j: nat).((subst1
  23 j u2 t1 t2) \to (\forall (u1: T).(\forall (u: T).(\forall (i: nat).((subst1 i
  24 u u1 u2) \to (ex2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda (t:
  25 T).(subst1 (S (plus i j)) u t t2)))))))))))
  26 \def
  27  \lambda (t1: T).(\lambda (t2: T).(\lambda (u2: T).(\lambda (j: nat).(\lambda
  28 (H: (subst1 j u2 t1 t2)).(subst1_ind j u2 t1 (\lambda (t: T).(\forall (u1:
  29 T).(\forall (u: T).(\forall (i: nat).((subst1 i u u1 u2) \to (ex2 T (\lambda
  30 (t0: T).(subst1 j u1 t1 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t0
  31 t)))))))) (\lambda (u1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda (_:
  32 (subst1 i u u1 u2)).(ex_intro2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda
  33 (t: T).(subst1 (S (plus i j)) u t t1)) t1 (subst1_refl j u1 t1) (subst1_refl
  34 (S (plus i j)) u t1)))))) (\lambda (t3: T).(\lambda (H0: (subst0 j u2 t1
  35 t3)).(\lambda (u1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda (H1: (subst1
  36 i u u1 u2)).(insert_eq T u2 (\lambda (t: T).(subst1 i u u1 t)) (\lambda (_:
  37 T).(ex2 T (\lambda (t0: T).(subst1 j u1 t1 t0)) (\lambda (t0: T).(subst1 (S
  38 (plus i j)) u t0 t3)))) (\lambda (y: T).(\lambda (H2: (subst1 i u u1
  39 y)).(subst1_ind i u u1 (\lambda (t: T).((eq T t u2) \to (ex2 T (\lambda (t0:
  40 T).(subst1 j u1 t1 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t0 t3)))))
  41 (\lambda (H3: (eq T u1 u2)).(eq_ind_r T u2 (\lambda (t: T).(ex2 T (\lambda
  42 (t0: T).(subst1 j t t1 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t0
  43 t3)))) (ex_intro2 T (\lambda (t: T).(subst1 j u2 t1 t)) (\lambda (t:
  44 T).(subst1 (S (plus i j)) u t t3)) t3 (subst1_single j u2 t1 t3 H0)
  45 (subst1_refl (S (plus i j)) u t3)) u1 H3)) (\lambda (t0: T).(\lambda (H3:
  46 (subst0 i u u1 t0)).(\lambda (H4: (eq T t0 u2)).(let H5 \def (eq_ind T t0
  47 (\lambda (t: T).(subst0 i u u1 t)) H3 u2 H4) in (ex2_ind T (\lambda (t:
  48 T).(subst0 j u1 t1 t)) (\lambda (t: T).(subst0 (S (plus i j)) u t t3)) (ex2 T
  49 (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda (t: T).(subst1 (S (plus i j)) u
  50 t t3))) (\lambda (x: T).(\lambda (H6: (subst0 j u1 t1 x)).(\lambda (H7:
  51 (subst0 (S (plus i j)) u x t3)).(ex_intro2 T (\lambda (t: T).(subst1 j u1 t1
  52 t)) (\lambda (t: T).(subst1 (S (plus i j)) u t t3)) x (subst1_single j u1 t1
  53 x H6) (subst1_single (S (plus i j)) u x t3 H7))))) (subst0_subst0 t1 t3 u2 j
  54 H0 u1 u i H5)))))) y H2))) H1))))))) t2 H))))).
  55 (* COMMENTS
  56 Initial nodes: 649
  57 END *)
  58
  59 theorem subst1_subst1_back:
  60  \forall (t1: T).(\forall (t2: T).(\forall (u2: T).(\forall (j: nat).((subst1
  61 j u2 t1 t2) \to (\forall (u1: T).(\forall (u: T).(\forall (i: nat).((subst1 i
  62 u u2 u1) \to (ex2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda (t:
  63 T).(subst1 (S (plus i j)) u t2 t)))))))))))
  64 \def
  65  \lambda (t1: T).(\lambda (t2: T).(\lambda (u2: T).(\lambda (j: nat).(\lambda
  66 (H: (subst1 j u2 t1 t2)).(subst1_ind j u2 t1 (\lambda (t: T).(\forall (u1:
  67 T).(\forall (u: T).(\forall (i: nat).((subst1 i u u2 u1) \to (ex2 T (\lambda
  68 (t0: T).(subst1 j u1 t1 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t
  69 t0)))))))) (\lambda (u1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda (_:
  70 (subst1 i u u2 u1)).(ex_intro2 T (\lambda (t: T).(subst1 j u1 t1 t)) (\lambda
  71 (t: T).(subst1 (S (plus i j)) u t1 t)) t1 (subst1_refl j u1 t1) (subst1_refl
  72 (S (plus i j)) u t1)))))) (\lambda (t3: T).(\lambda (H0: (subst0 j u2 t1
  73 t3)).(\lambda (u1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda (H1: (subst1
  74 i u u2 u1)).(subst1_ind i u u2 (\lambda (t: T).(ex2 T (\lambda (t0:
  75 T).(subst1 j t t1 t0)) (\lambda (t0: T).(subst1 (S (plus i j)) u t3 t0))))
  76 (ex_intro2 T (\lambda (t: T).(subst1 j u2 t1 t)) (\lambda (t: T).(subst1 (S
  77 (plus i j)) u t3 t)) t3 (subst1_single j u2 t1 t3 H0) (subst1_refl (S (plus i
  78 j)) u t3)) (\lambda (t0: T).(\lambda (H2: (subst0 i u u2 t0)).(ex2_ind T
  79 (\lambda (t: T).(subst0 j t0 t1 t)) (\lambda (t: T).(subst0 (S (plus i j)) u
  80 t3 t)) (ex2 T (\lambda (t: T).(subst1 j t0 t1 t)) (\lambda (t: T).(subst1 (S
  81 (plus i j)) u t3 t))) (\lambda (x: T).(\lambda (H3: (subst0 j t0 t1
  82 x)).(\lambda (H4: (subst0 (S (plus i j)) u t3 x)).(ex_intro2 T (\lambda (t:
  83 T).(subst1 j t0 t1 t)) (\lambda (t: T).(subst1 (S (plus i j)) u t3 t)) x
  84 (subst1_single j t0 t1 x H3) (subst1_single (S (plus i j)) u t3 x H4)))))
  85 (subst0_subst0_back t1 t3 u2 j H0 t0 u i H2)))) u1 H1))))))) t2 H))))).
  86 (* COMMENTS
  87 Initial nodes: 487
  88 END *)
  89
  90 theorem subst1_trans:
  91  \forall (t2: T).(\forall (t1: T).(\forall (v: T).(\forall (i: nat).((subst1
  92 i v t1 t2) \to (\forall (t3: T).((subst1 i v t2 t3) \to (subst1 i v t1
  93 t3)))))))
  94 \def
  95  \lambda (t2: T).(\lambda (t1: T).(\lambda (v: T).(\lambda (i: nat).(\lambda
  96 (H: (subst1 i v t1 t2)).(subst1_ind i v t1 (\lambda (t: T).(\forall (t3:
  97 T).((subst1 i v t t3) \to (subst1 i v t1 t3)))) (\lambda (t3: T).(\lambda
  98 (H0: (subst1 i v t1 t3)).H0)) (\lambda (t3: T).(\lambda (H0: (subst0 i v t1
  99 t3)).(\lambda (t4: T).(\lambda (H1: (subst1 i v t3 t4)).(subst1_ind i v t3
 100 (\lambda (t: T).(subst1 i v t1 t)) (subst1_single i v t1 t3 H0) (\lambda (t0:
 101 T).(\lambda (H2: (subst0 i v t3 t0)).(subst1_single i v t1 t0 (subst0_trans
 102 t3 t1 v i H0 t0 H2)))) t4 H1))))) t2 H))))).
 103 (* COMMENTS
 104 Initial nodes: 165
 105 END *)
 106
 107 theorem subst1_confluence_neq:
 108  \forall (t0: T).(\forall (t1: T).(\forall (u1: T).(\forall (i1:
 109 nat).((subst1 i1 u1 t0 t1) \to (\forall (t2: T).(\forall (u2: T).(\forall
 110 (i2: nat).((subst1 i2 u2 t0 t2) \to ((not (eq nat i1 i2)) \to (ex2 T (\lambda
 111 (t: T).(subst1 i2 u2 t1 t)) (\lambda (t: T).(subst1 i1 u1 t2 t))))))))))))
 112 \def
 113  \lambda (t0: T).(\lambda (t1: T).(\lambda (u1: T).(\lambda (i1:
 114 nat).(\lambda (H: (subst1 i1 u1 t0 t1)).(subst1_ind i1 u1 t0 (\lambda (t:
 115 T).(\forall (t2: T).(\forall (u2: T).(\forall (i2: nat).((subst1 i2 u2 t0 t2)
 116 \to ((not (eq nat i1 i2)) \to (ex2 T (\lambda (t3: T).(subst1 i2 u2 t t3))
 117 (\lambda (t3: T).(subst1 i1 u1 t2 t3))))))))) (\lambda (t2: T).(\lambda (u2:
 118 T).(\lambda (i2: nat).(\lambda (H0: (subst1 i2 u2 t0 t2)).(\lambda (_: (not
 119 (eq nat i1 i2))).(ex_intro2 T (\lambda (t: T).(subst1 i2 u2 t0 t)) (\lambda
 120 (t: T).(subst1 i1 u1 t2 t)) t2 H0 (subst1_refl i1 u1 t2))))))) (\lambda (t2:
 121 T).(\lambda (H0: (subst0 i1 u1 t0 t2)).(\lambda (t3: T).(\lambda (u2:
 122 T).(\lambda (i2: nat).(\lambda (H1: (subst1 i2 u2 t0 t3)).(\lambda (H2: (not
 123 (eq nat i1 i2))).(subst1_ind i2 u2 t0 (\lambda (t: T).(ex2 T (\lambda (t4:
 124 T).(subst1 i2 u2 t2 t4)) (\lambda (t4: T).(subst1 i1 u1 t t4)))) (ex_intro2 T
 125 (\lambda (t: T).(subst1 i2 u2 t2 t)) (\lambda (t: T).(subst1 i1 u1 t0 t)) t2
 126 (subst1_refl i2 u2 t2) (subst1_single i1 u1 t0 t2 H0)) (\lambda (t4:
 127 T).(\lambda (H3: (subst0 i2 u2 t0 t4)).(ex2_ind T (\lambda (t: T).(subst0 i1
 128 u1 t4 t)) (\lambda (t: T).(subst0 i2 u2 t2 t)) (ex2 T (\lambda (t: T).(subst1
 129 i2 u2 t2 t)) (\lambda (t: T).(subst1 i1 u1 t4 t))) (\lambda (x: T).(\lambda
 130 (H4: (subst0 i1 u1 t4 x)).(\lambda (H5: (subst0 i2 u2 t2 x)).(ex_intro2 T
 131 (\lambda (t: T).(subst1 i2 u2 t2 t)) (\lambda (t: T).(subst1 i1 u1 t4 t)) x
 132 (subst1_single i2 u2 t2 x H5) (subst1_single i1 u1 t4 x H4)))))
 133 (subst0_confluence_neq t0 t4 u2 i2 H3 t2 u1 i1 H0 (sym_not_eq nat i1 i2
 134 H2))))) t3 H1)))))))) t1 H))))).
 135 (* COMMENTS
 136 Initial nodes: 455
 137 END *)
 138
 139 theorem subst1_confluence_eq:
 140  \forall (t0: T).(\forall (t1: T).(\forall (u: T).(\forall (i: nat).((subst1
 141 i u t0 t1) \to (\forall (t2: T).((subst1 i u t0 t2) \to (ex2 T (\lambda (t:
 142 T).(subst1 i u t1 t)) (\lambda (t: T).(subst1 i u t2 t)))))))))
 143 \def
 144  \lambda (t0: T).(\lambda (t1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda
 145 (H: (subst1 i u t0 t1)).(subst1_ind i u t0 (\lambda (t: T).(\forall (t2:
 146 T).((subst1 i u t0 t2) \to (ex2 T (\lambda (t3: T).(subst1 i u t t3))
 147 (\lambda (t3: T).(subst1 i u t2 t3)))))) (\lambda (t2: T).(\lambda (H0:
 148 (subst1 i u t0 t2)).(ex_intro2 T (\lambda (t: T).(subst1 i u t0 t)) (\lambda
 149 (t: T).(subst1 i u t2 t)) t2 H0 (subst1_refl i u t2)))) (\lambda (t2:
 150 T).(\lambda (H0: (subst0 i u t0 t2)).(\lambda (t3: T).(\lambda (H1: (subst1 i
 151 u t0 t3)).(subst1_ind i u t0 (\lambda (t: T).(ex2 T (\lambda (t4: T).(subst1
 152 i u t2 t4)) (\lambda (t4: T).(subst1 i u t t4)))) (ex_intro2 T (\lambda (t:
 153 T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i u t0 t)) t2 (subst1_refl i u
 154 t2) (subst1_single i u t0 t2 H0)) (\lambda (t4: T).(\lambda (H2: (subst0 i u
 155 t0 t4)).(or4_ind (eq T t4 t2) (ex2 T (\lambda (t: T).(subst0 i u t4 t))
 156 (\lambda (t: T).(subst0 i u t2 t))) (subst0 i u t4 t2) (subst0 i u t2 t4)
 157 (ex2 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i u t4 t)))
 158 (\lambda (H3: (eq T t4 t2)).(eq_ind_r T t2 (\lambda (t: T).(ex2 T (\lambda
 159 (t5: T).(subst1 i u t2 t5)) (\lambda (t5: T).(subst1 i u t t5)))) (ex_intro2
 160 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i u t2 t)) t2
 161 (subst1_refl i u t2) (subst1_refl i u t2)) t4 H3)) (\lambda (H3: (ex2 T
 162 (\lambda (t: T).(subst0 i u t4 t)) (\lambda (t: T).(subst0 i u t2
 163 t)))).(ex2_ind T (\lambda (t: T).(subst0 i u t4 t)) (\lambda (t: T).(subst0 i
 164 u t2 t)) (ex2 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i
 165 u t4 t))) (\lambda (x: T).(\lambda (H4: (subst0 i u t4 x)).(\lambda (H5:
 166 (subst0 i u t2 x)).(ex_intro2 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda
 167 (t: T).(subst1 i u t4 t)) x (subst1_single i u t2 x H5) (subst1_single i u t4
 168 x H4))))) H3)) (\lambda (H3: (subst0 i u t4 t2)).(ex_intro2 T (\lambda (t:
 169 T).(subst1 i u t2 t)) (\lambda (t: T).(subst1 i u t4 t)) t2 (subst1_refl i u
 170 t2) (subst1_single i u t4 t2 H3))) (\lambda (H3: (subst0 i u t2
 171 t4)).(ex_intro2 T (\lambda (t: T).(subst1 i u t2 t)) (\lambda (t: T).(subst1
 172 i u t4 t)) t4 (subst1_single i u t2 t4 H3) (subst1_refl i u t4)))
 173 (subst0_confluence_eq t0 t4 u i H2 t2 H0)))) t3 H1))))) t1 H))))).
 174 (* COMMENTS
 175 Initial nodes: 729
 176 END *)
 177
 178 theorem subst1_confluence_lift:
 179  \forall (t0: T).(\forall (t1: T).(\forall (u: T).(\forall (i: nat).((subst1
 180 i u t0 (lift (S O) i t1)) \to (\forall (t2: T).((subst1 i u t0 (lift (S O) i
 181 t2)) \to (eq T t1 t2)))))))
 182 \def
 183  \lambda (t0: T).(\lambda (t1: T).(\lambda (u: T).(\lambda (i: nat).(\lambda
 184 (H: (subst1 i u t0 (lift (S O) i t1))).(insert_eq T (lift (S O) i t1)
 185 (\lambda (t: T).(subst1 i u t0 t)) (\lambda (_: T).(\forall (t2: T).((subst1
 186 i u t0 (lift (S O) i t2)) \to (eq T t1 t2)))) (\lambda (y: T).(\lambda (H0:
 187 (subst1 i u t0 y)).(subst1_ind i u t0 (\lambda (t: T).((eq T t (lift (S O) i
 188 t1)) \to (\forall (t2: T).((subst1 i u t0 (lift (S O) i t2)) \to (eq T t1
 189 t2))))) (\lambda (H1: (eq T t0 (lift (S O) i t1))).(\lambda (t2: T).(\lambda
 190 (H2: (subst1 i u t0 (lift (S O) i t2))).(let H3 \def (eq_ind T t0 (\lambda
 191 (t: T).(subst1 i u t (lift (S O) i t2))) H2 (lift (S O) i t1) H1) in (let H4
 192 \def (sym_eq T (lift (S O) i t2) (lift (S O) i t1) (subst1_gen_lift_eq t1 u
 193 (lift (S O) i t2) (S O) i i (le_n i) (eq_ind_r nat (plus (S O) i) (\lambda
 194 (n: nat).(lt i n)) (le_n (plus (S O) i)) (plus i (S O)) (plus_sym i (S O)))
 195 H3)) in (lift_inj t1 t2 (S O) i H4)))))) (\lambda (t2: T).(\lambda (H1:
 196 (subst0 i u t0 t2)).(\lambda (H2: (eq T t2 (lift (S O) i t1))).(\lambda (t3:
 197 T).(\lambda (H3: (subst1 i u t0 (lift (S O) i t3))).(let H4 \def (eq_ind T t2
 198 (\lambda (t: T).(subst0 i u t0 t)) H1 (lift (S O) i t1) H2) in (insert_eq T
 199 (lift (S O) i t3) (\lambda (t: T).(subst1 i u t0 t)) (\lambda (_: T).(eq T t1
 200 t3)) (\lambda (y0: T).(\lambda (H5: (subst1 i u t0 y0)).(subst1_ind i u t0
 201 (\lambda (t: T).((eq T t (lift (S O) i t3)) \to (eq T t1 t3))) (\lambda (H6:
 202 (eq T t0 (lift (S O) i t3))).(let H7 \def (eq_ind T t0 (\lambda (t:
 203 T).(subst0 i u t (lift (S O) i t1))) H4 (lift (S O) i t3) H6) in
 204 (subst0_gen_lift_false t3 u (lift (S O) i t1) (S O) i i (le_n i) (eq_ind_r
 205 nat (plus (S O) i) (\lambda (n: nat).(lt i n)) (le_n (plus (S O) i)) (plus i
 206 (S O)) (plus_sym i (S O))) H7 (eq T t1 t3)))) (\lambda (t4: T).(\lambda (H6:
 207 (subst0 i u t0 t4)).(\lambda (H7: (eq T t4 (lift (S O) i t3))).(let H8 \def
 208 (eq_ind T t4 (\lambda (t: T).(subst0 i u t0 t)) H6 (lift (S O) i t3) H7) in
 209 (sym_eq T t3 t1 (subst0_confluence_lift t0 t3 u i H8 t1 H4)))))) y0 H5)))
 210 H3))))))) y H0))) H))))).
 211 (* COMMENTS
 212 Initial nodes: 735
 213 END *)
 214