(* Properties based on preservation *****************************************)
-lemma cnv_cpms_nta (a) (h) (G) (L):
- ∀T. ⦃G,L⦄ ⊢ T ![a,h] → ∀U.⦃G,L⦄ ⊢ T ➡*[1,h] U → ⦃G,L⦄ ⊢ T :[a,h] U.
+lemma cnv_cpms_nta (h) (a) (G) (L):
+ ∀T. ⦃G,L⦄ ⊢ T ![h,a] → ∀U.⦃G,L⦄ ⊢ T ➡*[1,h] U → ⦃G,L⦄ ⊢ T :[h,a] U.
/3 width=4 by cnv_cast, cnv_cpms_trans/ qed.
-lemma cnv_nta_sn (a) (h) (G) (L):
- ∀T. ⦃G,L⦄ ⊢ T ![a,h] → ∃U. ⦃G,L⦄ ⊢ T :[a,h] U.
-#a #h #G #L #T #HT
+lemma cnv_nta_sn (h) (a) (G) (L):
+ ∀T. ⦃G,L⦄ ⊢ T ![h,a] → ∃U. ⦃G,L⦄ ⊢ T :[h,a] U.
+#h #a #G #L #T #HT
elim (cnv_fwd_cpm_SO … HT) #U #HTU
/4 width=2 by cnv_cpms_nta, cpm_cpms, ex_intro/
qed-.
(* Basic_1: was: ty3_typecheck *)
-lemma nta_typecheck (a) (h) (G) (L):
- ∀T,U. ⦃G,L⦄ ⊢ T :[a,h] U → ∃T0. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] T0.
+lemma nta_typecheck (h) (a) (G) (L):
+ ∀T,U. ⦃G,L⦄ ⊢ T :[h,a] U → ∃T0. ⦃G,L⦄ ⊢ ⓝU.T :[h,a] T0.
/3 width=1 by cnv_cast, cnv_nta_sn/ qed-.
(* Basic_1: was: ty3_correct *)
(* Basic_2A1: was: ntaa_fwd_correct *)
-lemma nta_fwd_correct (a) (h) (G) (L):
- ∀T,U. ⦃G,L⦄ ⊢ T :[a,h] U → ∃T0. ⦃G,L⦄ ⊢ U :[a,h] T0.
+lemma nta_fwd_correct (h) (a) (G) (L):
+ ∀T,U. ⦃G,L⦄ ⊢ T :[h,a] U → ∃T0. ⦃G,L⦄ ⊢ U :[h,a] T0.
/3 width=2 by nta_fwd_cnv_dx, cnv_nta_sn/ qed-.
lemma nta_pure_cnv (h) (G) (L):
- ∀T,U. ⦃G,L⦄ ⊢ T :*[h] U →
- ∀V. ⦃G,L⦄ ⊢ ⓐV.U !*[h] → ⦃G,L⦄ ⊢ ⓐV.T :*[h] ⓐV.U.
+ ∀T,U. ⦃G,L⦄ ⊢ T :[h,𝛚] U →
+ ∀V. ⦃G,L⦄ ⊢ ⓐV.U ![h,𝛚] → ⦃G,L⦄ ⊢ ⓐV.T :[h,𝛚] ⓐV.U.
#h #G #L #T #U #H1 #V #H2
elim (cnv_inv_cast … H1) -H1 #X0 #HU #HT #HUX0 #HTX0
elim (cnv_inv_appl … H2) #n #p #X1 #X2 #_ #HV #_ #HVX1 #HUX2
qed.
(* Basic_1: uses: ty3_sred_wcpr0_pr0 *)
-lemma nta_cpr_conf_lpr (a) (h) (G):
- ∀L1,T1,U. ⦃G,L1⦄ ⊢ T1 :[a,h] U → ∀T2. ⦃G,L1⦄ ⊢ T1 ➡[h] T2 →
- ∀L2. ⦃G,L1⦄ ⊢ ➡[h] L2 → ⦃G,L2⦄ ⊢ T2 :[a,h] U.
-#a #h #G #L1 #T1 #U #H #T2 #HT12 #L2 #HL12
+lemma nta_cpr_conf_lpr (h) (a) (G):
+ ∀L1,T1,U. ⦃G,L1⦄ ⊢ T1 :[h,a] U → ∀T2. ⦃G,L1⦄ ⊢ T1 ➡[h] T2 →
+ ∀L2. ⦃G,L1⦄ ⊢ ➡[h] L2 → ⦃G,L2⦄ ⊢ T2 :[h,a] U.
+#h #a #G #L1 #T1 #U #H #T2 #HT12 #L2 #HL12
/3 width=6 by cnv_cpm_trans_lpr, cpm_cast/
qed-.
(* Basic_1: uses: ty3_sred_pr2 ty3_sred_pr0 *)
-lemma nta_cpr_conf (a) (h) (G) (L):
- ∀T1,U. ⦃G,L⦄ ⊢ T1 :[a,h] U →
- ∀T2. ⦃G,L⦄ ⊢ T1 ➡[h] T2 → ⦃G,L⦄ ⊢ T2 :[a,h] U.
-#a #h #G #L #T1 #U #H #T2 #HT12
+lemma nta_cpr_conf (h) (a) (G) (L):
+ ∀T1,U. ⦃G,L⦄ ⊢ T1 :[h,a] U →
+ ∀T2. ⦃G,L⦄ ⊢ T1 ➡[h] T2 → ⦃G,L⦄ ⊢ T2 :[h,a] U.
+#h #a #G #L #T1 #U #H #T2 #HT12
/3 width=6 by cnv_cpm_trans, cpm_cast/
qed-.
(* Note: this is the preservation property *)
(* Basic_1: uses: ty3_sred_pr3 ty3_sred_pr1 *)
-lemma nta_cprs_conf (a) (h) (G) (L):
- ∀T1,U. ⦃G,L⦄ ⊢ T1 :[a,h] U →
- ∀T2. ⦃G,L⦄ ⊢ T1 ➡*[h] T2 → ⦃G,L⦄ ⊢ T2 :[a,h] U.
-#a #h #G #L #T1 #U #H #T2 #HT12
+lemma nta_cprs_conf (h) (a) (G) (L):
+ ∀T1,U. ⦃G,L⦄ ⊢ T1 :[h,a] U →
+ ∀T2. ⦃G,L⦄ ⊢ T1 ➡*[h] T2 → ⦃G,L⦄ ⊢ T2 :[h,a] U.
+#h #a #G #L #T1 #U #H #T2 #HT12
/3 width=6 by cnv_cpms_trans, cpms_cast/
qed-.
(* Basic_1: uses: ty3_cred_pr2 *)
-lemma nta_lpr_conf (a) (h) (G):
- ∀L1,T,U. ⦃G,L1⦄ ⊢ T :[a,h] U →
- ∀L2. ⦃G,L1⦄ ⊢ ➡[h] L2 → ⦃G,L2⦄ ⊢ T :[a,h] U.
-#a #h #G #L1 #T #U #HTU #L2 #HL12
+lemma nta_lpr_conf (h) (a) (G):
+ ∀L1,T,U. ⦃G,L1⦄ ⊢ T :[h,a] U →
+ ∀L2. ⦃G,L1⦄ ⊢ ➡[h] L2 → ⦃G,L2⦄ ⊢ T :[h,a] U.
+#h #a #G #L1 #T #U #HTU #L2 #HL12
/2 width=3 by cnv_lpr_trans/
qed-.
(* Basic_1: uses: ty3_cred_pr3 *)
-lemma nta_lprs_conf (a) (h) (G):
- ∀L1,T,U. ⦃G,L1⦄ ⊢ T :[a,h] U →
- ∀L2. ⦃G,L1⦄ ⊢ ➡*[h] L2 → ⦃G,L2⦄ ⊢ T :[a,h] U.
-#a #h #G #L1 #T #U #HTU #L2 #HL12
+lemma nta_lprs_conf (h) (a) (G):
+ ∀L1,T,U. ⦃G,L1⦄ ⊢ T :[h,a] U →
+ ∀L2. ⦃G,L1⦄ ⊢ ➡*[h] L2 → ⦃G,L2⦄ ⊢ T :[h,a] U.
+#h #a #G #L1 #T #U #HTU #L2 #HL12
/2 width=3 by cnv_lprs_trans/
qed-.
(* Inversion lemmas based on preservation ***********************************)
-lemma nta_inv_ldef_sn (a) (h) (G) (K) (V):
- ∀X2. ⦃G,K.ⓓV⦄ ⊢ #0 :[a,h] X2 →
- ∃∃W,U. ⦃G,K⦄ ⊢ V :[a,h] W & ⬆*[1] W ≘ U & ⦃G,K.ⓓV⦄ ⊢ U ⬌*[h] X2 & ⦃G,K.ⓓV⦄ ⊢ X2 ![a,h].
-#a #h #G #Y #X #X2 #H
+lemma nta_inv_ldef_sn (h) (a) (G) (K) (V):
+ ∀X2. ⦃G,K.ⓓV⦄ ⊢ #0 :[h,a] X2 →
+ ∃∃W,U. ⦃G,K⦄ ⊢ V :[h,a] W & ⬆*[1] W ≘ U & ⦃G,K.ⓓV⦄ ⊢ U ⬌*[h] X2 & ⦃G,K.ⓓV⦄ ⊢ X2 ![h,a].
+#h #a #G #Y #X #X2 #H
elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
elim (cnv_inv_zero … H1) -H1 #Z #K #V #HV #H destruct
elim (cpms_inv_delta_sn … H2) -H2 *
]
qed-.
-lemma nta_inv_lref_sn (a) (h) (G) (L):
- ∀X2,i. ⦃G,L⦄ ⊢ #↑i :[a,h] X2 →
- ∃∃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}.
-#a #h #G #L #X2 #i #H
+lemma nta_inv_lref_sn (h) (a) (G) (L):
+ ∀X2,i. ⦃G,L⦄ ⊢ #↑i :[h,a] X2 →
+ ∃∃I,K,T2,U2. ⦃G,K⦄ ⊢ #i :[h,a] T2 & ⬆*[1] T2 ≘ U2 & ⦃G,K.ⓘ{I}⦄ ⊢ U2 ⬌*[h] X2 & ⦃G,K.ⓘ{I}⦄ ⊢ X2 ![h,a] & L = K.ⓘ{I}.
+#h #a #G #L #X2 #i #H
elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
elim (cnv_inv_lref … H1) -H1 #I #K #Hi #H destruct
elim (cpms_inv_lref_sn … H2) -H2 *
]
qed-.
-lemma nta_inv_lref_sn_drops_cnv (a) (h) (G) (L):
- ∀X2,i. ⦃G,L⦄ ⊢ #i :[a,h] X2 →
- ∨∨ ∃∃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]
- | ∃∃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].
-#a #h #G #L #X2 #i #H
+lemma nta_inv_lref_sn_drops_cnv (h) (a) (G) (L):
+ ∀X2,i. ⦃G,L⦄ ⊢ #i :[h,a] X2 →
+ ∨∨ ∃∃K,V,W,U. ⬇*[i] L ≘ K.ⓓV & ⦃G,K⦄ ⊢ V :[h,a] W & ⬆*[↑i] W ≘ U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h,a]
+ | ∃∃K,W,U. ⬇*[i] L ≘ K. ⓛW & ⦃G,K⦄ ⊢ W ![h,a] & ⬆*[↑i] W ≘ U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h,a].
+#h #a #G #L #X2 #i #H
elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
elim (cnv_inv_lref_drops … H1) -H1 #I #K #V #HLK #HV
elim (cpms_inv_lref1_drops … H2) -H2 *
]
qed-.
-lemma nta_inv_bind_sn_cnv (a) (h) (p) (I) (G) (K) (X2):
- ∀V,T. ⦃G,K⦄ ⊢ ⓑ{p,I}V.T :[a,h] X2 →
- ∃∃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].
-#a #h #p * #G #K #X2 #V #T #H
+lemma nta_inv_bind_sn_cnv (h) (a) (p) (I) (G) (K) (X2):
+ ∀V,T. ⦃G,K⦄ ⊢ ⓑ{p,I}V.T :[h,a] X2 →
+ ∃∃U. ⦃G,K⦄ ⊢ V ![h,a] & ⦃G,K.ⓑ{I}V⦄ ⊢ T :[h,a] U & ⦃G,K⦄ ⊢ ⓑ{p,I}V.U ⬌*[h] X2 & ⦃G,K⦄ ⊢ X2 ![h,a].
+#h #a #p * #G #K #X2 #V #T #H
elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H2
elim (cnv_inv_bind … H1) -H1 #HV #HT
[ elim (cpms_inv_abbr_sn_dx … H2) -H2 *
(* Basic_1: uses: ty3_gen_appl *)
lemma nta_inv_appl_sn (h) (G) (L) (X2):
- ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :[h] X2 →
- ∃∃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].
+ ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :[h,𝟐] X2 →
+ ∃∃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,𝟐].
#h #G #L #X2 #V #T #H
elim (cnv_inv_cast … H) -H #X #HX2 #H1 #HX2 #H2
elim (cnv_inv_appl … H1) #n #p #W #U #H <H -n #HV #HT #HVW #HTU
(* Basic_2A1: uses: nta_fwd_pure1 *)
lemma nta_inv_pure_sn_cnv (h) (G) (L) (X2):
- ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :*[h] X2 →
- ∨∨ ∃∃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]
- | ∃∃U. ⦃G,L⦄ ⊢ T :*[h] U & ⦃G,L⦄ ⊢ ⓐV.U !*[h] & ⦃G,L⦄ ⊢ ⓐV.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 !*[h].
+ ∀V,T. ⦃G,L⦄ ⊢ ⓐV.T :[h,𝛚] X2 →
+ ∨∨ ∃∃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,𝛚]
+ | ∃∃U. ⦃G,L⦄ ⊢ T :[h,𝛚] U & ⦃G,L⦄ ⊢ ⓐV.U ![h,𝛚] & ⦃G,L⦄ ⊢ ⓐV.U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h,𝛚].
#h #G #L #X2 #V #T #H
elim (cnv_inv_cast … H) -H #X1 #HX2 #H1 #HX21 #H
elim (cnv_inv_appl … H1) * [| #n ] #p #W0 #T0 #Hn #HV #HT #HW0 #HT0
qed-.
(* Basic_2A1: uses: nta_inv_cast1 *)
-lemma nta_inv_cast_sn (a) (h) (G) (L) (X2):
- ∀U,T. ⦃G,L⦄ ⊢ ⓝU.T :[a,h] X2 →
- ∧∧ ⦃G,L⦄ ⊢ T :[a,h] U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
-#a #h #G #L #X2 #U #T #H
+lemma nta_inv_cast_sn (h) (a) (G) (L) (X2):
+ ∀U,T. ⦃G,L⦄ ⊢ ⓝU.T :[h,a] X2 →
+ ∧∧ ⦃G,L⦄ ⊢ T :[h,a] U & ⦃G,L⦄ ⊢ U ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h,a].
+#h #a #G #L #X2 #U #T #H
elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
elim (cnv_inv_cast … H1) #X #HU #HT #HUX #HTX
elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
qed-.
(* Basic_1: uses: ty3_gen_cast *)
-lemma nta_inv_cast_sn_old (a) (h) (G) (L) (X2):
- ∀T0,T1. ⦃G,L⦄ ⊢ ⓝT1.T0 :[a,h] X2 →
- ∃∃T2. ⦃G,L⦄ ⊢ T0 :[a,h] T1 & ⦃G,L⦄ ⊢ T1 :[a,h] T2 & ⦃G,L⦄ ⊢ ⓝT2.T1 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
-#a #h #G #L #X2 #T0 #T1 #H
+lemma nta_inv_cast_sn_old (h) (a) (G) (L) (X2):
+ ∀T0,T1. ⦃G,L⦄ ⊢ ⓝT1.T0 :[h,a] X2 →
+ ∃∃T2. ⦃G,L⦄ ⊢ T0 :[h,a] T1 & ⦃G,L⦄ ⊢ T1 :[h,a] T2 & ⦃G,L⦄ ⊢ ⓝT2.T1 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h,a].
+#h #a #G #L #X2 #T0 #T1 #H
elim (cnv_inv_cast … H) -H #X0 #HX2 #H1 #HX20 #H2
elim (cnv_inv_cast … H1) #X #HT1 #HT0 #HT1X #HT0X
elim (cpms_inv_cast1 … H2) -H2 [ * || * ]
(* Basic_1: uses: ty3_gen_lift *)
(* Note: "⦃G, L⦄ ⊢ U2 ⬌*[h] X2" can be "⦃G, L⦄ ⊢ X2 ➡*[h] U2" *)
-lemma nta_inv_lifts_sn (a) (h) (G):
- ∀L,T2,X2. ⦃G,L⦄ ⊢ T2 :[a,h] X2 →
+lemma nta_inv_lifts_sn (h) (a) (G):
+ ∀L,T2,X2. ⦃G,L⦄ ⊢ T2 :[h,a] X2 →
∀b,f,K. ⬇*[b,f] L ≘ K → ∀T1. ⬆*[f] T1 ≘ T2 →
- ∃∃U1,U2. ⦃G,K⦄ ⊢ T1 :[a,h] U1 & ⬆*[f] U1 ≘ U2 & ⦃G,L⦄ ⊢ U2 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![a,h].
-#a #h #G #L #T2 #X2 #H #b #f #K #HLK #T1 #HT12
+ ∃∃U1,U2. ⦃G,K⦄ ⊢ T1 :[h,a] U1 & ⬆*[f] U1 ≘ U2 & ⦃G,L⦄ ⊢ U2 ⬌*[h] X2 & ⦃G,L⦄ ⊢ X2 ![h,a].
+#h #a #G #L #T2 #X2 #H #b #f #K #HLK #T1 #HT12
elim (cnv_inv_cast … H) -H #U2 #HX2 #HT2 #HXU2 #HTU2
lapply (cnv_inv_lifts … HT2 … HLK … HT12) -HT2 #HT1
elim (cpms_inv_lifts_sn … HTU2 … HLK … HT12) -T2 -HLK #U1 #HU12 #HTU1
(* Forward lemmas based on preservation *************************************)
(* Basic_1: was: ty3_unique *)
-theorem nta_mono (a) (h) (G) (L) (T):
- ∀U1. ⦃G,L⦄ ⊢ T :[a,h] U1 → ∀U2. ⦃G,L⦄ ⊢ T :[a,h] U2 → ⦃G,L⦄ ⊢ U1 ⬌*[h] U2.
-#a #h #G #L #T #U1 #H1 #U2 #H2
+theorem nta_mono (h) (a) (G) (L) (T):
+ ∀U1. ⦃G,L⦄ ⊢ T :[h,a] U1 → ∀U2. ⦃G,L⦄ ⊢ T :[h,a] U2 → ⦃G,L⦄ ⊢ U1 ⬌*[h] U2.
+#h #a #G #L #T #U1 #H1 #U2 #H2
elim (cnv_inv_cast … H1) -H1 #X1 #_ #_ #HUX1 #HTX1
elim (cnv_inv_cast … H2) -H2 #X2 #_ #HT #HUX2 #HTX2
lapply (cnv_cpms_conf_eq … HT … HTX1 … HTX2) -T #HX12
(* Advanced properties ******************************************************)
(* Basic_1: uses: ty3_sconv_pc3 *)
-lemma nta_cpcs_bi (a) (h) (G) (L):
- ∀T1,U1. ⦃G,L⦄ ⊢ T1 :[a,h] U1 → ∀T2,U2. ⦃G,L⦄ ⊢ T2 :[a,h] U2 →
+lemma nta_cpcs_bi (h) (a) (G) (L):
+ ∀T1,U1. ⦃G,L⦄ ⊢ T1 :[h,a] U1 → ∀T2,U2. ⦃G,L⦄ ⊢ T2 :[h,a] U2 →
⦃G,L⦄ ⊢ T1 ⬌*[h] T2 → ⦃G,L⦄ ⊢ U1 ⬌*[h] U2.
-#a #h #G #L #T1 #U1 #HTU1 #T2 #U2 #HTU2 #HT12
+#h #a #G #L #T1 #U1 #HTU1 #T2 #U2 #HTU2 #HT12
elim (cpcs_inv_cprs … HT12) -HT12 #T0 #HT10 #HT02
/3 width=6 by nta_mono, nta_cprs_conf/
qed-.