matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lexs.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 "basic_2/relocation/lifts_lifts_bind.ma".
  16 include "basic_2/relocation/drops.ma".
  17
  18 (* GENERIC SLICING FOR LOCAL ENVIRONMENTS ***********************************)
  19
  20 (* Properties with entrywise extension of context-sensitive relations *******)
  21
  22 (* Basic_2A1: includes: lpx_sn_deliftable_dropable *) (**) (* changed after commit 13218 *)
  23 lemma lexs_co_dropable_sn: ∀RN,RP. co_dropable_sn (lexs RN RP).
  24 #RN #RP #b #f #L1 #K1 #H elim H -f -L1 -K1
  25 [ #f #Hf #_ #f2 #X #H #f1 #Hf2 >(lexs_inv_atom1 … H) -X
  26   /4 width=3 by lexs_atom, drops_atom, ex2_intro/
  27 | #f #I1 #L1 #K1 #_ #IH #Hf #f2 #X #H #f1 #Hf2
  28   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H2 destruct
  29   elim (lexs_inv_push1 … H) -H #I2 #L2 #HL12 #HI12 #H destruct
  30   elim (IH … HL12 … Hg2) -g2
  31   /3 width=3 by isuni_inv_next, drops_drop, ex2_intro/
  32 | #f #I1 #J1 #L1 #K1 #HLK #HJI1 #IH #Hf #f2 #X #H #f1 #Hf2
  33   lapply (isuni_inv_push … Hf ??) -Hf [3: |*: // ] #Hf
  34   lapply (drops_fwd_isid … HLK … Hf) -HLK #H0 destruct
  35   lapply (liftsb_fwd_isid … HJI1 … Hf) -HJI1 #H0 destruct
  36   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3:* |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
  37   [ elim (lexs_inv_push1 … H) | elim (lexs_inv_next1 … H) ] -H #I2 #L2 #HL12 #HI12 #H destruct
  38   elim (IH … HL12 … Hg2) -g2 -IH /2 width=1 by isuni_isid/ #K2 #HK12 #HLK2
  39   lapply (drops_fwd_isid … HLK2 … Hf) -HLK2 #H0 destruct
  40   /4 width=3 by drops_refl, lexs_next, lexs_push, isid_push, ex2_intro/
  41 ]
  42 qed-.
  43
  44 lemma lexs_liftable_co_dedropable_bi: ∀RN,RP. d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
  45                                       ∀f2,L1,L2. L1 ⪤*[cfull, RP, f2] L2 → ∀f1,K1,K2. K1 ⪤*[RN, RP, f1] K2 →
  46                                       ∀b,f. ⬇*[b, f] L1 ≡ K1 → ⬇*[b, f] L2 ≡ K2 →
  47                                       f ~⊚ f1 ≡ f2 → L1 ⪤*[RN, RP, f2] L2.
  48 #RN #RP #HRN #HRP #f2 #L1 #L2 #H elim H -f2 -L1 -L2 //
  49 #g2 #I1 #I2 #L1 #L2 #HL12 #HI12 #IH #f1 #Y1 #Y2 #HK12 #b #f #HY1 #HY2 #H
  50 [ elim (coafter_inv_xxn … H) [ |*: // ] -H #g #g1 #Hg2 #H1 #H2 destruct
  51   elim (drops_inv_skip1 … HY1) -HY1 #J1 #K1 #HLK1 #HJI1 #H destruct
  52   elim (drops_inv_skip1 … HY2) -HY2 #J2 #K2 #HLK2 #HJI2 #H destruct
  53   elim (lexs_inv_next … HK12) -HK12 #HK12 #HJ12
  54   elim (HRN … HJ12 … HLK1 … HJI1) -HJ12 -HJI1 #Z #Hz
  55   >(liftsb_mono … Hz … HJI2) -Z /3 width=9 by lexs_next/
  56 | elim (coafter_inv_xxp … H) [1,2: |*: // ] -H *
  57   [ #g #g1 #Hg2 #H1 #H2 destruct
  58     elim (drops_inv_skip1 … HY1) -HY1 #J1 #K1 #HLK1 #HJI1 #H destruct
  59     elim (drops_inv_skip1 … HY2) -HY2 #J2 #K2 #HLK2 #HJI2 #H destruct
  60     elim (lexs_inv_push … HK12) -HK12 #HK12 #HJ12
  61     elim (HRP … HJ12 … HLK1 … HJI1) -HJ12 -HJI1 #Z #Hz
  62     >(liftsb_mono … Hz … HJI2) -Z /3 width=9 by lexs_push/
  63   | #g #Hg2 #H destruct
  64     lapply (drops_inv_drop1 … HY1) -HY1 #HLK1
  65     lapply (drops_inv_drop1 … HY2) -HY2 #HLK2
  66     /3 width=9 by lexs_push/
  67   ]
  68 ]
  69 qed-.
  70
  71 (* Basic_2A1: includes: lpx_sn_liftable_dedropable *)
  72 lemma lexs_liftable_co_dedropable_sn: ∀RN,RP. (∀L. reflexive … (RN L)) → (∀L. reflexive … (RP L)) →
  73                                       d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
  74                                       co_dedropable_sn (lexs RN RP).
  75 #RN #RP #H1RN #H1RP #H2RN #H2RP #b #f #L1 #K1 #H elim H -f -L1 -K1
  76 [ #f #Hf #X #f1 #H #f2 #Hf2 >(lexs_inv_atom1 … H) -X
  77   /4 width=4 by drops_atom, lexs_atom, ex3_intro/
  78 | #f #I1 #L1 #K1 #_ #IHLK1 #K2 #f1 #HK12 #f2 #Hf2
  79   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H destruct
  80   elim (IHLK1 … HK12 … Hg2) -K1
  81   /3 width=6 by drops_drop, lexs_next, lexs_push, ex3_intro/
  82 | #f #I1 #J1 #L1 #K1 #HLK1 #HJI1 #IHLK1 #X #f1 #H #f2 #Hf2
  83   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3: * |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
  84   [ elim (lexs_inv_push1 … H) | elim (lexs_inv_next1 … H) ] -H #J2 #K2 #HK12 #HJ12 #H destruct
  85   [ elim (H2RP … HJ12 … HLK1 … HJI1) | elim (H2RN … HJ12 … HLK1 … HJI1) ] -J1
  86   elim (IHLK1 … HK12 … Hg2) -K1
  87   /3 width=6 by drops_skip, lexs_next, lexs_push, ex3_intro/
  88 ]
  89 qed-.
  90
  91 fact lexs_dropable_dx_aux: ∀RN,RP,b,f,L2,K2. ⬇*[b, f] L2 ≡ K2 → 𝐔⦃f⦄ →
  92                            ∀f2,L1. L1 ⪤*[RN, RP, f2] L2 → ∀f1. f ~⊚ f1 ≡ f2 →
  93                            ∃∃K1. ⬇*[b, f] L1 ≡ K1 & K1 ⪤*[RN, RP, f1] K2.
  94 #RN #RP #b #f #L2 #K2 #H elim H -f -L2 -K2
  95 [ #f #Hf #_ #f2 #X #H #f1 #Hf2 lapply (lexs_inv_atom2 … H) -H
  96   #H destruct /4 width=3 by lexs_atom, drops_atom, ex2_intro/
  97 | #f #I2 #L2 #K2 #_ #IH #Hf #f2 #X #HX #f1 #Hf2
  98   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H destruct
  99   elim (lexs_inv_push2 … HX) -HX #I1 #L1 #HL12 #HI12 #H destruct
 100   elim (IH … HL12 … Hg2) -L2 -I2 -g2
 101   /3 width=3 by drops_drop, isuni_inv_next, ex2_intro/
 102 | #f #I2 #J2 #L2 #K2 #_ #HJI2 #IH #Hf #f2 #X #HX #f1 #Hf2
 103   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3: * |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
 104   [ elim (lexs_inv_push2 … HX) | elim (lexs_inv_next2 … HX) ] -HX #I1 #L1 #HL12 #HI12 #H destruct
 105   elim (IH … HL12 … Hg2) -L2 -g2 /2 width=3 by isuni_fwd_push/ #K1 #HLK1 #HK12
 106   lapply (isuni_inv_push … Hf ??) -Hf [3,6: |*: // ] #Hf
 107   lapply (liftsb_fwd_isid … HJI2 … Hf) #H destruct -HJI2
 108   lapply (drops_fwd_isid … HLK1 … Hf) #H destruct -HLK1
 109   /4 width=5 by lexs_next, lexs_push, drops_refl, isid_push, ex2_intro/
 110 ]
 111 qed-.
 112
 113 (* Basic_2A1: includes: lpx_sn_dropable *)
 114 lemma lexs_co_dropable_dx: ∀RN,RP. co_dropable_dx (lexs RN RP).
 115 /2 width=5 by lexs_dropable_dx_aux/ qed-.
 116
 117 (* Basic_2A1: includes: lpx_sn_drop_conf *) (**)
 118 lemma lexs_drops_conf_next: ∀RN,RP.
 119                             ∀f2,L1,L2. L1 ⪤*[RN, RP, f2] L2 →
 120                             ∀b,f,I1,K1. ⬇*[b, f] L1 ≡ K1.ⓘ{I1} → 𝐔⦃f⦄ →
 121                             ∀f1. f ~⊚ ⫯f1 ≡ f2 →
 122                             ∃∃I2,K2. ⬇*[b, f] L2 ≡ K2.ⓘ{I2} & K1 ⪤*[RN, RP, f1] K2 & RN K1 I1 I2.
 123 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I1 #K1 #HLK1 #Hf #f1 #Hf2
 124 elim (lexs_co_dropable_sn … HLK1 … Hf … HL12 … Hf2) -L1 -f2 -Hf
 125 #X #HX #HLK2 elim (lexs_inv_next1 … HX) -HX
 126 #I2 #K2 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
 127 qed-.
 128
 129 lemma lexs_drops_conf_push: ∀RN,RP.
 130                             ∀f2,L1,L2. L1 ⪤*[RN, RP, f2] L2 →
 131                             ∀b,f,I1,K1. ⬇*[b, f] L1 ≡ K1.ⓘ{I1} → 𝐔⦃f⦄ →
 132                             ∀f1. f ~⊚ ↑f1 ≡ f2 →
 133                             ∃∃I2,K2. ⬇*[b, f] L2 ≡ K2.ⓘ{I2} & K1 ⪤*[RN, RP, f1] K2 & RP K1 I1 I2.
 134 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I1 #K1 #HLK1 #Hf #f1 #Hf2
 135 elim (lexs_co_dropable_sn … HLK1 … Hf … HL12 … Hf2) -L1 -f2 -Hf
 136 #X #HX #HLK2 elim (lexs_inv_push1 … HX) -HX
 137 #I2 #K2 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
 138 qed-.
 139
 140 (* Basic_2A1: includes: lpx_sn_drop_trans *)
 141 lemma lexs_drops_trans_next: ∀RN,RP,f2,L1,L2. L1 ⪤*[RN, RP, f2] L2 →
 142                              ∀b,f,I2,K2. ⬇*[b, f] L2 ≡ K2.ⓘ{I2} → 𝐔⦃f⦄ →
 143                              ∀f1. f ~⊚ ⫯f1 ≡ f2 →
 144                              ∃∃I1,K1. ⬇*[b, f] L1 ≡ K1.ⓘ{I1} & K1 ⪤*[RN, RP, f1] K2 & RN K1 I1 I2.
 145 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I2 #K2 #HLK2 #Hf #f1 #Hf2
 146 elim (lexs_co_dropable_dx … HL12 … HLK2 … Hf … Hf2) -L2 -f2 -Hf
 147 #X #HLK1 #HX elim (lexs_inv_next2 … HX) -HX
 148 #I1 #K1 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
 149 qed-.
 150
 151 lemma lexs_drops_trans_push: ∀RN,RP,f2,L1,L2. L1 ⪤*[RN, RP, f2] L2 →
 152                              ∀b,f,I2,K2. ⬇*[b, f] L2 ≡ K2.ⓘ{I2} → 𝐔⦃f⦄ →
 153                              ∀f1. f ~⊚ ↑f1 ≡ f2 →
 154                              ∃∃I1,K1. ⬇*[b, f] L1 ≡ K1.ⓘ{I1} & K1 ⪤*[RN, RP, f1] K2 & RP K1 I1 I2.
 155 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I2 #K2 #HLK2 #Hf #f1 #Hf2
 156 elim (lexs_co_dropable_dx … HL12 … HLK2 … Hf … Hf2) -L2 -f2 -Hf
 157 #X #HLK1 #HX elim (lexs_inv_push2 … HX) -HX
 158 #I1 #K1 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
 159 qed-.
 160
 161 lemma drops_lexs_trans_next: ∀RN,RP. (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
 162                              d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
 163                              ∀f1,K1,K2. K1 ⪤*[RN, RP, f1] K2 →
 164                              ∀b,f,I1,L1. ⬇*[b, f] L1.ⓘ{I1} ≡ K1 →
 165                              ∀f2. f ~⊚ f1 ≡ ⫯f2 →
 166                              ∃∃I2,L2. ⬇*[b, f] L2.ⓘ{I2} ≡ K2 & L1 ⪤*[RN, RP, f2] L2 & RN L1 I1 I2 & L1.ⓘ{I1} ≐[f] L2.ⓘ{I2}.
 167 #RN #RP #H1RN #H1RP #H2RN #H2RP #f1 #K1 #K2 #HK12 #b #f #I1 #L1 #HLK1 #f2 #Hf2
 168 elim (lexs_liftable_co_dedropable_sn … H1RN H1RP H2RN H2RP … HLK1 … HK12 … Hf2) -K1 -f1 -H1RN -H1RP -H2RN -H2RP
 169 #X #HX #HLK2 #H1L12 elim (lexs_inv_next1 … HX) -HX
 170 #I2 #L2 #H2L12 #HI12 #H destruct /2 width=6 by ex4_2_intro/
 171 qed-.
 172
 173 lemma drops_lexs_trans_push: ∀RN,RP. (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
 174                              d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
 175                              ∀f1,K1,K2. K1 ⪤*[RN, RP, f1] K2 →
 176                              ∀b,f,I1,L1. ⬇*[b, f] L1.ⓘ{I1} ≡ K1 →
 177                              ∀f2. f ~⊚ f1 ≡ ↑f2 →
 178                              ∃∃I2,L2. ⬇*[b, f] L2.ⓘ{I2} ≡ K2 & L1 ⪤*[RN, RP, f2] L2 & RP L1 I1 I2 & L1.ⓘ{I1} ≐[f] L2.ⓘ{I2}.
 179 #RN #RP #H1RN #H1RP #H2RN #H2RP #f1 #K1 #K2 #HK12 #b #f #I1 #L1 #HLK1 #f2 #Hf2
 180 elim (lexs_liftable_co_dedropable_sn … H1RN H1RP H2RN H2RP … HLK1 … HK12 … Hf2) -K1 -f1 -H1RN -H1RP -H2RN -H2RP
 181 #X #HX #HLK2 #H1L12 elim (lexs_inv_push1 … HX) -HX
 182 #I2 #L2 #H2L12 #HI12 #H destruct /2 width=6 by ex4_2_intro/
 183 qed-.
 184
 185 lemma drops_atom2_lexs_conf: ∀RN,RP,b,f1,L1. ⬇*[b, f1] L1 ≡ ⋆ → 𝐔⦃f1⦄ →
 186                              ∀f,L2. L1 ⪤*[RN, RP, f] L2 →
 187                              ∀f2. f1 ~⊚ f2 ≡f → ⬇*[b, f1] L2 ≡ ⋆.
 188 #RN #RP #b #f1 #L1 #H1 #Hf1 #f #L2 #H2 #f2 #H3
 189 elim (lexs_co_dropable_sn … H1 … H2 … H3) // -H1 -H2 -H3 -Hf1
 190 #L #H #HL2 lapply (lexs_inv_atom1 … H) -H //
 191 qed-.