matita/matita/contribs/lambdadelta/basic_2/etc_2A1/cpr/lift.etc

   1 definition t_liftable: relation term → Prop ≝
   2                        λR. ∀T1,T2. R T1 T2 → ∀U1,d,e. ⇧[d, e] T1 ≡ U1 →
   3                        ∀U2. ⇧[d, e] T2 ≡ U2 → R U1 U2.
   4
   5 definition t_deliftable_sn: relation term → Prop ≝
   6                             λR. ∀U1,U2. R U1 U2 → ∀T1,d,e. ⇧[d, e] T1 ≡ U1 →
   7                             ∃∃T2. ⇧[d, e] T2 ≡ U2 & R T1 T2.
   8
   9 lemma t_liftable_TC: ∀R. t_liftable R → t_liftable (TC … R).
  10 #R #HR #T1 #T2 #H elim H -T2
  11 [ /3 width=7/
  12 | #T #T2 #_ #HT2 #IHT1 #U1 #d #e #HTU1 #U2 #HTU2
  13   elim (lift_total T d e) /3 width=9/
  14 ]
  15 qed.
  16
  17 lemma t_deliftable_sn_TC: ∀R. t_deliftable_sn R → t_deliftable_sn (TC … R).
  18 #R #HR #U1 #U2 #H elim H -U2
  19 [ #U2 #HU12 #T1 #d #e #HTU1
  20   elim (HR … HU12 … HTU1) -U1 /3 width=3/
  21 | #U #U2 #_ #HU2 #IHU1 #T1 #d #e #HTU1
  22   elim (IHU1 … HTU1) -U1 #T #HTU #HT1
  23   elim (HR … HU2 … HTU) -U /3 width=5/
  24 ]
  25 qed-.