matita/matita/contribs/lambdadelta/static_2/relocation/drops_sex.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 "static_2/relocation/lifts_lifts_bind.ma".
  16 include "static_2/relocation/drops.ma".
  17
  18 (* GENERIC SLICING FOR LOCAL ENVIRONMENTS ***********************************)
  19
  20 (* Properties with entrywise extension of context-sensitive relations *******)
  21
  22 (**) (* changed after commit 13218 *)
  23 lemma sex_co_dropable_sn (RN) (RP):
  24       co_dropable_sn (sex RN RP).
  25 #RN #RP #b #f #L1 #K1 #H elim H -f -L1 -K1
  26 [ #f #Hf #_ #f2 #X #H #f1 #Hf2 >(sex_inv_atom1 … H) -X
  27   /4 width=3 by sex_atom, drops_atom, ex2_intro/
  28 | #f #I1 #L1 #K1 #_ #IH #Hf #f2 #X #H #f1 #Hf2
  29   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H2 destruct
  30   elim (sex_inv_push1 … H) -H #I2 #L2 #HL12 #HI12 #H destruct
  31   elim (IH … HL12 … Hg2) -g2
  32   /3 width=3 by isuni_inv_next, drops_drop, ex2_intro/
  33 | #f #I1 #J1 #L1 #K1 #HLK #HJI1 #IH #Hf #f2 #X #H #f1 #Hf2
  34   lapply (isuni_inv_push … Hf ??) -Hf [3: |*: // ] #Hf
  35   lapply (drops_fwd_isid … HLK … Hf) -HLK #H0 destruct
  36   lapply (liftsb_fwd_isid … HJI1 … Hf) -HJI1 #H0 destruct
  37   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3:* |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
  38   [ elim (sex_inv_push1 … H) | elim (sex_inv_next1 … H) ] -H #I2 #L2 #HL12 #HI12 #H destruct
  39   elim (IH … HL12 … Hg2) -g2 -IH /2 width=1 by isuni_isid/ #K2 #HK12 #HLK2
  40   lapply (drops_fwd_isid … HLK2 … Hf) -HLK2 #H0 destruct
  41   /4 width=3 by drops_refl, sex_next, sex_push, isid_push, ex2_intro/
  42 ]
  43 qed-.
  44
  45 lemma sex_liftable_co_dedropable_bi (RN) (RP):
  46       d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
  47       ∀f2,L1,L2. L1 ⪤[cfull,RP,f2] L2 → ∀f1,K1,K2. K1 ⪤[RN,RP,f1] K2 →
  48       ∀b,f. ⇩*[b,f] L1 ≘ K1 → ⇩*[b,f] L2 ≘ K2 →
  49       f ~⊚ f1 ≘ f2 → L1 ⪤[RN,RP,f2] L2.
  50 #RN #RP #HRN #HRP #f2 #L1 #L2 #H elim H -f2 -L1 -L2 //
  51 #g2 #I1 #I2 #L1 #L2 #HL12 #HI12 #IH #f1 #Y1 #Y2 #HK12 #b #f #HY1 #HY2 #H
  52 [ elim (coafter_inv_xxn … H) [ |*: // ] -H #g #g1 #Hg2 #H1 #H2 destruct
  53   elim (drops_inv_skip1 … HY1) -HY1 #J1 #K1 #HLK1 #HJI1 #H destruct
  54   elim (drops_inv_skip1 … HY2) -HY2 #J2 #K2 #HLK2 #HJI2 #H destruct
  55   elim (sex_inv_next … HK12) -HK12 #HK12 #HJ12
  56   elim (HRN … HJ12 … HLK1 … HJI1) -HJ12 -HJI1 #Z #Hz
  57   >(liftsb_mono … Hz … HJI2) -Z /3 width=9 by sex_next/
  58 | elim (coafter_inv_xxp … H) [1,2: |*: // ] -H *
  59   [ #g #g1 #Hg2 #H1 #H2 destruct
  60     elim (drops_inv_skip1 … HY1) -HY1 #J1 #K1 #HLK1 #HJI1 #H destruct
  61     elim (drops_inv_skip1 … HY2) -HY2 #J2 #K2 #HLK2 #HJI2 #H destruct
  62     elim (sex_inv_push … HK12) -HK12 #HK12 #HJ12
  63     elim (HRP … HJ12 … HLK1 … HJI1) -HJ12 -HJI1 #Z #Hz
  64     >(liftsb_mono … Hz … HJI2) -Z /3 width=9 by sex_push/
  65   | #g #Hg2 #H destruct
  66     lapply (drops_inv_drop1 … HY1) -HY1 #HLK1
  67     lapply (drops_inv_drop1 … HY2) -HY2 #HLK2
  68     /3 width=9 by sex_push/
  69   ]
  70 ]
  71 qed-.
  72
  73 lemma sex_liftable_co_dedropable_sn (RN) (RP):
  74       (∀L. reflexive … (RN L)) → (∀L. reflexive … (RP L)) →
  75       d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
  76       co_dedropable_sn (sex RN RP).
  77 #RN #RP #H1RN #H1RP #H2RN #H2RP #b #f #L1 #K1 #H elim H -f -L1 -K1
  78 [ #f #Hf #X #f1 #H #f2 #Hf2 >(sex_inv_atom1 … H) -X
  79   /4 width=4 by drops_atom, sex_atom, ex3_intro/
  80 | #f #I1 #L1 #K1 #_ #IHLK1 #K2 #f1 #HK12 #f2 #Hf2
  81   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H destruct
  82   elim (IHLK1 … HK12 … Hg2) -K1
  83   /3 width=6 by drops_drop, sex_next, sex_push, ex3_intro/
  84 | #f #I1 #J1 #L1 #K1 #HLK1 #HJI1 #IHLK1 #X #f1 #H #f2 #Hf2
  85   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3: * |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
  86   [ elim (sex_inv_push1 … H) | elim (sex_inv_next1 … H) ] -H #J2 #K2 #HK12 #HJ12 #H destruct
  87   [ elim (H2RP … HJ12 … HLK1 … HJI1) | elim (H2RN … HJ12 … HLK1 … HJI1) ] -J1
  88   elim (IHLK1 … HK12 … Hg2) -K1
  89   /3 width=6 by drops_skip, sex_next, sex_push, ex3_intro/
  90 ]
  91 qed-.
  92
  93 fact sex_dropable_dx_aux (RN) (RP):
  94      ∀b,f,L2,K2. ⇩*[b,f] L2 ≘ K2 → 𝐔❪f❫ →
  95      ∀f2,L1. L1 ⪤[RN,RP,f2] L2 → ∀f1. f ~⊚ f1 ≘ f2 →
  96      ∃∃K1. ⇩*[b,f] L1 ≘ K1 & K1 ⪤[RN,RP,f1] K2.
  97 #RN #RP #b #f #L2 #K2 #H elim H -f -L2 -K2
  98 [ #f #Hf #_ #f2 #X #H #f1 #Hf2 lapply (sex_inv_atom2 … H) -H
  99   #H destruct /4 width=3 by sex_atom, drops_atom, ex2_intro/
 100 | #f #I2 #L2 #K2 #_ #IH #Hf #f2 #X #HX #f1 #Hf2
 101   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H destruct
 102   elim (sex_inv_push2 … HX) -HX #I1 #L1 #HL12 #HI12 #H destruct
 103   elim (IH … HL12 … Hg2) -L2 -I2 -g2
 104   /3 width=3 by drops_drop, isuni_inv_next, ex2_intro/
 105 | #f #I2 #J2 #L2 #K2 #_ #HJI2 #IH #Hf #f2 #X #HX #f1 #Hf2
 106   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3: * |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
 107   [ elim (sex_inv_push2 … HX) | elim (sex_inv_next2 … HX) ] -HX #I1 #L1 #HL12 #HI12 #H destruct
 108   elim (IH … HL12 … Hg2) -L2 -g2 /2 width=3 by isuni_fwd_push/ #K1 #HLK1 #HK12
 109   lapply (isuni_inv_push … Hf ??) -Hf [3,6: |*: // ] #Hf
 110   lapply (liftsb_fwd_isid … HJI2 … Hf) #H destruct -HJI2
 111   lapply (drops_fwd_isid … HLK1 … Hf) #H destruct -HLK1
 112   /4 width=5 by sex_next, sex_push, drops_refl, isid_push, ex2_intro/
 113 ]
 114 qed-.
 115
 116 lemma sex_co_dropable_dx (RN) (RP):
 117       co_dropable_dx (sex RN RP).
 118 /2 width=5 by sex_dropable_dx_aux/ qed-.
 119
 120 lemma sex_drops_conf_next (RN) (RP):
 121       ∀f2,L1,L2. L1 ⪤[RN,RP,f2] L2 →
 122       ∀b,f,I1,K1. ⇩*[b,f] L1 ≘ K1.ⓘ[I1] → 𝐔❪f❫ →
 123       ∀f1. f ~⊚ ↑f1 ≘ f2 →
 124       ∃∃I2,K2. ⇩*[b,f] L2 ≘ K2.ⓘ[I2] & K1 ⪤[RN,RP,f1] K2 & RN K1 I1 I2.
 125 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I1 #K1 #HLK1 #Hf #f1 #Hf2
 126 elim (sex_co_dropable_sn … HLK1 … Hf … HL12 … Hf2) -L1 -f2 -Hf
 127 #X #HX #HLK2 elim (sex_inv_next1 … HX) -HX
 128 #I2 #K2 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
 129 qed-.
 130
 131 lemma sex_drops_conf_push (RN) (RP):
 132       ∀f2,L1,L2. L1 ⪤[RN,RP,f2] L2 →
 133       ∀b,f,I1,K1. ⇩*[b,f] L1 ≘ K1.ⓘ[I1] → 𝐔❪f❫ →
 134       ∀f1. f ~⊚ ⫯f1 ≘ f2 →
 135       ∃∃I2,K2. ⇩*[b,f] L2 ≘ K2.ⓘ[I2] & K1 ⪤[RN,RP,f1] K2 & RP K1 I1 I2.
 136 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I1 #K1 #HLK1 #Hf #f1 #Hf2
 137 elim (sex_co_dropable_sn … HLK1 … Hf … HL12 … Hf2) -L1 -f2 -Hf
 138 #X #HX #HLK2 elim (sex_inv_push1 … HX) -HX
 139 #I2 #K2 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
 140 qed-.
 141
 142 lemma sex_drops_trans_next (RN) (RP):
 143       ∀f2,L1,L2. L1 ⪤[RN,RP,f2] L2 →
 144       ∀b,f,I2,K2. ⇩*[b,f] L2 ≘ K2.ⓘ[I2] → 𝐔❪f❫ →
 145       ∀f1. f ~⊚ ↑f1 ≘ f2 →
 146       ∃∃I1,K1. ⇩*[b,f] L1 ≘ K1.ⓘ[I1] & K1 ⪤[RN,RP,f1] K2 & RN K1 I1 I2.
 147 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I2 #K2 #HLK2 #Hf #f1 #Hf2
 148 elim (sex_co_dropable_dx … HL12 … HLK2 … Hf … Hf2) -L2 -f2 -Hf
 149 #X #HLK1 #HX elim (sex_inv_next2 … HX) -HX
 150 #I1 #K1 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
 151 qed-.
 152
 153 lemma sex_drops_trans_push (RN) (RP): ∀f2,L1,L2. L1 ⪤[RN,RP,f2] L2 →
 154       ∀b,f,I2,K2. ⇩*[b,f] L2 ≘ K2.ⓘ[I2] → 𝐔❪f❫ →
 155       ∀f1. f ~⊚ ⫯f1 ≘ f2 →
 156       ∃∃I1,K1. ⇩*[b,f] L1 ≘ K1.ⓘ[I1] & K1 ⪤[RN,RP,f1] K2 & RP K1 I1 I2.
 157 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I2 #K2 #HLK2 #Hf #f1 #Hf2
 158 elim (sex_co_dropable_dx … HL12 … HLK2 … Hf … Hf2) -L2 -f2 -Hf
 159 #X #HLK1 #HX elim (sex_inv_push2 … HX) -HX
 160 #I1 #K1 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
 161 qed-.
 162
 163 lemma drops_sex_trans_next (RN) (RP):
 164       (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
 165       d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
 166       ∀f1,K1,K2. K1 ⪤[RN,RP,f1] K2 →
 167       ∀b,f,I1,L1. ⇩*[b,f] L1.ⓘ[I1] ≘ K1 →
 168       ∀f2. f ~⊚ f1 ≘ ↑f2 →
 169       ∃∃I2,L2. ⇩*[b,f] L2.ⓘ[I2] ≘ K2 & L1 ⪤[RN,RP,f2] L2 & RN L1 I1 I2 & L1.ⓘ[I1] ≡[f] L2.ⓘ[I2].
 170 #RN #RP #H1RN #H1RP #H2RN #H2RP #f1 #K1 #K2 #HK12 #b #f #I1 #L1 #HLK1 #f2 #Hf2
 171 elim (sex_liftable_co_dedropable_sn … H1RN H1RP H2RN H2RP … HLK1 … HK12 … Hf2) -K1 -f1 -H1RN -H1RP -H2RN -H2RP
 172 #X #HX #HLK2 #H1L12 elim (sex_inv_next1 … HX) -HX
 173 #I2 #L2 #H2L12 #HI12 #H destruct /2 width=6 by ex4_2_intro/
 174 qed-.
 175
 176 lemma drops_sex_trans_push (RN) (RP):
 177       (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
 178       d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
 179       ∀f1,K1,K2. K1 ⪤[RN,RP,f1] K2 →
 180       ∀b,f,I1,L1. ⇩*[b,f] L1.ⓘ[I1] ≘ K1 →
 181       ∀f2. f ~⊚ f1 ≘ ⫯f2 →
 182       ∃∃I2,L2. ⇩*[b,f] L2.ⓘ[I2] ≘ K2 & L1 ⪤[RN,RP,f2] L2 & RP L1 I1 I2 & L1.ⓘ[I1] ≡[f] L2.ⓘ[I2].
 183 #RN #RP #H1RN #H1RP #H2RN #H2RP #f1 #K1 #K2 #HK12 #b #f #I1 #L1 #HLK1 #f2 #Hf2
 184 elim (sex_liftable_co_dedropable_sn … H1RN H1RP H2RN H2RP … HLK1 … HK12 … Hf2) -K1 -f1 -H1RN -H1RP -H2RN -H2RP
 185 #X #HX #HLK2 #H1L12 elim (sex_inv_push1 … HX) -HX
 186 #I2 #L2 #H2L12 #HI12 #H destruct /2 width=6 by ex4_2_intro/
 187 qed-.
 188
 189 lemma drops_atom2_sex_conf (RN) (RP):
 190       ∀b,f1,L1. ⇩*[b,f1] L1 ≘ ⋆ → 𝐔❪f1❫ →
 191       ∀f,L2. L1 ⪤[RN,RP,f] L2 →
 192       ∀f2. f1 ~⊚ f2 ≘f → ⇩*[b,f1] L2 ≘ ⋆.
 193 #RN #RP #b #f1 #L1 #H1 #Hf1 #f #L2 #H2 #f2 #H3
 194 elim (sex_co_dropable_sn … H1 … H2 … H3) // -H1 -H2 -H3 -Hf1
 195 #L #H #HL2 lapply (sex_inv_atom1 … H) -H //
 196 qed-.
 197
 198 lemma sex_sdj_split_dx (R1) (R2) (RP):
 199       c_reflexive … R1 → c_reflexive … R2 → c_reflexive … RP →
 200       ∀L1,f1.
 201       (∀g,I,K,n. ⇩[n] L1 ≘ K.ⓘ[I] → ↑g = ⫰*[n] f1 → R_pw_confluent1_sex R1 R1 R2 cfull g K I) →
 202       ∀L2. L1 ⪤[R1,RP,f1] L2 → ∀f2. f1 ∥ f2 →
 203       ∃∃L. L1 ⪤[R2,cfull,f1] L & L ⪤[RP,R1,f2] L2.
 204 #R1 #R2 #RP #HR1 #HR2 #HRP #L1 elim L1 -L1
 205 [ #f1 #_ #L2 #H #f2 #_
 206   lapply (sex_inv_atom1 … H) -H #H destruct
 207   /2 width=3 by sex_atom, ex2_intro/
 208 | #K1 #I1 #IH #f1 elim (pn_split f1) * #g1 #H destruct
 209   #HR #L2 #H #f2 #Hf
 210   [ elim (sex_inv_push1 … H) -H #I2 #K2 #HK12 #HI12 #H destruct
 211     elim (sdj_inv_px … Hf ??) -Hf [1,3: * |*: // ] #g2 #Hg #H destruct
 212     elim (IH … HK12 … Hg) -IH -HK12 -Hg
 213     [1,3: /3 width=5 by sex_next, sex_push, ex2_intro/
 214     |2,4: /3 width=3 by drops_drop/
 215     ]
 216   | elim (sex_inv_next1 … H) -H #I2 #K2 #HK12 #HI12 #H destruct
 217     elim (sdj_inv_nx … Hf ??) -Hf [|*: // ] #g2 #Hg #H destruct
 218     elim (IH … HK12 … Hg) -IH -HK12 -Hg
 219     [ /5 width=11 by sex_next, sex_push, drops_refl, ex2_intro/
 220     | /3 width=3 by drops_drop/
 221     ]
 222   ]
 223 ]
 224 qed-.