matita/matita/contribs/lambdadelta/basic_1A/subst/props.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_1A/subst/defs.ma".
  18
  19 include "basic_1A/subst0/fwd.ma".
  20
  21 lemma subst_sort:
  22  \forall (v: T).(\forall (d: nat).(\forall (k: nat).(eq T (subst d v (TSort
  23 k)) (TSort k))))
  24 \def
  25  \lambda (_: T).(\lambda (_: nat).(\lambda (k: nat).(refl_equal T (TSort
  26 k)))).
  27
  28 lemma subst_lref_lt:
  29  \forall (v: T).(\forall (d: nat).(\forall (i: nat).((lt i d) \to (eq T
  30 (subst d v (TLRef i)) (TLRef i)))))
  31 \def
  32  \lambda (v: T).(\lambda (d: nat).(\lambda (i: nat).(\lambda (H: (lt i
  33 d)).(eq_ind_r bool true (\lambda (b: bool).(eq T (match b with [true
  34 \Rightarrow (TLRef i) | false \Rightarrow (match (blt d i) with [true
  35 \Rightarrow (TLRef (pred i)) | false \Rightarrow (lift d O v)])]) (TLRef i)))
  36 (refl_equal T (TLRef i)) (blt i d) (lt_blt d i H))))).
  37
  38 lemma subst_lref_eq:
  39  \forall (v: T).(\forall (i: nat).(eq T (subst i v (TLRef i)) (lift i O v)))
  40 \def
  41  \lambda (v: T).(\lambda (i: nat).(eq_ind_r bool false (\lambda (b: bool).(eq
  42 T (match b with [true \Rightarrow (TLRef i) | false \Rightarrow (match b with
  43 [true \Rightarrow (TLRef (pred i)) | false \Rightarrow (lift i O v)])]) (lift
  44 i O v))) (refl_equal T (lift i O v)) (blt i i) (le_bge i i (le_n i)))).
  45
  46 lemma subst_lref_gt:
  47  \forall (v: T).(\forall (d: nat).(\forall (i: nat).((lt d i) \to (eq T
  48 (subst d v (TLRef i)) (TLRef (pred i))))))
  49 \def
  50  \lambda (v: T).(\lambda (d: nat).(\lambda (i: nat).(\lambda (H: (lt d
  51 i)).(eq_ind_r bool false (\lambda (b: bool).(eq T (match b with [true
  52 \Rightarrow (TLRef i) | false \Rightarrow (match (blt d i) with [true
  53 \Rightarrow (TLRef (pred i)) | false \Rightarrow (lift d O v)])]) (TLRef
  54 (pred i)))) (eq_ind_r bool true (\lambda (b: bool).(eq T (match b with [true
  55 \Rightarrow (TLRef (pred i)) | false \Rightarrow (lift d O v)]) (TLRef (pred
  56 i)))) (refl_equal T (TLRef (pred i))) (blt d i) (lt_blt i d H)) (blt i d)
  57 (le_bge d i (lt_le_weak d i H)))))).
  58
  59 lemma subst_head:
  60  \forall (k: K).(\forall (w: T).(\forall (u: T).(\forall (t: T).(\forall (d:
  61 nat).(eq T (subst d w (THead k u t)) (THead k (subst d w u) (subst (s k d) w
  62 t)))))))
  63 \def
  64  \lambda (k: K).(\lambda (w: T).(\lambda (u: T).(\lambda (t: T).(\lambda (d:
  65 nat).(refl_equal T (THead k (subst d w u) (subst (s k d) w t))))))).
  66
  67 lemma subst_lift_SO:
  68  \forall (v: T).(\forall (t: T).(\forall (d: nat).(eq T (subst d v (lift (S
  69 O) d t)) t)))
  70 \def
  71  \lambda (v: T).(\lambda (t: T).(T_ind (\lambda (t0: T).(\forall (d: nat).(eq
  72 T (subst d v (lift (S O) d t0)) t0))) (\lambda (n: nat).(\lambda (d:
  73 nat).(eq_ind_r T (TSort n) (\lambda (t0: T).(eq T (subst d v t0) (TSort n)))
  74 (eq_ind_r T (TSort n) (\lambda (t0: T).(eq T t0 (TSort n))) (refl_equal T
  75 (TSort n)) (subst d v (TSort n)) (subst_sort v d n)) (lift (S O) d (TSort n))
  76 (lift_sort n (S O) d)))) (\lambda (n: nat).(\lambda (d: nat).(lt_le_e n d (eq
  77 T (subst d v (lift (S O) d (TLRef n))) (TLRef n)) (\lambda (H: (lt n
  78 d)).(eq_ind_r T (TLRef n) (\lambda (t0: T).(eq T (subst d v t0) (TLRef n)))
  79 (eq_ind_r T (TLRef n) (\lambda (t0: T).(eq T t0 (TLRef n))) (refl_equal T
  80 (TLRef n)) (subst d v (TLRef n)) (subst_lref_lt v d n H)) (lift (S O) d
  81 (TLRef n)) (lift_lref_lt n (S O) d H))) (\lambda (H: (le d n)).(eq_ind_r T
  82 (TLRef (plus n (S O))) (\lambda (t0: T).(eq T (subst d v t0) (TLRef n)))
  83 (eq_ind nat (S (plus n O)) (\lambda (n0: nat).(eq T (subst d v (TLRef n0))
  84 (TLRef n))) (eq_ind_r T (TLRef (pred (S (plus n O)))) (\lambda (t0: T).(eq T
  85 t0 (TLRef n))) (eq_ind nat (plus n O) (\lambda (n0: nat).(eq T (TLRef n0)
  86 (TLRef n))) (f_equal nat T TLRef (plus n O) n (sym_eq nat n (plus n O)
  87 (plus_n_O n))) (pred (S (plus n O))) (pred_Sn (plus n O))) (subst d v (TLRef
  88 (S (plus n O)))) (subst_lref_gt v d (S (plus n O)) (le_n_S d (plus n O)
  89 (le_plus_trans d n O H)))) (plus n (S O)) (plus_n_Sm n O)) (lift (S O) d
  90 (TLRef n)) (lift_lref_ge n (S O) d H)))))) (\lambda (k: K).(\lambda (t0:
  91 T).(\lambda (H: ((\forall (d: nat).(eq T (subst d v (lift (S O) d t0))
  92 t0)))).(\lambda (t1: T).(\lambda (H0: ((\forall (d: nat).(eq T (subst d v
  93 (lift (S O) d t1)) t1)))).(\lambda (d: nat).(eq_ind_r T (THead k (lift (S O)
  94 d t0) (lift (S O) (s k d) t1)) (\lambda (t2: T).(eq T (subst d v t2) (THead k
  95 t0 t1))) (eq_ind_r T (THead k (subst d v (lift (S O) d t0)) (subst (s k d) v
  96 (lift (S O) (s k d) t1))) (\lambda (t2: T).(eq T t2 (THead k t0 t1))) (sym_eq
  97 T (THead k t0 t1) (THead k (subst d v (lift (S O) d t0)) (subst (s k d) v
  98 (lift (S O) (s k d) t1))) (sym_eq T (THead k (subst d v (lift (S O) d t0))
  99 (subst (s k d) v (lift (S O) (s k d) t1))) (THead k t0 t1) (f_equal3 K T T T
 100 THead k k (subst d v (lift (S O) d t0)) t0 (subst (s k d) v (lift (S O) (s k
 101 d) t1)) t1 (refl_equal K k) (H d) (H0 (s k d))))) (subst d v (THead k (lift
 102 (S O) d t0) (lift (S O) (s k d) t1))) (subst_head k v (lift (S O) d t0) (lift
 103 (S O) (s k d) t1) d)) (lift (S O) d (THead k t0 t1)) (lift_head k t0 t1 (S O)
 104 d)))))))) t)).
 105
 106 lemma subst_subst0:
 107  \forall (v: T).(\forall (t1: T).(\forall (t2: T).(\forall (d: nat).((subst0
 108 d v t1 t2) \to (eq T (subst d v t1) (subst d v t2))))))
 109 \def
 110  \lambda (v: T).(\lambda (t1: T).(\lambda (t2: T).(\lambda (d: nat).(\lambda
 111 (H: (subst0 d v t1 t2)).(subst0_ind (\lambda (n: nat).(\lambda (t:
 112 T).(\lambda (t0: T).(\lambda (t3: T).(eq T (subst n t t0) (subst n t t3))))))
 113 (\lambda (v0: T).(\lambda (i: nat).(eq_ind_r T (lift i O v0) (\lambda (t:
 114 T).(eq T t (subst i v0 (lift (S i) O v0)))) (eq_ind nat (plus (S O) i)
 115 (\lambda (n: nat).(eq T (lift i O v0) (subst i v0 (lift n O v0)))) (eq_ind T
 116 (lift (S O) i (lift i O v0)) (\lambda (t: T).(eq T (lift i O v0) (subst i v0
 117 t))) (eq_ind_r T (lift i O v0) (\lambda (t: T).(eq T (lift i O v0) t))
 118 (refl_equal T (lift i O v0)) (subst i v0 (lift (S O) i (lift i O v0)))
 119 (subst_lift_SO v0 (lift i O v0) i)) (lift (plus (S O) i) O v0) (lift_free v0
 120 i (S O) O i (le_n (plus O i)) (le_O_n i))) (S i) (refl_equal nat (S i)))
 121 (subst i v0 (TLRef i)) (subst_lref_eq v0 i)))) (\lambda (v0: T).(\lambda (u2:
 122 T).(\lambda (u1: T).(\lambda (i: nat).(\lambda (_: (subst0 i v0 u1
 123 u2)).(\lambda (H1: (eq T (subst i v0 u1) (subst i v0 u2))).(\lambda (t:
 124 T).(\lambda (k: K).(eq_ind_r T (THead k (subst i v0 u1) (subst (s k i) v0 t))
 125 (\lambda (t0: T).(eq T t0 (subst i v0 (THead k u2 t)))) (eq_ind_r T (THead k
 126 (subst i v0 u2) (subst (s k i) v0 t)) (\lambda (t0: T).(eq T (THead k (subst
 127 i v0 u1) (subst (s k i) v0 t)) t0)) (eq_ind_r T (subst i v0 u2) (\lambda (t0:
 128 T).(eq T (THead k t0 (subst (s k i) v0 t)) (THead k (subst i v0 u2) (subst (s
 129 k i) v0 t)))) (refl_equal T (THead k (subst i v0 u2) (subst (s k i) v0 t)))
 130 (subst i v0 u1) H1) (subst i v0 (THead k u2 t)) (subst_head k v0 u2 t i))
 131 (subst i v0 (THead k u1 t)) (subst_head k v0 u1 t i)))))))))) (\lambda (k:
 132 K).(\lambda (v0: T).(\lambda (t3: T).(\lambda (t4: T).(\lambda (i:
 133 nat).(\lambda (_: (subst0 (s k i) v0 t4 t3)).(\lambda (H1: (eq T (subst (s k
 134 i) v0 t4) (subst (s k i) v0 t3))).(\lambda (u: T).(eq_ind_r T (THead k (subst
 135 i v0 u) (subst (s k i) v0 t4)) (\lambda (t: T).(eq T t (subst i v0 (THead k u
 136 t3)))) (eq_ind_r T (THead k (subst i v0 u) (subst (s k i) v0 t3)) (\lambda
 137 (t: T).(eq T (THead k (subst i v0 u) (subst (s k i) v0 t4)) t)) (eq_ind_r T
 138 (subst (s k i) v0 t3) (\lambda (t: T).(eq T (THead k (subst i v0 u) t) (THead
 139 k (subst i v0 u) (subst (s k i) v0 t3)))) (refl_equal T (THead k (subst i v0
 140 u) (subst (s k i) v0 t3))) (subst (s k i) v0 t4) H1) (subst i v0 (THead k u
 141 t3)) (subst_head k v0 u t3 i)) (subst i v0 (THead k u t4)) (subst_head k v0 u
 142 t4 i)))))))))) (\lambda (v0: T).(\lambda (u1: T).(\lambda (u2: T).(\lambda
 143 (i: nat).(\lambda (_: (subst0 i v0 u1 u2)).(\lambda (H1: (eq T (subst i v0
 144 u1) (subst i v0 u2))).(\lambda (k: K).(\lambda (t3: T).(\lambda (t4:
 145 T).(\lambda (_: (subst0 (s k i) v0 t3 t4)).(\lambda (H3: (eq T (subst (s k i)
 146 v0 t3) (subst (s k i) v0 t4))).(eq_ind_r T (THead k (subst i v0 u1) (subst (s
 147 k i) v0 t3)) (\lambda (t: T).(eq T t (subst i v0 (THead k u2 t4)))) (eq_ind_r
 148 T (THead k (subst i v0 u2) (subst (s k i) v0 t4)) (\lambda (t: T).(eq T
 149 (THead k (subst i v0 u1) (subst (s k i) v0 t3)) t)) (eq_ind_r T (subst i v0
 150 u2) (\lambda (t: T).(eq T (THead k t (subst (s k i) v0 t3)) (THead k (subst i
 151 v0 u2) (subst (s k i) v0 t4)))) (eq_ind_r T (subst (s k i) v0 t4) (\lambda
 152 (t: T).(eq T (THead k (subst i v0 u2) t) (THead k (subst i v0 u2) (subst (s k
 153 i) v0 t4)))) (refl_equal T (THead k (subst i v0 u2) (subst (s k i) v0 t4)))
 154 (subst (s k i) v0 t3) H3) (subst i v0 u1) H1) (subst i v0 (THead k u2 t4))
 155 (subst_head k v0 u2 t4 i)) (subst i v0 (THead k u1 t3)) (subst_head k v0 u1
 156 t3 i))))))))))))) d v t1 t2 H))))).
 157