matita/matita/contribs/lambdadelta/static_2/relocation/lifts.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 include "ground/arith/nat_le_plus.ma".
  16 include "ground/relocation/pr_compose.ma".
  17 include "ground/relocation/pr_nat_uni.ma".
  18 include "ground/relocation/pr_isi_nat.ma".
  19 include "ground/relocation/pr_ist_ist.ma".
  20 include "ground/relocation/pr_after_uni.ma".
  21 include "ground/relocation/pr_after_nat.ma".
  22 include "ground/relocation/pr_after_ist.ma".
  23 include "static_2/notation/relations/rliftstar_3.ma".
  24 include "static_2/notation/relations/rlift_3.ma".
  25 include "static_2/syntax/term.ma".
  26
  27 (* GENERIC RELOCATION FOR TERMS *********************************************)
  28
  29 (* Basic_1: includes:
  30             lift_sort lift_lref_lt lift_lref_ge lift_bind lift_flat
  31             lifts_nil lifts_cons
  32 *)
  33 inductive lifts: pr_map → relation term ≝
  34 | lifts_sort: ∀f,s. lifts f (⋆s) (⋆s)
  35 | lifts_lref: ∀f,i1,i2. ＠§❨i1,f❩ ≘ i2 → lifts f (#i1) (#i2)
  36 | lifts_gref: ∀f,l. lifts f (§l) (§l)
  37 | lifts_bind: ∀f,p,I,V1,V2,T1,T2.
  38               lifts f V1 V2 → lifts (⫯f) T1 T2 →
  39               lifts f (ⓑ[p,I]V1.T1) (ⓑ[p,I]V2.T2)
  40 | lifts_flat: ∀f,I,V1,V2,T1,T2.
  41               lifts f V1 V2 → lifts f T1 T2 →
  42               lifts f (ⓕ[I]V1.T1) (ⓕ[I]V2.T2)
  43 .
  44
  45 interpretation "generic relocation (term)"
  46    'RLiftStar f T1 T2 = (lifts f T1 T2).
  47
  48 interpretation "uniform relocation (term)"
  49    'RLift i T1 T2 = (lifts (pr_uni i) T1 T2).
  50
  51 definition liftable2_sn: predicate (relation term) ≝
  52                          λR. ∀T1,T2. R T1 T2 → ∀f,U1. ⇧*[f] T1 ≘ U1 →
  53                          ∃∃U2. ⇧*[f] T2 ≘ U2 & R U1 U2.
  54
  55 definition deliftable2_sn: predicate (relation term) ≝
  56                            λR. ∀U1,U2. R U1 U2 → ∀f,T1. ⇧*[f] T1 ≘ U1 →
  57                            ∃∃T2. ⇧*[f] T2 ≘ U2 & R T1 T2.
  58
  59 definition liftable2_bi: predicate (relation term) ≝
  60                          λR. ∀T1,T2. R T1 T2 → ∀f,U1. ⇧*[f] T1 ≘ U1 →
  61                          ∀U2. ⇧*[f] T2 ≘ U2 → R U1 U2.
  62
  63 definition deliftable2_bi: predicate (relation term) ≝
  64                            λR. ∀U1,U2. R U1 U2 → ∀f,T1. ⇧*[f] T1 ≘ U1 →
  65                            ∀T2. ⇧*[f] T2 ≘ U2 → R T1 T2.
  66
  67 definition liftable2_dx: predicate (relation term) ≝
  68                          λR. ∀T1,T2. R T1 T2 → ∀f,U2. ⇧*[f] T2 ≘ U2 →
  69                          ∃∃U1. ⇧*[f] T1 ≘ U1 & R U1 U2.
  70
  71 definition deliftable2_dx: predicate (relation term) ≝
  72                            λR. ∀U1,U2. R U1 U2 → ∀f,T2. ⇧*[f] T2 ≘ U2 →
  73                            ∃∃T1. ⇧*[f] T1 ≘ U1 & R T1 T2.
  74
  75 (* Basic inversion lemmas ***************************************************)
  76
  77 fact lifts_inv_sort1_aux: ∀f,X,Y. ⇧*[f] X ≘ Y → ∀s. X = ⋆s → Y = ⋆s.
  78 #f #X #Y * -f -X -Y //
  79 [ #f #i1 #i2 #_ #x #H destruct
  80 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
  81 | #f #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
  82 ]
  83 qed-.
  84
  85 (* Basic_1: was: lift1_sort *)
  86 (* Basic_2A1: includes: lift_inv_sort1 *)
  87 lemma lifts_inv_sort1: ∀f,Y,s. ⇧*[f] ⋆s ≘ Y → Y = ⋆s.
  88 /2 width=4 by lifts_inv_sort1_aux/ qed-.
  89
  90 fact lifts_inv_lref1_aux: ∀f,X,Y. ⇧*[f] X ≘ Y → ∀i1. X = #i1 →
  91                           ∃∃i2. ＠§❨i1,f❩ ≘ i2 & Y = #i2.
  92 #f #X #Y * -f -X -Y
  93 [ #f #s #x #H destruct
  94 | #f #i1 #i2 #Hi12 #x #H destruct /2 width=3 by ex2_intro/
  95 | #f #l #x #H destruct
  96 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
  97 | #f #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
  98 ]
  99 qed-.
 100
 101 (* Basic_1: was: lift1_lref *)
 102 (* Basic_2A1: includes: lift_inv_lref1 lift_inv_lref1_lt lift_inv_lref1_ge *)
 103 lemma lifts_inv_lref1: ∀f,Y,i1. ⇧*[f] #i1 ≘ Y →
 104                        ∃∃i2. ＠§❨i1,f❩ ≘ i2 & Y = #i2.
 105 /2 width=3 by lifts_inv_lref1_aux/ qed-.
 106
 107 fact lifts_inv_gref1_aux: ∀f,X,Y. ⇧*[f] X ≘ Y → ∀l. X = §l → Y = §l.
 108 #f #X #Y * -f -X -Y //
 109 [ #f #i1 #i2 #_ #x #H destruct
 110 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
 111 | #f #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
 112 ]
 113 qed-.
 114
 115 (* Basic_2A1: includes: lift_inv_gref1 *)
 116 lemma lifts_inv_gref1: ∀f,Y,l. ⇧*[f] §l ≘ Y → Y = §l.
 117 /2 width=4 by lifts_inv_gref1_aux/ qed-.
 118
 119 fact lifts_inv_bind1_aux: ∀f,X,Y. ⇧*[f] X ≘ Y →
 120                           ∀p,I,V1,T1. X = ⓑ[p,I]V1.T1 →
 121                           ∃∃V2,T2. ⇧*[f] V1 ≘ V2 & ⇧*[⫯f] T1 ≘ T2 &
 122                                    Y = ⓑ[p,I]V2.T2.
 123 #f #X #Y * -f -X -Y
 124 [ #f #s #q #J #W1 #U1 #H destruct
 125 | #f #i1 #i2 #_ #q #J #W1 #U1 #H destruct
 126 | #f #l #b #J #W1 #U1 #H destruct
 127 | #f #p #I #V1 #V2 #T1 #T2 #HV12 #HT12 #q #J #W1 #U1 #H destruct /2 width=5 by ex3_2_intro/
 128 | #f #I #V1 #V2 #T1 #T2 #_ #_ #q #J #W1 #U1 #H destruct
 129 ]
 130 qed-.
 131
 132 (* Basic_1: was: lift1_bind *)
 133 (* Basic_2A1: includes: lift_inv_bind1 *)
 134 lemma lifts_inv_bind1: ∀f,p,I,V1,T1,Y. ⇧*[f] ⓑ[p,I]V1.T1 ≘ Y →
 135                        ∃∃V2,T2. ⇧*[f] V1 ≘ V2 & ⇧*[⫯f] T1 ≘ T2 &
 136                                 Y = ⓑ[p,I]V2.T2.
 137 /2 width=3 by lifts_inv_bind1_aux/ qed-.
 138
 139 fact lifts_inv_flat1_aux: ∀f,X,Y. ⇧*[f] X ≘ Y →
 140                           ∀I,V1,T1. X = ⓕ[I]V1.T1 →
 141                           ∃∃V2,T2. ⇧*[f] V1 ≘ V2 & ⇧*[f] T1 ≘ T2 &
 142                                    Y = ⓕ[I]V2.T2.
 143 #f #X #Y * -f -X -Y
 144 [ #f #s #J #W1 #U1 #H destruct
 145 | #f #i1 #i2 #_ #J #W1 #U1 #H destruct
 146 | #f #l #J #W1 #U1 #H destruct
 147 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #J #W1 #U1 #H destruct
 148 | #f #I #V1 #V2 #T1 #T2 #HV12 #HT12 #J #W1 #U1 #H destruct /2 width=5 by ex3_2_intro/
 149 ]
 150 qed-.
 151
 152 (* Basic_1: was: lift1_flat *)
 153 (* Basic_2A1: includes: lift_inv_flat1 *)
 154 lemma lifts_inv_flat1: ∀f,I,V1,T1,Y. ⇧*[f] ⓕ[I]V1.T1 ≘ Y →
 155                        ∃∃V2,T2. ⇧*[f] V1 ≘ V2 & ⇧*[f] T1 ≘ T2 &
 156                                 Y = ⓕ[I]V2.T2.
 157 /2 width=3 by lifts_inv_flat1_aux/ qed-.
 158
 159 fact lifts_inv_sort2_aux: ∀f,X,Y. ⇧*[f] X ≘ Y → ∀s. Y = ⋆s → X = ⋆s.
 160 #f #X #Y * -f -X -Y //
 161 [ #f #i1 #i2 #_ #x #H destruct
 162 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
 163 | #f #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
 164 ]
 165 qed-.
 166
 167 (* Basic_1: includes: lift_gen_sort *)
 168 (* Basic_2A1: includes: lift_inv_sort2 *)
 169 lemma lifts_inv_sort2: ∀f,X,s. ⇧*[f] X ≘ ⋆s → X = ⋆s.
 170 /2 width=4 by lifts_inv_sort2_aux/ qed-.
 171
 172 fact lifts_inv_lref2_aux: ∀f,X,Y. ⇧*[f] X ≘ Y → ∀i2. Y = #i2 →
 173                           ∃∃i1. ＠§❨i1,f❩ ≘ i2 & X = #i1.
 174 #f #X #Y * -f -X -Y
 175 [ #f #s #x #H destruct
 176 | #f #i1 #i2 #Hi12 #x #H destruct /2 width=3 by ex2_intro/
 177 | #f #l #x #H destruct
 178 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
 179 | #f #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
 180 ]
 181 qed-.
 182
 183 (* Basic_1: includes: lift_gen_lref lift_gen_lref_lt lift_gen_lref_false lift_gen_lref_ge *)
 184 (* Basic_2A1: includes: lift_inv_lref2 lift_inv_lref2_lt lift_inv_lref2_be lift_inv_lref2_ge lift_inv_lref2_plus *)
 185 lemma lifts_inv_lref2: ∀f,X,i2. ⇧*[f] X ≘ #i2 →
 186                        ∃∃i1. ＠§❨i1,f❩ ≘ i2 & X = #i1.
 187 /2 width=3 by lifts_inv_lref2_aux/ qed-.
 188
 189 fact lifts_inv_gref2_aux: ∀f,X,Y. ⇧*[f] X ≘ Y → ∀l. Y = §l → X = §l.
 190 #f #X #Y * -f -X -Y //
 191 [ #f #i1 #i2 #_ #x #H destruct
 192 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
 193 | #f #I #V1 #V2 #T1 #T2 #_ #_ #x #H destruct
 194 ]
 195 qed-.
 196
 197 (* Basic_2A1: includes: lift_inv_gref1 *)
 198 lemma lifts_inv_gref2: ∀f,X,l. ⇧*[f] X ≘ §l → X = §l.
 199 /2 width=4 by lifts_inv_gref2_aux/ qed-.
 200
 201 fact lifts_inv_bind2_aux: ∀f,X,Y. ⇧*[f] X ≘ Y →
 202                           ∀p,I,V2,T2. Y = ⓑ[p,I]V2.T2 →
 203                           ∃∃V1,T1. ⇧*[f] V1 ≘ V2 & ⇧*[⫯f] T1 ≘ T2 &
 204                                    X = ⓑ[p,I]V1.T1.
 205 #f #X #Y * -f -X -Y
 206 [ #f #s #q #J #W2 #U2 #H destruct
 207 | #f #i1 #i2 #_ #q #J #W2 #U2 #H destruct
 208 | #f #l #q #J #W2 #U2 #H destruct
 209 | #f #p #I #V1 #V2 #T1 #T2 #HV12 #HT12 #q #J #W2 #U2 #H destruct /2 width=5 by ex3_2_intro/
 210 | #f #I #V1 #V2 #T1 #T2 #_ #_ #q #J #W2 #U2 #H destruct
 211 ]
 212 qed-.
 213
 214 (* Basic_1: includes: lift_gen_bind *)
 215 (* Basic_2A1: includes: lift_inv_bind2 *)
 216 lemma lifts_inv_bind2: ∀f,p,I,V2,T2,X. ⇧*[f] X ≘ ⓑ[p,I]V2.T2 →
 217                        ∃∃V1,T1. ⇧*[f] V1 ≘ V2 & ⇧*[⫯f] T1 ≘ T2 &
 218                                 X = ⓑ[p,I]V1.T1.
 219 /2 width=3 by lifts_inv_bind2_aux/ qed-.
 220
 221 fact lifts_inv_flat2_aux: ∀f,X,Y. ⇧*[f] X ≘ Y →
 222                           ∀I,V2,T2. Y = ⓕ[I]V2.T2 →
 223                           ∃∃V1,T1. ⇧*[f] V1 ≘ V2 & ⇧*[f] T1 ≘ T2 &
 224                                    X = ⓕ[I]V1.T1.
 225 #f #X #Y * -f -X -Y
 226 [ #f #s #J #W2 #U2 #H destruct
 227 | #f #i1 #i2 #_ #J #W2 #U2 #H destruct
 228 | #f #l #J #W2 #U2 #H destruct
 229 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #J #W2 #U2 #H destruct
 230 | #f #I #V1 #V2 #T1 #T2 #HV12 #HT12 #J #W2 #U2 #H destruct /2 width=5 by ex3_2_intro/
 231 ]
 232 qed-.
 233
 234 (* Basic_1: includes: lift_gen_flat *)
 235 (* Basic_2A1: includes: lift_inv_flat2 *)
 236 lemma lifts_inv_flat2: ∀f,I,V2,T2,X. ⇧*[f] X ≘ ⓕ[I]V2.T2 →
 237                        ∃∃V1,T1. ⇧*[f] V1 ≘ V2 & ⇧*[f] T1 ≘ T2 &
 238                                 X = ⓕ[I]V1.T1.
 239 /2 width=3 by lifts_inv_flat2_aux/ qed-.
 240
 241 (* Advanced inversion lemmas ************************************************)
 242
 243 lemma lifts_inv_atom1: ∀f,I,Y. ⇧*[f] ⓪[I] ≘ Y →
 244                        ∨∨ ∃∃s. I = Sort s & Y = ⋆s
 245                         | ∃∃i,j. ＠§❨i,f❩ ≘ j & I = LRef i & Y = #j
 246                         | ∃∃l. I = GRef l & Y = §l.
 247 #f * #n #Y #H
 248 [ lapply (lifts_inv_sort1 … H)
 249 | elim (lifts_inv_lref1 … H)
 250 | lapply (lifts_inv_gref1 … H)
 251 ] -H /3 width=5 by or3_intro0, or3_intro1, or3_intro2, ex3_2_intro, ex2_intro/
 252 qed-.
 253
 254 lemma lifts_inv_atom2: ∀f,I,X. ⇧*[f] X ≘ ⓪[I] →
 255                        ∨∨ ∃∃s. X = ⋆s & I = Sort s
 256                         | ∃∃i,j. ＠§❨i,f❩ ≘ j & X = #i & I = LRef j
 257                         | ∃∃l. X = §l & I = GRef l.
 258 #f * #n #X #H
 259 [ lapply (lifts_inv_sort2 … H)
 260 | elim (lifts_inv_lref2 … H)
 261 | lapply (lifts_inv_gref2 … H)
 262 ] -H /3 width=5 by or3_intro0, or3_intro1, or3_intro2, ex3_2_intro, ex2_intro/
 263 qed-.
 264
 265 (* Basic_2A1: includes: lift_inv_pair_xy_x *)
 266 lemma lifts_inv_pair_xy_x: ∀f,I,V,T. ⇧*[f] ②[I]V.T ≘ V → ⊥.
 267 #f #J #V elim V -V
 268 [ * #i #U #H
 269   [ lapply (lifts_inv_sort2 … H) -H #H destruct
 270   | elim (lifts_inv_lref2 … H) -H
 271     #x #_ #H destruct
 272   | lapply (lifts_inv_gref2 … H) -H #H destruct
 273   ]
 274 | * [ #p ] #I #V2 #T2 #IHV2 #_ #U #H
 275   [ elim (lifts_inv_bind2 … H) -H #V1 #T1 #HV12 #_ #H destruct /2 width=3 by/
 276   | elim (lifts_inv_flat2 … H) -H #V1 #T1 #HV12 #_ #H destruct /2 width=3 by/
 277   ]
 278 ]
 279 qed-.
 280
 281 (* Basic_1: includes: thead_x_lift_y_y *)
 282 (* Basic_2A1: includes: lift_inv_pair_xy_y *)
 283 lemma lifts_inv_pair_xy_y: ∀I,T,V,f. ⇧*[f] ②[I]V.T ≘ T → ⊥.
 284 #J #T elim T -T
 285 [ * #i #W #f #H
 286   [ lapply (lifts_inv_sort2 … H) -H #H destruct
 287   | elim (lifts_inv_lref2 … H) -H
 288     #x #_ #H destruct
 289   | lapply (lifts_inv_gref2 … H) -H #H destruct
 290   ]
 291 | * [ #p ] #I #V2 #T2 #_ #IHT2 #W #f #H
 292   [ elim (lifts_inv_bind2 … H) -H #V1 #T1 #_ #HT12 #H destruct /2 width=4 by/
 293   | elim (lifts_inv_flat2 … H) -H #V1 #T1 #_ #HT12 #H destruct /2 width=4 by/
 294   ]
 295 ]
 296 qed-.
 297
 298 lemma lifts_inv_push_zero_sn (f):
 299       ∀X. ⇧*[⫯f]#𝟎 ≘ X → #(𝟎) = X.
 300 #f #X #H
 301 elim (lifts_inv_lref1 … H) -H #i #Hi #H destruct
 302 lapply (pr_pat_inv_unit_push … Hi ???) -Hi //
 303 qed-.
 304
 305 lemma lifts_inv_push_succ_sn (f) (i1):
 306       ∀X. ⇧*[⫯f]#(↑i1) ≘ X →
 307       ∃∃i2. ⇧*[f]#i1 ≘ #i2 & #(↑i2) = X.
 308 #f #i1 #X #H
 309 elim (lifts_inv_lref1 … H) -H #j #Hij #H destruct
 310 elim (pr_nat_inv_succ_push … Hij) -Hij [|*: // ] #i2 #Hi12 #H destruct
 311 /3 width=3 by lifts_lref, ex2_intro/
 312 qed-.
 313
 314 (* Inversion lemmas with uniform relocations ********************************)
 315
 316 lemma lifts_inv_lref1_uni: ∀l,Y,i. ⇧[l] #i ≘ Y → Y = #(l+i).
 317 #l #Y #i1 #H elim (lifts_inv_lref1 … H) -H
 318 #i2 #H #H2 destruct
 319 /4 width=4 by pr_nat_mono, eq_f/
 320 qed-.
 321
 322 lemma lifts_inv_lref2_uni: ∀l,X,i2. ⇧[l] X ≘ #i2 →
 323                            ∃∃i1. X = #i1 & i1 + l = i2.
 324 #l #X #i2 #H elim (lifts_inv_lref2 … H) -H
 325 /3 width=3 by pr_nat_inv_uni, ex2_intro/
 326 qed-.
 327
 328 lemma lifts_inv_lref2_uni_ge: ∀l,X,i. ⇧[l] X ≘ #(i+l) → X = #i.
 329 #l #X #i2 #H elim (lifts_inv_lref2_uni … H) -H
 330 #i1 #H1 #H2 destruct
 331 /4 width=2 by eq_inv_nplus_bi_dx, eq_f/
 332 qed-.
 333
 334 lemma lifts_inv_lref2_uni_lt: ∀l,X,i. ⇧[l] X ≘ #i → i < l → ⊥.
 335 #l #X #i2 #H elim (lifts_inv_lref2_uni … H) -H
 336 #i1 #_ #H1 #H2 destruct
 337 /2 width=4 by nlt_ge_false/
 338 qed-.
 339
 340 (* Basic forward lemmas *****************************************************)
 341
 342 (* Basic_2A1: includes: lift_inv_O2 *)
 343 lemma lifts_fwd_isid: ∀f,T1,T2. ⇧*[f] T1 ≘ T2 → 𝐈❨f❩ → T1 = T2.
 344 #f #T1 #T2 #H elim H -f -T1 -T2
 345 /4 width=3 by pr_isi_nat_des, pr_isi_push, eq_f2, eq_f/
 346 qed-.
 347
 348 (* Basic_2A1: includes: lift_fwd_pair1 *)
 349 lemma lifts_fwd_pair1: ∀f,I,V1,T1,Y. ⇧*[f] ②[I]V1.T1 ≘ Y →
 350                        ∃∃V2,T2. ⇧*[f] V1 ≘ V2 & Y = ②[I]V2.T2.
 351 #f * [ #p ] #I #V1 #T1 #Y #H
 352 [ elim (lifts_inv_bind1 … H) -H /2 width=4 by ex2_2_intro/
 353 | elim (lifts_inv_flat1 … H) -H /2 width=4 by ex2_2_intro/
 354 ]
 355 qed-.
 356
 357 (* Basic_2A1: includes: lift_fwd_pair2 *)
 358 lemma lifts_fwd_pair2: ∀f,I,V2,T2,X. ⇧*[f] X ≘ ②[I]V2.T2 →
 359                        ∃∃V1,T1. ⇧*[f] V1 ≘ V2 & X = ②[I]V1.T1.
 360 #f * [ #p ] #I #V2 #T2 #X #H
 361 [ elim (lifts_inv_bind2 … H) -H /2 width=4 by ex2_2_intro/
 362 | elim (lifts_inv_flat2 … H) -H /2 width=4 by ex2_2_intro/
 363 ]
 364 qed-.
 365
 366 (* Basic properties *********************************************************)
 367
 368 lemma liftable2_sn_dx (R): symmetric … R → liftable2_sn R → liftable2_dx R.
 369 #R #H2R #H1R #T1 #T2 #HT12 #f #U2 #HTU2
 370 elim (H1R … T1 … HTU2) -H1R /3 width=3 by ex2_intro/
 371 qed-.
 372
 373 lemma deliftable2_sn_dx (R): symmetric … R → deliftable2_sn R → deliftable2_dx R.
 374 #R #H2R #H1R #U1 #U2 #HU12 #f #T2 #HTU2
 375 elim (H1R … U1 … HTU2) -H1R /3 width=3 by ex2_intro/
 376 qed-.
 377
 378 lemma lifts_eq_repl_back: ∀T1,T2. pr_eq_repl_back … (λf. ⇧*[f] T1 ≘ T2).
 379 #T1 #T2 #f1 #H elim H -T1 -T2 -f1
 380 /4 width=5 by lifts_flat, lifts_bind, lifts_lref, pr_pat_eq_repl_back, pr_eq_push/
 381 qed-.
 382
 383 lemma lifts_eq_repl_fwd: ∀T1,T2. pr_eq_repl_fwd … (λf. ⇧*[f] T1 ≘ T2).
 384 #T1 #T2 @pr_eq_repl_sym /2 width=3 by lifts_eq_repl_back/ (**) (* full auto fails *)
 385 qed-.
 386
 387 (* Basic_1: includes: lift_r *)
 388 (* Basic_2A1: includes: lift_refl *)
 389 lemma lifts_refl: ∀T,f. 𝐈❨f❩ → ⇧*[f] T ≘ T.
 390 #T elim T -T *
 391 /4 width=3 by lifts_flat, lifts_bind, lifts_lref, pr_isi_inv_pat, pr_isi_push/
 392 qed.
 393
 394 (* Basic_2A1: includes: lift_total *)
 395 lemma lifts_total: ∀T1,f. 𝐓❨f❩ → ∃T2. ⇧*[f] T1 ≘ T2.
 396 #T1 elim T1 -T1 *
 397 /3 width=2 by lifts_sort, lifts_gref, ex_intro/
 398 [ #i #f #Hf elim (Hf (↑i)) -Hf /3 width=2 by ex_intro, lifts_lref/ ]
 399 [ #p ] #I #V1 #T1 #IHV1 #IHT1 #f #Hf
 400 elim (IHV1 f) -IHV1 // #V2 #HV12
 401 [ elim (IHT1 (⫯f)) -IHT1 /3 width=2 by pr_ist_push, ex_intro, lifts_bind/
 402 | elim (IHT1 f) -IHT1 /3 width=2 by lifts_flat, ex_intro/
 403 ]
 404 qed-.
 405
 406 lemma lifts_push_zero (f): ⇧*[⫯f]#(𝟎) ≘ #(𝟎).
 407 /3 width=2 by pr_nat_refl, lifts_lref/ qed.
 408
 409 lemma lifts_push_lref (f) (i1) (i2): ⇧*[f]#i1 ≘ #i2 → ⇧*[⫯f]#(↑i1) ≘ #(↑i2).
 410 #f1 #i1 #i2 #H
 411 elim (lifts_inv_lref1 … H) -H #j #Hij #H destruct
 412 /3 width=7 by lifts_lref, pr_pat_push/
 413 qed.
 414
 415 lemma lifts_lref_uni: ∀l,i. ⇧[l] #i ≘ #(l+i).
 416 #l elim l -l /2 width=1 by lifts_lref/
 417 qed.
 418
 419 (* Basic_1: includes: lift_free (right to left) *)
 420 (* Basic_2A1: includes: lift_split *)
 421 lemma lifts_split_trans: ∀f,T1,T2. ⇧*[f] T1 ≘ T2 →
 422                          ∀f1,f2. f2 ⊚ f1 ≘ f →
 423                          ∃∃T. ⇧*[f1] T1 ≘ T & ⇧*[f2] T ≘ T2.
 424 #f #T1 #T2 #H elim H -f -T1 -T2
 425 [ /3 width=3 by lifts_sort, ex2_intro/
 426 | #f #i1 #i2 #Hi #f1 #f2 #Ht elim (pr_after_nat_des … Hi … Ht) -Hi -Ht
 427   /3 width=3 by lifts_lref, ex2_intro/
 428 | /3 width=3 by lifts_gref, ex2_intro/
 429 | #f #p #I #V1 #V2 #T1 #T2 #_ #_ #IHV #IHT #f1 #f2 #Ht
 430   elim (IHV … Ht) elim (IHT (⫯f1) (⫯f2)) -IHV -IHT
 431   /3 width=7 by pr_after_refl, ex2_intro, lifts_bind/
 432 | #f #I #V1 #V2 #T1 #T2 #_ #_ #IHV #IHT #f1 #f2 #Ht
 433   elim (IHV … Ht) elim (IHT … Ht) -IHV -IHT -Ht
 434   /3 width=5 by lifts_flat, ex2_intro/
 435 ]
 436 qed-.
 437
 438 (* Note: apparently, this was missing in Basic_2A1 *)
 439 lemma lifts_split_div: ∀f1,T1,T2. ⇧*[f1] T1 ≘ T2 →
 440                        ∀f2. 𝐓❨f2❩ → ∀f. f2 ⊚ f1 ≘ f →
 441                        ∃∃T. ⇧*[f2] T2 ≘ T & ⇧*[f] T1 ≘ T.
 442 #f1 #T1 #T2 #H elim H -f1 -T1 -T2
 443 [ /3 width=3 by lifts_sort, ex2_intro/
 444 | #f1 #i1 #i2 #Hi #f2 #Hf2 #f #Ht
 445   elim (pr_after_des_ist_nat … Hi … Ht) -Hi -Ht
 446   /3 width=3 by lifts_lref, ex2_intro/
 447 | /3 width=3 by lifts_gref, ex2_intro/
 448 | #f1 #p #I #V1 #V2 #T1 #T2 #_ #_ #IHV #IHT #f2 #Hf2 #f #Ht
 449   elim (IHV … Ht) elim (IHT (⫯f2) … (⫯f)) -IHV -IHT
 450   /3 width=7 by pr_ist_push, pr_after_refl, ex2_intro, lifts_bind/
 451 | #f1 #I #V1 #V2 #T1 #T2 #_ #_ #IHV #IHT #f2 #Hf2 #f #Ht
 452   elim (IHV … Ht) elim (IHT … Ht) -IHV -IHT -Ht
 453   /3 width=5 by lifts_flat, ex2_intro/
 454 ]
 455 qed-.
 456
 457 (* Basic_1: includes: dnf_dec2 dnf_dec *)
 458 (* Basic_2A1: includes: is_lift_dec *)
 459 lemma is_lifts_dec: ∀T2,f. 𝐓❨f❩ → Decidable (∃T1. ⇧*[f] T1 ≘ T2).
 460 #T1 elim T1 -T1
 461 [ * [1,3: /3 width=2 by lifts_sort, lifts_gref, ex_intro, or_introl/ ]
 462   #i2 #f #Hf elim (is_pr_nat_dec f i2) //
 463   [ * /4 width=3 by lifts_lref, ex_intro, or_introl/
 464   | #H @or_intror *
 465     #X #HX elim (lifts_inv_lref2 … HX) -HX
 466     /3 width=2 by ex_intro/
 467   ]
 468 | * [ #p ] #I #V2 #T2 #IHV2 #IHT2 #f #Hf
 469   [ elim (IHV2 f) -IHV2 //
 470     [ * #V1 #HV12 elim (IHT2 (⫯f)) -IHT2 /2 width=1 by pr_ist_push/
 471       [ * #T1 #HT12 @or_introl /3 width=2 by lifts_bind, ex_intro/
 472       | -V1 #HT2 @or_intror * #X #H
 473         elim (lifts_inv_bind2 … H) -H /3 width=2 by ex_intro/
 474       ]
 475     | -IHT2 #HV2 @or_intror * #X #H
 476       elim (lifts_inv_bind2 … H) -H /3 width=2 by ex_intro/
 477     ]
 478   | elim (IHV2 f) -IHV2 //
 479     [ * #V1 #HV12 elim (IHT2 f) -IHT2 //
 480       [ * #T1 #HT12 /4 width=2 by lifts_flat, ex_intro, or_introl/
 481       | -V1 #HT2 @or_intror * #X #H
 482         elim (lifts_inv_flat2 … H) -H /3 width=2 by ex_intro/
 483       ]
 484     | -IHT2 #HV2 @or_intror * #X #H
 485       elim (lifts_inv_flat2 … H) -H /3 width=2 by ex_intro/
 486     ]
 487   ]
 488 ]
 489 qed-.
 490
 491 (* Properties with uniform relocation ***************************************)
 492
 493 lemma lifts_uni: ∀n1,n2,T,U. ⇧*[𝐮❨n2❩∘𝐮❨n1❩] T ≘ U → ⇧[n1+n2] T ≘ U.
 494 /3 width=4 by lifts_eq_repl_back, pr_after_inv_total/ qed.
 495
 496 (* Basic_2A1: removed theorems 14:
 497               lifts_inv_nil lifts_inv_cons
 498               lift_inv_Y1 lift_inv_Y2 lift_inv_lref_Y1 lift_inv_lref_Y2 lift_lref_Y lift_Y1
 499               lift_lref_lt_eq lift_lref_ge_eq lift_lref_plus lift_lref_pred
 500               lift_lref_ge_minus lift_lref_ge_minus_eq
 501 *)
 502 (* Basic_1: removed theorems 8:
 503             lift_lref_gt
 504             lift_head lift_gen_head
 505             lift_weight_map lift_weight lift_weight_add lift_weight_add_O
 506             lift_tlt_dx
 507 *)