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/rt_equivalence/cpcs_cpcs.ma".
16 include "basic_2/dynamic/cnv_preserve_cpcs.ma".
17 include "basic_2/dynamic/nta.ma".
19 (* NATIVE TYPE ASSIGNMENT FOR TERMS *****************************************)
21 (* Properties based on preservation *****************************************)
23 lemma cnv_cpms_nta (a) (h) (G) (L):
24 ∀T. ⦃G,L⦄ ⊢ T ![a,h] → ∀U.⦃G,L⦄ ⊢ T ➡*[1,h] U → ⦃G,L⦄ ⊢ T :[a,h] U.
25 /3 width=4 by cnv_cast, cnv_cpms_trans/ qed.
27 lemma cnv_nta_sn (a) (h) (G) (L):
28 ∀T. ⦃G,L⦄ ⊢ T ![a,h] → ∃U. ⦃G,L⦄ ⊢ T :[a,h] U.
30 elim (cnv_fwd_cpm_SO … HT) #U #HTU
31 /4 width=2 by cnv_cpms_nta, cpm_cpms, ex_intro/
34 (* Basic_1: was: ty3_typecheck *)
35 lemma nta_typecheck (a) (h) (G) (L):
36 ∀T,U. ⦃G,L⦄ ⊢ T :[a,h] U → ∃T0. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] T0.
37 /3 width=1 by cnv_cast, cnv_nta_sn/ qed-.
39 (* Basic_1: was: ty3_correct *)
40 (* Basic_2A1: was: ntaa_fwd_correct *)
41 lemma nta_fwd_correct (a) (h) (G) (L):
42 ∀T,U. ⦃G,L⦄ ⊢ T :[a,h] U → ∃T0. ⦃G,L⦄ ⊢ U :[a,h] T0.
43 /3 width=2 by nta_fwd_cnv_dx, cnv_nta_sn/ qed-.
45 lemma nta_pure_cnv (h) (G) (L):
46 ∀T,U. ⦃G,L⦄ ⊢ T :*[h] U →
47 ∀V. ⦃G,L⦄ ⊢ ⓐV.U !*[h] → ⦃G,L⦄ ⊢ ⓐV.T :*[h] ⓐV.U.
48 #h #G #L #T #U #H1 #V #H2
49 elim (cnv_inv_cast … H1) -H1 #X0 #HU #HT #HUX0 #HTX0
50 elim (cnv_inv_appl … H2) #n #p #X1 #X2 #_ #HV #_ #HVX1 #HUX2
51 elim (cnv_cpms_conf … HU … HUX0 … HUX2) -HU -HUX2
52 <minus_O_n <minus_n_O #X #HX0 #H
53 elim (cpms_inv_abst_sn … H) -H #X3 #X4 #HX13 #HX24 #H destruct
54 @(cnv_cast … (ⓐV.X0)) [2:|*: /2 width=1 by cpms_appl_dx/ ] (**) (* full auto a bit slow *)
55 /3 width=10 by cnv_appl, cpms_trans, cpms_cprs_trans/
58 (* Basic_1: uses: ty3_sred_wcpr0_pr0 *)
59 lemma nta_cpr_conf_lpr (a) (h) (G):
60 ∀L1,T1,U. ⦃G,L1⦄ ⊢ T1 :[a,h] U → ∀T2. ⦃G,L1⦄ ⊢ T1 ➡[h] T2 →
61 ∀L2. ⦃G,L1⦄ ⊢ ➡[h] L2 → ⦃G,L2⦄ ⊢ T2 :[a,h] U.
62 #a #h #G #L1 #T1 #U #H #T2 #HT12 #L2 #HL12
63 /3 width=6 by cnv_cpm_trans_lpr, cpm_cast/
66 (* Basic_1: uses: ty3_sred_pr2 ty3_sred_pr0 *)
67 lemma nta_cpr_conf (a) (h) (G) (L):
68 ∀T1,U. ⦃G,L⦄ ⊢ T1 :[a,h] U →
69 ∀T2. ⦃G,L⦄ ⊢ T1 ➡[h] T2 → ⦃G,L⦄ ⊢ T2 :[a,h] U.
70 #a #h #G #L #T1 #U #H #T2 #HT12
71 /3 width=6 by cnv_cpm_trans, cpm_cast/
74 (* Note: this is the preservation property *)
75 (* Basic_1: uses: ty3_sred_pr3 ty3_sred_pr1 *)
76 lemma nta_cprs_conf (a) (h) (G) (L):
77 ∀T1,U. ⦃G,L⦄ ⊢ T1 :[a,h] U →
78 ∀T2. ⦃G,L⦄ ⊢ T1 ➡*[h] T2 → ⦃G,L⦄ ⊢ T2 :[a,h] U.
79 #a #h #G #L #T1 #U #H #T2 #HT12
80 /3 width=6 by cnv_cpms_trans, cpms_cast/
83 (* Basic_1: uses: ty3_cred_pr2 *)
84 lemma nta_lpr_conf (a) (h) (G):
85 ∀L1,T,U. ⦃G,L1⦄ ⊢ T :[a,h] U →
86 ∀L2. ⦃G,L1⦄ ⊢ ➡[h] L2 → ⦃G,L2⦄ ⊢ T :[a,h] U.
87 #a #h #G #L1 #T #U #HTU #L2 #HL12
88 /2 width=3 by cnv_lpr_trans/
91 (* Basic_1: uses: ty3_cred_pr3 *)
92 lemma nta_lprs_conf (a) (h) (G):
93 ∀L1,T,U. ⦃G,L1⦄ ⊢ T :[a,h] U →
94 ∀L2. ⦃G,L1⦄ ⊢ ➡*[h] L2 → ⦃G,L2⦄ ⊢ T :[a,h] U.
95 #a #h #G #L1 #T #U #HTU #L2 #HL12
96 /2 width=3 by cnv_lprs_trans/
99 (* Inversion lemmas based on preservation ***********************************)
101 lemma nta_inv_ldef_sn (a) (h) (G) (K) (V):
102 ∀X2. ⦃G,K.ⓓV⦄ ⊢ #0 :[a,h] X2 →
103 ∃∃W,U. ⦃G,K⦄ ⊢ V :[a,h] W & ⬆*[1] W ≘ U & ⦃G,K.ⓓV⦄ ⊢ U ⬌*[h] X2 & ⦃G,K.ⓓV⦄ ⊢ X2 ![a,h].
104 #a #h #G #Y #X #X2 #H
105 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
106 elim (cnv_inv_zero … H1) -H1 #Z #K #V #HV #H destruct
107 elim (cpms_inv_delta_sn … H2) -H2 *
110 /3 width=5 by cnv_cpms_nta, cpcs_cprs_sn, ex4_2_intro/
114 lemma nta_inv_lref_sn (a) (h) (G) (L):
115 ∀X2,i. ⦃G,L⦄ ⊢ #↑i :[a,h] X2 →
116 ∃∃I,K,T2,U2. ⦃G,K⦄ ⊢ #i :[a,h] T2 & ⬆*[1] T2 ≘ U2 & ⦃G,K.ⓘ{I}⦄ ⊢ U2 ⬌*[h] X2 & ⦃G,K.ⓘ{I}⦄ ⊢ X2 ![a,h] & L = K.ⓘ{I}.
117 #a #h #G #L #X2 #i #H
118 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
119 elim (cnv_inv_lref … H1) -H1 #I #K #Hi #H destruct
120 elim (cpms_inv_lref_sn … H2) -H2 *
123 /3 width=9 by cnv_cpms_nta, cpcs_cprs_sn, ex5_4_intro/
127 lemma nta_inv_lref_sn_drops_cnv (a) (h) (G) (L):
128 ∀X2,i. ⦃G,L⦄ ⊢ #i :[a,h] X2 →
129 ∨∨ ∃∃K,V,W,U. ⬇*[i] L ≘ K.ⓓV & ⦃G,K⦄ ⊢ V :[a,h] W & ⬆*[↑i] W ≘ U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h]
130 | ∃∃K,W,U. ⬇*[i] L ≘ K. ⓛW & ⦃G,K⦄ ⊢ W ![a,h] & ⬆*[↑i] W ≘ U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
131 #a #h #G #L #X2 #i #H
132 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
133 elim (cnv_inv_lref_drops … H1) -H1 #I #K #V #HLK #HV
134 elim (cpms_inv_lref1_drops … H2) -H2 *
136 | #Y #X #W #H #HVW #HUX1
137 lapply (drops_mono … H … HLK) -H #H destruct
138 /4 width=8 by cnv_cpms_nta, cpcs_cprs_sn, ex5_4_intro, or_introl/
139 | #n #Y #X #U #H #HVU #HUX1 #H0 destruct
140 lapply (drops_mono … H … HLK) -H #H destruct
141 elim (lifts_total V (𝐔❴↑i❵)) #W #HVW
142 lapply (cpms_lifts_bi … HVU (Ⓣ) … L … HVW … HUX1) -U
143 [ /2 width=2 by drops_isuni_fwd_drop2/ ] #HWX1
144 /4 width=9 by cprs_div, ex5_3_intro, or_intror/
148 lemma nta_inv_bind_sn_cnv (a) (h) (p) (I) (G) (K) (X2):
149 ∀V,T. ⦃G,K⦄ ⊢ ⓑ{p,I}V.T :[a,h] X2 →
150 ∃∃U. ⦃G,K⦄ ⊢ V ![a,h] & ⦃G,K.ⓑ{I}V⦄ ⊢ T :[a,h] U & ⦃G,K⦄ ⊢ ⓑ{p,I}V.U ⬌*[h] X2 & ⦃G,K⦄ ⊢ X2 ![a,h].
151 #a #h #p * #G #K #X2 #V #T #H
152 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
153 elim (cnv_inv_bind … H1) -H1 #HV #HT
154 [ elim (cpms_inv_abbr_sn_dx … H2) -H2 *
155 [ #V0 #U #HV0 #HTU #H destruct
156 /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
157 | #U #HTU #HX1U #H destruct
158 /4 width=5 by cnv_cpms_nta, cprs_div, cpms_zeta, ex4_intro/
160 | elim (cpms_inv_abst_sn … H2) -H2 #V0 #U #HV0 #HTU #H destruct
161 /4 width=5 by cnv_cpms_nta, cprs_div, cpms_bind, ex4_intro/
165 (* Basic_1: uses: ty3_gen_appl *)
166 lemma nta_inv_appl_sn (h) (G) (L) (X2):
167 ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :[h] X2 →
168 ∃∃p,W,U. ⦃G,L⦄ ⊢ V :[h] W & ⦃G,L⦄ ⊢ T :[h] ⓛ{p}W.U & ⦃G,L⦄ ⊢ ⓐV.ⓛ{p}W.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h].
169 #h #G #L #X2 #V #T #H
170 elim (cnv_inv_cast … H) -H #X #HX2 #H1 #HX2 #H2
171 elim (cnv_inv_appl … H1) #n #p #W #U #H <H -n #HV #HT #HVW #HTU
172 /5 width=11 by cnv_cpms_nta, cnv_cpms_conf_eq, cpcs_cprs_div, cpms_appl_dx, ex4_3_intro/
175 (* Basic_2A1: uses: nta_fwd_pure1 *)
176 lemma nta_inv_pure_sn_cnv (h) (G) (L) (X2):
177 ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :*[h] X2 →
178 ∨∨ ∃∃p,W,U. ⦃G,L⦄ ⊢ V :*[h] W & ⦃G,L⦄ ⊢ T :*[h] ⓛ{p}W.U & ⦃G,L⦄ ⊢ ⓐV.ⓛ{p}W.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 !*[h]
179 | ∃∃U. ⦃G,L⦄ ⊢ T :*[h] U & ⦃G,L⦄ ⊢ ⓐV.U !*[h] & ⦃G,L⦄ ⊢ ⓐV.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 !*[h].
180 #h #G #L #X2 #V #T #H
181 elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H
182 elim (cnv_inv_appl … H1) * [| #n ] #p #W0 #T0 #Hn #HV #HT #HW0 #HT0
183 [ lapply (cnv_cpms_trans … HT … HT0) #H0
184 elim (cnv_inv_bind … H0) -H0 #_ #HU
185 elim (cnv_fwd_cpm_SO … HU) #U0 #HU0 -HU
186 lapply (cpms_step_dx … HT0 1 (ⓛ{p}W0.U0) ?) -HT0 [ /2 width=1 by cpm_bind/ ] #HT0
187 lapply (cpms_appl_dx … V V … HT0) [ // ] #HTU0
188 lapply (cnv_cpms_conf_eq … H1 … HTU0 … H) -H1 -H -HTU0 #HU0X1
189 /4 width=8 by cnv_cpms_nta, cpcs_cprs_div, ex4_3_intro, or_introl/
190 | elim (cnv_cpms_fwd_appl_sn_decompose … H1 … H) -H1 -H #X0 #_ #H #HX01
191 elim (cpms_inv_plus … 1 n … HT0) #U #HTU #HUT0
192 lapply (cnv_cpms_trans … HT … HTU) #HU
193 lapply (cnv_cpms_conf_eq … HT … HTU … H) -H #HUX0
194 @or_intror @(ex4_intro … U … HX2) -HX2
195 [ /2 width=1 by cnv_cpms_nta/
196 | /4 width=7 by cnv_appl, lt_to_le/
197 | /4 width=3 by cpcs_trans, cpcs_cprs_div, cpcs_flat/
202 (* Basic_2A1: uses: nta_inv_cast1 *)
203 lemma nta_inv_cast_sn (a) (h) (G) (L) (X2):
204 ∀U,T. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] X2 →
205 ∧∧ ⦃G,L⦄ ⊢ T :[a,h] U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
206 #a #h #G #L #X2 #U #T #H
207 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
208 elim (cnv_inv_cast … H1) #X #HU #HT #HUX #HTX
209 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
210 [ #U0 #T0 #HU0 #HT0 #H destruct -HU -HU0
211 lapply (cnv_cpms_conf_eq … HT … HTX … HT0) -HT -HT0 -HTX #HXT0
212 lapply (cprs_step_dx … HX20 T0 ?) -HX20 [ /2 width=1 by cpm_eps/ ] #HX20
214 lapply (cnv_cpms_conf_eq … HT … HTX … HTX0) -HT -HTX -HTX0 #HX0
215 | #m #HUX0 #H destruct -HT -HTX
216 lapply (cnv_cpms_conf_eq … HU … HUX … HUX0) -HU -HUX0 #HX0
218 /4 width=3 by cpcs_cprs_div, cpcs_cprs_step_sn, and3_intro/
221 (* Basic_1: uses: ty3_gen_cast *)
222 lemma nta_inv_cast_sn_old (a) (h) (G) (L) (X2):
223 ∀T0,T1. ⦃G,L⦄ ⊢ ⓝT1.T0 :[a,h] X2 →
224 ∃∃T2. ⦃G,L⦄ ⊢ T0 :[a,h] T1 & ⦃G,L⦄ ⊢ T1 :[a,h] T2 & ⦃G,L⦄ ⊢ ⓝT2.T1 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
225 #a #h #G #L #X2 #T0 #T1 #H
226 elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
227 elim (cnv_inv_cast … H1) #X #HT1 #HT0 #HT1X #HT0X
228 elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
229 [ #U1 #U0 #HTU1 #HTU0 #H destruct
230 lapply (cnv_cpms_conf_eq … HT0 … HT0X … HTU0) -HT0 -HT0X -HTU0 #HXU0
231 /5 width=5 by cnv_cpms_nta, cpcs_cprs_div, cpcs_cprs_step_sn, cpcs_flat, ex4_intro/
233 elim (cnv_nta_sn … HT1) -HT1 #U1 #HTU1
234 lapply (cnv_cpms_conf_eq … HT0 … HT0X … HTX0) -HT0 -HT0X -HTX0 #HX0
235 lapply (cprs_step_sn … (ⓝU1.T1) … HT1X) -HT1X [ /2 width=1 by cpm_eps/ ] #HT1X
236 /4 width=5 by cpcs_cprs_div, cpcs_cprs_step_sn, ex4_intro/
237 | #n #HT1X0 #H destruct -X -HT0
238 elim (cnv_nta_sn … HT1) -HT1 #U1 #HTU1
239 /4 width=5 by cprs_div, cpms_eps, ex4_intro/
243 (* Basic_1: uses: ty3_gen_lift *)
244 (* Note: "⦃G, L⦄ ⊢ U2 ⬌*[h] X2" can be "⦃G, L⦄ ⊢ X2 ➡*[h] U2" *)
245 lemma nta_inv_lifts_sn (a) (h) (G):
246 ∀L,T2,X2. ⦃G,L⦄ ⊢ T2 :[a,h] X2 →
247 ∀b,f,K. ⬇*[b,f] L ≘ K → ∀T1. ⬆*[f] T1 ≘ T2 →
248 ∃∃U1,U2. ⦃G,K⦄ ⊢ T1 :[a,h] U1 & ⬆*[f] U1 ≘ U2 & ⦃G,L⦄ ⊢ U2 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
249 #a #h #G #L #T2 #X2 #H #b #f #K #HLK #T1 #HT12
250 elim (cnv_inv_cast … H) -H #U2 #HX2 #HT2 #HXU2 #HTU2
251 lapply (cnv_inv_lifts … HT2 … HLK … HT12) -HT2 #HT1
252 elim (cpms_inv_lifts_sn … HTU2 … HLK … HT12) -T2 -HLK #U1 #HU12 #HTU1
253 /3 width=5 by cnv_cpms_nta, cpcs_cprs_sn, ex4_2_intro/
256 (* Forward lemmas based on preservation *************************************)
258 (* Basic_1: was: ty3_unique *)
259 theorem nta_mono (a) (h) (G) (L) (T):
260 ∀U1. ⦃G,L⦄ ⊢ T :[a,h] U1 → ∀U2. ⦃G,L⦄ ⊢ T :[a,h] U2 → ⦃G,L⦄ ⊢ U1 ⬌*[h] U2.
261 #a #h #G #L #T #U1 #H1 #U2 #H2
262 elim (cnv_inv_cast … H1) -H1 #X1 #_ #_ #HUX1 #HTX1
263 elim (cnv_inv_cast … H2) -H2 #X2 #_ #HT #HUX2 #HTX2
264 lapply (cnv_cpms_conf_eq … HT … HTX1 … HTX2) -T #HX12
265 /3 width=3 by cpcs_cprs_div, cpcs_cprs_step_sn/
268 (* Advanced properties ******************************************************)
270 (* Basic_1: uses: ty3_sconv_pc3 *)
271 lemma nta_cpcs_bi (a) (h) (G) (L):
272 ∀T1,U1. ⦃G,L⦄ ⊢ T1 :[a,h] U1 → ∀T2,U2. ⦃G,L⦄ ⊢ T2 :[a,h] U2 →
273 ⦃G,L⦄ ⊢ T1 ⬌*[h] T2 → ⦃G,L⦄ ⊢ U1 ⬌*[h] U2.
274 #a #h #G #L #T1 #U1 #HTU1 #T2 #U2 #HTU2 #HT12
275 elim (cpcs_inv_cprs … HT12) -HT12 #T0 #HT10 #HT02
276 /3 width=6 by nta_mono, nta_cprs_conf/