matita/matita/contribs/lambdadelta/basic_1/sn3/fwd.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/sn3/defs.ma".
  18
  19 include "basic_1/pr3/props.ma".
  20
  21 implied rec lemma sn3_ind (c: C) (P: (T \to Prop)) (f: (\forall (t1:
  22 T).(((\forall (t2: T).((((eq T t1 t2) \to (\forall (P0: Prop).P0))) \to ((pr3
  23 c t1 t2) \to (sn3 c t2))))) \to (((\forall (t2: T).((((eq T t1 t2) \to
  24 (\forall (P0: Prop).P0))) \to ((pr3 c t1 t2) \to (P t2))))) \to (P t1)))))
  25 (t: T) (s0: sn3 c t) on s0: P t \def match s0 with [(sn3_sing t1 s1)
  26 \Rightarrow (f t1 s1 (\lambda (t2: T).(\lambda (p: (((eq T t1 t2) \to
  27 (\forall (P0: Prop).P0)))).(\lambda (p0: (pr3 c t1 t2)).((sn3_ind c P f) t2
  28 (s1 t2 p p0))))))].
  29
  30 lemma sn3_gen_bind:
  31  \forall (b: B).(\forall (c: C).(\forall (u: T).(\forall (t: T).((sn3 c
  32 (THead (Bind b) u t)) \to (land (sn3 c u) (sn3 (CHead c (Bind b) u) t))))))
  33 \def
  34  \lambda (b: B).(\lambda (c: C).(\lambda (u: T).(\lambda (t: T).(\lambda (H:
  35 (sn3 c (THead (Bind b) u t))).(insert_eq T (THead (Bind b) u t) (\lambda (t0:
  36 T).(sn3 c t0)) (\lambda (_: T).(land (sn3 c u) (sn3 (CHead c (Bind b) u) t)))
  37 (\lambda (y: T).(\lambda (H0: (sn3 c y)).(unintro T t (\lambda (t0: T).((eq T
  38 y (THead (Bind b) u t0)) \to (land (sn3 c u) (sn3 (CHead c (Bind b) u) t0))))
  39 (unintro T u (\lambda (t0: T).(\forall (x: T).((eq T y (THead (Bind b) t0 x))
  40 \to (land (sn3 c t0) (sn3 (CHead c (Bind b) t0) x))))) (sn3_ind c (\lambda
  41 (t0: T).(\forall (x: T).(\forall (x0: T).((eq T t0 (THead (Bind b) x x0)) \to
  42 (land (sn3 c x) (sn3 (CHead c (Bind b) x) x0)))))) (\lambda (t1: T).(\lambda
  43 (H1: ((\forall (t2: T).((((eq T t1 t2) \to (\forall (P: Prop).P))) \to ((pr3
  44 c t1 t2) \to (sn3 c t2)))))).(\lambda (H2: ((\forall (t2: T).((((eq T t1 t2)
  45 \to (\forall (P: Prop).P))) \to ((pr3 c t1 t2) \to (\forall (x: T).(\forall
  46 (x0: T).((eq T t2 (THead (Bind b) x x0)) \to (land (sn3 c x) (sn3 (CHead c
  47 (Bind b) x) x0)))))))))).(\lambda (x: T).(\lambda (x0: T).(\lambda (H3: (eq T
  48 t1 (THead (Bind b) x x0))).(let H4 \def (eq_ind T t1 (\lambda (t0:
  49 T).(\forall (t2: T).((((eq T t0 t2) \to (\forall (P: Prop).P))) \to ((pr3 c
  50 t0 t2) \to (\forall (x1: T).(\forall (x2: T).((eq T t2 (THead (Bind b) x1
  51 x2)) \to (land (sn3 c x1) (sn3 (CHead c (Bind b) x1) x2))))))))) H2 (THead
  52 (Bind b) x x0) H3) in (let H5 \def (eq_ind T t1 (\lambda (t0: T).(\forall
  53 (t2: T).((((eq T t0 t2) \to (\forall (P: Prop).P))) \to ((pr3 c t0 t2) \to
  54 (sn3 c t2))))) H1 (THead (Bind b) x x0) H3) in (conj (sn3 c x) (sn3 (CHead c
  55 (Bind b) x) x0) (sn3_sing c x (\lambda (t2: T).(\lambda (H6: (((eq T x t2)
  56 \to (\forall (P: Prop).P)))).(\lambda (H7: (pr3 c x t2)).(let H8 \def (H4
  57 (THead (Bind b) t2 x0) (\lambda (H8: (eq T (THead (Bind b) x x0) (THead (Bind
  58 b) t2 x0))).(\lambda (P: Prop).(let H9 \def (f_equal T T (\lambda (e:
  59 T).(match e with [(TSort _) \Rightarrow x | (TLRef _) \Rightarrow x | (THead
  60 _ t0 _) \Rightarrow t0])) (THead (Bind b) x x0) (THead (Bind b) t2 x0) H8) in
  61 (let H10 \def (eq_ind_r T t2 (\lambda (t0: T).(pr3 c x t0)) H7 x H9) in (let
  62 H11 \def (eq_ind_r T t2 (\lambda (t0: T).((eq T x t0) \to (\forall (P0:
  63 Prop).P0))) H6 x H9) in (H11 (refl_equal T x) P)))))) (pr3_head_12 c x t2 H7
  64 (Bind b) x0 x0 (pr3_refl (CHead c (Bind b) t2) x0)) t2 x0 (refl_equal T
  65 (THead (Bind b) t2 x0))) in (land_ind (sn3 c t2) (sn3 (CHead c (Bind b) t2)
  66 x0) (sn3 c t2) (\lambda (H9: (sn3 c t2)).(\lambda (_: (sn3 (CHead c (Bind b)
  67 t2) x0)).H9)) H8)))))) (sn3_sing (CHead c (Bind b) x) x0 (\lambda (t2:
  68 T).(\lambda (H6: (((eq T x0 t2) \to (\forall (P: Prop).P)))).(\lambda (H7:
  69 (pr3 (CHead c (Bind b) x) x0 t2)).(let H8 \def (H4 (THead (Bind b) x t2)
  70 (\lambda (H8: (eq T (THead (Bind b) x x0) (THead (Bind b) x t2))).(\lambda
  71 (P: Prop).(let H9 \def (f_equal T T (\lambda (e: T).(match e with [(TSort _)
  72 \Rightarrow x0 | (TLRef _) \Rightarrow x0 | (THead _ _ t0) \Rightarrow t0]))
  73 (THead (Bind b) x x0) (THead (Bind b) x t2) H8) in (let H10 \def (eq_ind_r T
  74 t2 (\lambda (t0: T).(pr3 (CHead c (Bind b) x) x0 t0)) H7 x0 H9) in (let H11
  75 \def (eq_ind_r T t2 (\lambda (t0: T).((eq T x0 t0) \to (\forall (P0:
  76 Prop).P0))) H6 x0 H9) in (H11 (refl_equal T x0) P)))))) (pr3_head_12 c x x
  77 (pr3_refl c x) (Bind b) x0 t2 H7) x t2 (refl_equal T (THead (Bind b) x t2)))
  78 in (land_ind (sn3 c x) (sn3 (CHead c (Bind b) x) t2) (sn3 (CHead c (Bind b)
  79 x) t2) (\lambda (_: (sn3 c x)).(\lambda (H10: (sn3 (CHead c (Bind b) x)
  80 t2)).H10)) H8))))))))))))))) y H0))))) H))))).
  81
  82 lemma sn3_gen_flat:
  83  \forall (f: F).(\forall (c: C).(\forall (u: T).(\forall (t: T).((sn3 c
  84 (THead (Flat f) u t)) \to (land (sn3 c u) (sn3 c t))))))
  85 \def
  86  \lambda (f: F).(\lambda (c: C).(\lambda (u: T).(\lambda (t: T).(\lambda (H:
  87 (sn3 c (THead (Flat f) u t))).(insert_eq T (THead (Flat f) u t) (\lambda (t0:
  88 T).(sn3 c t0)) (\lambda (_: T).(land (sn3 c u) (sn3 c t))) (\lambda (y:
  89 T).(\lambda (H0: (sn3 c y)).(unintro T t (\lambda (t0: T).((eq T y (THead
  90 (Flat f) u t0)) \to (land (sn3 c u) (sn3 c t0)))) (unintro T u (\lambda (t0:
  91 T).(\forall (x: T).((eq T y (THead (Flat f) t0 x)) \to (land (sn3 c t0) (sn3
  92 c x))))) (sn3_ind c (\lambda (t0: T).(\forall (x: T).(\forall (x0: T).((eq T
  93 t0 (THead (Flat f) x x0)) \to (land (sn3 c x) (sn3 c x0)))))) (\lambda (t1:
  94 T).(\lambda (H1: ((\forall (t2: T).((((eq T t1 t2) \to (\forall (P:
  95 Prop).P))) \to ((pr3 c t1 t2) \to (sn3 c t2)))))).(\lambda (H2: ((\forall
  96 (t2: T).((((eq T t1 t2) \to (\forall (P: Prop).P))) \to ((pr3 c t1 t2) \to
  97 (\forall (x: T).(\forall (x0: T).((eq T t2 (THead (Flat f) x x0)) \to (land
  98 (sn3 c x) (sn3 c x0)))))))))).(\lambda (x: T).(\lambda (x0: T).(\lambda (H3:
  99 (eq T t1 (THead (Flat f) x x0))).(let H4 \def (eq_ind T t1 (\lambda (t0:
 100 T).(\forall (t2: T).((((eq T t0 t2) \to (\forall (P: Prop).P))) \to ((pr3 c
 101 t0 t2) \to (\forall (x1: T).(\forall (x2: T).((eq T t2 (THead (Flat f) x1
 102 x2)) \to (land (sn3 c x1) (sn3 c x2))))))))) H2 (THead (Flat f) x x0) H3) in
 103 (let H5 \def (eq_ind T t1 (\lambda (t0: T).(\forall (t2: T).((((eq T t0 t2)
 104 \to (\forall (P: Prop).P))) \to ((pr3 c t0 t2) \to (sn3 c t2))))) H1 (THead
 105 (Flat f) x x0) H3) in (conj (sn3 c x) (sn3 c x0) (sn3_sing c x (\lambda (t2:
 106 T).(\lambda (H6: (((eq T x t2) \to (\forall (P: Prop).P)))).(\lambda (H7:
 107 (pr3 c x t2)).(let H8 \def (H4 (THead (Flat f) t2 x0) (\lambda (H8: (eq T
 108 (THead (Flat f) x x0) (THead (Flat f) t2 x0))).(\lambda (P: Prop).(let H9
 109 \def (f_equal T T (\lambda (e: T).(match e with [(TSort _) \Rightarrow x |
 110 (TLRef _) \Rightarrow x | (THead _ t0 _) \Rightarrow t0])) (THead (Flat f) x
 111 x0) (THead (Flat f) t2 x0) H8) in (let H10 \def (eq_ind_r T t2 (\lambda (t0:
 112 T).(pr3 c x t0)) H7 x H9) in (let H11 \def (eq_ind_r T t2 (\lambda (t0:
 113 T).((eq T x t0) \to (\forall (P0: Prop).P0))) H6 x H9) in (H11 (refl_equal T
 114 x) P)))))) (pr3_head_12 c x t2 H7 (Flat f) x0 x0 (pr3_refl (CHead c (Flat f)
 115 t2) x0)) t2 x0 (refl_equal T (THead (Flat f) t2 x0))) in (land_ind (sn3 c t2)
 116 (sn3 c x0) (sn3 c t2) (\lambda (H9: (sn3 c t2)).(\lambda (_: (sn3 c x0)).H9))
 117 H8)))))) (sn3_sing c x0 (\lambda (t2: T).(\lambda (H6: (((eq T x0 t2) \to
 118 (\forall (P: Prop).P)))).(\lambda (H7: (pr3 c x0 t2)).(let H8 \def (H4 (THead
 119 (Flat f) x t2) (\lambda (H8: (eq T (THead (Flat f) x x0) (THead (Flat f) x
 120 t2))).(\lambda (P: Prop).(let H9 \def (f_equal T T (\lambda (e: T).(match e
 121 with [(TSort _) \Rightarrow x0 | (TLRef _) \Rightarrow x0 | (THead _ _ t0)
 122 \Rightarrow t0])) (THead (Flat f) x x0) (THead (Flat f) x t2) H8) in (let H10
 123 \def (eq_ind_r T t2 (\lambda (t0: T).(pr3 c x0 t0)) H7 x0 H9) in (let H11
 124 \def (eq_ind_r T t2 (\lambda (t0: T).((eq T x0 t0) \to (\forall (P0:
 125 Prop).P0))) H6 x0 H9) in (H11 (refl_equal T x0) P)))))) (pr3_thin_dx c x0 t2
 126 H7 x f) x t2 (refl_equal T (THead (Flat f) x t2))) in (land_ind (sn3 c x)
 127 (sn3 c t2) (sn3 c t2) (\lambda (_: (sn3 c x)).(\lambda (H10: (sn3 c
 128 t2)).H10)) H8))))))))))))))) y H0))))) H))))).
 129
 130 lemma sn3_gen_head:
 131  \forall (k: K).(\forall (c: C).(\forall (u: T).(\forall (t: T).((sn3 c
 132 (THead k u t)) \to (sn3 c u)))))
 133 \def
 134  \lambda (k: K).(K_ind (\lambda (k0: K).(\forall (c: C).(\forall (u:
 135 T).(\forall (t: T).((sn3 c (THead k0 u t)) \to (sn3 c u)))))) (\lambda (b:
 136 B).(\lambda (c: C).(\lambda (u: T).(\lambda (t: T).(\lambda (H: (sn3 c (THead
 137 (Bind b) u t))).(let H_x \def (sn3_gen_bind b c u t H) in (let H0 \def H_x in
 138 (land_ind (sn3 c u) (sn3 (CHead c (Bind b) u) t) (sn3 c u) (\lambda (H1: (sn3
 139 c u)).(\lambda (_: (sn3 (CHead c (Bind b) u) t)).H1)) H0)))))))) (\lambda (f:
 140 F).(\lambda (c: C).(\lambda (u: T).(\lambda (t: T).(\lambda (H: (sn3 c (THead
 141 (Flat f) u t))).(let H_x \def (sn3_gen_flat f c u t H) in (let H0 \def H_x in
 142 (land_ind (sn3 c u) (sn3 c t) (sn3 c u) (\lambda (H1: (sn3 c u)).(\lambda (_:
 143 (sn3 c t)).H1)) H0)))))))) k).
 144
 145 lemma sn3_gen_cflat:
 146  \forall (f: F).(\forall (c: C).(\forall (u: T).(\forall (t: T).((sn3 (CHead
 147 c (Flat f) u) t) \to (sn3 c t)))))
 148 \def
 149  \lambda (f: F).(\lambda (c: C).(\lambda (u: T).(\lambda (t: T).(\lambda (H:
 150 (sn3 (CHead c (Flat f) u) t)).(sn3_ind (CHead c (Flat f) u) (\lambda (t0:
 151 T).(sn3 c t0)) (\lambda (t1: T).(\lambda (_: ((\forall (t2: T).((((eq T t1
 152 t2) \to (\forall (P: Prop).P))) \to ((pr3 (CHead c (Flat f) u) t1 t2) \to
 153 (sn3 (CHead c (Flat f) u) t2)))))).(\lambda (H1: ((\forall (t2: T).((((eq T
 154 t1 t2) \to (\forall (P: Prop).P))) \to ((pr3 (CHead c (Flat f) u) t1 t2) \to
 155 (sn3 c t2)))))).(sn3_sing c t1 (\lambda (t2: T).(\lambda (H2: (((eq T t1 t2)
 156 \to (\forall (P: Prop).P)))).(\lambda (H3: (pr3 c t1 t2)).(H1 t2 H2
 157 (pr3_cflat c t1 t2 H3 f u))))))))) t H))))).
 158
 159 lemma sn3_gen_lift:
 160  \forall (c1: C).(\forall (t: T).(\forall (h: nat).(\forall (d: nat).((sn3 c1
 161 (lift h d t)) \to (\forall (c2: C).((drop h d c1 c2) \to (sn3 c2 t)))))))
 162 \def
 163  \lambda (c1: C).(\lambda (t: T).(\lambda (h: nat).(\lambda (d: nat).(\lambda
 164 (H: (sn3 c1 (lift h d t))).(insert_eq T (lift h d t) (\lambda (t0: T).(sn3 c1
 165 t0)) (\lambda (_: T).(\forall (c2: C).((drop h d c1 c2) \to (sn3 c2 t))))
 166 (\lambda (y: T).(\lambda (H0: (sn3 c1 y)).(unintro T t (\lambda (t0: T).((eq
 167 T y (lift h d t0)) \to (\forall (c2: C).((drop h d c1 c2) \to (sn3 c2 t0)))))
 168 (sn3_ind c1 (\lambda (t0: T).(\forall (x: T).((eq T t0 (lift h d x)) \to
 169 (\forall (c2: C).((drop h d c1 c2) \to (sn3 c2 x)))))) (\lambda (t1:
 170 T).(\lambda (H1: ((\forall (t2: T).((((eq T t1 t2) \to (\forall (P:
 171 Prop).P))) \to ((pr3 c1 t1 t2) \to (sn3 c1 t2)))))).(\lambda (H2: ((\forall
 172 (t2: T).((((eq T t1 t2) \to (\forall (P: Prop).P))) \to ((pr3 c1 t1 t2) \to
 173 (\forall (x: T).((eq T t2 (lift h d x)) \to (\forall (c2: C).((drop h d c1
 174 c2) \to (sn3 c2 x)))))))))).(\lambda (x: T).(\lambda (H3: (eq T t1 (lift h d
 175 x))).(\lambda (c2: C).(\lambda (H4: (drop h d c1 c2)).(let H5 \def (eq_ind T
 176 t1 (\lambda (t0: T).(\forall (t2: T).((((eq T t0 t2) \to (\forall (P:
 177 Prop).P))) \to ((pr3 c1 t0 t2) \to (\forall (x0: T).((eq T t2 (lift h d x0))
 178 \to (\forall (c3: C).((drop h d c1 c3) \to (sn3 c3 x0))))))))) H2 (lift h d
 179 x) H3) in (let H6 \def (eq_ind T t1 (\lambda (t0: T).(\forall (t2: T).((((eq
 180 T t0 t2) \to (\forall (P: Prop).P))) \to ((pr3 c1 t0 t2) \to (sn3 c1 t2)))))
 181 H1 (lift h d x) H3) in (sn3_sing c2 x (\lambda (t2: T).(\lambda (H7: (((eq T
 182 x t2) \to (\forall (P: Prop).P)))).(\lambda (H8: (pr3 c2 x t2)).(H5 (lift h d
 183 t2) (\lambda (H9: (eq T (lift h d x) (lift h d t2))).(\lambda (P: Prop).(let
 184 H10 \def (eq_ind_r T t2 (\lambda (t0: T).(pr3 c2 x t0)) H8 x (lift_inj x t2 h
 185 d H9)) in (let H11 \def (eq_ind_r T t2 (\lambda (t0: T).((eq T x t0) \to
 186 (\forall (P0: Prop).P0))) H7 x (lift_inj x t2 h d H9)) in (H11 (refl_equal T
 187 x) P))))) (pr3_lift c1 c2 h d H4 x t2 H8) t2 (refl_equal T (lift h d t2)) c2
 188 H4)))))))))))))) y H0)))) H))))).
 189