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/drops.ma".
  16
  17 (* GENERIC SLICING FOR LOCAL ENVIRONMENTS ***********************************)
  18
  19 (* Properties with entrywise extension of context-sensitive relations *******)
  20
  21 (* Basic_2A1: includes: lpx_sn_deliftable_dropable *) (**) (* changed after commit 13218 *)
  22 lemma lexs_co_dropable_sn: ∀RN,RP. co_dropable_sn (lexs RN RP).
  23 #RN #RP #b #f #L1 #K1 #H elim H -f -L1 -K1
  24 [ #f #Hf #_ #f2 #X #H #f1 #Hf2 >(lexs_inv_atom1 … H) -X
  25   /4 width=3 by lexs_atom, drops_atom, ex2_intro/
  26 | #f #I #L1 #K1 #V1 #_ #IH #Hf #f2 #X #H #f1 #Hf2
  27   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H2 destruct
  28   elim (lexs_inv_push1 … H) -H #L2 #V2 #HL12 #HV12 #H destruct
  29   elim (IH … HL12 … Hg2) -g2
  30   /3 width=3 by isuni_inv_next, drops_drop, ex2_intro/
  31 | #f #I #L1 #K1 #V1 #W1 #HLK #HWV #IH #Hf #f2 #X #H #f1 #Hf2
  32   lapply (isuni_inv_push … Hf ??) -Hf [3: |*: // ] #Hf
  33   lapply (drops_fwd_isid … HLK … Hf) -HLK #H0 destruct
  34   lapply (lifts_fwd_isid … HWV … Hf) -HWV #H0 destruct
  35   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3:* |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
  36   [ elim (lexs_inv_push1 … H) | elim (lexs_inv_next1 … H) ] -H #L2 #V2 #HL12 #HV12 #H destruct
  37   elim (IH … HL12 … Hg2) -g2 -IH /2 width=1 by isuni_isid/ #K2 #HK12 #HLK2
  38   lapply (drops_fwd_isid … HLK2 … Hf) -HLK2 #H0 destruct
  39   /4 width=3 by drops_refl, lexs_next, lexs_push, isid_push, ex2_intro/
  40 ]
  41 qed-.
  42
  43 (* Basic_2A1: includes: lpx_sn_liftable_dedropable *)
  44 lemma lexs_liftable_co_dedropable: ∀RN,RP. (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
  45                                    d_liftable2 RN → d_liftable2 RP → co_dedropable_sn (lexs RN RP).
  46 #RN #RP #H1RN #H1RP #H2RN #H2RP #b #f #L1 #K1 #H elim H -f -L1 -K1
  47 [ #f #Hf #X #f1 #H #f2 #Hf2 >(lexs_inv_atom1 … H) -X
  48   /4 width=4 by drops_atom, lexs_atom, ex3_intro/
  49 | #f #I #L1 #K1 #V1 #_ #IHLK1 #K2 #f1 #HK12 #f2 #Hf2
  50   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H destruct
  51   elim (IHLK1 … HK12 … Hg2) -K1
  52   /3 width=6 by drops_drop, lexs_next, lexs_push, ex3_intro/
  53 | #f #I #L1 #K1 #V1 #W1 #HLK1 #HWV1 #IHLK1 #X #f1 #H #f2 #Hf2
  54   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3: * |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
  55   [ elim (lexs_inv_push1 … H) | elim (lexs_inv_next1 … H) ] -H #K2 #W2 #HK12 #HW12 #H destruct
  56   [ elim (H2RP … HW12 … HLK1 … HWV1) | elim (H2RN … HW12 … HLK1 … HWV1) ] -W1
  57   elim (IHLK1 … HK12 … Hg2) -K1
  58   /3 width=6 by drops_skip, lexs_next, lexs_push, ex3_intro/
  59 ]
  60 qed-.
  61
  62 fact lexs_dropable_dx_aux: ∀RN,RP,b,f,L2,K2. ⬇*[b, f] L2 ≡ K2 → 𝐔⦃f⦄ →
  63                            ∀f2,L1. L1 ⦻*[RN, RP, f2] L2 → ∀f1. f ~⊚ f1 ≡ f2 →
  64                            ∃∃K1. ⬇*[b, f] L1 ≡ K1 & K1 ⦻*[RN, RP, f1] K2.
  65 #RN #RP #b #f #L2 #K2 #H elim H -f -L2 -K2
  66 [ #f #Hf #_ #f2 #X #H #f1 #Hf2 lapply (lexs_inv_atom2 … H) -H
  67   #H destruct /4 width=3 by lexs_atom, drops_atom, ex2_intro/
  68 | #f #I #L2 #K2 #V2 #_ #IH #Hf #f2 #X #HX #f1 #Hf2
  69   elim (coafter_inv_nxx … Hf2) -Hf2 [2,3: // ] #g2 #Hg2 #H destruct
  70   elim (lexs_inv_push2 … HX) -HX #L1 #V1 #HL12 #HV12 #H destruct
  71   elim (IH … HL12 … Hg2) -L2 -V2 -g2
  72   /3 width=3 by drops_drop, isuni_inv_next, ex2_intro/
  73 | #f #I #L2 #K2 #V2 #W2 #_ #HWV2 #IH #Hf #f2 #X #HX #f1 #Hf2
  74   elim (coafter_inv_pxx … Hf2) -Hf2 [1,3: * |*: // ] #g1 #g2 #Hg2 #H1 #H2 destruct
  75   [ elim (lexs_inv_push2 … HX) | elim (lexs_inv_next2 … HX) ] -HX #L1 #V1 #HL12 #HV12 #H destruct
  76   elim (IH … HL12 … Hg2) -L2 -g2 /2 width=3 by isuni_fwd_push/ #K1 #HLK1 #HK12
  77   lapply (isuni_inv_push … Hf ??) -Hf [3,6: |*: // ] #Hf
  78   lapply (lifts_fwd_isid … HWV2 … Hf) #H destruct -HWV2
  79   lapply (drops_fwd_isid … HLK1 … Hf) #H destruct -HLK1
  80   /4 width=5 by lexs_next, lexs_push, drops_refl, isid_push, ex2_intro/
  81 ]
  82 qed-.
  83
  84 (* Basic_2A1: includes: lpx_sn_dropable *)
  85 lemma lexs_co_dropable_dx: ∀RN,RP. co_dropable_dx (lexs RN RP).
  86 /2 width=5 by lexs_dropable_dx_aux/ qed-.
  87
  88 (* Basic_2A1: includes: lpx_sn_drop_conf *) (**)
  89 lemma lexs_drops_conf_next: ∀RN,RP.
  90                             ∀f2,L1,L2. L1 ⦻*[RN, RP, f2] L2 →
  91                             ∀b,f,I,K1,V1. ⬇*[b,f] L1 ≡ K1.ⓑ{I}V1 → 𝐔⦃f⦄ →
  92                             ∀f1. f ~⊚ ⫯f1 ≡ f2 →
  93                             ∃∃K2,V2. ⬇*[b,f] L2 ≡ K2.ⓑ{I}V2 & K1 ⦻*[RN, RP, f1] K2 & RN K1 V1 V2.
  94 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I #K1 #V1 #HLK1 #Hf #f1 #Hf2
  95 elim (lexs_co_dropable_sn … HLK1 … Hf … HL12 … Hf2) -L1 -f2 -Hf
  96 #X #HX #HLK2 elim (lexs_inv_next1 … HX) -HX
  97 #K2 #V2 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
  98 qed-.
  99
 100 lemma lexs_drops_conf_push: ∀RN,RP.
 101                             ∀f2,L1,L2. L1 ⦻*[RN, RP, f2] L2 →
 102                             ∀b,f,I,K1,V1. ⬇*[b,f] L1 ≡ K1.ⓑ{I}V1 → 𝐔⦃f⦄ →
 103                             ∀f1. f ~⊚ ↑f1 ≡ f2 →
 104                             ∃∃K2,V2. ⬇*[b,f] L2 ≡ K2.ⓑ{I}V2 & K1 ⦻*[RN, RP, f1] K2 & RP K1 V1 V2.
 105 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I #K1 #V1 #HLK1 #Hf #f1 #Hf2
 106 elim (lexs_co_dropable_sn … HLK1 … Hf … HL12 … Hf2) -L1 -f2 -Hf
 107 #X #HX #HLK2 elim (lexs_inv_push1 … HX) -HX
 108 #K2 #V2 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
 109 qed-.
 110
 111 (* Basic_2A1: includes: lpx_sn_drop_trans *)
 112 lemma lexs_drops_trans_next: ∀RN,RP,f2,L1,L2. L1 ⦻*[RN, RP, f2] L2 →
 113                              ∀b,f,I,K2,V2. ⬇*[b,f] L2 ≡ K2.ⓑ{I}V2 → 𝐔⦃f⦄ →
 114                              ∀f1. f ~⊚ ⫯f1 ≡ f2 →
 115                              ∃∃K1,V1. ⬇*[b,f] L1 ≡ K1.ⓑ{I}V1 & K1 ⦻*[RN, RP, f1] K2 & RN K1 V1 V2.
 116 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I #K1 #V1 #HLK1 #Hf #f1 #Hf2
 117 elim (lexs_co_dropable_dx … HL12 … HLK1 … Hf … Hf2) -L2 -f2 -Hf
 118 #X #HLK1 #HX elim (lexs_inv_next2 … HX) -HX
 119 #K1 #V1 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
 120 qed-.
 121
 122 lemma lexs_drops_trans_push: ∀RN,RP,f2,L1,L2. L1 ⦻*[RN, RP, f2] L2 →
 123                              ∀b,f,I,K2,V2. ⬇*[b,f] L2 ≡ K2.ⓑ{I}V2 → 𝐔⦃f⦄ →
 124                              ∀f1. f ~⊚ ↑f1 ≡ f2 →
 125                              ∃∃K1,V1. ⬇*[b,f] L1 ≡ K1.ⓑ{I}V1 & K1 ⦻*[RN, RP, f1] K2 & RP K1 V1 V2.
 126 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I #K1 #V1 #HLK1 #Hf #f1 #Hf2
 127 elim (lexs_co_dropable_dx … HL12 … HLK1 … Hf … Hf2) -L2 -f2 -Hf
 128 #X #HLK1 #HX elim (lexs_inv_push2 … HX) -HX
 129 #K1 #V1 #HK12 #HV12 #H destruct /2 width=5 by ex3_2_intro/
 130 qed-.
 131
 132 lemma drops_lexs_trans_next: ∀RN,RP. (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
 133                              d_liftable2 RN → d_liftable2 RP →
 134                              ∀f1,K1,K2. K1 ⦻*[RN, RP, f1] K2 →
 135                              ∀b,f,I,L1,V1. ⬇*[b,f] L1.ⓑ{I}V1 ≡ K1 →
 136                              ∀f2. f ~⊚ f1 ≡ ⫯f2 →
 137                              ∃∃L2,V2. ⬇*[b,f] L2.ⓑ{I}V2 ≡ K2 & L1 ⦻*[RN, RP, f2] L2 & RN L1 V1 V2 & L1.ⓑ{I}V1≡[f]L2.ⓑ{I}V2.
 138 #RN #RP #H1RN #H1RP #H2RN #H2RP #f1 #K1 #K2 #HK12 #b #f #I #L1 #V1 #HLK1 #f2 #Hf2
 139 elim (lexs_liftable_co_dedropable … H1RN H1RP H2RN H2RP … HLK1 … HK12 … Hf2) -K1 -f1 -H1RN -H1RP -H2RN -H2RP
 140 #X #HX #HLK2 #H1L12 elim (lexs_inv_next1 … HX) -HX
 141 #L2 #V2 #H2L12 #HV12 #H destruct /2 width=6 by ex4_2_intro/
 142 qed-.
 143
 144 lemma drops_lexs_trans_push: ∀RN,RP. (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
 145                              d_liftable2 RN → d_liftable2 RP →
 146                              ∀f1,K1,K2. K1 ⦻*[RN, RP, f1] K2 →
 147                              ∀b,f,I,L1,V1. ⬇*[b,f] L1.ⓑ{I}V1 ≡ K1 →
 148                              ∀f2. f ~⊚ f1 ≡ ↑f2 →
 149                              ∃∃L2,V2. ⬇*[b,f] L2.ⓑ{I}V2 ≡ K2 & L1 ⦻*[RN, RP, f2] L2 & RP L1 V1 V2 & L1.ⓑ{I}V1≡[f]L2.ⓑ{I}V2.
 150 #RN #RP #H1RN #H1RP #H2RN #H2RP #f1 #K1 #K2 #HK12 #b #f #I #L1 #V1 #HLK1 #f2 #Hf2
 151 elim (lexs_liftable_co_dedropable … H1RN H1RP H2RN H2RP … HLK1 … HK12 … Hf2) -K1 -f1 -H1RN -H1RP -H2RN -H2RP
 152 #X #HX #HLK2 #H1L12 elim (lexs_inv_push1 … HX) -HX
 153 #L2 #V2 #H2L12 #HV12 #H destruct /2 width=6 by ex4_2_intro/
 154 qed-.