From: Ferruccio Guidi Date: Sun, 22 May 2016 11:28:36 +0000 (+0000) Subject: - notational change for cpg and cpx X-Git-Tag: make_still_working~584 X-Git-Url: http://matita.cs.unibo.it/gitweb/?p=helm.git;a=commitdiff_plain;h=f694e3336cbdabdeefd86f85d827edfd26bf3464 - notational change for cpg and cpx - versions table updated on site --- diff --git a/helm/www/lambdadelta/BTM.html b/helm/www/lambdadelta/BTM.html index 0ef28910c..34a4afa3e 100644 --- a/helm/www/lambdadelta/BTM.html +++ b/helm/www/lambdadelta/BTM.html @@ -222,6 +222,6 @@

-
Last update: Sat, 21 May 2016 22:22:39 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/apps_2.html b/helm/www/lambdadelta/apps_2.html index d3a930ba1..47d3e3188 100644 --- a/helm/www/lambdadelta/apps_2.html +++ b/helm/www/lambdadelta/apps_2.html @@ -258,6 +258,6 @@

-
Last update: Sat, 21 May 2016 22:22:39 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/basic_1.html b/helm/www/lambdadelta/basic_1.html index 0b508490b..2a0caeec0 100644 --- a/helm/www/lambdadelta/basic_1.html +++ b/helm/www/lambdadelta/basic_1.html @@ -823,6 +823,6 @@

-
Last update: Sat, 21 May 2016 22:22:39 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/basic_2.html b/helm/www/lambdadelta/basic_2.html index 5f68c0935..a50882199 100644 --- a/helm/www/lambdadelta/basic_2.html +++ b/helm/www/lambdadelta/basic_2.html @@ -144,29 +144,29 @@ sizes files - 143 + 133 characters - 116151 + 92667 nodes - 604153 + 334596 propositions theorems - 45 + 44 lemmas - 428 + 369 total - 473 + 413 concepts declared - 23 + 22 defined - 33 + 32 total - 56 + 54 @@ -795,6 +795,6 @@

-
Last update: Sat, 21 May 2016 22:22:39 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/documentation.html b/helm/www/lambdadelta/documentation.html index 92b0a113a..6b1211cc0 100644 --- a/helm/www/lambdadelta/documentation.html +++ b/helm/www/lambdadelta/documentation.html @@ -389,6 +389,6 @@

-
Last update: Sat, 21 May 2016 22:22:38 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/ground_1.html b/helm/www/lambdadelta/ground_1.html index 8f3f5c5fa..a97822a7f 100644 --- a/helm/www/lambdadelta/ground_1.html +++ b/helm/www/lambdadelta/ground_1.html @@ -291,6 +291,6 @@

-
Last update: Sat, 21 May 2016 22:22:39 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/ground_2.html b/helm/www/lambdadelta/ground_2.html index bb0294819..e5d2f0e37 100644 --- a/helm/www/lambdadelta/ground_2.html +++ b/helm/www/lambdadelta/ground_2.html @@ -134,27 +134,27 @@ files 86 characters - 109249 + 98269 nodes - 217872 + 207871 propositions theorems - 30 + 23 lemmas - 506 + 497 total - 536 + 520 concepts declared - 59 - defined 55 + defined + 57 total - 114 + 112 @@ -759,6 +759,6 @@

-
Last update: Sat, 21 May 2016 22:22:39 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/implementation.html b/helm/www/lambdadelta/implementation.html index 868f34477..99992380f 100644 --- a/helm/www/lambdadelta/implementation.html +++ b/helm/www/lambdadelta/implementation.html @@ -302,6 +302,6 @@

-
Last update: Sat, 21 May 2016 22:22:38 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/index.html b/helm/www/lambdadelta/index.html index 93c9c5e9d..c6a88f020 100644 --- a/helm/www/lambdadelta/index.html +++ b/helm/www/lambdadelta/index.html @@ -283,6 +283,6 @@

-
Last update: Sat, 21 May 2016 22:22:38 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/news.html b/helm/www/lambdadelta/news.html index 25794154e..f53e74441 100644 --- a/helm/www/lambdadelta/news.html +++ b/helm/www/lambdadelta/news.html @@ -380,6 +380,6 @@

-
Last update: Sat, 21 May 2016 22:22:37 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/specification.html b/helm/www/lambdadelta/specification.html index 9c941d31c..f1c9fb06e 100644 --- a/helm/www/lambdadelta/specification.html +++ b/helm/www/lambdadelta/specification.html @@ -127,8 +127,8 @@ version name - developed with stage + developed with started announced released @@ -155,17 +155,15 @@ Version 2 "basic_2" + "A2" - Matita 0.99.2 + Matita 0.99.3 - "A2" October 2015 - -
- + @@ -174,10 +172,10 @@
- -
- "A1" + + Matita 0.99.2 + April 2011 June 2014 October 2014 @@ -190,27 +188,25 @@ Abandoned + Coq 7.3.1 - March 2008 February 2011 - -
- + Version 1 "basic_1" + Coq 7.3.1 - May 2004 December 2005 November 2006 @@ -382,6 +378,6 @@

