1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "basic_2/relocation/drops.ma".
17 (* GENERIC SLICING FOR LOCAL ENVIRONMENTS ***********************************)
19 (* Properties with entrywise extension of context-sensitive relations *******)
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 #I1 #L1 #K1 #_ #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 #I2 #L2 #HL12 #HI12 #H destruct
29 elim (IH … HL12 … Hg2) -g2
30 /3 width=3 by isuni_inv_next, drops_drop, ex2_intro/
31 | #f #I1 #J1 #L1 #K1 #HLK #HJI1 #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 (liftsb_fwd_isid … HJI1 … Hf) -HJI1 #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 #I2 #L2 #HL12 #HI12 #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/
43 (* Basic_2A1: includes: lpx_sn_liftable_dedropable *)
44 lemma lexs_liftable_co_dedropable_sn: ∀RN,RP. (∀L. reflexive … (RN L)) → (∀L. reflexive … (RP L)) →
45 d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb 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 #I1 #L1 #K1 #_ #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 #I1 #J1 #L1 #K1 #HLK1 #HJI1 #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 #J2 #K2 #HK12 #HJ12 #H destruct
56 [ elim (H2RP … HJ12 … HLK1 … HJI1) | elim (H2RN … HJ12 … HLK1 … HJI1) ] -J1
57 elim (IHLK1 … HK12 … Hg2) -K1
58 /3 width=6 by drops_skip, lexs_next, lexs_push, ex3_intro/
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 #I2 #L2 #K2 #_ #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 #I1 #L1 #HL12 #HI12 #H destruct
71 elim (IH … HL12 … Hg2) -L2 -I2 -g2
72 /3 width=3 by drops_drop, isuni_inv_next, ex2_intro/
73 | #f #I2 #J2 #L2 #K2 #_ #HJI2 #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 #I1 #L1 #HL12 #HI12 #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 (liftsb_fwd_isid … HJI2 … Hf) #H destruct -HJI2
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/
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-.
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,I1,K1. ⬇*[b, f] L1 ≡ K1.ⓘ{I1} → 𝐔⦃f⦄ →
93 ∃∃I2,K2. ⬇*[b, f] L2 ≡ K2.ⓘ{I2} & K1 ⪤*[RN, RP, f1] K2 & RN K1 I1 I2.
94 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I1 #K1 #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 #I2 #K2 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
100 lemma lexs_drops_conf_push: ∀RN,RP.
101 ∀f2,L1,L2. L1 ⪤*[RN, RP, f2] L2 →
102 ∀b,f,I1,K1. ⬇*[b, f] L1 ≡ K1.ⓘ{I1} → 𝐔⦃f⦄ →
104 ∃∃I2,K2. ⬇*[b, f] L2 ≡ K2.ⓘ{I2} & K1 ⪤*[RN, RP, f1] K2 & RP K1 I1 I2.
105 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I1 #K1 #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 #I2 #K2 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
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,I2,K2. ⬇*[b, f] L2 ≡ K2.ⓘ{I2} → 𝐔⦃f⦄ →
115 ∃∃I1,K1. ⬇*[b, f] L1 ≡ K1.ⓘ{I1} & K1 ⪤*[RN, RP, f1] K2 & RN K1 I1 I2.
116 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I2 #K2 #HLK2 #Hf #f1 #Hf2
117 elim (lexs_co_dropable_dx … HL12 … HLK2 … Hf … Hf2) -L2 -f2 -Hf
118 #X #HLK1 #HX elim (lexs_inv_next2 … HX) -HX
119 #I1 #K1 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
122 lemma lexs_drops_trans_push: ∀RN,RP,f2,L1,L2. L1 ⪤*[RN, RP, f2] L2 →
123 ∀b,f,I2,K2. ⬇*[b, f] L2 ≡ K2.ⓘ{I2} → 𝐔⦃f⦄ →
125 ∃∃I1,K1. ⬇*[b, f] L1 ≡ K1.ⓘ{I1} & K1 ⪤*[RN, RP, f1] K2 & RP K1 I1 I2.
126 #RN #RP #f2 #L1 #L2 #HL12 #b #f #I2 #K2 #HLK2 #Hf #f1 #Hf2
127 elim (lexs_co_dropable_dx … HL12 … HLK2 … Hf … Hf2) -L2 -f2 -Hf
128 #X #HLK1 #HX elim (lexs_inv_push2 … HX) -HX
129 #I1 #K1 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/
132 lemma drops_lexs_trans_next: ∀RN,RP. (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
133 d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
134 ∀f1,K1,K2. K1 ⪤*[RN, RP, f1] K2 →
135 ∀b,f,I1,L1. ⬇*[b, f] L1.ⓘ{I1} ≡ K1 →
137 ∃∃I2,L2. ⬇*[b, f] L2.ⓘ{I2} ≡ K2 & L1 ⪤*[RN, RP, f2] L2 & RN L1 I1 I2 & L1.ⓘ{I1} ≡[f] L2.ⓘ{I2}.
138 #RN #RP #H1RN #H1RP #H2RN #H2RP #f1 #K1 #K2 #HK12 #b #f #I1 #L1 #HLK1 #f2 #Hf2
139 elim (lexs_liftable_co_dedropable_sn … 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 #I2 #L2 #H2L12 #HI12 #H destruct /2 width=6 by ex4_2_intro/
144 lemma drops_lexs_trans_push: ∀RN,RP. (∀L. reflexive ? (RN L)) → (∀L. reflexive ? (RP L)) →
145 d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP →
146 ∀f1,K1,K2. K1 ⪤*[RN, RP, f1] K2 →
147 ∀b,f,I1,L1. ⬇*[b, f] L1.ⓘ{I1} ≡ K1 →
149 ∃∃I2,L2. ⬇*[b, f] L2.ⓘ{I2} ≡ K2 & L1 ⪤*[RN, RP, f2] L2 & RP L1 I1 I2 & L1.ⓘ{I1} ≡[f] L2.ⓘ{I2}.
150 #RN #RP #H1RN #H1RP #H2RN #H2RP #f1 #K1 #K2 #HK12 #b #f #I1 #L1 #HLK1 #f2 #Hf2
151 elim (lexs_liftable_co_dedropable_sn … 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 #I2 #L2 #H2L12 #HI12 #H destruct /2 width=6 by ex4_2_intro/
156 lemma drops_atom2_lexs_conf: ∀RN,RP,b,f1,L1. ⬇*[b, f1] L1 ≡ ⋆ → 𝐔⦃f1⦄ →
157 ∀f,L2. L1 ⪤*[RN, RP, f] L2 →
158 ∀f2. f1 ~⊚ f2 ≡f → ⬇*[b, f1] L2 ≡ ⋆.
159 #RN #RP #b #f1 #L1 #H1 #Hf1 #f #L2 #H2 #f2 #H3
160 elim (lexs_co_dropable_sn … H1 … H2 … H3) // -H1 -H2 -H3 -Hf1
161 #L #H #HL2 lapply (lexs_inv_atom1 … H) -H //