-
Last update: Sat, 21 May 2016 22:22:39 +0200
+
Last update: Sun, 22 May 2016 11:12:18 +0200
diff --git a/helm/www/lambdadelta/web/home/versions.tbl b/helm/www/lambdadelta/web/home/versions.tbl index 1d88064b3..d89ffd340 100644 --- a/helm/www/lambdadelta/web/home/versions.tbl +++ b/helm/www/lambdadelta/web/home/versions.tbl @@ -2,35 +2,41 @@ name "versions" table { class "gray" - [ "version" "name" "developed with" - "stage" "started" "announced" "released" "concluded" + [ "version" "name" + "stage" "developed with" + "started" "announced" "released" "concluded" "references" ] class "yellow" - [ @@("specification#v3" "Version 3") "\"basic_3\"" "" - "" "" "" "" "" + [ @@("specification#v3" "Version 3") "\"basic_3\"" + "" "" + "" "" "" "" @@("documentation#ldJ3a" "J3a") ] class "orange" { [ { @@("specification#v2" "Version 2") * } { "\"basic_2\"" * } - { @("http://matita.cs.unibo.it/" "Matita 0.99.2") * } - { [ "\"A2\"" "October 2015" "" "" "" - * + { [ "\"A2\"" @("http://matita.cs.unibo.it/" "Matita 0.99.3") + "October 2015" "" "" "" + "" * ] - [ "\"A1\"" "April 2011" "June 2014" "October 2014" "August 2015" - @@("documentation#ldV2a" "V2a") + " " + @@("documentation#ldR2c" "R2c") + [ "\"A1\"" @("http://matita.cs.unibo.it/" "Matita 0.99.2") + "April 2011" "June 2014" "October 2014" "August 2015" + @@("documentation#ldV2a" "V2a") + " " + @@("documentation#ldR2c" "R2c") * ] } ] - [ "Abandoned" "" @("http://coq.inria.fr/" "Coq 7.3.1") - "" "March 2008" "" "" "February 2011" * + [ "Abandoned" "" + "" @("http://coq.inria.fr/" "Coq 7.3.1") + "March 2008" "" "" "February 2011" + "" * ] } class "red" - [ @@("specification#v1" "Version 1") "\"basic_1\"" @("http://coq.inria.fr/" "Coq 7.3.1") - "" "May 2004" "December 2005" "November 2006" "May 2008" - @@("documentation#ldV1a" "V1a") + " " + @@("documentation#ldJ1a" "J1a") + [ @@("specification#v1" "Version 1") "\"basic_1\"" + "" @("http://coq.inria.fr/" "Coq 7.3.1") + "May 2004" "December 2005" "November 2006" "May 2008" + @@("documentation#ldV1a" "V1a") + " " + @@("documentation#ldJ1a" "J1a") * ] } diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/pred_6.ma b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/pred_6.ma deleted file mode 100644 index 8832e1fb4..000000000 --- a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/pred_6.ma +++ /dev/null @@ -1,19 +0,0 @@ -(**************************************************************************) -(* ___ *) -(* ||M|| *) -(* ||A|| A project by Andrea Asperti *) -(* ||T|| *) -(* ||I|| Developers: *) -(* ||T|| The HELM team. *) -(* ||A|| http://helm.cs.unibo.it *) -(* \ / *) -(* \ / This file is distributed under the terms of the *) -(* v GNU General Public License Version 2 *) -(* *) -(**************************************************************************) - -(* NOTATION FOR THE FORMAL SYSTEM λδ ****************************************) - -notation "hvbox( ⦃ term 46 G, break term 46 L ⦄ ⊢ break term 46 T1 ➡ break [ term 46 c , break term 46 h ] break term 46 T2 )" - non associative with precedence 45 - for @{ 'PRed $c $h $G $L $T1 $T2 }. diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predty_5.ma b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predty_5.ma new file mode 100644 index 000000000..8ffd00516 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predty_5.ma @@ -0,0 +1,19 @@ +(**************************************************************************) +(* ___ *) +(* ||M|| *) +(* ||A|| A project by Andrea Asperti *) +(* ||T|| *) +(* ||I|| Developers: *) +(* ||T|| The HELM team. *) +(* ||A|| http://helm.cs.unibo.it *) +(* \ / *) +(* \ / This file is distributed under the terms of the *) +(* v GNU General Public License Version 2 *) +(* *) +(**************************************************************************) + +(* NOTATION FOR THE FORMAL SYSTEM λδ ****************************************) + +notation "hvbox( ⦃ term 46 G, break term 46 L ⦄ ⊢ break term 46 T1 ⬈ break [ term 46 h ] break term 46 T2 )" + non associative with precedence 45 + for @{ 'PRedTy $h $G $L $T1 $T2 }. diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predty_6.ma b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predty_6.ma new file mode 100644 index 000000000..096a26e4c --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predty_6.ma @@ -0,0 +1,19 @@ +(**************************************************************************) +(* ___ *) +(* ||M|| *) +(* ||A|| A project by Andrea Asperti *) +(* ||T|| *) +(* ||I|| Developers: *) +(* ||T|| The HELM team. *) +(* ||A|| http://helm.cs.unibo.it *) +(* \ / *) +(* \ / This file is distributed under the terms of the *) +(* v GNU General Public License Version 2 *) +(* *) +(**************************************************************************) + +(* NOTATION FOR THE FORMAL SYSTEM λδ ****************************************) + +notation "hvbox( ⦃ term 46 G, break term 46 L ⦄ ⊢ break term 46 T1 ⬈ break [ term 46 c , break term 46 h ] break term 46 T2 )" + non associative with precedence 45 + for @{ 'PRedTy $c $h $G $L $T1 $T2 }. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxe.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxe.ma index 00fd04247..e71eebdc4 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxe.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxe.ma @@ -19,14 +19,14 @@ include "basic_2/computation/csx.ma". (* EVALUATION FOR CONTEXT-SENSITIVE EXTENDED PARALLEL REDUCTION ON TERMS ****) definition cpxe: ∀h. sd h → relation4 genv lenv term term ≝ - λh,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 ∧ ⦃G, L⦄ ⊢ ➡[h, o] 𝐍⦃T2⦄. + λh,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 ∧ ⦃G, L⦄ ⊢ ⬈[h, o] 𝐍⦃T2⦄. interpretation "evaluation for context-sensitive extended parallel reduction (term)" 'PRedEval h o G L T1 T2 = (cpxe h o G L T1 T2). (* Basic properties *********************************************************) -lemma csx_cpxe: ∀h,o,G,L,T1. ⦃G, L⦄ ⊢ ⬊*[h, o] T1 → ∃T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] 𝐍⦃T2⦄. +lemma csx_cpxe: ∀h,o,G,L,T1. ⦃G, L⦄ ⊢ ⬊*[h, o] T1 → ∃T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] 𝐍⦃T2⦄. #h #o #G #L #T1 #H @(csx_ind … H) -T1 #T1 #_ #IHT1 elim (cnx_dec h o G L T1) /3 width=3 by ex_intro, conj/ * #T #H1T1 #H2T1 elim (IHT1 … H1T1 H2T1) -IHT1 -H2T1 diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs.ma index 037113f24..d21a90427 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs.ma @@ -27,45 +27,45 @@ interpretation "extended context-sensitive parallel computation (term)" (* Basic eliminators ********************************************************) lemma cpxs_ind: ∀h,o,G,L,T1. ∀R:predicate term. R T1 → - (∀T,T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T → ⦃G, L⦄ ⊢ T ➡[h, o] T2 → R T → R T2) → - ∀T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 → R T2. + (∀T,T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T → ⦃G, L⦄ ⊢ T ⬈[h, o] T2 → R T → R T2) → + ∀T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 → R T2. #h #o #L #G #T1 #R #HT1 #IHT1 #T2 #HT12 @(TC_star_ind … HT1 IHT1 … HT12) // qed-. lemma cpxs_ind_dx: ∀h,o,G,L,T2. ∀R:predicate term. R T2 → - (∀T1,T. ⦃G, L⦄ ⊢ T1 ➡[h, o] T → ⦃G, L⦄ ⊢ T ➡*[h, o] T2 → R T → R T1) → - ∀T1. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 → R T1. + (∀T1,T. ⦃G, L⦄ ⊢ T1 ⬈[h, o] T → ⦃G, L⦄ ⊢ T ⬈*[h, o] T2 → R T → R T1) → + ∀T1. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 → R T1. #h #o #G #L #T2 #R #HT2 #IHT2 #T1 #HT12 @(TC_star_ind_dx … HT2 IHT2 … HT12) // qed-. (* Basic properties *********************************************************) -lemma cpxs_refl: ∀h,o,G,L,T. ⦃G, L⦄ ⊢ T ➡*[h, o] T. +lemma cpxs_refl: ∀h,o,G,L,T. ⦃G, L⦄ ⊢ T ⬈*[h, o] T. /2 width=1 by inj/ qed. -lemma cpx_cpxs: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡[h, o] T2 → ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2. +lemma cpx_cpxs: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈[h, o] T2 → ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2. /2 width=1 by inj/ qed. -lemma cpxs_strap1: ∀h,o,G,L,T1,T. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T → - ∀T2. ⦃G, L⦄ ⊢ T ➡[h, o] T2 → ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2. +lemma cpxs_strap1: ∀h,o,G,L,T1,T. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T → + ∀T2. ⦃G, L⦄ ⊢ T ⬈[h, o] T2 → ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2. normalize /2 width=3 by step/ qed. -lemma cpxs_strap2: ∀h,o,G,L,T1,T. ⦃G, L⦄ ⊢ T1 ➡[h, o] T → - ∀T2. ⦃G, L⦄ ⊢ T ➡*[h, o] T2 → ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2. +lemma cpxs_strap2: ∀h,o,G,L,T1,T. ⦃G, L⦄ ⊢ T1 ⬈[h, o] T → + ∀T2. ⦃G, L⦄ ⊢ T ⬈*[h, o] T2 → ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2. normalize /2 width=3 by TC_strap/ qed. lemma lsubr_cpxs_trans: ∀h,o,G. lsub_trans … (cpxs h o G) lsubr. /3 width=5 by lsubr_cpx_trans, LTC_lsub_trans/ qed-. -lemma cprs_cpxs: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡* T2 → ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2. +lemma cprs_cpxs: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈* T2 → ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2. #h #o #G #L #T1 #T2 #H @(cprs_ind … H) -T2 /3 width=3 by cpxs_strap1, cpr_cpx/ qed. lemma cpxs_sort: ∀h,o,G,L,s,d1. deg h o s d1 → - ∀d2. d2 ≤ d1 → ⦃G, L⦄ ⊢ ⋆s ➡*[h, o] ⋆((next h)^d2 s). + ∀d2. d2 ≤ d1 → ⦃G, L⦄ ⊢ ⋆s ⬈*[h, o] ⋆((next h)^d2 s). #h #o #G #L #s #d1 #Hkd1 #d2 @(nat_ind_plus … d2) -d2 /2 width=1 by cpx_cpxs/ #d2 #IHd2 #Hd21 >iter_SO @(cpxs_strap1 … (⋆(iter d2 ℕ (next h) s))) @@ -75,68 +75,68 @@ lemma cpxs_sort: ∀h,o,G,L,s,d1. deg h o s d1 → ] qed. -lemma cpxs_bind_dx: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡[h, o] V2 → - ∀I,T1,T2. ⦃G, L. ⓑ{I}V1⦄ ⊢ T1 ➡*[h, o] T2 → - ∀a. ⦃G, L⦄ ⊢ ⓑ{a,I}V1.T1 ➡*[h, o] ⓑ{a,I}V2.T2. +lemma cpxs_bind_dx: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[h, o] V2 → + ∀I,T1,T2. ⦃G, L. ⓑ{I}V1⦄ ⊢ T1 ⬈*[h, o] T2 → + ∀a. ⦃G, L⦄ ⊢ ⓑ{a,I}V1.T1 ⬈*[h, o] ⓑ{a,I}V2.T2. #h #o #G #L #V1 #V2 #HV12 #I #T1 #T2 #HT12 #a @(cpxs_ind_dx … HT12) -T1 /3 width=3 by cpxs_strap2, cpx_cpxs, cpx_pair_sn, cpx_bind/ qed. -lemma cpxs_flat_dx: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡[h, o] V2 → - ∀T1,T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 → - ∀I. ⦃G, L⦄ ⊢ ⓕ{I}V1.T1 ➡*[h, o] ⓕ{I}V2.T2. +lemma cpxs_flat_dx: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[h, o] V2 → + ∀T1,T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 → + ∀I. ⦃G, L⦄ ⊢ ⓕ{I}V1.T1 ⬈*[h, o] ⓕ{I}V2.T2. #h #o #G #L #V1 #V2 #HV12 #T1 #T2 #HT12 @(cpxs_ind … HT12) -T2 /3 width=5 by cpxs_strap1, cpx_cpxs, cpx_pair_sn, cpx_flat/ qed. -lemma cpxs_flat_sn: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡[h, o] T2 → - ∀V1,V2. ⦃G, L⦄ ⊢ V1 ➡*[h, o] V2 → - ∀I. ⦃G, L⦄ ⊢ ⓕ{I}V1.T1 ➡*[h, o] ⓕ{I}V2.T2. +lemma cpxs_flat_sn: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈[h, o] T2 → + ∀V1,V2. ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V2 → + ∀I. ⦃G, L⦄ ⊢ ⓕ{I}V1.T1 ⬈*[h, o] ⓕ{I}V2.T2. #h #o #G #L #T1 #T2 #HT12 #V1 #V2 #H @(cpxs_ind … H) -V2 /3 width=5 by cpxs_strap1, cpx_cpxs, cpx_pair_sn, cpx_flat/ qed. -lemma cpxs_pair_sn: ∀h,o,I,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡*[h, o] V2 → - ∀T. ⦃G, L⦄ ⊢ ②{I}V1.T ➡*[h, o] ②{I}V2.T. +lemma cpxs_pair_sn: ∀h,o,I,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V2 → + ∀T. ⦃G, L⦄ ⊢ ②{I}V1.T ⬈*[h, o] ②{I}V2.T. #h #o #I #G #L #V1 #V2 #H @(cpxs_ind … H) -V2 /3 width=3 by cpxs_strap1, cpx_pair_sn/ qed. lemma cpxs_zeta: ∀h,o,G,L,V,T1,T,T2. ⬆[0, 1] T2 ≡ T → - ⦃G, L.ⓓV⦄ ⊢ T1 ➡*[h, o] T → ⦃G, L⦄ ⊢ +ⓓV.T1 ➡*[h, o] T2. + ⦃G, L.ⓓV⦄ ⊢ T1 ⬈*[h, o] T → ⦃G, L⦄ ⊢ +ⓓV.T1 ⬈*[h, o] T2. #h #o #G #L #V #T1 #T #T2 #HT2 #H @(cpxs_ind_dx … H) -T1 /3 width=3 by cpxs_strap2, cpx_cpxs, cpx_bind, cpx_zeta/ qed. -lemma cpxs_eps: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 → - ∀V. ⦃G, L⦄ ⊢ ⓝV.T1 ➡*[h, o] T2. +lemma cpxs_eps: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 → + ∀V. ⦃G, L⦄ ⊢ ⓝV.T1 ⬈*[h, o] T2. #h #o #G #L #T1 #T2 #H @(cpxs_ind … H) -T2 /3 width=3 by cpxs_strap1, cpx_cpxs, cpx_eps/ qed. -lemma cpxs_ct: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡*[h, o] V2 → - ∀T. ⦃G, L⦄ ⊢ ⓝV1.T ➡*[h, o] V2. +lemma cpxs_ct: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V2 → + ∀T. ⦃G, L⦄ ⊢ ⓝV1.T ⬈*[h, o] V2. #h #o #G #L #V1 #V2 #H @(cpxs_ind … H) -V2 /3 width=3 by cpxs_strap1, cpx_cpxs, cpx_ct/ qed. lemma cpxs_beta_dx: ∀h,o,a,G,L,V1,V2,W1,W2,T1,T2. - ⦃G, L⦄ ⊢ V1 ➡[h, o] V2 → ⦃G, L.ⓛW1⦄ ⊢ T1 ➡*[h, o] T2 → ⦃G, L⦄ ⊢ W1 ➡[h, o] W2 → - ⦃G, L⦄ ⊢ ⓐV1.ⓛ{a}W1.T1 ➡*[h, o] ⓓ{a}ⓝW2.V2.T2. + ⦃G, L⦄ ⊢ V1 ⬈[h, o] V2 → ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈*[h, o] T2 → ⦃G, L⦄ ⊢ W1 ⬈[h, o] W2 → + ⦃G, L⦄ ⊢ ⓐV1.ⓛ{a}W1.T1 ⬈*[h, o] ⓓ{a}ⓝW2.V2.T2. #h #o #a #G #L #V1 #V2 #W1 #W2 #T1 #T2 #HV12 * -T2 /4 width=7 by cpx_cpxs, cpxs_strap1, cpxs_bind_dx, cpxs_flat_dx, cpx_beta/ qed. lemma cpxs_theta_dx: ∀h,o,a,G,L,V1,V,V2,W1,W2,T1,T2. - ⦃G, L⦄ ⊢ V1 ➡[h, o] V → ⬆[0, 1] V ≡ V2 → ⦃G, L.ⓓW1⦄ ⊢ T1 ➡*[h, o] T2 → - ⦃G, L⦄ ⊢ W1 ➡[h, o] W2 → ⦃G, L⦄ ⊢ ⓐV1.ⓓ{a}W1.T1 ➡*[h, o] ⓓ{a}W2.ⓐV2.T2. + ⦃G, L⦄ ⊢ V1 ⬈[h, o] V → ⬆[0, 1] V ≡ V2 → ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈*[h, o] T2 → + ⦃G, L⦄ ⊢ W1 ⬈[h, o] W2 → ⦃G, L⦄ ⊢ ⓐV1.ⓓ{a}W1.T1 ⬈*[h, o] ⓓ{a}W2.ⓐV2.T2. #h #o #a #G #L #V1 #V #V2 #W1 #W2 #T1 #T2 #HV1 #HV2 * -T2 /4 width=9 by cpx_cpxs, cpxs_strap1, cpxs_bind_dx, cpxs_flat_dx, cpx_theta/ qed. (* Basic inversion lemmas ***************************************************) -lemma cpxs_inv_sort1: ∀h,o,G,L,U2,s. ⦃G, L⦄ ⊢ ⋆s ➡*[h, o] U2 → +lemma cpxs_inv_sort1: ∀h,o,G,L,U2,s. ⦃G, L⦄ ⊢ ⋆s ⬈*[h, o] U2 → ∃∃n,d. deg h o s (n+d) & U2 = ⋆((next h)^n s). #h #o #G #L #U2 #s #H @(cpxs_ind … H) -U2 [ elim (deg_total h o s) #d #Hkd @@ -150,10 +150,10 @@ lemma cpxs_inv_sort1: ∀h,o,G,L,U2,s. ⦃G, L⦄ ⊢ ⋆s ➡*[h, o] U2 → ] qed-. -lemma cpxs_inv_cast1: ∀h,o,G,L,W1,T1,U2. ⦃G, L⦄ ⊢ ⓝW1.T1 ➡*[h, o] U2 → - ∨∨ ∃∃W2,T2. ⦃G, L⦄ ⊢ W1 ➡*[h, o] W2 & ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 & U2 = ⓝW2.T2 - | ⦃G, L⦄ ⊢ T1 ➡*[h, o] U2 - | ⦃G, L⦄ ⊢ W1 ➡*[h, o] U2. +lemma cpxs_inv_cast1: ∀h,o,G,L,W1,T1,U2. ⦃G, L⦄ ⊢ ⓝW1.T1 ⬈*[h, o] U2 → + ∨∨ ∃∃W2,T2. ⦃G, L⦄ ⊢ W1 ⬈*[h, o] W2 & ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 & U2 = ⓝW2.T2 + | ⦃G, L⦄ ⊢ T1 ⬈*[h, o] U2 + | ⦃G, L⦄ ⊢ W1 ⬈*[h, o] U2. #h #o #G #L #W1 #T1 #U2 #H @(cpxs_ind … H) -U2 /3 width=5 by or3_intro0, ex3_2_intro/ #U2 #U #_ #HU2 * /3 width=3 by cpxs_strap1, or3_intro1, or3_intro2/ * #W #T #HW1 #HT1 #H destruct @@ -163,14 +163,14 @@ lapply (cpxs_strap1 … HW1 … HW2) -W lapply (cpxs_strap1 … HT1 … HT2) -T /3 width=5 by or3_intro0, ex3_2_intro/ qed-. -lemma cpxs_inv_cnx1: ∀h,o,G,L,T,U. ⦃G, L⦄ ⊢ T ➡*[h, o] U → ⦃G, L⦄ ⊢ ➡[h, o] 𝐍⦃T⦄ → T = U. +lemma cpxs_inv_cnx1: ∀h,o,G,L,T,U. ⦃G, L⦄ ⊢ T ⬈*[h, o] U → ⦃G, L⦄ ⊢ ⬈[h, o] 𝐍⦃T⦄ → T = U. #h #o #G #L #T #U #H @(cpxs_ind_dx … H) -T // #T0 #T #H1T0 #_ #IHT #H2T0 lapply (H2T0 … H1T0) -H1T0 #H destruct /2 width=1 by/ qed-. -lemma cpxs_neq_inv_step_sn: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 → (T1 = T2 → ⊥) → - ∃∃T. ⦃G, L⦄ ⊢ T1 ➡[h, o] T & T1 = T → ⊥ & ⦃G, L⦄ ⊢ T ➡*[h, o] T2. +lemma cpxs_neq_inv_step_sn: ∀h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 → (T1 = T2 → ⊥) → + ∃∃T. ⦃G, L⦄ ⊢ T1 ⬈[h, o] T & T1 = T → ⊥ & ⦃G, L⦄ ⊢ T ⬈*[h, o] T2. #h #o #G #L #T1 #T2 #H @(cpxs_ind_dx … H) -T1 [ #H elim H -H // | #T1 #T #H1 #H2 #IH2 #H12 elim (eq_term_dec T1 T) #H destruct diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_aaa.ma index e3d5e8af1..2266edbad 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_aaa.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_aaa.ma @@ -20,10 +20,10 @@ include "basic_2/computation/cpxs.ma". (* Properties about atomic arity assignment on terms ************************) lemma cpxs_aaa_conf: ∀h,o,G,L,T1,A. ⦃G, L⦄ ⊢ T1 ⁝ A → - ∀T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 → ⦃G, L⦄ ⊢ T2 ⁝ A. + ∀T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 → ⦃G, L⦄ ⊢ T2 ⁝ A. #h #o #G #L #T1 #A #HT1 #T2 #HT12 @(TC_Conf3 … HT1 ? HT12) -A -T1 -T2 /2 width=5 by cpx_aaa_conf/ qed-. -lemma cprs_aaa_conf: ∀G,L,T1,A. ⦃G, L⦄ ⊢ T1 ⁝ A → ∀T2. ⦃G, L⦄ ⊢ T1 ➡* T2 → ⦃G, L⦄ ⊢ T2 ⁝ A. +lemma cprs_aaa_conf: ∀G,L,T1,A. ⦃G, L⦄ ⊢ T1 ⁝ A → ∀T2. ⦃G, L⦄ ⊢ T1 ⬈* T2 → ⦃G, L⦄ ⊢ T2 ⁝ A. /3 width=5 by cpxs_aaa_conf, cprs_cpxs/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_cpxs.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_cpxs.ma index 8f77d9190..4f1d7ceee 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_cpxs.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_cpxs.ma @@ -22,58 +22,58 @@ include "basic_2/computation/cpxs_lift.ma". theorem cpxs_trans: ∀h,o,G,L. Transitive … (cpxs h o G L). normalize /2 width=3 by trans_TC/ qed-. -theorem cpxs_bind: ∀h,o,a,I,G,L,V1,V2,T1,T2. ⦃G, L.ⓑ{I}V1⦄ ⊢ T1 ➡*[h, o] T2 → - ⦃G, L⦄ ⊢ V1 ➡*[h, o] V2 → - ⦃G, L⦄ ⊢ ⓑ{a,I}V1.T1 ➡*[h, o] ⓑ{a,I}V2.T2. +theorem cpxs_bind: ∀h,o,a,I,G,L,V1,V2,T1,T2. ⦃G, L.ⓑ{I}V1⦄ ⊢ T1 ⬈*[h, o] T2 → + ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V2 → + ⦃G, L⦄ ⊢ ⓑ{a,I}V1.T1 ⬈*[h, o] ⓑ{a,I}V2.T2. #h #o #a #I #G #L #V1 #V2 #T1 #T2 #HT12 #H @(cpxs_ind … H) -V2 /3 width=5 by cpxs_trans, cpxs_bind_dx/ qed. -theorem cpxs_flat: ∀h,o,I,G,L,V1,V2,T1,T2. ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 → - ⦃G, L⦄ ⊢ V1 ➡*[h, o] V2 → - ⦃G, L⦄ ⊢ ⓕ{I}V1.T1 ➡*[h, o] ⓕ{I}V2.T2. +theorem cpxs_flat: ∀h,o,I,G,L,V1,V2,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 → + ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V2 → + ⦃G, L⦄ ⊢ ⓕ{I}V1.T1 ⬈*[h, o] ⓕ{I}V2.T2. #h #o #I #G #L #V1 #V2 #T1 #T2 #HT12 #H @(cpxs_ind … H) -V2 /3 width=5 by cpxs_trans, cpxs_flat_dx/ qed. theorem cpxs_beta_rc: ∀h,o,a,G,L,V1,V2,W1,W2,T1,T2. - ⦃G, L⦄ ⊢ V1 ➡[h, o] V2 → ⦃G, L.ⓛW1⦄ ⊢ T1 ➡*[h, o] T2 → ⦃G, L⦄ ⊢ W1 ➡*[h, o] W2 → - ⦃G, L⦄ ⊢ ⓐV1.ⓛ{a}W1.T1 ➡*[h, o] ⓓ{a}ⓝW2.V2.T2. + ⦃G, L⦄ ⊢ V1 ⬈[h, o] V2 → ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈*[h, o] T2 → ⦃G, L⦄ ⊢ W1 ⬈*[h, o] W2 → + ⦃G, L⦄ ⊢ ⓐV1.ⓛ{a}W1.T1 ⬈*[h, o] ⓓ{a}ⓝW2.V2.T2. #h #o #a #G #L #V1 #V2 #W1 #W2 #T1 #T2 #HV12 #HT12 #H @(cpxs_ind … H) -W2 /4 width=5 by cpxs_trans, cpxs_beta_dx, cpxs_bind_dx, cpx_pair_sn/ qed. theorem cpxs_beta: ∀h,o,a,G,L,V1,V2,W1,W2,T1,T2. - ⦃G, L.ⓛW1⦄ ⊢ T1 ➡*[h, o] T2 → ⦃G, L⦄ ⊢ W1 ➡*[h, o] W2 → ⦃G, L⦄ ⊢ V1 ➡*[h, o] V2 → - ⦃G, L⦄ ⊢ ⓐV1.ⓛ{a}W1.T1 ➡*[h, o] ⓓ{a}ⓝW2.V2.T2. + ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈*[h, o] T2 → ⦃G, L⦄ ⊢ W1 ⬈*[h, o] W2 → ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V2 → + ⦃G, L⦄ ⊢ ⓐV1.ⓛ{a}W1.T1 ⬈*[h, o] ⓓ{a}ⓝW2.V2.T2. #h #o #a #G #L #V1 #V2 #W1 #W2 #T1 #T2 #HT12 #HW12 #H @(cpxs_ind … H) -V2 /4 width=5 by cpxs_trans, cpxs_beta_rc, cpxs_bind_dx, cpx_flat/ qed. theorem cpxs_theta_rc: ∀h,o,a,G,L,V1,V,V2,W1,W2,T1,T2. - ⦃G, L⦄ ⊢ V1 ➡[h, o] V → ⬆[0, 1] V ≡ V2 → - ⦃G, L.ⓓW1⦄ ⊢ T1 ➡*[h, o] T2 → ⦃G, L⦄ ⊢ W1 ➡*[h, o] W2 → - ⦃G, L⦄ ⊢ ⓐV1.ⓓ{a}W1.T1 ➡*[h, o] ⓓ{a}W2.ⓐV2.T2. + ⦃G, L⦄ ⊢ V1 ⬈[h, o] V → ⬆[0, 1] V ≡ V2 → + ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈*[h, o] T2 → ⦃G, L⦄ ⊢ W1 ⬈*[h, o] W2 → + ⦃G, L⦄ ⊢ ⓐV1.ⓓ{a}W1.T1 ⬈*[h, o] ⓓ{a}W2.ⓐV2.T2. #h #o #a #G #L #V1 #V #V2 #W1 #W2 #T1 #T2 #HV1 #HV2 #HT12 #H @(cpxs_ind … H) -W2 /3 width=5 by cpxs_trans, cpxs_theta_dx, cpxs_bind_dx/ qed. theorem cpxs_theta: ∀h,o,a,G,L,V1,V,V2,W1,W2,T1,T2. - ⬆[0, 1] V ≡ V2 → ⦃G, L⦄ ⊢ W1 ➡*[h, o] W2 → - ⦃G, L.ⓓW1⦄ ⊢ T1 ➡*[h, o] T2 → ⦃G, L⦄ ⊢ V1 ➡*[h, o] V → - ⦃G, L⦄ ⊢ ⓐV1.ⓓ{a}W1.T1 ➡*[h, o] ⓓ{a}W2.ⓐV2.T2. + ⬆[0, 1] V ≡ V2 → ⦃G, L⦄ ⊢ W1 ⬈*[h, o] W2 → + ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈*[h, o] T2 → ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V → + ⦃G, L⦄ ⊢ ⓐV1.ⓓ{a}W1.T1 ⬈*[h, o] ⓓ{a}W2.ⓐV2.T2. #h #o #a #G #L #V1 #V #V2 #W1 #W2 #T1 #T2 #HV2 #HW12 #HT12 #H @(TC_ind_dx … V1 H) -V1 /3 width=5 by cpxs_trans, cpxs_theta_rc, cpxs_flat_dx/ qed. (* Advanced inversion lemmas ************************************************) -lemma cpxs_inv_appl1: ∀h,o,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓐV1.T1 ➡*[h, o] U2 → - ∨∨ ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ➡*[h, o] V2 & ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2 & +lemma cpxs_inv_appl1: ∀h,o,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓐV1.T1 ⬈*[h, o] U2 → + ∨∨ ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V2 & ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2 & U2 = ⓐV2. T2 - | ∃∃a,W,T. ⦃G, L⦄ ⊢ T1 ➡*[h, o] ⓛ{a}W.T & ⦃G, L⦄ ⊢ ⓓ{a}ⓝW.V1.T ➡*[h, o] U2 - | ∃∃a,V0,V2,V,T. ⦃G, L⦄ ⊢ V1 ➡*[h, o] V0 & ⬆[0,1] V0 ≡ V2 & - ⦃G, L⦄ ⊢ T1 ➡*[h, o] ⓓ{a}V.T & ⦃G, L⦄ ⊢ ⓓ{a}V.ⓐV2.T ➡*[h, o] U2. + | ∃∃a,W,T. ⦃G, L⦄ ⊢ T1 ⬈*[h, o] ⓛ{a}W.T & ⦃G, L⦄ ⊢ ⓓ{a}ⓝW.V1.T ⬈*[h, o] U2 + | ∃∃a,V0,V2,V,T. ⦃G, L⦄ ⊢ V1 ⬈*[h, o] V0 & ⬆[0,1] V0 ≡ V2 & + ⦃G, L⦄ ⊢ T1 ⬈*[h, o] ⓓ{a}V.T & ⦃G, L⦄ ⊢ ⓓ{a}V.ⓐV2.T ⬈*[h, o] U2. #h #o #G #L #V1 #T1 #U2 #H @(cpxs_ind … H) -U2 [ /3 width=5 by or3_intro0, ex3_2_intro/ ] #U #U2 #_ #HU2 * * [ #V0 #T0 #HV10 #HT10 #H destruct @@ -108,9 +108,9 @@ lemma lpx_cpx_trans: ∀h,o,G. b_c_transitive … (cpx h o G) (λ_.lpx h o G). ] qed-. -lemma cpx_bind2: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡[h, o] V2 → - ∀I,T1,T2. ⦃G, L.ⓑ{I}V2⦄ ⊢ T1 ➡[h, o] T2 → - ∀a. ⦃G, L⦄ ⊢ ⓑ{a,I}V1.T1 ➡*[h, o] ⓑ{a,I}V2.T2. +lemma cpx_bind2: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[h, o] V2 → + ∀I,T1,T2. ⦃G, L.ⓑ{I}V2⦄ ⊢ T1 ⬈[h, o] T2 → + ∀a. ⦃G, L⦄ ⊢ ⓑ{a,I}V1.T1 ⬈*[h, o] ⓑ{a,I}V2.T2. /4 width=5 by lpx_cpx_trans, cpxs_bind_dx, lpx_pair/ qed. (* Advanced properties ******************************************************) @@ -119,16 +119,16 @@ lemma lpx_cpxs_trans: ∀h,o,G. b_rs_transitive … (cpx h o G) (λ_.lpx h o G). #h #o #G @b_c_trans_LTC1 /2 width=3 by lpx_cpx_trans/ (**) (* full auto fails *) qed-. -lemma cpxs_bind2_dx: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡[h, o] V2 → - ∀I,T1,T2. ⦃G, L.ⓑ{I}V2⦄ ⊢ T1 ➡*[h, o] T2 → - ∀a. ⦃G, L⦄ ⊢ ⓑ{a,I}V1.T1 ➡*[h, o] ⓑ{a,I}V2.T2. +lemma cpxs_bind2_dx: ∀h,o,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[h, o] V2 → + ∀I,T1,T2. ⦃G, L.ⓑ{I}V2⦄ ⊢ T1 ⬈*[h, o] T2 → + ∀a. ⦃G, L⦄ ⊢ ⓑ{a,I}V1.T1 ⬈*[h, o] ⓑ{a,I}V2.T2. /4 width=5 by lpx_cpxs_trans, cpxs_bind_dx, lpx_pair/ qed. (* Properties on supclosure *************************************************) lemma fqu_cpxs_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡*[h, o] U2 → (T2 = U2 → ⊥) → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈*[h, o] U2 → (T2 = U2 → ⊥) → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 [ #I #G #L #V1 #V2 #HV12 #_ elim (lift_total V2 0 1) #U2 #HVU2 @(ex3_intro … U2) @@ -156,8 +156,8 @@ lemma fqu_cpxs_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐ ⦃G2, qed-. lemma fquq_cpxs_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡*[h, o] U2 → (T2 = U2 → ⊥) → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈*[h, o] U2 → (T2 = U2 → ⊥) → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H12 #U2 #HTU2 #H elim (fquq_inv_gen … H12) -H12 [ #H12 elim (fqu_cpxs_trans_neq … H12 … HTU2 H) -T2 /3 width=4 by fqu_fquq, ex3_intro/ @@ -166,8 +166,8 @@ lemma fquq_cpxs_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃ qed-. lemma fqup_cpxs_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐+ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡*[h, o] U2 → (T2 = U2 → ⊥) → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐+ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈*[h, o] U2 → (T2 = U2 → ⊥) → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐+ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H @(fqup_ind_dx … H) -G1 -L1 -T1 [ #G1 #L1 #T1 #H12 #U2 #HTU2 #H elim (fqu_cpxs_trans_neq … H12 … HTU2 H) -T2 /3 width=4 by fqu_fqup, ex3_intro/ @@ -178,8 +178,8 @@ lemma fqup_cpxs_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐+ ⦃G2 qed-. lemma fqus_cpxs_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐* ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡*[h, o] U2 → (T2 = U2 → ⊥) → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈*[h, o] U2 → (T2 = U2 → ⊥) → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H12 #U2 #HTU2 #H elim (fqus_inv_gen … H12) -H12 [ #H12 elim (fqup_cpxs_trans_neq … H12 … HTU2 H) -T2 /3 width=4 by fqup_fqus, ex3_intro/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_lift.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_lift.ma index 9ff2b6f2c..9b4822e58 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_lift.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_lift.ma @@ -21,8 +21,8 @@ include "basic_2/computation/cpxs.ma". (* Advanced properties ******************************************************) lemma cpxs_delta: ∀h,o,I,G,L,K,V,V2,i. - ⬇[i] L ≡ K.ⓑ{I}V → ⦃G, K⦄ ⊢ V ➡*[h, o] V2 → - ∀W2. ⬆[0, i+1] V2 ≡ W2 → ⦃G, L⦄ ⊢ #i ➡*[h, o] W2. + ⬇[i] L ≡ K.ⓑ{I}V → ⦃G, K⦄ ⊢ V ⬈*[h, o] V2 → + ∀W2. ⬆[0, i+1] V2 ≡ W2 → ⦃G, L⦄ ⊢ #i ⬈*[h, o] W2. #h #o #I #G #L #K #V #V2 #i #HLK #H elim H -V2 [ /3 width=9 by cpx_cpxs, cpx_delta/ | #V1 lapply (drop_fwd_drop2 … HLK) -HLK @@ -31,7 +31,7 @@ lemma cpxs_delta: ∀h,o,I,G,L,K,V,V2,i. qed. lemma lstas_cpxs: ∀h,o,G,L,T1,T2,d2. ⦃G, L⦄ ⊢ T1 •*[h, d2] T2 → - ∀d1. ⦃G, L⦄ ⊢ T1 ▪[h, o] d1 → d2 ≤ d1 → ⦃G, L⦄ ⊢ T1 ➡*[h, o] T2. + ∀d1. ⦃G, L⦄ ⊢ T1 ▪[h, o] d1 → d2 ≤ d1 → ⦃G, L⦄ ⊢ T1 ⬈*[h, o] T2. #h #o #G #L #T1 #T2 #d2 #H elim H -G -L -T1 -T2 -d2 // [ /3 width=3 by cpxs_sort, da_inv_sort/ | #G #L #K #V1 #V2 #W2 #i #d2 #HLK #_ #HVW2 #IHV12 #d1 #H #Hd21 @@ -50,9 +50,9 @@ qed. (* Advanced inversion lemmas ************************************************) -lemma cpxs_inv_lref1: ∀h,o,G,L,T2,i. ⦃G, L⦄ ⊢ #i ➡*[h, o] T2 → +lemma cpxs_inv_lref1: ∀h,o,G,L,T2,i. ⦃G, L⦄ ⊢ #i ⬈*[h, o] T2 → T2 = #i ∨ - ∃∃I,K,V1,T1. ⬇[i] L ≡ K.ⓑ{I}V1 & ⦃G, K⦄ ⊢ V1 ➡*[h, o] T1 & + ∃∃I,K,V1,T1. ⬇[i] L ≡ K.ⓑ{I}V1 & ⦃G, K⦄ ⊢ V1 ⬈*[h, o] T1 & ⬆[0, i+1] T1 ≡ T2. #h #o #G #L #T2 #i #H @(cpxs_ind … H) -T2 /2 width=1 by or_introl/ #T #T2 #_ #HT2 * @@ -77,17 +77,17 @@ qed-. (* Properties on supclosure *************************************************) -lemma fqu_cpxs_trans: ∀h,o,G1,G2,L1,L2,T2,U2. ⦃G2, L2⦄ ⊢ T2 ➡*[h, o] U2 → +lemma fqu_cpxs_trans: ∀h,o,G1,G2,L1,L2,T2,U2. ⦃G2, L2⦄ ⊢ T2 ⬈*[h, o] U2 → ∀T1. ⦃G1, L1, T1⦄ ⊐ ⦃G2, L2, T2⦄ → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐ ⦃G2, L2, U2⦄. + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T2 #U2 #H @(cpxs_ind_dx … H) -T2 /2 width=3 by ex2_intro/ #T #T2 #HT2 #_ #IHTU2 #T1 #HT1 elim (fqu_cpx_trans … HT1 … HT2) -T #T #HT1 #HT2 elim (IHTU2 … HT2) -T2 /3 width=3 by cpxs_strap2, ex2_intro/ qed-. -lemma fquq_cpxs_trans: ∀h,o,G1,G2,L1,L2,T2,U2. ⦃G2, L2⦄ ⊢ T2 ➡*[h, o] U2 → +lemma fquq_cpxs_trans: ∀h,o,G1,G2,L1,L2,T2,U2. ⦃G2, L2⦄ ⊢ T2 ⬈*[h, o] U2 → ∀T1. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G2, L2, T2⦄ → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T2 #U2 #HTU2 #T1 #H elim (fquq_inv_gen … H) -H [ #HT12 elim (fqu_cpxs_trans … HTU2 … HT12) /3 width=3 by fqu_fquq, ex2_intro/ | * #H1 #H2 #H3 destruct /2 width=3 by ex2_intro/ @@ -97,20 +97,20 @@ qed-. lemma fquq_lstas_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G2, L2, T2⦄ → ∀U2,d1. ⦃G2, L2⦄ ⊢ T2 •*[h, d1] U2 → ∀d2. ⦃G2, L2⦄ ⊢ T2 ▪[h, o] d2 → d1 ≤ d2 → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. /3 width=5 by fquq_cpxs_trans, lstas_cpxs/ qed-. -lemma fqup_cpxs_trans: ∀h,o,G1,G2,L1,L2,T2,U2. ⦃G2, L2⦄ ⊢ T2 ➡*[h, o] U2 → +lemma fqup_cpxs_trans: ∀h,o,G1,G2,L1,L2,T2,U2. ⦃G2, L2⦄ ⊢ T2 ⬈*[h, o] U2 → ∀T1. ⦃G1, L1, T1⦄ ⊐+ ⦃G2, L2, T2⦄ → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐+ ⦃G2, L2, U2⦄. + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐+ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T2 #U2 #H @(cpxs_ind_dx … H) -T2 /2 width=3 by ex2_intro/ #T #T2 #HT2 #_ #IHTU2 #T1 #HT1 elim (fqup_cpx_trans … HT1 … HT2) -T #U1 #HTU1 #H2 elim (IHTU2 … H2) -T2 /3 width=3 by cpxs_strap2, ex2_intro/ qed-. -lemma fqus_cpxs_trans: ∀h,o,G1,G2,L1,L2,T2,U2. ⦃G2, L2⦄ ⊢ T2 ➡*[h, o] U2 → +lemma fqus_cpxs_trans: ∀h,o,G1,G2,L1,L2,T2,U2. ⦃G2, L2⦄ ⊢ T2 ⬈*[h, o] U2 → ∀T1. ⦃G1, L1, T1⦄ ⊐* ⦃G2, L2, T2⦄ → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T2 #U2 #HTU2 #T1 #H elim (fqus_inv_gen … H) -H [ #HT12 elim (fqup_cpxs_trans … HTU2 … HT12) /3 width=3 by fqup_fqus, ex2_intro/ | * #H1 #H2 #H3 destruct /2 width=3 by ex2_intro/ @@ -120,5 +120,5 @@ qed-. lemma fqus_lstas_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐* ⦃G2, L2, T2⦄ → ∀U2,d1. ⦃G2, L2⦄ ⊢ T2 •*[h, d1] U2 → ∀d2. ⦃G2, L2⦄ ⊢ T2 ▪[h, o] d2 → d1 ≤ d2 → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈*[h, o] U1 & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. /3 width=6 by fqus_cpxs_trans, lstas_cpxs/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_lleq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_lleq.ma index be3e0f0b5..2765cf1bc 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_lleq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_lleq.ma @@ -19,21 +19,21 @@ include "basic_2/computation/cpxs.ma". (* Properties on lazy equivalence for local environments ********************) -lemma lleq_cpxs_trans: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ➡*[h, o] T2 → - ∀L1. L1 ≡[T1, 0] L2 → ⦃G, L1⦄ ⊢ T1 ➡*[h, o] T2. +lemma lleq_cpxs_trans: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ⬈*[h, o] T2 → + ∀L1. L1 ≡[T1, 0] L2 → ⦃G, L1⦄ ⊢ T1 ⬈*[h, o] T2. #h #o #G #L2 #T1 #T2 #H @(cpxs_ind_dx … H) -T1 /4 width=6 by cpx_lleq_conf_dx, lleq_cpx_trans, cpxs_strap2/ qed-. -lemma cpxs_lleq_conf: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ➡*[h, o] T2 → - ∀L1. L2 ≡[T1, 0] L1 → ⦃G, L1⦄ ⊢ T1 ➡*[h, o] T2. +lemma cpxs_lleq_conf: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ⬈*[h, o] T2 → + ∀L1. L2 ≡[T1, 0] L1 → ⦃G, L1⦄ ⊢ T1 ⬈*[h, o] T2. /3 width=3 by lleq_cpxs_trans, lleq_sym/ qed-. -lemma cpxs_lleq_conf_dx: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ➡*[h, o] T2 → +lemma cpxs_lleq_conf_dx: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ⬈*[h, o] T2 → ∀L1. L1 ≡[T1, 0] L2 → L1 ≡[T2, 0] L2. #h #o #G #L2 #T1 #T2 #H @(cpxs_ind … H) -T2 /3 width=6 by cpx_lleq_conf_dx/ qed-. -lemma cpxs_lleq_conf_sn: ∀h,o,G,L1,T1,T2. ⦃G, L1⦄ ⊢ T1 ➡*[h, o] T2 → +lemma cpxs_lleq_conf_sn: ∀h,o,G,L1,T1,T2. ⦃G, L1⦄ ⊢ T1 ⬈*[h, o] T2 → ∀L2. L1 ≡[T1, 0] L2 → L1 ≡[T2, 0] L2. /4 width=6 by cpxs_lleq_conf_dx, lleq_sym/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_tsts.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_tsts.ma index ace2532d9..6434ff37f 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_tsts.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_tsts.ma @@ -19,13 +19,13 @@ include "basic_2/computation/lpxs_cpxs.ma". (* Forward lemmas involving same top term structure *************************) -lemma cpxs_fwd_cnx: ∀h,o,G,L,T. ⦃G, L⦄ ⊢ ➡[h, o] 𝐍⦃T⦄ → ∀U. ⦃G, L⦄ ⊢ T ➡*[h, o] U → T ≂ U. +lemma cpxs_fwd_cnx: ∀h,o,G,L,T. ⦃G, L⦄ ⊢ ⬈[h, o] 𝐍⦃T⦄ → ∀U. ⦃G, L⦄ ⊢ T ⬈*[h, o] U → T ≂ U. #h #o #G #L #T #HT #U #H >(cpxs_inv_cnx1 … H HT) -G -L -T // qed-. -lemma cpxs_fwd_sort: ∀h,o,G,L,U,s. ⦃G, L⦄ ⊢ ⋆s ➡*[h, o] U → - ⋆s ≂ U ∨ ⦃G, L⦄ ⊢ ⋆(next h s) ➡*[h, o] U. +lemma cpxs_fwd_sort: ∀h,o,G,L,U,s. ⦃G, L⦄ ⊢ ⋆s ⬈*[h, o] U → + ⋆s ≂ U ∨ ⦃G, L⦄ ⊢ ⋆(next h s) ⬈*[h, o] U. #h #o #G #L #U #s #H elim (cpxs_inv_sort1 … H) -H #n #d generalize in match s; -s @(nat_ind_plus … n) -n [ #s #_ #H -d destruct /2 width=1 by or_introl/ @@ -41,8 +41,8 @@ elim (cpxs_inv_sort1 … H) -H #n #d generalize in match s; -s @(nat_ind_plus qed-. (* Basic_1: was just: pr3_iso_beta *) -lemma cpxs_fwd_beta: ∀h,o,a,G,L,V,W,T,U. ⦃G, L⦄ ⊢ ⓐV.ⓛ{a}W.T ➡*[h, o] U → - ⓐV.ⓛ{a}W.T ≂ U ∨ ⦃G, L⦄ ⊢ ⓓ{a}ⓝW.V.T ➡*[h, o] U. +lemma cpxs_fwd_beta: ∀h,o,a,G,L,V,W,T,U. ⦃G, L⦄ ⊢ ⓐV.ⓛ{a}W.T ⬈*[h, o] U → + ⓐV.ⓛ{a}W.T ≂ U ∨ ⦃G, L⦄ ⊢ ⓓ{a}ⓝW.V.T ⬈*[h, o] U. #h #o #a #G #L #V #W #T #U #H elim (cpxs_inv_appl1 … H) -H * [ #V0 #T0 #_ #_ #H destruct /2 width=1 by tsts_pair, or_introl/ @@ -58,8 +58,8 @@ qed-. (* Note: probably this is an inversion lemma *) lemma cpxs_fwd_delta: ∀h,o,I,G,L,K,V1,i. ⬇[i] L ≡ K.ⓑ{I}V1 → ∀V2. ⬆[0, i + 1] V1 ≡ V2 → - ∀U. ⦃G, L⦄ ⊢ #i ➡*[h, o] U → - #i ≂ U ∨ ⦃G, L⦄ ⊢ V2 ➡*[h, o] U. + ∀U. ⦃G, L⦄ ⊢ #i ⬈*[h, o] U → + #i ≂ U ∨ ⦃G, L⦄ ⊢ V2 ⬈*[h, o] U. #h #o #I #G #L #K #V1 #i #HLK #V2 #HV12 #U #H elim (cpxs_inv_lref1 … H) -H /2 width=1 by or_introl/ * #I0 #K0 #V0 #U0 #HLK0 #HVU0 #HU0 @@ -67,9 +67,9 @@ lapply (drop_mono … HLK0 … HLK) -HLK0 #H destruct /4 width=10 by cpxs_lift, drop_fwd_drop2, or_intror/ qed-. -lemma cpxs_fwd_theta: ∀h,o,a,G,L,V1,V,T,U. ⦃G, L⦄ ⊢ ⓐV1.ⓓ{a}V.T ➡*[h, o] U → +lemma cpxs_fwd_theta: ∀h,o,a,G,L,V1,V,T,U. ⦃G, L⦄ ⊢ ⓐV1.ⓓ{a}V.T ⬈*[h, o] U → ∀V2. ⬆[0, 1] V1 ≡ V2 → ⓐV1.ⓓ{a}V.T ≂ U ∨ - ⦃G, L⦄ ⊢ ⓓ{a}V.ⓐV2.T ➡*[h, o] U. + ⦃G, L⦄ ⊢ ⓓ{a}V.ⓐV2.T ⬈*[h, o] U. #h #o #a #G #L #V1 #V #T #U #H #V2 #HV12 elim (cpxs_inv_appl1 … H) -H * [ -HV12 #V0 #T0 #_ #_ #H destruct /2 width=1 by tsts_pair, or_introl/ @@ -99,8 +99,8 @@ elim (cpxs_inv_appl1 … H) -H * ] qed-. -lemma cpxs_fwd_cast: ∀h,o,G,L,W,T,U. ⦃G, L⦄ ⊢ ⓝW.T ➡*[h, o] U → - ∨∨ ⓝW. T ≂ U | ⦃G, L⦄ ⊢ T ➡*[h, o] U | ⦃G, L⦄ ⊢ W ➡*[h, o] U. +lemma cpxs_fwd_cast: ∀h,o,G,L,W,T,U. ⦃G, L⦄ ⊢ ⓝW.T ⬈*[h, o] U → + ∨∨ ⓝW. T ≂ U | ⦃G, L⦄ ⊢ T ⬈*[h, o] U | ⦃G, L⦄ ⊢ W ⬈*[h, o] U. #h #o #G #L #W #T #U #H elim (cpxs_inv_cast1 … H) -H /2 width=1 by or3_intro1, or3_intro2/ * #W0 #T0 #_ #_ #H destruct /2 width=1 by tsts_pair, or3_intro0/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_tsts_vector.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_tsts_vector.ma index c408aaf67..738d5907a 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_tsts_vector.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_computation/cpxs_tsts_vector.ma @@ -21,8 +21,8 @@ include "basic_2/computation/cpxs_tsts.ma". (* Vector form of forward lemmas involving same top term structure **********) (* Basic_1: was just: nf2_iso_appls_lref *) -lemma cpxs_fwd_cnx_vector: ∀h,o,G,L,T. 𝐒⦃T⦄ → ⦃G, L⦄ ⊢ ➡[h, o] 𝐍⦃T⦄ → - ∀Vs,U. ⦃G, L⦄ ⊢ ⒶVs.T ➡*[h, o] U → ⒶVs.T ≂ U. +lemma cpxs_fwd_cnx_vector: ∀h,o,G,L,T. 𝐒⦃T⦄ → ⦃G, L⦄ ⊢ ⬈[h, o] 𝐍⦃T⦄ → + ∀Vs,U. ⦃G, L⦄ ⊢ ⒶVs.T ⬈*[h, o] U → ⒶVs.T ≂ U. #h #o #G #L #T #H1T #H2T #Vs elim Vs -Vs [ @(cpxs_fwd_cnx … H2T) ] (**) (* /2 width=3 by cpxs_fwd_cnx/ does not work *) #V #Vs #IHVs #U #H elim (cpxs_inv_appl1 … H) -H * @@ -36,8 +36,8 @@ elim (cpxs_inv_appl1 … H) -H * ] qed-. -lemma cpxs_fwd_sort_vector: ∀h,o,G,L,s,Vs,U. ⦃G, L⦄ ⊢ ⒶVs.⋆s ➡*[h, o] U → - ⒶVs.⋆s ≂ U ∨ ⦃G, L⦄ ⊢ ⒶVs.⋆(next h s) ➡*[h, o] U. +lemma cpxs_fwd_sort_vector: ∀h,o,G,L,s,Vs,U. ⦃G, L⦄ ⊢ ⒶVs.⋆s ⬈*[h, o] U → + ⒶVs.⋆s ≂ U ∨ ⦃G, L⦄ ⊢ ⒶVs.⋆(next h s) ⬈*[h, o] U. #h #o #G #L #s #Vs elim Vs -Vs /2 width=1 by cpxs_fwd_sort/ #V #Vs #IHVs #U #H elim (cpxs_inv_appl1 … H) -H * @@ -61,8 +61,8 @@ qed-. (* Basic_1: was just: pr3_iso_appls_beta *) -lemma cpxs_fwd_beta_vector: ∀h,o,a,G,L,Vs,V,W,T,U. ⦃G, L⦄ ⊢ ⒶVs.ⓐV.ⓛ{a}W.T ➡*[h, o] U → - ⒶVs. ⓐV. ⓛ{a}W. T ≂ U ∨ ⦃G, L⦄ ⊢ ⒶVs.ⓓ{a}ⓝW.V.T ➡*[h, o] U. +lemma cpxs_fwd_beta_vector: ∀h,o,a,G,L,Vs,V,W,T,U. ⦃G, L⦄ ⊢ ⒶVs.ⓐV.ⓛ{a}W.T ⬈*[h, o] U → + ⒶVs. ⓐV. ⓛ{a}W. T ≂ U ∨ ⦃G, L⦄ ⊢ ⒶVs.ⓓ{a}ⓝW.V.T ⬈*[h, o] U. #h #o #a #G #L #Vs elim Vs -Vs /2 width=1 by cpxs_fwd_beta/ #V0 #Vs #IHVs #V #W #T #U #H elim (cpxs_inv_appl1 … H) -H * @@ -86,8 +86,8 @@ qed-. lemma cpxs_fwd_delta_vector: ∀h,o,I,G,L,K,V1,i. ⬇[i] L ≡ K.ⓑ{I}V1 → ∀V2. ⬆[0, i + 1] V1 ≡ V2 → - ∀Vs,U. ⦃G, L⦄ ⊢ ⒶVs.#i ➡*[h, o] U → - ⒶVs.#i ≂ U ∨ ⦃G, L⦄ ⊢ ⒶVs.V2 ➡*[h, o] U. + ∀Vs,U. ⦃G, L⦄ ⊢ ⒶVs.#i ⬈*[h, o] U → + ⒶVs.#i ≂ U ∨ ⦃G, L⦄ ⊢ ⒶVs.V2 ⬈*[h, o] U. #h #o #I #G #L #K #V1 #i #HLK #V2 #HV12 #Vs elim Vs -Vs /2 width=5 by cpxs_fwd_delta/ #V #Vs #IHVs #U #H -K -V1 elim (cpxs_inv_appl1 … H) -H * @@ -111,8 +111,8 @@ qed-. (* Basic_1: was just: pr3_iso_appls_abbr *) lemma cpxs_fwd_theta_vector: ∀h,o,G,L,V1b,V2b. ⬆[0, 1] V1b ≡ V2b → - ∀a,V,T,U. ⦃G, L⦄ ⊢ ⒶV1b.ⓓ{a}V.T ➡*[h, o] U → - ⒶV1b. ⓓ{a}V. T ≂ U ∨ ⦃G, L⦄ ⊢ ⓓ{a}V.ⒶV2b.T ➡*[h, o] U. + ∀a,V,T,U. ⦃G, L⦄ ⊢ ⒶV1b.ⓓ{a}V.T ⬈*[h, o] U → + ⒶV1b. ⓓ{a}V. T ≂ U ∨ ⦃G, L⦄ ⊢ ⓓ{a}V.ⒶV2b.T ⬈*[h, o] U. #h #o #G #L #V1b #V2b * -V1b -V2b /3 width=1 by or_intror/ #V1b #V2b #V1a #V2a #HV12a #HV12b #a generalize in match HV12a; -HV12a @@ -159,10 +159,10 @@ elim (cpxs_inv_appl1 … H) -H * qed-. (* Basic_1: was just: pr3_iso_appls_cast *) -lemma cpxs_fwd_cast_vector: ∀h,o,G,L,Vs,W,T,U. ⦃G, L⦄ ⊢ ⒶVs.ⓝW.T ➡*[h, o] U → +lemma cpxs_fwd_cast_vector: ∀h,o,G,L,Vs,W,T,U. ⦃G, L⦄ ⊢ ⒶVs.ⓝW.T ⬈*[h, o] U → ∨∨ ⒶVs. ⓝW. T ≂ U - | ⦃G, L⦄ ⊢ ⒶVs.T ➡*[h, o] U - | ⦃G, L⦄ ⊢ ⒶVs.W ➡*[h, o] U. + | ⦃G, L⦄ ⊢ ⒶVs.T ⬈*[h, o] U + | ⦃G, L⦄ ⊢ ⒶVs.W ⬈*[h, o] U. #h #o #G #L #Vs elim Vs -Vs /2 width=1 by cpxs_fwd_cast/ #V #Vs #IHVs #W #T #U #H elim (cpxs_inv_appl1 … H) -H * diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg.ma index 5dab2812e..b8742090c 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg.ma @@ -14,7 +14,7 @@ include "ground_2/steps/rtc_shift.ma". include "ground_2/steps/rtc_plus.ma". -include "basic_2/notation/relations/pred_6.ma". +include "basic_2/notation/relations/predty_6.ma". include "basic_2/grammar/lenv.ma". include "basic_2/grammar/genv.ma". include "basic_2/relocation/lifts.ma". @@ -53,30 +53,30 @@ inductive cpg (h): rtc → relation4 genv lenv term term ≝ interpretation "counted context-sensitive parallel rt-transition (term)" - 'PRed c h G L T1 T2 = (cpg h c G L T1 T2). + 'PRedTy c h G L T1 T2 = (cpg h c G L T1 T2). (* Basic properties *********************************************************) (* Note: this is "∀h,g,L. reflexive … (cpg h (𝟘𝟘) L)" *) -lemma cpg_refl: ∀h,G,T,L. ⦃G, L⦄ ⊢ T ➡[𝟘𝟘, h] T. +lemma cpg_refl: ∀h,G,T,L. ⦃G, L⦄ ⊢ T ⬈[𝟘𝟘, h] T. #h #G #T elim T -T // * /2 width=1 by cpg_bind, cpg_flat/ qed. -lemma cpg_pair_sn: ∀c,h,I,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡[c, h] V2 → - ∀T. ⦃G, L⦄ ⊢ ②{I}V1.T ➡[↓c, h] ②{I}V2.T. +lemma cpg_pair_sn: ∀c,h,I,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[c, h] V2 → + ∀T. ⦃G, L⦄ ⊢ ②{I}V1.T ⬈[↓c, h] ②{I}V2.T. #c #h * /2 width=1 by cpg_bind, cpg_flat/ qed. (* Basic inversion lemmas ***************************************************) -fact cpg_inv_atom1_aux: ∀c,h,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡[c, h] T2 → ∀J. T1 = ⓪{J} → +fact cpg_inv_atom1_aux: ∀c,h,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈[c, h] T2 → ∀J. T1 = ⓪{J} → ∨∨ T2 = ⓪{J} ∧ c = 𝟘𝟘 | ∃∃s. J = Sort s & T2 = ⋆(next h s) & c = 𝟘𝟙 - | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ➡[cV, h] V2 & ⬆*[1] V2 ≡ T2 & + | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ⬈[cV, h] V2 & ⬆*[1] V2 ≡ T2 & L = K.ⓓV1 & J = LRef 0 & c = cV - | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ➡[cV, h] V2 & ⬆*[1] V2 ≡ T2 & + | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ⬈[cV, h] V2 & ⬆*[1] V2 ≡ T2 & L = K.ⓛV1 & J = LRef 0 & c = (↓cV)+𝟘𝟙 - | ∃∃I,K,V,T,i. ⦃G, K⦄ ⊢ #i ➡[c, h] T & ⬆*[1] T ≡ T2 & + | ∃∃I,K,V,T,i. ⦃G, K⦄ ⊢ #i ⬈[c, h] T & ⬆*[1] T ≡ T2 & L = K.ⓑ{I}V & J = LRef (⫯i). #c #h #G #L #T1 #T2 * -c -G -L -T1 -T2 [ #I #G #L #J #H destruct /3 width=1 by or5_intro0, conj/ @@ -94,18 +94,18 @@ fact cpg_inv_atom1_aux: ∀c,h,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡[c, h] T2 → ∀ ] qed-. -lemma cpg_inv_atom1: ∀c,h,J,G,L,T2. ⦃G, L⦄ ⊢ ⓪{J} ➡[c, h] T2 → +lemma cpg_inv_atom1: ∀c,h,J,G,L,T2. ⦃G, L⦄ ⊢ ⓪{J} ⬈[c, h] T2 → ∨∨ T2 = ⓪{J} ∧ c = 𝟘𝟘 | ∃∃s. J = Sort s & T2 = ⋆(next h s) & c = 𝟘𝟙 - | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ➡[cV, h] V2 & ⬆*[1] V2 ≡ T2 & + | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ⬈[cV, h] V2 & ⬆*[1] V2 ≡ T2 & L = K.ⓓV1 & J = LRef 0 & c = cV - | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ➡[cV, h] V2 & ⬆*[1] V2 ≡ T2 & + | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ⬈[cV, h] V2 & ⬆*[1] V2 ≡ T2 & L = K.ⓛV1 & J = LRef 0 & c = (↓cV)+𝟘𝟙 - | ∃∃I,K,V,T,i. ⦃G, K⦄ ⊢ #i ➡[c, h] T & ⬆*[1] T ≡ T2 & + | ∃∃I,K,V,T,i. ⦃G, K⦄ ⊢ #i ⬈[c, h] T & ⬆*[1] T ≡ T2 & L = K.ⓑ{I}V & J = LRef (⫯i). /2 width=3 by cpg_inv_atom1_aux/ qed-. -lemma cpg_inv_sort1: ∀c,h,G,L,T2,s. ⦃G, L⦄ ⊢ ⋆s ➡[c, h] T2 → +lemma cpg_inv_sort1: ∀c,h,G,L,T2,s. ⦃G, L⦄ ⊢ ⋆s ⬈[c, h] T2 → (T2 = ⋆s ∧ c = 𝟘𝟘) ∨ (T2 = ⋆(next h s) ∧ c = 𝟘𝟙). #c #h #G #L #T2 #s #H elim (cpg_inv_atom1 … H) -H * /3 width=1 by or_introl, conj/ @@ -115,11 +115,11 @@ elim (cpg_inv_atom1 … H) -H * /3 width=1 by or_introl, conj/ ] qed-. -lemma cpg_inv_zero1: ∀c,h,G,L,T2. ⦃G, L⦄ ⊢ #0 ➡[c, h] T2 → +lemma cpg_inv_zero1: ∀c,h,G,L,T2. ⦃G, L⦄ ⊢ #0 ⬈[c, h] T2 → ∨∨ (T2 = #0 ∧ c = 𝟘𝟘) - | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ➡[cV, h] V2 & ⬆*[1] V2 ≡ T2 & + | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ⬈[cV, h] V2 & ⬆*[1] V2 ≡ T2 & L = K.ⓓV1 & c = cV - | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ➡[cV, h] V2 & ⬆*[1] V2 ≡ T2 & + | ∃∃cV,K,V1,V2. ⦃G, K⦄ ⊢ V1 ⬈[cV, h] V2 & ⬆*[1] V2 ≡ T2 & L = K.ⓛV1 & c = (↓cV)+𝟘𝟙. #c #h #G #L #T2 #H elim (cpg_inv_atom1 … H) -H * /3 width=1 by or3_intro0, conj/ @@ -129,9 +129,9 @@ elim (cpg_inv_atom1 … H) -H * /3 width=1 by or3_intro0, conj/ ] qed-. -lemma cpg_inv_lref1: ∀c,h,G,L,T2,i. ⦃G, L⦄ ⊢ #⫯i ➡[c, h] T2 → +lemma cpg_inv_lref1: ∀c,h,G,L,T2,i. ⦃G, L⦄ ⊢ #⫯i ⬈[c, h] T2 → (T2 = #(⫯i) ∧ c = 𝟘𝟘) ∨ - ∃∃I,K,V,T. ⦃G, K⦄ ⊢ #i ➡[c, h] T & ⬆*[1] T ≡ T2 & L = K.ⓑ{I}V. + ∃∃I,K,V,T. ⦃G, K⦄ ⊢ #i ⬈[c, h] T & ⬆*[1] T ≡ T2 & L = K.ⓑ{I}V. #c #h #G #L #T2 #i #H elim (cpg_inv_atom1 … H) -H * /3 width=1 by or_introl, conj/ [ #s #H destruct @@ -140,7 +140,7 @@ elim (cpg_inv_atom1 … H) -H * /3 width=1 by or_introl, conj/ ] qed-. -lemma cpg_inv_gref1: ∀c,h,G,L,T2,l. ⦃G, L⦄ ⊢ §l ➡[c, h] T2 → T2 = §l ∧ c = 𝟘𝟘. +lemma cpg_inv_gref1: ∀c,h,G,L,T2,l. ⦃G, L⦄ ⊢ §l ⬈[c, h] T2 → T2 = §l ∧ c = 𝟘𝟘. #c #h #G #L #T2 #l #H elim (cpg_inv_atom1 … H) -H * /2 width=1 by conj/ [ #s #H destruct @@ -149,12 +149,12 @@ elim (cpg_inv_atom1 … H) -H * /2 width=1 by conj/ ] qed-. -fact cpg_inv_bind1_aux: ∀c,h,G,L,U,U2. ⦃G, L⦄ ⊢ U ➡[c, h] U2 → +fact cpg_inv_bind1_aux: ∀c,h,G,L,U,U2. ⦃G, L⦄ ⊢ U ⬈[c, h] U2 → ∀p,J,V1,U1. U = ⓑ{p,J}V1.U1 → ( - ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L.ⓑ{J}V1⦄ ⊢ U1 ➡[cT, h] T2 & + ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L.ⓑ{J}V1⦄ ⊢ U1 ⬈[cT, h] T2 & U2 = ⓑ{p,J}V2.T2 & c = (↓cV)+cT ) ∨ - ∃∃cT,T. ⦃G, L.ⓓV1⦄ ⊢ U1 ➡[cT, h] T & ⬆*[1] U2 ≡ T & + ∃∃cT,T. ⦃G, L.ⓓV1⦄ ⊢ U1 ⬈[cT, h] T & ⬆*[1] U2 ≡ T & p = true & J = Abbr & c = (↓cT)+𝟙𝟘. #c #h #G #L #U #U2 * -c -G -L -U -U2 [ #I #G #L #q #J #W #U1 #H destruct @@ -172,26 +172,26 @@ fact cpg_inv_bind1_aux: ∀c,h,G,L,U,U2. ⦃G, L⦄ ⊢ U ➡[c, h] U2 → ] qed-. -lemma cpg_inv_bind1: ∀c,h,p,I,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ➡[c, h] U2 → ( - ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L.ⓑ{I}V1⦄ ⊢ T1 ➡[cT, h] T2 & +lemma cpg_inv_bind1: ∀c,h,p,I,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ⬈[c, h] U2 → ( + ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L.ⓑ{I}V1⦄ ⊢ T1 ⬈[cT, h] T2 & U2 = ⓑ{p,I}V2.T2 & c = (↓cV)+cT ) ∨ - ∃∃cT,T. ⦃G, L.ⓓV1⦄ ⊢ T1 ➡[cT, h] T & ⬆*[1] U2 ≡ T & + ∃∃cT,T. ⦃G, L.ⓓV1⦄ ⊢ T1 ⬈[cT, h] T & ⬆*[1] U2 ≡ T & p = true & I = Abbr & c = (↓cT)+𝟙𝟘. /2 width=3 by cpg_inv_bind1_aux/ qed-. -lemma cpg_inv_abbr1: ∀c,h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓓ{p}V1.T1 ➡[c, h] U2 → ( - ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L.ⓓV1⦄ ⊢ T1 ➡[cT, h] T2 & +lemma cpg_inv_abbr1: ∀c,h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓓ{p}V1.T1 ⬈[c, h] U2 → ( + ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L.ⓓV1⦄ ⊢ T1 ⬈[cT, h] T2 & U2 = ⓓ{p}V2.T2 & c = (↓cV)+cT ) ∨ - ∃∃cT,T. ⦃G, L.ⓓV1⦄ ⊢ T1 ➡[cT, h] T & ⬆*[1] U2 ≡ T & + ∃∃cT,T. ⦃G, L.ⓓV1⦄ ⊢ T1 ⬈[cT, h] T & ⬆*[1] U2 ≡ T & p = true & c = (↓cT)+𝟙𝟘. #c #h #p #G #L #V1 #T1 #U2 #H elim (cpg_inv_bind1 … H) -H * /3 width=8 by ex4_4_intro, ex4_2_intro, or_introl, or_intror/ qed-. -lemma cpg_inv_abst1: ∀c,h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓛ{p}V1.T1 ➡[c, h] U2 → - ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L.ⓛV1⦄ ⊢ T1 ➡[cT, h] T2 & +lemma cpg_inv_abst1: ∀c,h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓛ{p}V1.T1 ⬈[c, h] U2 → + ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L.ⓛV1⦄ ⊢ T1 ⬈[cT, h] T2 & U2 = ⓛ{p}V2.T2 & c = (↓cV)+cT. #c #h #p #G #L #V1 #T1 #U2 #H elim (cpg_inv_bind1 … H) -H * [ /3 width=8 by ex4_4_intro/ @@ -199,15 +199,15 @@ lemma cpg_inv_abst1: ∀c,h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓛ{p}V1.T1 ➡[c, h] ] qed-. -fact cpg_inv_flat1_aux: ∀c,h,G,L,U,U2. ⦃G, L⦄ ⊢ U ➡[c, h] U2 → +fact cpg_inv_flat1_aux: ∀c,h,G,L,U,U2. ⦃G, L⦄ ⊢ U ⬈[c, h] U2 → ∀J,V1,U1. U = ⓕ{J}V1.U1 → - ∨∨ ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L⦄ ⊢ U1 ➡[cT, h] T2 & + ∨∨ ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L⦄ ⊢ U1 ⬈[cT, h] T2 & U2 = ⓕ{J}V2.T2 & c = (↓cV)+cT - | ∃∃cT. ⦃G, L⦄ ⊢ U1 ➡[cT, h] U2 & J = Cast & c = (↓cT)+𝟙𝟘 - | ∃∃cV. ⦃G, L⦄ ⊢ V1 ➡[cV, h] U2 & J = Cast & c = (↓cV)+𝟘𝟙 - | ∃∃cV,cW,cT,p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L⦄ ⊢ W1 ➡[cW, h] W2 & ⦃G, L.ⓛW1⦄ ⊢ T1 ➡[cT, h] T2 & + | ∃∃cT. ⦃G, L⦄ ⊢ U1 ⬈[cT, h] U2 & J = Cast & c = (↓cT)+𝟙𝟘 + | ∃∃cV. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] U2 & J = Cast & c = (↓cV)+𝟘𝟙 + | ∃∃cV,cW,cT,p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L⦄ ⊢ W1 ⬈[cW, h] W2 & ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈[cT, h] T2 & J = Appl & U1 = ⓛ{p}W1.T1 & U2 = ⓓ{p}ⓝW2.V2.T2 & c = (↓cV)+(↓cW)+(↓cT)+𝟙𝟘 - | ∃∃cV,cW,cT,p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V & ⬆*[1] V ≡ V2 & ⦃G, L⦄ ⊢ W1 ➡[cW, h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ➡[cT, h] T2 & + | ∃∃cV,cW,cT,p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V & ⬆*[1] V ≡ V2 & ⦃G, L⦄ ⊢ W1 ⬈[cW, h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈[cT, h] T2 & J = Appl & U1 = ⓓ{p}W1.T1 & U2 = ⓓ{p}W2.ⓐV2.T2 & c = (↓cV)+(↓cW)+(↓cT)+𝟙𝟘. #c #h #G #L #U #U2 * -c -G -L -U -U2 [ #I #G #L #J #W #U1 #H destruct @@ -225,23 +225,23 @@ fact cpg_inv_flat1_aux: ∀c,h,G,L,U,U2. ⦃G, L⦄ ⊢ U ➡[c, h] U2 → ] qed-. -lemma cpg_inv_flat1: ∀c,h,I,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓕ{I}V1.U1 ➡[c, h] U2 → - ∨∨ ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L⦄ ⊢ U1 ➡[cT, h] T2 & +lemma cpg_inv_flat1: ∀c,h,I,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓕ{I}V1.U1 ⬈[c, h] U2 → + ∨∨ ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L⦄ ⊢ U1 ⬈[cT, h] T2 & U2 = ⓕ{I}V2.T2 & c = (↓cV)+cT - | ∃∃cT. ⦃G, L⦄ ⊢ U1 ➡[cT, h] U2 & I = Cast & c = (↓cT)+𝟙𝟘 - | ∃∃cV. ⦃G, L⦄ ⊢ V1 ➡[cV, h] U2 & I = Cast & c = (↓cV)+𝟘𝟙 - | ∃∃cV,cW,cT,p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L⦄ ⊢ W1 ➡[cW, h] W2 & ⦃G, L.ⓛW1⦄ ⊢ T1 ➡[cT, h] T2 & + | ∃∃cT. ⦃G, L⦄ ⊢ U1 ⬈[cT, h] U2 & I = Cast & c = (↓cT)+𝟙𝟘 + | ∃∃cV. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] U2 & I = Cast & c = (↓cV)+𝟘𝟙 + | ∃∃cV,cW,cT,p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L⦄ ⊢ W1 ⬈[cW, h] W2 & ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈[cT, h] T2 & I = Appl & U1 = ⓛ{p}W1.T1 & U2 = ⓓ{p}ⓝW2.V2.T2 & c = (↓cV)+(↓cW)+(↓cT)+𝟙𝟘 - | ∃∃cV,cW,cT,p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V & ⬆*[1] V ≡ V2 & ⦃G, L⦄ ⊢ W1 ➡[cW, h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ➡[cT, h] T2 & + | ∃∃cV,cW,cT,p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V & ⬆*[1] V ≡ V2 & ⦃G, L⦄ ⊢ W1 ⬈[cW, h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈[cT, h] T2 & I = Appl & U1 = ⓓ{p}W1.T1 & U2 = ⓓ{p}W2.ⓐV2.T2 & c = (↓cV)+(↓cW)+(↓cT)+𝟙𝟘. /2 width=3 by cpg_inv_flat1_aux/ qed-. -lemma cpg_inv_appl1: ∀c,h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓐV1.U1 ➡[c, h] U2 → - ∨∨ ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L⦄ ⊢ U1 ➡[cT, h] T2 & +lemma cpg_inv_appl1: ∀c,h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓐV1.U1 ⬈[c, h] U2 → + ∨∨ ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L⦄ ⊢ U1 ⬈[cT, h] T2 & U2 = ⓐV2.T2 & c = (↓cV)+cT - | ∃∃cV,cW,cT,p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L⦄ ⊢ W1 ➡[cW, h] W2 & ⦃G, L.ⓛW1⦄ ⊢ T1 ➡[cT, h] T2 & + | ∃∃cV,cW,cT,p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L⦄ ⊢ W1 ⬈[cW, h] W2 & ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈[cT, h] T2 & U1 = ⓛ{p}W1.T1 & U2 = ⓓ{p}ⓝW2.V2.T2 & c = (↓cV)+(↓cW)+(↓cT)+𝟙𝟘 - | ∃∃cV,cW,cT,p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V & ⬆*[1] V ≡ V2 & ⦃G, L⦄ ⊢ W1 ➡[cW, h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ➡[cT, h] T2 & + | ∃∃cV,cW,cT,p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V & ⬆*[1] V ≡ V2 & ⦃G, L⦄ ⊢ W1 ⬈[cW, h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈[cT, h] T2 & U1 = ⓓ{p}W1.T1 & U2 = ⓓ{p}W2.ⓐV2.T2 & c = (↓cV)+(↓cW)+(↓cT)+𝟙𝟘. #c #h #G #L #V1 #U1 #U2 #H elim (cpg_inv_flat1 … H) -H * [ /3 width=8 by or3_intro0, ex4_4_intro/ @@ -251,11 +251,11 @@ lemma cpg_inv_appl1: ∀c,h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓐV1.U1 ➡[c, h] U2 ] qed-. -lemma cpg_inv_cast1: ∀c,h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓝV1.U1 ➡[c, h] U2 → - ∨∨ ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L⦄ ⊢ U1 ➡[cT, h] T2 & +lemma cpg_inv_cast1: ∀c,h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓝV1.U1 ⬈[c, h] U2 → + ∨∨ ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L⦄ ⊢ U1 ⬈[cT, h] T2 & U2 = ⓝV2.T2 & c = (↓cV)+cT - | ∃∃cT. ⦃G, L⦄ ⊢ U1 ➡[cT, h] U2 & c = (↓cT)+𝟙𝟘 - | ∃∃cV. ⦃G, L⦄ ⊢ V1 ➡[cV, h] U2 & c = (↓cV)+𝟘𝟙. + | ∃∃cT. ⦃G, L⦄ ⊢ U1 ⬈[cT, h] U2 & c = (↓cT)+𝟙𝟘 + | ∃∃cV. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] U2 & c = (↓cV)+𝟘𝟙. #c #h #G #L #V1 #U1 #U2 #H elim (cpg_inv_flat1 … H) -H * [ /3 width=8 by or3_intro0, ex4_4_intro/ |2,3: /3 width=3 by or3_intro1, or3_intro2, ex2_intro/ @@ -266,8 +266,8 @@ qed-. (* Basic forward lemmas *****************************************************) -lemma cpg_fwd_bind1_minus: ∀c,h,I,G,L,V1,T1,T. ⦃G, L⦄ ⊢ -ⓑ{I}V1.T1 ➡[c, h] T → ∀p. - ∃∃V2,T2. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ➡[c, h] ⓑ{p,I}V2.T2 & +lemma cpg_fwd_bind1_minus: ∀c,h,I,G,L,V1,T1,T. ⦃G, L⦄ ⊢ -ⓑ{I}V1.T1 ⬈[c, h] T → ∀p. + ∃∃V2,T2. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ⬈[c, h] ⓑ{p,I}V2.T2 & T = -ⓑ{I}V2.T2. #c #h #I #G #L #V1 #T1 #T #H #p elim (cpg_inv_bind1 … H) -H * [ #cV #cT #V2 #T2 #HV12 #HT12 #H1 #H2 destruct /3 width=4 by cpg_bind, ex2_2_intro/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg_drops.ma index c8f0b394f..779ea690b 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg_drops.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg_drops.ma @@ -21,8 +21,8 @@ include "basic_2/rt_transition/cpg.ma". (* Advanced properties ******************************************************) -lemma cpg_delta_drops: ∀c,h,G,K,V,V2,i,L,T2. ⬇*[i] L ≡ K.ⓓV → ⦃G, K⦄ ⊢ V ➡[c, h] V2 → - ⬆*[⫯i] V2 ≡ T2 → ⦃G, L⦄ ⊢ #i ➡[c, h] T2. +lemma cpg_delta_drops: ∀c,h,G,K,V,V2,i,L,T2. ⬇*[i] L ≡ K.ⓓV → ⦃G, K⦄ ⊢ V ⬈[c, h] V2 → + ⬆*[⫯i] V2 ≡ T2 → ⦃G, L⦄ ⊢ #i ⬈[c, h] T2. #c #h #G #K #V #V2 #i elim i -i [ #L #T2 #HLK lapply (drops_fwd_isid … HLK ?) // #H destruct /3 width=3 by cpg_delta/ | #i #IH #L0 #T0 #H0 #HV2 #HVT2 @@ -31,8 +31,8 @@ lemma cpg_delta_drops: ∀c,h,G,K,V,V2,i,L,T2. ⬇*[i] L ≡ K.ⓓV → ⦃G, K ] qed. -lemma cpg_ell_drops: ∀c,h,G,K,V,V2,i,L,T2. ⬇*[i] L ≡ K.ⓛV → ⦃G, K⦄ ⊢ V ➡[c, h] V2 → - ⬆*[⫯i] V2 ≡ T2 → ⦃G, L⦄ ⊢ #i ➡[(↓c)+𝟘𝟙, h] T2. +lemma cpg_ell_drops: ∀c,h,G,K,V,V2,i,L,T2. ⬇*[i] L ≡ K.ⓛV → ⦃G, K⦄ ⊢ V ⬈[c, h] V2 → + ⬆*[⫯i] V2 ≡ T2 → ⦃G, L⦄ ⊢ #i ⬈[(↓c)+𝟘𝟙, h] T2. #c #h #G #K #V #V2 #i elim i -i [ #L #T2 #HLK lapply (drops_fwd_isid … HLK ?) // #H destruct /3 width=3 by cpg_ell/ | #i #IH #L0 #T0 #H0 #HV2 #HVT2 @@ -43,11 +43,11 @@ qed. (* Advanced inversion lemmas ************************************************) -lemma cpg_inv_lref1_drops: ∀c,h,G,i,L,T2. ⦃G, L⦄ ⊢ #i ➡[c, h] T2 → +lemma cpg_inv_lref1_drops: ∀c,h,G,i,L,T2. ⦃G, L⦄ ⊢ #i ⬈[c, h] T2 → ∨∨ T2 = #i ∧ c = 𝟘𝟘 - | ∃∃cV,K,V,V2. ⬇*[i] L ≡ K.ⓓV & ⦃G, K⦄ ⊢ V ➡[cV, h] V2 & + | ∃∃cV,K,V,V2. ⬇*[i] L ≡ K.ⓓV & ⦃G, K⦄ ⊢ V ⬈[cV, h] V2 & ⬆*[⫯i] V2 ≡ T2 & c = cV - | ∃∃cV,K,V,V2. ⬇*[i] L ≡ K.ⓛV & ⦃G, K⦄ ⊢ V ➡[cV, h] V2 & + | ∃∃cV,K,V,V2. ⬇*[i] L ≡ K.ⓛV & ⦃G, K⦄ ⊢ V ⬈[cV, h] V2 & ⬆*[⫯i] V2 ≡ T2 & c = (↓cV) + 𝟘𝟙. #c #h #G #i elim i -i [ #L #T2 #H elim (cpg_inv_zero1 … H) -H * /3 width=1 by or3_intro0, conj/ @@ -61,12 +61,12 @@ lemma cpg_inv_lref1_drops: ∀c,h,G,i,L,T2. ⦃G, L⦄ ⊢ #i ➡[c, h] T2 → ] qed-. -lemma cpg_inv_atom1_drops: ∀c,h,I,G,L,T2. ⦃G, L⦄ ⊢ ⓪{I} ➡[c, h] T2 → +lemma cpg_inv_atom1_drops: ∀c,h,I,G,L,T2. ⦃G, L⦄ ⊢ ⓪{I} ⬈[c, h] T2 → ∨∨ T2 = ⓪{I} ∧ c = 𝟘𝟘 | ∃∃s. T2 = ⋆(next h s) & I = Sort s & c = 𝟘𝟙 - | ∃∃cV,i,K,V,V2. ⬇*[i] L ≡ K.ⓓV & ⦃G, K⦄ ⊢ V ➡[cV, h] V2 & + | ∃∃cV,i,K,V,V2. ⬇*[i] L ≡ K.ⓓV & ⦃G, K⦄ ⊢ V ⬈[cV, h] V2 & ⬆*[⫯i] V2 ≡ T2 & I = LRef i & c = cV - | ∃∃cV,i,K,V,V2. ⬇*[i] L ≡ K.ⓛV & ⦃G, K⦄ ⊢ V ➡[cV, h] V2 & + | ∃∃cV,i,K,V,V2. ⬇*[i] L ≡ K.ⓛV & ⦃G, K⦄ ⊢ V ⬈[cV, h] V2 & ⬆*[⫯i] V2 ≡ T2 & I = LRef i & c = (↓cV) + 𝟘𝟙. #c #h * #n #G #L #T2 #H [ elim (cpg_inv_sort1 … H) -H * diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg_simple.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg_simple.ma index 5dcf8ece0..a53be69b0 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg_simple.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpg_simple.ma @@ -20,8 +20,8 @@ include "basic_2/rt_transition/cpg.ma". (* Properties with simple terms *********************************************) (* Note: the main property of simple terms *) -lemma cpg_inv_appl1_simple: ∀c,h,G,L,V1,T1,U. ⦃G, L⦄ ⊢ ⓐV1.T1 ➡[c, h] U → 𝐒⦃T1⦄ → - ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ➡[cV, h] V2 & ⦃G, L⦄ ⊢ T1 ➡[cT, h] T2 & +lemma cpg_inv_appl1_simple: ∀c,h,G,L,V1,T1,U. ⦃G, L⦄ ⊢ ⓐV1.T1 ⬈[c, h] U → 𝐒⦃T1⦄ → + ∃∃cV,cT,V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[cV, h] V2 & ⦃G, L⦄ ⊢ T1 ⬈[cT, h] T2 & U = ⓐV2.T2 & c = (↓cV)+cT. #c #h #G #L #V1 #T1 #U #H #HT1 elim (cpg_inv_appl1 … H) -H * [ /2 width=8 by ex4_4_intro/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx.ma index c40733142..ac0248923 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx.ma @@ -12,81 +12,81 @@ (* *) (**************************************************************************) -include "basic_2/notation/relations/pred_5.ma". +include "basic_2/notation/relations/predty_5.ma". include "basic_2/rt_transition/cpg.ma". -(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL REDUCTION FOR TERMS *****************) +(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************) definition cpx (h): relation4 genv lenv term term ≝ - λG,L,T1,T2. ∃c. ⦃G, L⦄ ⊢ T1 ➡[c, h] T2. + λG,L,T1,T2. ∃c. ⦃G, L⦄ ⊢ T1 ⬈[c, h] T2. interpretation "uncounted context-sensitive parallel reduction (term)" - 'PRed h G L T1 T2 = (cpx h G L T1 T2). + 'PRedTy h G L T1 T2 = (cpx h G L T1 T2). (* Basic properties *********************************************************) -lemma cpx_atom: ∀h,I,G,L. ⦃G, L⦄ ⊢ ⓪{I} ➡[h] ⓪{I}. +lemma cpx_atom: ∀h,I,G,L. ⦃G, L⦄ ⊢ ⓪{I} ⬈[h] ⓪{I}. /2 width=2 by cpg_atom, ex_intro/ qed. (* Basic_2A1: was: cpx_st *) -lemma cpx_ess: ∀h,G,L,s. ⦃G, L⦄ ⊢ ⋆s ➡[h] ⋆(next h s). +lemma cpx_ess: ∀h,G,L,s. ⦃G, L⦄ ⊢ ⋆s ⬈[h] ⋆(next h s). /2 width=2 by cpg_ess, ex_intro/ qed. -lemma cpx_delta: ∀h,I,G,K,V1,V2,W2. ⦃G, K⦄ ⊢ V1 ➡[h] V2 → - ⬆*[1] V2 ≡ W2 → ⦃G, K.ⓑ{I}V1⦄ ⊢ #0 ➡[h] W2. +lemma cpx_delta: ∀h,I,G,K,V1,V2,W2. ⦃G, K⦄ ⊢ V1 ⬈[h] V2 → + ⬆*[1] V2 ≡ W2 → ⦃G, K.ⓑ{I}V1⦄ ⊢ #0 ⬈[h] W2. #h * #G #K #V1 #V2 #W2 * /3 width=4 by cpg_delta, cpg_ell, ex_intro/ qed. -lemma cpx_lref: ∀h,I,G,K,V,T,U,i. ⦃G, K⦄ ⊢ #i ➡[h] T → - ⬆*[1] T ≡ U → ⦃G, K.ⓑ{I}V⦄ ⊢ #⫯i ➡[h] U. +lemma cpx_lref: ∀h,I,G,K,V,T,U,i. ⦃G, K⦄ ⊢ #i ⬈[h] T → + ⬆*[1] T ≡ U → ⦃G, K.ⓑ{I}V⦄ ⊢ #⫯i ⬈[h] U. #h #I #G #K #V #T #U #i * /3 width=4 by cpg_lref, ex_intro/ qed. lemma cpx_bind: ∀h,p,I,G,L,V1,V2,T1,T2. - ⦃G, L⦄ ⊢ V1 ➡[h] V2 → ⦃G, L.ⓑ{I}V1⦄ ⊢ T1 ➡[h] T2 → - ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ➡[h] ⓑ{p,I}V2.T2. + ⦃G, L⦄ ⊢ V1 ⬈[h] V2 → ⦃G, L.ⓑ{I}V1⦄ ⊢ T1 ⬈[h] T2 → + ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ⬈[h] ⓑ{p,I}V2.T2. #h #p #I #G #L #V1 #V2 #T1 #T2 * #cV #HV12 * /3 width=2 by cpg_bind, ex_intro/ qed. lemma cpx_flat: ∀h,I,G,L,V1,V2,T1,T2. - ⦃G, L⦄ ⊢ V1 ➡[h] V2 → ⦃G, L⦄ ⊢ T1 ➡[h] T2 → - ⦃G, L⦄ ⊢ ⓕ{I}V1.T1 ➡[h] ⓕ{I}V2.T2. + ⦃G, L⦄ ⊢ V1 ⬈[h] V2 → ⦃G, L⦄ ⊢ T1 ⬈[h] T2 → + ⦃G, L⦄ ⊢ ⓕ{I}V1.T1 ⬈[h] ⓕ{I}V2.T2. #h #I #G #L #V1 #V2 #T1 #T2 * #cV #HV12 * /3 width=2 by cpg_flat, ex_intro/ qed. -lemma cpx_zeta: ∀h,G,L,V,T1,T,T2. ⦃G, L.ⓓV⦄ ⊢ T1 ➡[h] T → - ⬆*[1] T2 ≡ T → ⦃G, L⦄ ⊢ +ⓓV.T1 ➡[h] T2. +lemma cpx_zeta: ∀h,G,L,V,T1,T,T2. ⦃G, L.ⓓV⦄ ⊢ T1 ⬈[h] T → + ⬆*[1] T2 ≡ T → ⦃G, L⦄ ⊢ +ⓓV.T1 ⬈[h] T2. #h #G #L #V #T1 #T #T2 * /3 width=4 by cpg_zeta, ex_intro/ qed. -lemma cpx_eps: ∀h,G,L,V,T1,T2. ⦃G, L⦄ ⊢ T1 ➡[h] T2 → ⦃G, L⦄ ⊢ ⓝV.T1 ➡[h] T2. +lemma cpx_eps: ∀h,G,L,V,T1,T2. ⦃G, L⦄ ⊢ T1 ⬈[h] T2 → ⦃G, L⦄ ⊢ ⓝV.T1 ⬈[h] T2. #h #G #L #V #T1 #T2 * /3 width=2 by cpg_eps, ex_intro/ qed. (* Basic_2A1: was: cpx_ct *) -lemma cpx_ee: ∀h,G,L,V1,V2,T. ⦃G, L⦄ ⊢ V1 ➡[h] V2 → ⦃G, L⦄ ⊢ ⓝV1.T ➡[h] V2. +lemma cpx_ee: ∀h,G,L,V1,V2,T. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 → ⦃G, L⦄ ⊢ ⓝV1.T ⬈[h] V2. #h #G #L #V1 #V2 #T * /3 width=2 by cpg_ee, ex_intro/ qed. lemma cpx_beta: ∀h,p,G,L,V1,V2,W1,W2,T1,T2. - ⦃G, L⦄ ⊢ V1 ➡[h] V2 → ⦃G, L⦄ ⊢ W1 ➡[h] W2 → ⦃G, L.ⓛW1⦄ ⊢ T1 ➡[h] T2 → - ⦃G, L⦄ ⊢ ⓐV1.ⓛ{p}W1.T1 ➡[h] ⓓ{p}ⓝW2.V2.T2. + ⦃G, L⦄ ⊢ V1 ⬈[h] V2 → ⦃G, L⦄ ⊢ W1 ⬈[h] W2 → ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈[h] T2 → + ⦃G, L⦄ ⊢ ⓐV1.ⓛ{p}W1.T1 ⬈[h] ⓓ{p}ⓝW2.V2.T2. #h #p #G #L #V1 #V2 #W1 #W2 #T1 #T2 * #cV #HV12 * #cW #HW12 * /3 width=2 by cpg_beta, ex_intro/ qed. lemma cpx_theta: ∀h,p,G,L,V1,V,V2,W1,W2,T1,T2. - ⦃G, L⦄ ⊢ V1 ➡[h] V → ⬆*[1] V ≡ V2 → ⦃G, L⦄ ⊢ W1 ➡[h] W2 → - ⦃G, L.ⓓW1⦄ ⊢ T1 ➡[h] T2 → - ⦃G, L⦄ ⊢ ⓐV1.ⓓ{p}W1.T1 ➡[h] ⓓ{p}W2.ⓐV2.T2. + ⦃G, L⦄ ⊢ V1 ⬈[h] V → ⬆*[1] V ≡ V2 → ⦃G, L⦄ ⊢ W1 ⬈[h] W2 → + ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈[h] T2 → + ⦃G, L⦄ ⊢ ⓐV1.ⓓ{p}W1.T1 ⬈[h] ⓓ{p}W2.ⓐV2.T2. #h #p #G #L #V1 #V #V2 #W1 #W2 #T1 #T2 * #cV #HV1 #HV2 * #cW #HW12 * /3 width=4 by cpg_theta, ex_intro/ qed. @@ -94,119 +94,119 @@ qed. lemma cpx_refl: ∀h,G,L. reflexive … (cpx h G L). /2 width=2 by ex_intro/ qed. -lemma cpx_pair_sn: ∀h,I,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 → - ∀T. ⦃G, L⦄ ⊢ ②{I}V1.T ➡[h] ②{I}V2.T. +lemma cpx_pair_sn: ∀h,I,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 → + ∀T. ⦃G, L⦄ ⊢ ②{I}V1.T ⬈[h] ②{I}V2.T. #h #I #G #L #V1 #V2 * /3 width=2 by cpg_pair_sn, ex_intro/ qed. (* Basic inversion lemmas ***************************************************) -lemma cpx_inv_atom1: ∀h,J,G,L,T2. ⦃G, L⦄ ⊢ ⓪{J} ➡[h] T2 → +lemma cpx_inv_atom1: ∀h,J,G,L,T2. ⦃G, L⦄ ⊢ ⓪{J} ⬈[h] T2 → ∨∨ T2 = ⓪{J} | ∃∃s. T2 = ⋆(next h s) & J = Sort s - | ∃∃I,K,V1,V2. ⦃G, K⦄ ⊢ V1 ➡[h] V2 & ⬆*[1] V2 ≡ T2 & + | ∃∃I,K,V1,V2. ⦃G, K⦄ ⊢ V1 ⬈[h] V2 & ⬆*[1] V2 ≡ T2 & L = K.ⓑ{I}V1 & J = LRef 0 - | ∃∃I,K,V,T,i. ⦃G, K⦄ ⊢ #i ➡[h] T & ⬆*[1] T ≡ T2 & + | ∃∃I,K,V,T,i. ⦃G, K⦄ ⊢ #i ⬈[h] T & ⬆*[1] T ≡ T2 & L = K.ⓑ{I}V & J = LRef (⫯i). #h #J #G #L #T2 * #c #H elim (cpg_inv_atom1 … H) -H * /4 width=9 by or4_intro0, or4_intro1, or4_intro2, or4_intro3, ex4_5_intro, ex4_4_intro, ex2_intro, ex_intro/ qed-. -lemma cpx_inv_sort1: ∀h,G,L,T2,s. ⦃G, L⦄ ⊢ ⋆s ➡[h] T2 → +lemma cpx_inv_sort1: ∀h,G,L,T2,s. ⦃G, L⦄ ⊢ ⋆s ⬈[h] T2 → T2 = ⋆s ∨ T2 = ⋆(next h s). #h #G #L #T2 #s * #c #H elim (cpg_inv_sort1 … H) -H * /2 width=1 by or_introl, or_intror/ qed-. -lemma cpx_inv_zero1: ∀h,G,L,T2. ⦃G, L⦄ ⊢ #0 ➡[h] T2 → +lemma cpx_inv_zero1: ∀h,G,L,T2. ⦃G, L⦄ ⊢ #0 ⬈[h] T2 → T2 = #0 ∨ - ∃∃I,K,V1,V2. ⦃G, K⦄ ⊢ V1 ➡[h] V2 & ⬆*[1] V2 ≡ T2 & + ∃∃I,K,V1,V2. ⦃G, K⦄ ⊢ V1 ⬈[h] V2 & ⬆*[1] V2 ≡ T2 & L = K.ⓑ{I}V1. #h #G #L #T2 * #c #H elim (cpg_inv_zero1 … H) -H * /4 width=7 by ex3_4_intro, ex_intro, or_introl, or_intror/ qed-. -lemma cpx_inv_lref1: ∀h,G,L,T2,i. ⦃G, L⦄ ⊢ #⫯i ➡[h] T2 → +lemma cpx_inv_lref1: ∀h,G,L,T2,i. ⦃G, L⦄ ⊢ #⫯i ⬈[h] T2 → T2 = #(⫯i) ∨ - ∃∃I,K,V,T. ⦃G, K⦄ ⊢ #i ➡[h] T & ⬆*[1] T ≡ T2 & L = K.ⓑ{I}V. + ∃∃I,K,V,T. ⦃G, K⦄ ⊢ #i ⬈[h] T & ⬆*[1] T ≡ T2 & L = K.ⓑ{I}V. #h #G #L #T2 #i * #c #H elim (cpg_inv_lref1 … H) -H * /4 width=7 by ex3_4_intro, ex_intro, or_introl, or_intror/ qed-. -lemma cpx_inv_gref1: ∀h,G,L,T2,l. ⦃G, L⦄ ⊢ §l ➡[h] T2 → T2 = §l. +lemma cpx_inv_gref1: ∀h,G,L,T2,l. ⦃G, L⦄ ⊢ §l ⬈[h] T2 → T2 = §l. #h #G #L #T2 #l * #c #H elim (cpg_inv_gref1 … H) -H // qed-. -lemma cpx_inv_bind1: ∀h,p,I,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ➡[h] U2 → ( - ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L.ⓑ{I}V1⦄ ⊢ T1 ➡[h] T2 & +lemma cpx_inv_bind1: ∀h,p,I,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ⬈[h] U2 → ( + ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L.ⓑ{I}V1⦄ ⊢ T1 ⬈[h] T2 & U2 = ⓑ{p,I}V2.T2 ) ∨ - ∃∃T. ⦃G, L.ⓓV1⦄ ⊢ T1 ➡[h] T & ⬆*[1] U2 ≡ T & + ∃∃T. ⦃G, L.ⓓV1⦄ ⊢ T1 ⬈[h] T & ⬆*[1] U2 ≡ T & p = true & I = Abbr. #h #p #I #G #L #V1 #T1 #U2 * #c #H elim (cpg_inv_bind1 … H) -H * /4 width=5 by ex4_intro, ex3_2_intro, ex_intro, or_introl, or_intror/ qed-. -lemma cpx_inv_abbr1: ∀h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓓ{p}V1.T1 ➡[h] U2 → ( - ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L.ⓓV1⦄ ⊢ T1 ➡[h] T2 & +lemma cpx_inv_abbr1: ∀h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓓ{p}V1.T1 ⬈[h] U2 → ( + ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L.ⓓV1⦄ ⊢ T1 ⬈[h] T2 & U2 = ⓓ{p}V2.T2 ) ∨ - ∃∃T. ⦃G, L.ⓓV1⦄ ⊢ T1 ➡[h] T & ⬆*[1] U2 ≡ T & p = true. + ∃∃T. ⦃G, L.ⓓV1⦄ ⊢ T1 ⬈[h] T & ⬆*[1] U2 ≡ T & p = true. #h #p #G #L #V1 #T1 #U2 * #c #H elim (cpg_inv_abbr1 … H) -H * /4 width=5 by ex3_2_intro, ex3_intro, ex_intro, or_introl, or_intror/ qed-. -lemma cpx_inv_abst1: ∀h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓛ{p}V1.T1 ➡[h] U2 → - ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L.ⓛV1⦄ ⊢ T1 ➡[h] T2 & +lemma cpx_inv_abst1: ∀h,p,G,L,V1,T1,U2. ⦃G, L⦄ ⊢ ⓛ{p}V1.T1 ⬈[h] U2 → + ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L.ⓛV1⦄ ⊢ T1 ⬈[h] T2 & U2 = ⓛ{p}V2.T2. #h #p #G #L #V1 #T1 #U2 * #c #H elim (cpg_inv_abst1 … H) -H /3 width=5 by ex3_2_intro, ex_intro/ qed-. -lemma cpx_inv_flat1: ∀h,I,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓕ{I}V1.U1 ➡[h] U2 → - ∨∨ ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L⦄ ⊢ U1 ➡[h] T2 & +lemma cpx_inv_flat1: ∀h,I,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓕ{I}V1.U1 ⬈[h] U2 → + ∨∨ ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L⦄ ⊢ U1 ⬈[h] T2 & U2 = ⓕ{I}V2.T2 - | (⦃G, L⦄ ⊢ U1 ➡[h] U2 ∧ I = Cast) - | (⦃G, L⦄ ⊢ V1 ➡[h] U2 ∧ I = Cast) - | ∃∃p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L⦄ ⊢ W1 ➡[h] W2 & - ⦃G, L.ⓛW1⦄ ⊢ T1 ➡[h] T2 & + | (⦃G, L⦄ ⊢ U1 ⬈[h] U2 ∧ I = Cast) + | (⦃G, L⦄ ⊢ V1 ⬈[h] U2 ∧ I = Cast) + | ∃∃p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L⦄ ⊢ W1 ⬈[h] W2 & + ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈[h] T2 & U1 = ⓛ{p}W1.T1 & U2 = ⓓ{p}ⓝW2.V2.T2 & I = Appl - | ∃∃p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V & ⬆*[1] V ≡ V2 & - ⦃G, L⦄ ⊢ W1 ➡[h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ➡[h] T2 & + | ∃∃p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V & ⬆*[1] V ≡ V2 & + ⦃G, L⦄ ⊢ W1 ⬈[h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈[h] T2 & U1 = ⓓ{p}W1.T1 & U2 = ⓓ{p}W2.ⓐV2.T2 & I = Appl. #h #I #G #L #V1 #U1 #U2 * #c #H elim (cpg_inv_flat1 … H) -H * /4 width=14 by or5_intro0, or5_intro1, or5_intro2, or5_intro3, or5_intro4, ex7_7_intro, ex6_6_intro, ex3_2_intro, ex_intro, conj/ qed-. -lemma cpx_inv_appl1: ∀h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓐ V1.U1 ➡[h] U2 → - ∨∨ ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L⦄ ⊢ U1 ➡[h] T2 & +lemma cpx_inv_appl1: ∀h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓐ V1.U1 ⬈[h] U2 → + ∨∨ ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L⦄ ⊢ U1 ⬈[h] T2 & U2 = ⓐV2.T2 - | ∃∃p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L⦄ ⊢ W1 ➡[h] W2 & - ⦃G, L.ⓛW1⦄ ⊢ T1 ➡[h] T2 & + | ∃∃p,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L⦄ ⊢ W1 ⬈[h] W2 & + ⦃G, L.ⓛW1⦄ ⊢ T1 ⬈[h] T2 & U1 = ⓛ{p}W1.T1 & U2 = ⓓ{p}ⓝW2.V2.T2 - | ∃∃p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V & ⬆*[1] V ≡ V2 & - ⦃G, L⦄ ⊢ W1 ➡[h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ➡[h] T2 & + | ∃∃p,V,V2,W1,W2,T1,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V & ⬆*[1] V ≡ V2 & + ⦃G, L⦄ ⊢ W1 ⬈[h] W2 & ⦃G, L.ⓓW1⦄ ⊢ T1 ⬈[h] T2 & U1 = ⓓ{p}W1.T1 & U2 = ⓓ{p}W2.ⓐV2.T2. #h #G #L #V1 #U1 #U2 * #c #H elim (cpg_inv_appl1 … H) -H * /4 width=13 by or3_intro0, or3_intro1, or3_intro2, ex6_7_intro, ex5_6_intro, ex3_2_intro, ex_intro/ qed-. -lemma cpx_inv_cast1: ∀h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓝV1.U1 ➡[h] U2 → - ∨∨ ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L⦄ ⊢ U1 ➡[h] T2 & +lemma cpx_inv_cast1: ∀h,G,L,V1,U1,U2. ⦃G, L⦄ ⊢ ⓝV1.U1 ⬈[h] U2 → + ∨∨ ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L⦄ ⊢ U1 ⬈[h] T2 & U2 = ⓝV2.T2 - | ⦃G, L⦄ ⊢ U1 ➡[h] U2 - | ⦃G, L⦄ ⊢ V1 ➡[h] U2. + | ⦃G, L⦄ ⊢ U1 ⬈[h] U2 + | ⦃G, L⦄ ⊢ V1 ⬈[h] U2. #h #G #L #V1 #U1 #U2 * #c #H elim (cpg_inv_cast1 … H) -H * /4 width=5 by or3_intro0, or3_intro1, or3_intro2, ex3_2_intro, ex_intro/ qed-. (* Basic forward lemmas *****************************************************) -lemma cpx_fwd_bind1_minus: ∀h,I,G,L,V1,T1,T. ⦃G, L⦄ ⊢ -ⓑ{I}V1.T1 ➡[h] T → ∀p. - ∃∃V2,T2. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ➡[h] ⓑ{p,I}V2.T2 & +lemma cpx_fwd_bind1_minus: ∀h,I,G,L,V1,T1,T. ⦃G, L⦄ ⊢ -ⓑ{I}V1.T1 ⬈[h] T → ∀p. + ∃∃V2,T2. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ⬈[h] ⓑ{p,I}V2.T2 & T = -ⓑ{I}V2.T2. #h #I #G #L #V1 #T1 #T * #c #H #p elim (cpg_fwd_bind1_minus … H p) -H /3 width=4 by ex2_2_intro, ex_intro/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_drops.ma index 6caaa1d76..98c2b491f 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_drops.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_drops.ma @@ -15,14 +15,14 @@ include "basic_2/rt_transition/cpg_drops.ma". include "basic_2/rt_transition/cpx.ma". -(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL REDUCTION FOR TERMS *****************) +(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************) (* Advanced properties ******************************************************) (* Basic_2A1: was: cpx_delta *) lemma cpx_delta_drops: ∀h,I,G,L,K,V,V2,W2,i. - ⬇*[i] L ≡ K.ⓑ{I}V → ⦃G, K⦄ ⊢ V ➡[h] V2 → - ⬆*[⫯i] V2 ≡ W2 → ⦃G, L⦄ ⊢ #i ➡[h] W2. + ⬇*[i] L ≡ K.ⓑ{I}V → ⦃G, K⦄ ⊢ V ⬈[h] V2 → + ⬆*[⫯i] V2 ≡ W2 → ⦃G, L⦄ ⊢ #i ⬈[h] W2. #h * #G #L #K #V #V2 #W2 #i #HLK * /3 width=7 by cpg_ell_drops, cpg_delta_drops, ex_intro/ qed. @@ -30,19 +30,19 @@ qed. (* Advanced inversion lemmas ************************************************) (* Basic_2A1: was: cpx_inv_atom1 *) -lemma cpx_inv_atom1_drops: ∀h,I,G,L,T2. ⦃G, L⦄ ⊢ ⓪{I} ➡[h] T2 → +lemma cpx_inv_atom1_drops: ∀h,I,G,L,T2. ⦃G, L⦄ ⊢ ⓪{I} ⬈[h] T2 → ∨∨ T2 = ⓪{I} | ∃∃s. T2 = ⋆(next h s) & I = Sort s - | ∃∃J,K,V,V2,i. ⬇*[i] L ≡ K.ⓑ{J}V & ⦃G, K⦄ ⊢ V ➡[h] V2 & + | ∃∃J,K,V,V2,i. ⬇*[i] L ≡ K.ⓑ{J}V & ⦃G, K⦄ ⊢ V ⬈[h] V2 & ⬆*[⫯i] V2 ≡ T2 & I = LRef i. #h #I #G #L #T2 * #c #H elim (cpg_inv_atom1_drops … H) -H * /4 width=9 by or3_intro0, or3_intro1, or3_intro2, ex4_5_intro, ex2_intro, ex_intro/ qed-. (* Basic_2A1: was: cpx_inv_lref1 *) -lemma cpx_inv_lref1_drops: ∀h,G,L,T2,i. ⦃G, L⦄ ⊢ #i ➡[h] T2 → +lemma cpx_inv_lref1_drops: ∀h,G,L,T2,i. ⦃G, L⦄ ⊢ #i ⬈[h] T2 → T2 = #i ∨ - ∃∃J,K,V,V2. ⬇*[i] L ≡ K. ⓑ{J}V & ⦃G, K⦄ ⊢ V ➡[h] V2 & + ∃∃J,K,V,V2. ⬇*[i] L ≡ K. ⓑ{J}V & ⦃G, K⦄ ⊢ V ⬈[h] V2 & ⬆*[⫯i] V2 ≡ T2. #h #G #L #T1 #i * #c #H elim (cpg_inv_lref1_drops … H) -H * /4 width=7 by ex3_4_intro, ex_intro, or_introl, or_intror/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_fqus.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_fqus.ma index 645f59987..41763dfa2 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_fqus.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_fqus.ma @@ -12,11 +12,13 @@ (* *) (**************************************************************************) +(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************) + (* Properties on supclosure *************************************************) lemma fqu_cpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h, o] U2 → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡[h, o] U1 & ⦃G1, L1, U1⦄ ⊐ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈[h, o] U2 → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] U1 & ⦃G1, L1, U1⦄ ⊐ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 /3 width=3 by fqu_pair_sn, fqu_bind_dx, fqu_flat_dx, cpx_pair_sn, cpx_bind, cpx_flat, ex2_intro/ [ #I #G #L #V2 #U2 #HVU2 @@ -29,8 +31,8 @@ lemma fqu_cpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐ ⦃G2, L2, T qed-. lemma fquq_cpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h, o] U2 → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡[h, o] U1 & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈[h, o] U2 → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] U1 & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H #U2 #HTU2 elim (fquq_inv_gen … H) -H [ #HT12 elim (fqu_cpx_trans … HT12 … HTU2) /3 width=3 by fqu_fquq, ex2_intro/ | * #H1 #H2 #H3 destruct /2 width=3 by ex2_intro/ @@ -38,8 +40,8 @@ lemma fquq_cpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G2, L qed-. lemma fqup_cpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐+ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h, o] U2 → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡[h, o] U1 & ⦃G1, L1, U1⦄ ⊐+ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈[h, o] U2 → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] U1 & ⦃G1, L1, U1⦄ ⊐+ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H @(fqup_ind … H) -G2 -L2 -T2 [ #G2 #L2 #T2 #H12 #U2 #HTU2 elim (fqu_cpx_trans … H12 … HTU2) -T2 /3 width=3 by fqu_fqup, ex2_intro/ @@ -50,8 +52,8 @@ lemma fqup_cpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐+ ⦃G2, L2, qed-. lemma fqus_cpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐* ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h, o] U2 → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡[h, o] U1 & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈[h, o] U2 → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] U1 & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H #U2 #HTU2 elim (fqus_inv_gen … H) -H [ #HT12 elim (fqup_cpx_trans … HT12 … HTU2) /3 width=3 by fqup_fqus, ex2_intro/ | * #H1 #H2 #H3 destruct /2 width=3 by ex2_intro/ @@ -59,8 +61,8 @@ lemma fqus_cpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐* ⦃G2, L2, qed-. lemma fqu_cpx_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h, o] U2 → (T2 = U2 → ⊥) → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈[h, o] U2 → (T2 = U2 → ⊥) → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 [ #I #G #L #V1 #V2 #HV12 #_ elim (lift_total V2 0 1) #U2 #HVU2 @(ex3_intro … U2) @@ -88,8 +90,8 @@ lemma fqu_cpx_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐ ⦃G2, L qed-. lemma fquq_cpx_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h, o] U2 → (T2 = U2 → ⊥) → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈[h, o] U2 → (T2 = U2 → ⊥) → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐⸮ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H12 #U2 #HTU2 #H elim (fquq_inv_gen … H12) -H12 [ #H12 elim (fqu_cpx_trans_neq … H12 … HTU2 H) -T2 /3 width=4 by fqu_fquq, ex3_intro/ @@ -98,8 +100,8 @@ lemma fquq_cpx_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G qed-. lemma fqup_cpx_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐+ ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h, o] U2 → (T2 = U2 → ⊥) → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐+ ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈[h, o] U2 → (T2 = U2 → ⊥) → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐+ ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H @(fqup_ind_dx … H) -G1 -L1 -T1 [ #G1 #L1 #T1 #H12 #U2 #HTU2 #H elim (fqu_cpx_trans_neq … H12 … HTU2 H) -T2 /3 width=4 by fqu_fqup, ex3_intro/ @@ -110,8 +112,8 @@ lemma fqup_cpx_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐+ ⦃G2, qed-. lemma fqus_cpx_trans_neq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐* ⦃G2, L2, T2⦄ → - ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h, o] U2 → (T2 = U2 → ⊥) → - ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ➡[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. + ∀U2. ⦃G2, L2⦄ ⊢ T2 ⬈[h, o] U2 → (T2 = U2 → ⊥) → + ∃∃U1. ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] U1 & T1 = U1 → ⊥ & ⦃G1, L1, U1⦄ ⊐* ⦃G2, L2, U2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 #H12 #U2 #HTU2 #H elim (fqus_inv_gen … H12) -H12 [ #H12 elim (fqup_cpx_trans_neq … H12 … HTU2 H) -T2 /3 width=4 by fqup_fqus, ex3_intro/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lleq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lleq.ma index 2f608db01..946975957 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lleq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lleq.ma @@ -15,12 +15,12 @@ include "basic_2/multiple/lleq_drop.ma". include "basic_2/reduction/cpx_llpx_sn.ma". -(* CONTEXT-SENSITIVE EXTENDED PARALLEL REDUCTION FOR TERMS ******************) +(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************) (* Properties on lazy equivalence for local environments ********************) -lemma lleq_cpx_trans: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ➡[h, o] T2 → - ∀L1. L1 ≡[T1, 0] L2 → ⦃G, L1⦄ ⊢ T1 ➡[h, o] T2. +lemma lleq_cpx_trans: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ⬈[h, o] T2 → + ∀L1. L1 ≡[T1, 0] L2 → ⦃G, L1⦄ ⊢ T1 ⬈[h, o] T2. #h #o #G #L2 #T1 #T2 #H elim H -G -L2 -T1 -T2 /2 width=2 by cpx_st/ [ #I #G #L2 #K2 #V1 #V2 #W2 #i #HLK2 #_ #HVW2 #IHV12 #L1 #H elim (lleq_fwd_lref_dx … H … HLK2) -L2 [ #H elim (ylt_yle_false … H) // @@ -43,13 +43,13 @@ lemma lleq_cpx_trans: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ➡[h, o] T2 → ] qed-. -lemma cpx_lleq_conf: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ➡[h, o] T2 → - ∀L1. L2 ≡[T1, 0] L1 → ⦃G, L1⦄ ⊢ T1 ➡[h, o] T2. +lemma cpx_lleq_conf: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ⬈[h, o] T2 → + ∀L1. L2 ≡[T1, 0] L1 → ⦃G, L1⦄ ⊢ T1 ⬈[h, o] T2. /3 width=3 by lleq_cpx_trans, lleq_sym/ qed-. lemma cpx_lleq_conf_sn: ∀h,o,G. b_c_confluent1 … (cpx h o G) (lleq 0). /3 width=6 by cpx_llpx_sn_conf, lift_mono, ex2_intro/ qed-. -lemma cpx_lleq_conf_dx: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ➡[h, o] T2 → +lemma cpx_lleq_conf_dx: ∀h,o,G,L2,T1,T2. ⦃G, L2⦄ ⊢ T1 ⬈[h, o] T2 → ∀L1. L1 ≡[T1, 0] L2 → L1 ≡[T2, 0] L2. /4 width=6 by cpx_lleq_conf_sn, lleq_sym/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_llpx_sn.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_llpx_sn.ma index 6be896ddc..ec6255dfc 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_llpx_sn.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_llpx_sn.ma @@ -15,7 +15,7 @@ include "basic_2/multiple/llpx_sn_drop.ma". include "basic_2/reduction/cpx.ma". -(* CONTEXT-SENSITIVE EXTENDED PARALLEL REDUCTION FOR TERMS ******************) +(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************) (* Properties on lazy sn pointwise extensions *******************************) diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lreq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lreq.ma index 04d85b66f..9c41e252a 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lreq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lreq.ma @@ -15,7 +15,7 @@ include "basic_2/substitution/drop_lreq.ma". include "basic_2/reduction/cpx.ma". -(* CONTEXT-SENSITIVE EXTENDED PARALLEL REDUCTION FOR TERMS ******************) +(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************) (* Properties on equivalence for local environments *************************) diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lsubr.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lsubr.ma index cd50906ec..c2e3d8ad7 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lsubr.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_lsubr.ma @@ -15,7 +15,7 @@ include "basic_2/rt_transition/cpg_lsubr.ma". include "basic_2/rt_transition/cpx.ma". -(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL REDUCTION FOR TERMS *****************) +(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************) lemma lsubr_cpx_trans: ∀h,G. lsub_trans … (cpx h G) lsubr. #h #G #L1 #T1 #T2 * /3 width=4 by lsubr_cpg_trans, ex_intro/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_simple.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_simple.ma index 70e2d3dd3..fbc9eb644 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_simple.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpx_simple.ma @@ -15,10 +15,10 @@ include "basic_2/rt_transition/cpg_simple.ma". include "basic_2/rt_transition/cpx.ma". -(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL REDUCTION FOR TERMS *****************) +(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************) -lemma cpx_inv_appl1_simple: ∀h,G,L,V1,T1,U. ⦃G, L⦄ ⊢ ⓐV1.T1 ➡[h] U → 𝐒⦃T1⦄ → - ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 & ⦃G, L⦄ ⊢ T1 ➡[h] T2 & +lemma cpx_inv_appl1_simple: ∀h,G,L,V1,T1,U. ⦃G, L⦄ ⊢ ⓐV1.T1 ⬈[h] U → 𝐒⦃T1⦄ → + ∃∃V2,T2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 & ⦃G, L⦄ ⊢ T1 ⬈[h] T2 & U = ⓐV2.T2. #h #G #L #V1 #T1 #U * #c #H #HT1 elim (cpg_inv_appl1_simple … H) -H /3 width=5 by ex3_2_intro, ex_intro/ diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/partial.txt b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/partial.txt new file mode 100644 index 000000000..e69bf6b0a --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/partial.txt @@ -0,0 +1,2 @@ +cpg.ma cpg_simple.ma cpg_drops.ma cpg_lsubr.ma +cpx.ma cpx_simple.ma cpx_drops.ma cpx_lsubr.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/web/basic_2_src.tbl b/matita/matita/contribs/lambdadelta/basic_2/web/basic_2_src.tbl index a5aeb85db..6e479eaa3 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/web/basic_2_src.tbl +++ b/matita/matita/contribs/lambdadelta/basic_2/web/basic_2_src.tbl @@ -149,11 +149,11 @@ table { ] *) [ { "uncounted context-sensitive rt-transition" * } { - [ "cpx ( ⦃?,?⦄ ⊢ ? ➡[?] ? )" "cpx_simple" + "cpx_drops" + "cpx_lsubr" * ] + [ "cpx ( ⦃?,?⦄ ⊢ ? ⬈[?] ? )" "cpx_simple" + "cpx_drops" + "cpx_lsubr" * ] } ] [ { "counted context-sensitive rt-transition" * } { - [ "cpg ( ⦃?,?⦄ ⊢ ? ➡[?,?] ? )" "cpg_simple" + "cpg_drops" + "cpg_lsubr" * ] + [ "cpg ( ⦃?,?⦄ ⊢ ? ⬈[?,?] ? )" "cpg_simple" + "cpg_drops" + "cpg_lsubr" * ] } ] } @@ -215,8 +215,8 @@ table { class "orange" [ { "relocation" * } { [ { "generic slicing for local environments" * } { - [ "drops_vector ( ⬇*[?,?] ? ≡ ? )" * ] - [ "drops ( ⬇*[?,?] ? ≡ ? )" "drops_lstar" + "drops_weight" + "drops_length" + "drops_ceq" + "drops_lexs" + "drops_lreq" + "drops_drops" * ] + [ "drops_vector ( ⬇*[?,?] ? ≡ ? ) ( ⬇*[?] ? ≡ ? )" * ] + [ "drops ( ⬇*[?,?] ? ≡ ? ) ( ⬇*[?] ? ≡ ? )" "drops_lstar" + "drops_weight" + "drops_length" + "drops_ceq" + "drops_lexs" + "drops_lreq" + "drops_drops" * ] } ] [ { "generic relocation for terms" * } { diff --git a/matita/matita/contribs/lambdadelta/replace.sh b/matita/matita/contribs/lambdadelta/replace.sh index 5e281b251..739dd9871 100644 --- a/matita/matita/contribs/lambdadelta/replace.sh +++ b/matita/matita/contribs/lambdadelta/replace.sh @@ -1,5 +1,6 @@ #!/bin/sh -for MA in `find -name "*.ma"`; do +#for MA in `find -name "*.ma"`; do +for MA in `find -name "cpg*.ma" -or -name "cpx*.ma"`; do echo ${MA}; sed "s!$1!$2!g" ${MA} > ${MA}.new if diff ${MA} ${MA}.new > /dev/null; then rm -f ${MA}.new; diff --git a/matita/matita/predefined_virtuals.ml b/matita/matita/predefined_virtuals.ml index 768850779..6b259a253 100644 --- a/matita/matita/predefined_virtuals.ml +++ b/matita/matita/predefined_virtuals.ml @@ -1514,7 +1514,7 @@ let predefined_classes = [ ["-"; "÷"; "⊢"; "⊩"; "⊟"; ]; ["="; "≝"; "≡"; "⩬"; "≂"; "≃"; "≈"; "≅"; "≗"; "≐"; "≑"; "≚"; "≙"; "⌆"; "⊜"; ]; ["→"; "↦"; "⇝"; "⤞"; "⇾"; "⤍"; "⤏"; "⤳"; ] ; - ["⇒"; "⤇"; "➾"; "⇨"; "➡"; "➤"; "➸"; "⇉"; "⥰"; ] ; + ["⇒"; "⤇"; "➾"; "⇨"; "➡"; "⬈"; "➤"; "➸"; "⇉"; "⥰"; ] ; ["^"; "↑"; ] ; ["⇑"; "⇧"; "⬆"; ] ; ["⇓"; "⇩"; "⬇"; "⬊"; "➷"; ] ;