From 05b047be6817f430c8c72fd9b0902df8bb9f579e Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Wed, 23 May 2018 21:08:25 +0200 Subject: [PATCH] update in ground_2 and basic_2 (partial commit) + preferring lpx and lpr over lfpx and lfpr since lpx seems unavoidable + rt_computation will be updated by the next commit --- .../lambdadelta/basic_2/etc/lpx/lpx_fquq.etc | 22 -- .../lfpr.ma => etc/referred/lfpr.etc} | 0 .../lfpr_aaa.ma => etc/referred/lfpr_aaa.etc} | 0 .../referred/lfpr_drops.etc} | 0 .../referred/lfpr_fqup.etc} | 0 .../referred/lfpr_fquq.etc} | 0 .../referred/lfpr_length.etc} | 0 .../referred/lfpr_lfpr.etc} | 1 - .../referred/lfpr_lfpx.etc} | 0 .../lfpx_aaa.ma => etc/referred/lfpx_aaa.etc} | 6 - .../referred/lfpx_drops.etc} | 0 .../referred/lfpx_fquq.etc} | 2 - .../predsn_5.ma => etc/referred/predsn_5.etc} | 0 .../basic_2/i_static/tc_lfxs_drops.ma | 30 +- .../basic_2/notation/relations/predsn_4.ma | 19 + .../basic_2/relocation/drops_lex.ma | 83 ++++ .../basic_2/relocation/drops_lexs.ma | 6 +- .../lambdadelta/basic_2/relocation/lex.ma | 103 ++++- .../lambdadelta/basic_2/relocation/lex_lex.ma | 52 +++ .../basic_2/relocation/lexs_lexs.ma | 2 - .../basic_2/rt_transition/cpm_aaa.ma | 24 ++ .../basic_2/rt_transition/cpm_lsubr.ma | 7 +- .../basic_2/rt_transition/cpr_cpr.ma | 23 ++ .../basic_2/rt_transition/cpx_lsubr.ma | 8 +- .../lambdadelta/basic_2/rt_transition/fpb.ma | 19 +- .../basic_2/rt_transition/fpb_lfdeq.ma | 8 +- .../lambdadelta/basic_2/rt_transition/fpbq.ma | 12 +- .../basic_2/rt_transition/fpbq_aaa.ma | 4 +- .../basic_2/rt_transition/fpbq_fpb.ma | 4 +- .../lambdadelta/basic_2/rt_transition/lfpx.ma | 12 +- .../basic_2/rt_transition/lfpx_fqup.ma | 4 +- .../basic_2/rt_transition/lfpx_fsle.ma | 29 +- .../basic_2/rt_transition/lfpx_length.ma | 3 +- .../basic_2/rt_transition/lfpx_lfdeq.ma | 3 +- .../basic_2/rt_transition/lfpx_lfpx.ma | 2 +- .../basic_2/rt_transition/lfpx_lpx.ma | 13 +- .../lambdadelta/basic_2/rt_transition/lpr.ma | 98 +++++ .../basic_2/rt_transition/lpr_aaa.ma | 23 ++ .../basic_2/rt_transition/lpr_drops.ma | 37 ++ .../basic_2/rt_transition/lpr_fquq.ma | 128 +++++++ .../basic_2/rt_transition/lpr_length.ma | 21 + .../basic_2/rt_transition/lpr_lpr.ma | 362 ++++++++++++++++++ .../basic_2/rt_transition/lpr_lpx.ma | 25 ++ .../lambdadelta/basic_2/rt_transition/lpx.ma | 68 ++-- .../basic_2/rt_transition/lpx_aaa.ma | 80 ++++ .../basic_2/rt_transition/lpx_drops.ma | 35 ++ .../basic_2/rt_transition/lpx_fquq.ma | 75 ++++ .../basic_2/rt_transition/lpx_fsle.ma | 28 ++ .../basic_2/rt_transition/lpx_length.ma | 23 ++ .../basic_2/rt_transition/lpx_lfdeq.ma | 32 ++ .../lambdadelta/basic_2/static/lfdeq_drops.ma | 6 +- .../lambdadelta/basic_2/static/lfxs_drops.ma | 34 +- .../lambdadelta/basic_2/static/lfxs_fsle.ma | 2 +- .../lambdadelta/basic_2/web/basic_2_src.tbl | 24 +- .../lambdadelta/ground_2/pull/pull_2.ma | 24 ++ .../lambdadelta/ground_2/pull/pull_4.ma | 26 ++ .../lambdadelta/ground_2/web/ground_2_src.tbl | 6 +- 57 files changed, 1455 insertions(+), 203 deletions(-) delete mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/lpx/lpx_fquq.etc rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpr.ma => etc/referred/lfpr.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpr_aaa.ma => etc/referred/lfpr_aaa.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpr_drops.ma => etc/referred/lfpr_drops.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpr_fqup.ma => etc/referred/lfpr_fqup.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpr_fquq.ma => etc/referred/lfpr_fquq.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpr_length.ma => etc/referred/lfpr_length.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpr_lfpr.ma => etc/referred/lfpr_lfpr.etc} (99%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpr_lfpx.ma => etc/referred/lfpr_lfpx.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpx_aaa.ma => etc/referred/lfpx_aaa.etc} (95%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpx_drops.ma => etc/referred/lfpx_drops.etc} (100%) rename matita/matita/contribs/lambdadelta/basic_2/{rt_transition/lfpx_fquq.ma => etc/referred/lfpx_fquq.etc} (97%) rename matita/matita/contribs/lambdadelta/basic_2/{notation/relations/predsn_5.ma => etc/referred/predsn_5.etc} (100%) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/notation/relations/predsn_4.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lex.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/relocation/lex_lex.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpm_aaa.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpr_cpr.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_aaa.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_drops.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_fquq.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_length.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_lpr.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_lpx.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_aaa.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_drops.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_fquq.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_fsle.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_length.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_lfdeq.ma create mode 100644 matita/matita/contribs/lambdadelta/ground_2/pull/pull_2.ma create mode 100644 matita/matita/contribs/lambdadelta/ground_2/pull/pull_4.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/lpx/lpx_fquq.etc b/matita/matita/contribs/lambdadelta/basic_2/etc/lpx/lpx_fquq.etc deleted file mode 100644 index a775683dd..000000000 --- a/matita/matita/contribs/lambdadelta/basic_2/etc/lpx/lpx_fquq.etc +++ /dev/null @@ -1,22 +0,0 @@ -lemma fqu_lpx_trans: ∀h,b,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐[b] ⦃G2, L2, T2⦄ → - ∀K2. ⦃G2, L2⦄ ⊢ ⬈[h] K2 → - ∃∃K1,T. ⦃G1, L1⦄ ⊢ ⬈[h] K1 & ⦃G1, L1⦄ ⊢ T1 ⬈[h] T & ⦃G1, K1, T⦄ ⊐[b] ⦃G2, K2, T2⦄. -#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 -/3 width=5 by fqu_lref_O, fqu_pair_sn, fqu_flat_dx, lpx_pair, ex3_2_intro/ -[ #a #I #G2 #L2 #V2 #T2 #X #H elim (lpx_inv_pair1 … H) -H - #K2 #W2 #HLK2 #HVW2 #H destruct - /3 width=5 by cpx_pair_sn, fqu_bind_dx, ex3_2_intro/ -| #G #L1 #K1 #T1 #U1 #k #HLK1 #HTU1 #K2 #HK12 - elim (drop_lpx_trans … HLK1 … HK12) -HK12 - /3 width=7 by fqu_drop, ex3_2_intro/ -] -qed-. - -lemma fquq_lpx_trans: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G2, L2, T2⦄ → - ∀K2. ⦃G2, L2⦄ ⊢ ⬈[h, o] K2 → - ∃∃K1,T. ⦃G1, L1⦄ ⊢ ⬈[h, o] K1 & ⦃G1, L1⦄ ⊢ T1 ⬈[h, o] T & ⦃G1, K1, T⦄ ⊐⸮ ⦃G2, K2, T2⦄. -#h #o #G1 #G2 #L1 #L2 #T1 #T2 #H #K2 #HLK2 elim (fquq_inv_gen … H) -H -[ #HT12 elim (fqu_lpx_trans … HT12 … HLK2) /3 width=5 by fqu_fquq, ex3_2_intro/ -| * #H1 #H2 #H3 destruct /2 width=5 by ex3_2_intro/ -] -qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_aaa.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_aaa.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_aaa.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_drops.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_drops.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_drops.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_fqup.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_fqup.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_fqup.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_fqup.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_fquq.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_fquq.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_fquq.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_fquq.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_length.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_length.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_length.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_length.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_lfpr.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_lfpr.etc similarity index 99% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_lfpr.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_lfpr.etc index 7d3264482..117dd0267 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_lfpr.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_lfpr.etc @@ -358,7 +358,6 @@ theorem cpr_conf_lfpr: ∀h,G. R_confluent2_lfxs (λL. cpm h G L 0) (λL. cpm h ] qed-. -(* Basic_1: includes: pr0_confluence pr2_confluence *) theorem cpr_conf: ∀h,G,L. confluent … (cpm h G L 0). /2 width=6 by cpr_conf_lfpr/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_lfpx.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_lfpx.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpr_lfpx.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpr_lfpx.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpx_aaa.etc similarity index 95% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_aaa.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpx_aaa.etc index 6dc8c1946..fe8886160 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_aaa.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpx_aaa.etc @@ -20,8 +20,6 @@ include "basic_2/rt_transition/lfpx_fqup.ma". (* Properties with atomic arity assignment for terms ************************) -(* Note: lemma 500 *) -(* Basic_2A1: uses: cpx_lpx_aaa_conf *) lemma cpx_aaa_conf_lfpx: ∀h,G,L1,T1,A. ⦃G, L1⦄ ⊢ T1 ⁝ A → ∀T2. ⦃G, L1⦄ ⊢ T1 ⬈[h] T2 → ∀L2. ⦃G, L1⦄ ⊢ ⬈[h, T1] L2 → ⦃G, L2⦄ ⊢ T2 ⁝ A. @@ -73,9 +71,5 @@ lemma cpx_aaa_conf_lfpx: ∀h,G,L1,T1,A. ⦃G, L1⦄ ⊢ T1 ⁝ A → ] qed-. -lemma cpx_aaa_conf: ∀h,G,L. Conf3 … (aaa G L) (cpx h G L). -/2 width=6 by cpx_aaa_conf_lfpx/ qed-. - -(* Basic_2A1: uses: lpx_aaa_conf *) lemma lfpx_aaa_conf: ∀h,G,T. Conf3 … (λL. aaa G L T) (lfpx h G T). /2 width=6 by cpx_aaa_conf_lfpx/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpx_drops.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_drops.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpx_drops.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fquq.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpx_fquq.etc similarity index 97% rename from matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fquq.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpx_fquq.etc index f08b90319..a0587c329 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fquq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/lfpx_fquq.etc @@ -20,7 +20,6 @@ include "basic_2/s_transition/fquq.ma". (* Properties with extended structural successor for closures ***************) -(* Basic_2A1: uses: lpx_fqu_trans *) lemma lfpx_fqu_trans: ∀h,b,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐[b] ⦃G2, L2, T2⦄ → ∀K1. ⦃G1, K1⦄ ⊢ ⬈[h, T1] L1 → ∃∃K2,T. ⦃G1, K1⦄ ⊢ T1 ⬈[h] T & ⦃G1, K1, T⦄ ⊐[b] ⦃G2, K2, T2⦄ & ⦃G2, K2⦄ ⊢ ⬈[h, T2] L2. @@ -44,7 +43,6 @@ qed-. (* Properties with extended optional structural successor for closures ******) -(* Basic_2A1: uses: lpx_fquq_trans *) lemma lfpx_fquq_trans: ∀h,b,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮[b] ⦃G2, L2, T2⦄ → ∀K1. ⦃G1, K1⦄ ⊢ ⬈[h, T1] L1 → ∃∃K2,T. ⦃G1, K1⦄ ⊢ T1 ⬈[h] T & ⦃G1, K1, T⦄ ⊐⸮[b] ⦃G2, K2, T2⦄ & ⦃G2, K2⦄ ⊢ ⬈[h, T2] L2. diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predsn_5.ma b/matita/matita/contribs/lambdadelta/basic_2/etc/referred/predsn_5.etc similarity index 100% rename from matita/matita/contribs/lambdadelta/basic_2/notation/relations/predsn_5.ma rename to matita/matita/contribs/lambdadelta/basic_2/etc/referred/predsn_5.etc diff --git a/matita/matita/contribs/lambdadelta/basic_2/i_static/tc_lfxs_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/i_static/tc_lfxs_drops.ma index 6d24a75c7..006ca8f1a 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/i_static/tc_lfxs_drops.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/i_static/tc_lfxs_drops.ma @@ -18,24 +18,24 @@ include "basic_2/i_static/tc_lfxs.ma". (* ITERATED EXTENSION ON REFERRED ENTRIES OF A CONTEXT-SENSITIVE REALTION ***) -definition tc_dedropable_sn: predicate (relation3 lenv term term) ≝ - λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → - ∀K2,T. K1 ⪤**[R, T] K2 → ∀U. ⬆*[f] T ≘ U → - ∃∃L2. L1 ⪤**[R, U] L2 & ⬇*[b, f] L2 ≘ K2 & L1 ≡[f] L2. +definition tc_f_dedropable_sn: predicate (relation3 lenv term term) ≝ + λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → + ∀K2,T. K1 ⪤**[R, T] K2 → ∀U. ⬆*[f] T ≘ U → + ∃∃L2. L1 ⪤**[R, U] L2 & ⬇*[b, f] L2 ≘ K2 & L1 ≡[f] L2. -definition tc_dropable_sn: predicate (relation3 lenv term term) ≝ - λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → 𝐔⦃f⦄ → - ∀L2,U. L1 ⪤**[R, U] L2 → ∀T. ⬆*[f] T ≘ U → - ∃∃K2. K1 ⪤**[R, T] K2 & ⬇*[b, f] L2 ≘ K2. +definition tc_f_dropable_sn: predicate (relation3 lenv term term) ≝ + λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → 𝐔⦃f⦄ → + ∀L2,U. L1 ⪤**[R, U] L2 → ∀T. ⬆*[f] T ≘ U → + ∃∃K2. K1 ⪤**[R, T] K2 & ⬇*[b, f] L2 ≘ K2. -definition tc_dropable_dx: predicate (relation3 lenv term term) ≝ - λR. ∀L1,L2,U. L1 ⪤**[R, U] L2 → - ∀b,f,K2. ⬇*[b, f] L2 ≘ K2 → 𝐔⦃f⦄ → ∀T. ⬆*[f] T ≘ U → - ∃∃K1. ⬇*[b, f] L1 ≘ K1 & K1 ⪤**[R, T] K2. +definition tc_f_dropable_dx: predicate (relation3 lenv term term) ≝ + λR. ∀L1,L2,U. L1 ⪤**[R, U] L2 → + ∀b,f,K2. ⬇*[b, f] L2 ≘ K2 → 𝐔⦃f⦄ → ∀T. ⬆*[f] T ≘ U → + ∃∃K1. ⬇*[b, f] L1 ≘ K1 & K1 ⪤**[R, T] K2. (* Properties with generic slicing for local environments *******************) -lemma dedropable_sn_CTC: ∀R. dedropable_sn R → tc_dedropable_sn R. +lemma dedropable_sn_CTC: ∀R. f_dedropable_sn R → tc_f_dedropable_sn R. #R #HR #b #f #L1 #K1 #HLK1 #K2 #T #H elim H -K2 [ #K2 #HK12 #U #HTU elim (HR … HLK1 … HK12 … HTU) -K1 -T -HR /3 width=4 by ex3_intro, inj/ @@ -48,7 +48,7 @@ qed-. (* Inversion lemmas with generic slicing for local environments *************) -lemma dropable_sn_CTC: ∀R. dropable_sn R → tc_dropable_sn R. +lemma dropable_sn_CTC: ∀R. f_dropable_sn R → tc_f_dropable_sn R. #R #HR #b #f #L1 #K1 #HLK1 #Hf #L2 #U #H elim H -L2 [ #L2 #HL12 #T #HTU elim (HR … HLK1 … HL12 … HTU) -L1 -U -HR /3 width=3 by inj, ex2_intro/ @@ -59,7 +59,7 @@ lemma dropable_sn_CTC: ∀R. dropable_sn R → tc_dropable_sn R. ] qed-. -lemma dropable_dx_CTC: ∀R. dropable_dx R → tc_dropable_dx R. +lemma dropable_dx_CTC: ∀R. f_dropable_dx R → tc_f_dropable_dx R. #R #HR #L1 #L2 #U #H elim H -L2 [ #L2 #HL12 #b #f #K2 #HLK2 #Hf #T #HTU elim (HR … HL12 … HLK2 … HTU) -L2 -U -HR diff --git a/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predsn_4.ma b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predsn_4.ma new file mode 100644 index 000000000..5912f1d40 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/notation/relations/predsn_4.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 L1 ⦄ ⊢ ➡[ break term 46 h ] break term 46 L2 )" + non associative with precedence 45 + for @{ 'PRedSn $h $G $L1 $L2 }. diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lex.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lex.ma new file mode 100644 index 000000000..b1c4f4d91 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lex.ma @@ -0,0 +1,83 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/relocation/lex.ma". +include "basic_2/relocation/drops_cext2.ma". +include "basic_2/relocation/drops_lexs.ma". + +(* GENERIC SLICING FOR LOCAL ENVIRONMENTS ***********************************) + +definition dedropable_sn: predicate … ≝ + λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → ∀K2. K1 ⪤[R] K2 → + ∃∃L2. L1 ⪤[R] L2 & ⬇*[b, f] L2 ≘ K2 & L1 ≡[f] L2. + +definition dropable_sn: predicate … ≝ + λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → 𝐔⦃f⦄ → ∀L2. L1 ⪤[R] L2 → + ∃∃K2. K1 ⪤[R] K2 & ⬇*[b, f] L2 ≘ K2. + +definition dropable_dx: predicate … ≝ + λR. ∀L1,L2. L1 ⪤[R] L2 → ∀b,f,K2. ⬇*[b, f] L2 ≘ K2 → 𝐔⦃f⦄ → + ∃∃K1. ⬇*[b, f] L1 ≘ K1 & K1 ⪤[R] K2. + +(* Properties with generic extension ****************************************) + +(* Basic_2A1: was: lpx_sn_liftable_dedropable *) +lemma lex_liftable_dedropable_sn (R): c_reflexive … R → + d_liftable2_sn … lifts R → dedropable_sn R. +#R #H1R #H2R #b #f #L1 #K1 #HLK1 #K2 * #f1 #Hf1 #HK12 +elim (lexs_liftable_co_dedropable_sn … HLK1 … HK12) -K1 +/3 width=6 by cext2_d_liftable2_sn, cfull_lift_sn, ext2_refl, coafter_isid_dx, ex3_intro, ex2_intro/ +qed-. + +(* Inversion lemmas with generic extension **********************************) + +(* Basic_2A1: was: lpx_sn_deliftable_dropable *) +lemma lex_dropable_sn (R): dropable_sn R. +#R #b #f #L1 #K1 #HLK1 #H1f #L2 * #f2 #Hf2 #HL12 +elim (lexs_co_dropable_sn … HLK1 … HL12) -L1 +/3 width=3 by coafter_isid_dx, ex2_intro/ +qed-. + +(* Basic_2A1: was: lpx_sn_dropable *) +lemma lex_dropable_dx (R): dropable_dx R. +#R #L1 #L2 * #f2 #Hf2 #HL12 #b #f #K2 #HLK2 #Hf +elim (lexs_co_dropable_dx … HL12 … HLK2) -L2 +/3 width=5 by coafter_isid_dx, ex2_intro/ +qed-. + +(* Basic_2A1: includes: lpx_sn_drop_conf *) +lemma lex_drops_conf_pair (R): ∀L1,L2. L1 ⪤[R] L2 → + ∀b,f,I,K1,V1. ⬇*[b, f] L1 ≘ K1.ⓑ{I}V1 → 𝐔⦃f⦄ → + ∃∃K2,V2. ⬇*[b, f] L2 ≘ K2.ⓑ{I}V2 & K1 ⪤[R] K2 & R K1 V1 V2. +#R #L1 #L2 * #f2 #Hf2 #HL12 #b #f #I #K1 #V1 #HLK1 #Hf +elim (lexs_drops_conf_push … HL12 … HLK1 Hf f2) -L1 -Hf +[ #Z2 #K2 #HLK2 #HK12 #H + elim (ext2_inv_pair_sn … H) -H #V2 #HV12 #H destruct + /3 width=5 by ex3_2_intro, ex2_intro/ +| /3 width=3 by coafter_isid_dx, isid_push/ +] +qed-. + +(* Basic_2A1: includes: lpx_sn_drop_trans *) +lemma lex_drops_trans_pair (R): ∀L1,L2. L1 ⪤[R] L2 → + ∀b,f,I,K2,V2. ⬇*[b, f] L2 ≘ K2.ⓑ{I}V2 → 𝐔⦃f⦄ → + ∃∃K1,V1. ⬇*[b, f] L1 ≘ K1.ⓑ{I}V1 & K1 ⪤[R] K2 & R K1 V1 V2. +#R #L1 #L2 * #f2 #Hf2 #HL12 #b #f #I #K2 #V2 #HLK2 #Hf +elim (lexs_drops_trans_push … HL12 … HLK2 Hf f2) -L2 -Hf +[ #Z1 #K1 #HLK1 #HK12 #H + elim (ext2_inv_pair_dx … H) -H #V1 #HV12 #H destruct + /3 width=5 by ex3_2_intro, ex2_intro/ +| /3 width=3 by coafter_isid_dx, isid_push/ +] +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lexs.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lexs.ma index 18519b6fc..11b08f3e6 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lexs.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/drops_lexs.ma @@ -19,7 +19,7 @@ include "basic_2/relocation/drops.ma". (* Properties with entrywise extension of context-sensitive relations *******) -(* Basic_2A1: includes: lpx_sn_deliftable_dropable *) (**) (* changed after commit 13218 *) +(**) (* changed after commit 13218 *) lemma lexs_co_dropable_sn: ∀RN,RP. co_dropable_sn (lexs RN RP). #RN #RP #b #f #L1 #K1 #H elim H -f -L1 -K1 [ #f #Hf #_ #f2 #X #H #f1 #Hf2 >(lexs_inv_atom1 … H) -X @@ -68,7 +68,6 @@ lemma lexs_liftable_co_dedropable_bi: ∀RN,RP. d_liftable2_sn … liftsb RN → ] qed-. -(* Basic_2A1: includes: lpx_sn_liftable_dedropable *) lemma lexs_liftable_co_dedropable_sn: ∀RN,RP. (∀L. reflexive … (RN L)) → (∀L. reflexive … (RP L)) → d_liftable2_sn … liftsb RN → d_liftable2_sn … liftsb RP → co_dedropable_sn (lexs RN RP). @@ -110,11 +109,9 @@ fact lexs_dropable_dx_aux: ∀RN,RP,b,f,L2,K2. ⬇*[b, f] L2 ≘ K2 → 𝐔⦃f ] qed-. -(* Basic_2A1: includes: lpx_sn_dropable *) lemma lexs_co_dropable_dx: ∀RN,RP. co_dropable_dx (lexs RN RP). /2 width=5 by lexs_dropable_dx_aux/ qed-. -(* Basic_2A1: includes: lpx_sn_drop_conf *) (**) lemma lexs_drops_conf_next: ∀RN,RP. ∀f2,L1,L2. L1 ⪤*[RN, RP, f2] L2 → ∀b,f,I1,K1. ⬇*[b, f] L1 ≘ K1.ⓘ{I1} → 𝐔⦃f⦄ → @@ -137,7 +134,6 @@ elim (lexs_co_dropable_sn … HLK1 … Hf … HL12 … Hf2) -L1 -f2 -Hf #I2 #K2 #HK12 #HI12 #H destruct /2 width=5 by ex3_2_intro/ qed-. -(* Basic_2A1: includes: lpx_sn_drop_trans *) lemma lexs_drops_trans_next: ∀RN,RP,f2,L1,L2. L1 ⪤*[RN, RP, f2] L2 → ∀b,f,I2,K2. ⬇*[b, f] L2 ≘ K2.ⓘ{I2} → 𝐔⦃f⦄ → ∀f1. f ~⊚ ↑f1 ≘ f2 → diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/lex.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/lex.ma index 5c76651b2..b1d925a3a 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/relocation/lex.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/lex.ma @@ -12,6 +12,8 @@ (* *) (**************************************************************************) +include "ground_2/pull/pull_2.ma". +include "ground_2/pull/pull_4.ma". include "ground_2/relocation/rtmap_uni.ma". include "basic_2/notation/relations/relation_3.ma". include "basic_2/syntax/cext2.ma". @@ -19,40 +21,65 @@ include "basic_2/relocation/lexs.ma". (* GENERIC EXTENSION OF A CONTEXT-SENSITIVE REALTION FOR TERMS **************) -(* Basic_2A1: includes: lpx_sn_atom lpx_sn_pair *) -definition lex: (lenv → relation term) → relation lenv ≝ - λR,L1,L2. ∃∃f. 𝐈⦃f⦄ & L1 ⪤*[cfull, cext2 R, f] L2. +definition lex (R): relation lenv ≝ + λL1,L2. ∃∃f. 𝐈⦃f⦄ & L1 ⪤*[cfull, cext2 R, f] L2. interpretation "generic extension (local environment)" 'Relation R L1 L2 = (lex R L1 L2). +definition lex_confluent: relation (relation3 …) ≝ λR1,R2. + ∀L0,T0,T1. R1 L0 T0 T1 → ∀T2. R2 L0 T0 T2 → + ∀L1. L0 ⪤[R1] L1 → ∀L2. L0 ⪤[R2] L2 → + ∃∃T. R2 L1 T1 T & R1 L2 T2 T. + +definition lex_transitive: relation (relation3 …) ≝ λR1,R2. + ∀L1,T1,T. R1 L1 T1 T → ∀L2. L1 ⪤[R1] L2 → + ∀T2. R2 L2 T T2 → R1 L1 T1 T2. + (* Basic properties *********************************************************) -lemma lex_bind: ∀R,I1,I2,K1,K2. K1 ⪤[R] K2 → cext2 R K1 I1 I2 → - K1.ⓘ{I1} ⪤[R] K2.ⓘ{I2}. +(* Basic_2A1: was: lpx_sn_atom *) +lemma lex_atom (R): ⋆ ⪤[R] ⋆. +/2 width=3 by lexs_atom, ex2_intro/ qed. + +lemma lex_bind (R): ∀I1,I2,K1,K2. K1 ⪤[R] K2 → cext2 R K1 I1 I2 → + K1.ⓘ{I1} ⪤[R] K2.ⓘ{I2}. #R #I1 #I2 #K1 #K2 * #f #Hf #HK12 #HI12 /3 width=3 by lexs_push, isid_push, ex2_intro/ qed. (* Basic_2A1: was: lpx_sn_refl *) -lemma lex_refl: ∀R. c_reflexive … R → reflexive … (lex R). +lemma lex_refl (R): c_reflexive … R → reflexive … (lex R). /4 width=3 by lexs_refl, ext2_refl, ex2_intro/ qed. +lemma lex_co (R1) (R2): (∀L,T1,T2. R1 L T1 T2 → R2 L T1 T2) → + ∀L1,L2. L1 ⪤[R1] L2 → L1 ⪤[R2] L2. +#R1 #R2 #HR #L1 #L2 * /5 width=7 by lexs_co, cext2_co, ex2_intro/ +qed-. + (* Advanced properties ******************************************************) -lemma lex_bind_refl_dx: ∀R. c_reflexive … R → - ∀I,K1,K2. K1 ⪤[R] K2 → K1.ⓘ{I} ⪤[R] K2.ⓘ{I}. +lemma lex_bind_refl_dx (R): c_reflexive … R → + ∀I,K1,K2. K1 ⪤[R] K2 → K1.ⓘ{I} ⪤[R] K2.ⓘ{I}. /3 width=3 by ext2_refl, lex_bind/ qed. +lemma lex_unit (R): ∀I,K1,K2. K1 ⪤[R] K2 → K1.ⓤ{I} ⪤[R] K2.ⓤ{I}. +/3 width=1 by lex_bind, ext2_unit/ qed. + +(* Basic_2A1: was: lpx_sn_pair *) +lemma lex_pair (R): ∀I,K1,K2,V1,V2. K1 ⪤[R] K2 → R K1 V1 V2 → + K1.ⓑ{I}V1 ⪤[R] K2.ⓑ{I}V2. +/3 width=1 by lex_bind, ext2_pair/ qed. + (* Basic inversion lemmas ***************************************************) (* Basic_2A1: was: lpx_sn_inv_atom1: *) -lemma lex_inv_atom_sn: ∀R,L2. ⋆ ⪤[R] L2 → L2 = ⋆. +lemma lex_inv_atom_sn (R): ∀L2. ⋆ ⪤[R] L2 → L2 = ⋆. #R #L2 * #f #Hf #H >(lexs_inv_atom1 … H) -L2 // qed-. -lemma lex_inv_bind_sn: ∀R,I1,L2,K1. K1.ⓘ{I1} ⪤[R] L2 → - ∃∃I2,K2. K1 ⪤[R] K2 & cext2 R K1 I1 I2 & L2 = K2.ⓘ{I2}. +lemma lex_inv_bind_sn (R): ∀I1,L2,K1. K1.ⓘ{I1} ⪤[R] L2 → + ∃∃I2,K2. K1 ⪤[R] K2 & cext2 R K1 I1 I2 & L2 = K2.ⓘ{I2}. #R #I1 #L2 #K1 * #f #Hf #H lapply (lexs_eq_repl_fwd … H (⫯f) ?) -H /2 width=1 by eq_push_inv_isid/ #H elim (lexs_inv_push1 … H) -H #I2 #K2 #HK12 #HI12 #H destruct @@ -60,12 +87,12 @@ elim (lexs_inv_push1 … H) -H #I2 #K2 #HK12 #HI12 #H destruct qed-. (* Basic_2A1: was: lpx_sn_inv_atom2 *) -lemma lex_inv_atom_dx: ∀R,L1. L1 ⪤[R] ⋆ → L1 = ⋆. +lemma lex_inv_atom_dx (R): ∀L1. L1 ⪤[R] ⋆ → L1 = ⋆. #R #L1 * #f #Hf #H >(lexs_inv_atom2 … H) -L1 // qed-. -lemma lex_inv_bind_dx: ∀R,I2,L1,K2. L1 ⪤[R] K2.ⓘ{I2} → - ∃∃I1,K1. K1 ⪤[R] K2 & cext2 R K1 I1 I2 & L1 = K1.ⓘ{I1}. +lemma lex_inv_bind_dx (R): ∀I2,L1,K2. L1 ⪤[R] K2.ⓘ{I2} → + ∃∃I1,K1. K1 ⪤[R] K2 & cext2 R K1 I1 I2 & L1 = K1.ⓘ{I1}. #R #I2 #L1 #K2 * #f #Hf #H lapply (lexs_eq_repl_fwd … H (⫯f) ?) -H /2 width=1 by eq_push_inv_isid/ #H elim (lexs_inv_push2 … H) -H #I1 #K1 #HK12 #HI12 #H destruct @@ -74,18 +101,34 @@ qed-. (* Advanced inversion lemmas ************************************************) +lemma lex_inv_unit_sn (R): ∀I,L2,K1. K1.ⓤ{I} ⪤[R] L2 → + ∃∃K2. K1 ⪤[R] K2 & L2 = K2.ⓤ{I}. +#R #I #L2 #K1 #H +elim (lex_inv_bind_sn … H) -H #Z2 #K2 #HK12 #HZ2 #H destruct +elim (ext2_inv_unit_sn … HZ2) -HZ2 +/2 width=3 by ex2_intro/ +qed-. + (* Basic_2A1: was: lpx_sn_inv_pair1 *) -lemma lex_inv_pair_sn: ∀R,I,L2,K1,V1. K1.ⓑ{I}V1 ⪤[R] L2 → - ∃∃K2,V2. K1 ⪤[R] K2 & R K1 V1 V2 & L2 = K2.ⓑ{I}V2. +lemma lex_inv_pair_sn (R): ∀I,L2,K1,V1. K1.ⓑ{I}V1 ⪤[R] L2 → + ∃∃K2,V2. K1 ⪤[R] K2 & R K1 V1 V2 & L2 = K2.ⓑ{I}V2. #R #I #L2 #K1 #V1 #H elim (lex_inv_bind_sn … H) -H #Z2 #K2 #HK12 #HZ2 #H destruct elim (ext2_inv_pair_sn … HZ2) -HZ2 #V2 #HV12 #H destruct /2 width=5 by ex3_2_intro/ qed-. +lemma lex_inv_unit_dx (R): ∀I,L1,K2. L1 ⪤[R] K2.ⓤ{I} → + ∃∃K1. K1 ⪤[R] K2 & L1 = K1.ⓤ{I}. +#R #I #L1 #K2 #H +elim (lex_inv_bind_dx … H) -H #Z1 #K1 #HK12 #HZ1 #H destruct +elim (ext2_inv_unit_dx … HZ1) -HZ1 +/2 width=3 by ex2_intro/ +qed-. + (* Basic_2A1: was: lpx_sn_inv_pair2 *) -lemma lex_inv_pair_dx: ∀R,I,L1,K2,V2. L1 ⪤[R] K2.ⓑ{I}V2 → - ∃∃K1,V1. K1 ⪤[R] K2 & R K1 V1 V2 & L1 = K1.ⓑ{I}V1. +lemma lex_inv_pair_dx (R): ∀I,L1,K2,V2. L1 ⪤[R] K2.ⓑ{I}V2 → + ∃∃K1,V1. K1 ⪤[R] K2 & R K1 V1 V2 & L1 = K1.ⓑ{I}V1. #R #I #L1 #K2 #V2 #H elim (lex_inv_bind_dx … H) -H #Z1 #K1 #HK12 #HZ1 #H destruct elim (ext2_inv_pair_dx … HZ1) -HZ1 #V1 #HV12 #H destruct @@ -93,9 +136,27 @@ elim (ext2_inv_pair_dx … HZ1) -HZ1 #V1 #HV12 #H destruct qed-. (* Basic_2A1: was: lpx_sn_inv_pair *) -lemma lex_inv_pair: ∀R,I1,I2,L1,L2,V1,V2. - L1.ⓑ{I1}V1 ⪤[R] L2.ⓑ{I2}V2 → - ∧∧ L1 ⪤[R] L2 & R L1 V1 V2 & I1 = I2. +lemma lex_inv_pair (R): ∀I1,I2,L1,L2,V1,V2. + L1.ⓑ{I1}V1 ⪤[R] L2.ⓑ{I2}V2 → + ∧∧ L1 ⪤[R] L2 & R L1 V1 V2 & I1 = I2. #R #I1 #I2 #L1 #L2 #V1 #V2 #H elim (lex_inv_pair_sn … H) -H #L0 #V0 #HL10 #HV10 #H destruct /2 width=1 by and3_intro/ qed-. + +(* Basic eliminators ********************************************************) + +lemma lex_ind (R) (Q:relation2 …): + Q (⋆) (⋆) → + ( + ∀I,K1,K2. K1 ⪤[R] K2 → Q K1 K2 → Q (K1.ⓤ{I}) (K2.ⓤ{I}) + ) → ( + ∀I,K1,K2,V1,V2. K1 ⪤[R] K2 → Q K1 K2 → R K1 V1 V2 →Q (K1.ⓑ{I}V1) (K2.ⓑ{I}V2) + ) → + ∀L1,L2. L1 ⪤[R] L2 → Q L1 L2. +#R #Q #IH1 #IH2 #IH3 #L1 #L2 * #f @pull_2 #H +elim H -f -L1 -L2 // #f #I1 #I2 #K1 #K2 @pull_4 #H +[ elim (isid_inv_next … H) +| lapply (isid_inv_push … H ??) +] -H [5:|*: // ] #Hf @pull_2 #H +elim H -H /3 width=3 by ex2_intro/ +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/lex_lex.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/lex_lex.ma new file mode 100644 index 000000000..e8b30f23d --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/lex_lex.ma @@ -0,0 +1,52 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/relocation/lex.ma". + +(* GENERIC ENTRYWISE EXTENSION OF CONTEXT-SENSITIVE REALTIONS FOR TERMS *****) + +(* Main properties **********************************************************) + +(* Basic_2A1: was: lpx_sn_trans *) +theorem lex_trans (R): lex_transitive R R → Transitive … (lex R). +#R #HR #L1 #L #H @(lex_ind … H) -L1 -L // +[ #I #K1 #K #HK1 #IH #Y #H + elim (lex_inv_unit_sn … H) -H #K2 #K2 #H destruct + /3 width=1 by lex_unit/ +| #I #K1 #L #V1 #V #HK1 #IH #HV1 #X #H + elim (lex_inv_pair_sn … H) -H #K2 #V2 #HK2 #HV2 #H destruct + /3 width=5 by lex_pair/ +] +qed-. + +(* Basic_2A1: was: lpx_sn_conf *) +theorem lex_conf (R1) (R2): lex_confluent R1 R2 → confluent2 … (lex R1) (lex R2). +#R1 #R2 #HR12 #L0 elim L0 -L0 [| #K0 * ] +[ #Y1 #H1 #Y2 #H2 + >(lex_inv_atom_sn … H1) -Y1 + >(lex_inv_atom_sn … H2) -Y2 + /2 width=3 by lex_atom, ex2_intro/ +| #I #IH #Y1 #H1 #Y2 #H2 + elim (lex_inv_unit_sn … H1) -H1 #K1 #HK01 #H destruct + elim (lex_inv_unit_sn … H2) -H2 #K2 #HK02 #H destruct + elim (IH … HK01 … HK02) -K0 #K #HK1 #HK2 + /3 width=3 by lex_unit, ex2_intro/ +| #I #V0 #IH #Y1 #H1 #Y2 #H2 + elim (lex_inv_pair_sn … H1) -H1 #K1 #V1 #HK01 #HV01 #H destruct + elim (lex_inv_pair_sn … H2) -H2 #K2 #V2 #HK02 #HV02 #H destruct + elim (HR12 … HV01 … HV02 … HK01 … HK02) -V0 #V #HV1 #HV2 + elim (IH … HK01 … HK02) -K0 #K #HK1 #HK2 + /3 width=5 by lex_pair, ex2_intro/ +] +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/relocation/lexs_lexs.ma b/matita/matita/contribs/lambdadelta/basic_2/relocation/lexs_lexs.ma index 545420f3b..20e2f91a2 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/relocation/lexs_lexs.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/relocation/lexs_lexs.ma @@ -45,7 +45,6 @@ theorem lexs_trans_gen (RN1) (RP1) (RN2) (RP2) (RN) (RP): ] qed-. -(* Basic_2A1: includes: lpx_sn_trans *) theorem lexs_trans (RN) (RP) (f): (∀g,I,K. lexs_transitive RN RN RN RN RP g K I) → (∀g,I,K. lexs_transitive RP RP RP RN RP g K I) → Transitive … (lexs RN RP f). @@ -61,7 +60,6 @@ elim (lexs_inv_push1 … H) -H #I2 #K2 #HK2 #_ #H destruct /3 width=1 by lexs_push/ qed-. -(* Basic_2A1: includes: lpx_sn_conf *) theorem lexs_conf (RN1) (RP1) (RN2) (RP2): ∀L,f. (∀g,I,K,n. ⬇*[n] L ≘ K.ⓘ{I} → ↑g = ⫱*[n] f → R_pw_confluent2_lexs RN1 RN2 RN1 RP1 RN2 RP2 g K I) → diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpm_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpm_aaa.ma new file mode 100644 index 000000000..eff341b1d --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpm_aaa.ma @@ -0,0 +1,24 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/rt_transition/cpm_cpx.ma". +include "basic_2/rt_transition/lpx_aaa.ma". + +(* T-BOUND CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS ***************) + +(* Properties with atomic arity assignment for terms ************************) + +(* Basic_2A1: includes: cpr_aaa_conf *) +lemma cpm_aaa_conf (n) (h): ∀G,L. Conf3 … (aaa G L) (cpm h G L n). +/3 width=5 by cpx_aaa_conf, cpm_fwd_cpx/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpm_lsubr.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpm_lsubr.ma index 20385588f..29f43808c 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpm_lsubr.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpm_lsubr.ma @@ -20,6 +20,11 @@ include "basic_2/rt_transition/cpm.ma". (* Properties with restricted refinement for local environments *************) (* Basic_2A1: includes: lsubr_cpr_trans *) -lemma lsubr_cpm_trans: ∀n,h,G. lsub_trans … (λL. cpm h G L n) lsubr. +lemma lsubr_cpm_trans (n) (h) (G): lsub_trans … (λL. cpm h G L n) lsubr. #n #h #G #L1 #T1 #T2 * /3 width=5 by lsubr_cpg_trans, ex2_intro/ qed-. + +lemma cpm_bind_unit (n) (h) (G): ∀L,V1,V2. ⦃G, L⦄ ⊢ V1 ➡[h] V2 → + ∀J,T1,T2. ⦃G, L.ⓤ{J}⦄ ⊢ T1 ➡[n, h] T2 → + ∀p,I. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ➡[n, h] ⓑ{p,I}V2.T2. +/4 width=4 by lsubr_cpm_trans, cpm_bind, lsubr_unit/ qed. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpr_cpr.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpr_cpr.ma new file mode 100644 index 000000000..5b04a00f8 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/cpr_cpr.ma @@ -0,0 +1,23 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/rt_transition/lpr_lpr.ma". + +(* PARALLEL R-TRANSITION FOR FULL LOCAL ENVIRONMENTS ************************) + +(* Main properties **********************************************************) + +(* Basic_1: includes: pr0_confluence pr2_confluence *) +theorem cpr_conf (h) (G) (L): confluent … (cpm h G L 0). +/2 width=6 by cpr_conf_lpr/ qed-. 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 864f8eb99..b11694680 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 @@ -19,12 +19,12 @@ include "basic_2/rt_transition/cpx.ma". (* Properties with restricted refinement for local environments *************) -lemma lsubr_cpx_trans: ∀h,G. lsub_trans … (cpx h G) lsubr. +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/ qed-. -lemma cpx_bind_unit: ∀h,L,G,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 → - ∀J,T1,T2. ⦃G, L.ⓤ{J}⦄ ⊢ T1 ⬈[h] T2 → - ∀p,I. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ⬈[h] ⓑ{p,I}V2.T2. +lemma cpx_bind_unit (h) (G): ∀L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 → + ∀J,T1,T2. ⦃G, L.ⓤ{J}⦄ ⊢ T1 ⬈[h] T2 → + ∀p,I. ⦃G, L⦄ ⊢ ⓑ{p,I}V1.T1 ⬈[h] ⓑ{p,I}V2.T2. /4 width=4 by lsubr_cpx_trans, cpx_bind, lsubr_unit/ qed. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpb.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpb.ma index 39de38ce2..268e45283 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpb.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpb.ma @@ -15,14 +15,14 @@ include "basic_2/notation/relations/predsubtyproper_8.ma". include "basic_2/s_transition/fqu.ma". include "basic_2/static/lfdeq.ma". -include "basic_2/rt_transition/lfpr_lfpx.ma". +include "basic_2/rt_transition/lpr_lpx.ma". (* PROPER PARALLEL RST-TRANSITION FOR CLOSURES ******************************) inductive fpb (h) (o) (G1) (L1) (T1): relation3 genv lenv term ≝ -| fpb_fqu : ∀G2,L2,T2. ⦃G1, L1, T1⦄ ⊐ ⦃G2, L2, T2⦄ → fpb h o G1 L1 T1 G2 L2 T2 -| fpb_cpx : ∀T2. ⦃G1, L1⦄ ⊢ T1 ⬈[h] T2 → (T1 ≛[h, o] T2 → ⊥) → fpb h o G1 L1 T1 G1 L1 T2 -| fpb_lfpx: ∀L2. ⦃G1, L1⦄ ⊢ ⬈[h, T1] L2 → (L1 ≛[h, o, T1] L2 → ⊥) → fpb h o G1 L1 T1 G1 L2 T1 +| fpb_fqu: ∀G2,L2,T2. ⦃G1, L1, T1⦄ ⊐ ⦃G2, L2, T2⦄ → fpb h o G1 L1 T1 G2 L2 T2 +| fpb_cpx: ∀T2. ⦃G1, L1⦄ ⊢ T1 ⬈[h] T2 → (T1 ≛[h, o] T2 → ⊥) → fpb h o G1 L1 T1 G1 L1 T2 +| fpb_lpx: ∀L2. ⦃G1, L1⦄ ⊢ ⬈[h] L2 → (L1 ≛[h, o, T1] L2 → ⊥) → fpb h o G1 L1 T1 G1 L2 T1 . interpretation @@ -32,11 +32,10 @@ interpretation (* Basic properties *********************************************************) (* Basic_2A1: includes: cpr_fpb *) -lemma cpm_fpb: ∀n,h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡[n, h] T2 → (T1 ≛[h, o] T2 → ⊥) → - ⦃G, L, T1⦄ ≻[h, o] ⦃G, L, T2⦄. +lemma cpm_fpb (n) (h) (o) (G) (L): ∀T1,T2. ⦃G, L⦄ ⊢ T1 ➡[n, h] T2 → (T1 ≛[h, o] T2 → ⊥) → + ⦃G, L, T1⦄ ≻[h, o] ⦃G, L, T2⦄. /3 width=2 by fpb_cpx, cpm_fwd_cpx/ qed. -(* Basic_2A1: includes: lpr_fpb *) -lemma lfpr_fpb: ∀h,o,G,L1,L2,T. ⦃G, L1⦄ ⊢ ➡[h, T] L2 → (L1 ≛[h, o, T] L2 → ⊥) → - ⦃G, L1, T⦄ ≻[h, o] ⦃G, L2, T⦄. -/3 width=1 by fpb_lfpx, lfpr_fwd_lfpx/ qed. +lemma lpr_fpb (h) (o) (G) (T): ∀L1,L2. ⦃G, L1⦄ ⊢ ➡[h] L2 → (L1 ≛[h, o, T] L2 → ⊥) → + ⦃G, L1, T⦄ ≻[h, o] ⦃G, L2, T⦄. +/3 width=1 by fpb_lpx, lpr_fwd_lpx/ qed. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpb_lfdeq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpb_lfdeq.ma index b98034aa3..ee1dea03e 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpb_lfdeq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpb_lfdeq.ma @@ -14,7 +14,7 @@ include "basic_2/static/lfdeq_fqus.ma". include "basic_2/rt_transition/cpx_lfdeq.ma". -include "basic_2/rt_transition/lfpx_lfdeq.ma". +include "basic_2/rt_transition/lpx_lfdeq.ma". include "basic_2/rt_transition/fpb.ma". (* PROPER PARALLEL RST-TRANSITION FOR CLOSURES ******************************) @@ -31,7 +31,7 @@ lemma tdeq_fpb_trans: ∀h,o,U2,U1. U2 ≛[h, o] U1 → | #T1 #HUT1 #HnUT1 elim (tdeq_cpx_trans … HU21 … HUT1) -HUT1 /6 width=5 by fpb_cpx, tdeq_canc_sn, tdeq_trans, ex3_2_intro/ -| /6 width=5 by fpb_lfpx, lfpx_tdeq_div, tdeq_lfdeq_conf, ex3_2_intro/ +| /6 width=5 by fpb_lpx, lfpx_tdeq_div, tdeq_lfdeq_conf, ex3_2_intro/ ] qed-. @@ -44,7 +44,7 @@ lemma lfdeq_fpb_trans: ∀h,o,F,K1,K2,T. K1 ≛[h, o, T] K2 → /3 width=5 by fpb_fqu, ex3_2_intro/ | #U #HTU #HnTU elim (lfdeq_cpx_trans … HT … HTU) -HTU /5 width=10 by fpb_cpx, cpx_lfdeq_conf_sn, tdeq_trans, tdeq_lfdeq_conf, ex3_2_intro/ -| #L2 #HKL2 #HnKL2 elim (lfdeq_lfpx_trans … HKL2 … HT) -HKL2 - /6 width=5 by fpb_lfpx, (* 2x *) lfdeq_canc_sn, ex3_2_intro/ +| #L2 #HKL2 #HnKL2 elim (lfdeq_lpx_trans … HKL2 … HT) -HKL2 + /6 width=5 by fpb_lpx, (* 2x *) lfdeq_canc_sn, ex3_2_intro/ ] qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq.ma index 08c3d16db..600d9190a 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq.ma @@ -15,7 +15,7 @@ include "basic_2/notation/relations/predsubty_8.ma". include "basic_2/static/ffdeq.ma". include "basic_2/s_transition/fquq.ma". -include "basic_2/rt_transition/lfpr_lfpx.ma". +include "basic_2/rt_transition/lpr_lpx.ma". (* PARALLEL RST-TRANSITION FOR CLOSURES *************************************) @@ -23,7 +23,7 @@ include "basic_2/rt_transition/lfpr_lfpx.ma". inductive fpbq (h) (o) (G1) (L1) (T1): relation3 genv lenv term ≝ | fpbq_fquq : ∀G2,L2,T2. ⦃G1, L1, T1⦄ ⊐⸮ ⦃G2, L2, T2⦄ → fpbq h o G1 L1 T1 G2 L2 T2 | fpbq_cpx : ∀T2. ⦃G1, L1⦄ ⊢ T1 ⬈[h] T2 → fpbq h o G1 L1 T1 G1 L1 T2 -| fpbq_lfpx : ∀L2. ⦃G1, L1⦄ ⊢ ⬈[h, T1] L2 → fpbq h o G1 L1 T1 G1 L2 T1 +| fpbq_lpx : ∀L2. ⦃G1, L1⦄ ⊢ ⬈[h] L2 → fpbq h o G1 L1 T1 G1 L2 T1 | fpbq_ffdeq: ∀G2,L2,T2. ⦃G1, L1, T1⦄ ≛[h, o] ⦃G2, L2, T2⦄ → fpbq h o G1 L1 T1 G2 L2 T2 . @@ -33,15 +33,15 @@ interpretation (* Basic properties *********************************************************) -lemma fpbq_refl: ∀h,o. tri_reflexive … (fpbq h o). +lemma fpbq_refl (h) (o): tri_reflexive … (fpbq h o). /2 width=1 by fpbq_cpx/ qed. (* Basic_2A1: includes: cpr_fpbq *) -lemma cpm_fpbq: ∀n,h,o,G,L,T1,T2. ⦃G, L⦄ ⊢ T1 ➡[n, h] T2 → ⦃G, L, T1⦄ ≽[h, o] ⦃G, L, T2⦄. +lemma cpm_fpbq (n) (h) (o) (G) (L): ∀T1,T2. ⦃G, L⦄ ⊢ T1 ➡[n, h] T2 → ⦃G, L, T1⦄ ≽[h, o] ⦃G, L, T2⦄. /3 width=2 by fpbq_cpx, cpm_fwd_cpx/ qed. -lemma lfpr_fpbq: ∀h,o,G,L1,L2,T. ⦃G, L1⦄ ⊢ ➡[h, T] L2 → ⦃G, L1, T⦄ ≽[h, o] ⦃G, L2, T⦄. -/3 width=1 by fpbq_lfpx, lfpr_fwd_lfpx/ qed. +lemma lpr_fpbq (h) (o) (G) (T): ∀L1,L2. ⦃G, L1⦄ ⊢ ➡[h] L2 → ⦃G, L1, T⦄ ≽[h, o] ⦃G, L2, T⦄. +/3 width=1 by fpbq_lpx, lpr_fwd_lpx/ qed. (* Basic_2A1: removed theorems 2: fpbq_fpbqa fpbqa_inv_fpbq diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq_aaa.ma index 4330c1852..530e3b8c2 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq_aaa.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq_aaa.ma @@ -14,7 +14,7 @@ include "basic_2/static/aaa_fqus.ma". include "basic_2/static/aaa_ffdeq.ma". -include "basic_2/rt_transition/lfpx_aaa.ma". +include "basic_2/rt_transition/lpx_aaa.ma". include "basic_2/rt_transition/fpbq.ma". (* PARALLEL RST-TRANSITION FOR CLOSURES *************************************) @@ -24,5 +24,5 @@ include "basic_2/rt_transition/fpbq.ma". lemma fpbq_aaa_conf: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ≽[h, o] ⦃G2, L2, T2⦄ → ∀A1. ⦃G1, L1⦄ ⊢ T1 ⁝ A1 → ∃A2. ⦃G2, L2⦄ ⊢ T2 ⁝ A2. #h #o #G1 #G2 #L1 #L2 #T1 #T2 * -G2 -L2 -T2 -/3 width=8 by lfpx_aaa_conf, cpx_aaa_conf, aaa_ffdeq_conf, aaa_fquq_conf, ex_intro/ +/3 width=8 by lpx_aaa_conf, cpx_aaa_conf, aaa_ffdeq_conf, aaa_fquq_conf, ex_intro/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq_fpb.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq_fpb.ma index ac20a6259..6400d582e 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq_fpb.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/fpbq_fpb.ma @@ -22,7 +22,7 @@ include "basic_2/rt_transition/fpbq.ma". lemma fpb_fpbq: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ≻[h, o] ⦃G2, L2, T2⦄ → ⦃G1, L1, T1⦄ ≽[h, o] ⦃G2, L2, T2⦄. #h #o #G1 #G2 #L1 #L2 #T1 #T2 * -G2 -L2 -T2 -/3 width=1 by fpbq_fquq, fpbq_cpx, fpbq_lfpx, fqu_fquq/ +/3 width=1 by fpbq_fquq, fpbq_cpx, fpbq_lpx, fqu_fquq/ qed. (* Basic_2A1: fpb_fpbq_alt *) @@ -42,7 +42,7 @@ lemma fpbq_inv_fpb: ∀h,o,G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ≽[h, o] ⦃G2, | #T2 #H elim (tdeq_dec h o T1 T2) /4 width=1 by fpb_cpx, ffdeq_intro_sn, or_intror, or_introl/ | #L2 elim (lfdeq_dec h o L1 L2 T1) - /4 width=1 by fpb_lfpx, ffdeq_intro_sn, or_intror, or_introl/ + /4 width=1 by fpb_lpx, ffdeq_intro_sn, or_intror, or_introl/ | /2 width=1 by or_introl/ ] qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx.ma index 29cbfe765..4067962d8 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx.ma @@ -16,10 +16,10 @@ include "basic_2/notation/relations/predtysn_5.ma". include "basic_2/static/lfxs.ma". include "basic_2/rt_transition/cpx_ext.ma". -(* UNBOUND PARALLEL RT-TRANSITION FOR LOCAL ENV.S ON REFERRED ENTRIES *******) +(* UNBOUND PARALLEL RT-TRANSITION FOR REFERRED LOCAL ENVIRONMENTS ***********) -definition lfpx: sh → genv → relation3 term lenv lenv ≝ - λh,G. lfxs (cpx h G). +definition lfpx (h) (G): relation3 term lenv lenv ≝ + lfxs (cpx h G). interpretation "unbound parallel rt-transition on referred entries (local environment)" @@ -54,11 +54,9 @@ lemma lfpx_bind_repl_dx: ∀h,I,I1,G,L1,L2,T. (* Basic inversion lemmas ***************************************************) -(* Basic_2A1: uses: lpx_inv_atom1 *) lemma lfpx_inv_atom_sn: ∀h,G,Y2,T. ⦃G, ⋆⦄ ⊢ ⬈[h, T] Y2 → Y2 = ⋆. /2 width=3 by lfxs_inv_atom_sn/ qed-. -(* Basic_2A1: uses: lpx_inv_atom2 *) lemma lfpx_inv_atom_dx: ∀h,G,Y1,T. ⦃G, Y1⦄ ⊢ ⬈[h, T] ⋆ → Y1 = ⋆. /2 width=3 by lfxs_inv_atom_dx/ qed-. @@ -137,7 +135,3 @@ lemma lfpx_fwd_bind_dx: ∀h,p,I,G,L1,L2,V,T. lemma lfpx_fwd_flat_dx: ∀h,I,G,L1,L2,V,T. ⦃G, L1⦄ ⊢ ⬈[h, ⓕ{I}V.T] L2 → ⦃G, L1⦄ ⊢ ⬈[h, T] L2. /2 width=3 by lfxs_fwd_flat_dx/ qed-. - -(* Basic_2A1: removed theorems 3: - lpx_inv_pair1 lpx_inv_pair2 lpx_inv_pair -*) diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fqup.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fqup.ma index ab3d5b2a0..c3de116d0 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fqup.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fqup.ma @@ -15,15 +15,13 @@ include "basic_2/static/lfxs_fqup.ma". include "basic_2/rt_transition/lfpx.ma". -(* UNBOUND PARALLEL RT-TRANSITION FOR LOCAL ENV.S ON REFERRED ENTRIES *******) +(* UNBOUND PARALLEL RT-TRANSITION FOR REFERRED LOCAL ENVIRONMENTS ***********) (* Advanced properties ******************************************************) -(* Basic_2A1: uses: lpx_refl *) lemma lfpx_refl: ∀h,G,T. reflexive … (lfpx h G T). /2 width=1 by lfxs_refl/ qed. -(* Basic_2A1: uses: lpx_pair *) lemma lfpx_pair_refl: ∀h,G,L,V1,V2. ⦃G, L⦄ ⊢ V1 ⬈[h] V2 → ∀I,T. ⦃G, L.ⓑ{I}V1⦄ ⊢ ⬈[h, T] L.ⓑ{I}V2. /2 width=1 by lfxs_pair_refl/ qed. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fsle.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fsle.ma index 047fd37ae..0b7078664 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fsle.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_fsle.ma @@ -17,16 +17,15 @@ include "basic_2/static/lfxs_fsle.ma". include "basic_2/rt_transition/lfpx_length.ma". include "basic_2/rt_transition/lfpx_fqup.ma". -(* UNBOUND CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS ***************) +(* UNBOUND PARALLEL RT-TRANSITION FOR REFERRED LOCAL ENVIRONMENTS ***********) (* Forward lemmas with free variables inclusion for restricted closures *****) (* Note: "⦃L2, T1⦄ ⊆ ⦃L2, T0⦄" does not hold *) (* Note: Take L0 = K0.ⓓ(ⓝW.V), L2 = K0.ⓓW, T0 = #0, T1 = ⬆*[1]V *) (* Note: This invalidates lfpxs_cpx_conf: "∀h,G. s_r_confluent1 … (cpx h G) (lfpxs h G)" *) -(* Basic_2A1: uses: lpx_cpx_frees_trans *) -lemma lfpx_cpx_conf_fsge: ∀h,G,L0,T0,T1. ⦃G, L0⦄ ⊢ T0 ⬈[h] T1 → - ∀L2. ⦃G, L0⦄ ⊢⬈[h, T0] L2 → ⦃L2, T1⦄ ⊆ ⦃L0, T0⦄. +lemma lfpx_cpx_conf_fsge (h) (G): ∀L0,T0,T1. ⦃G, L0⦄ ⊢ T0 ⬈[h] T1 → + ∀L2. ⦃G, L0⦄ ⊢⬈[h, T0] L2 → ⦃L2, T1⦄ ⊆ ⦃L0, T0⦄. #h #G0 #L0 #T0 @(fqup_wf_ind_eq (Ⓕ) … G0 L0 T0) -G0 -L0 -T0 #G #L #T #IH #G0 #L0 * * [ #s #HG #HL #HT #X #HX #Y #HY destruct -IH @@ -110,28 +109,28 @@ lemma lfpx_cpx_conf_fsge: ∀h,G,L0,T0,T1. ⦃G, L0⦄ ⊢ T0 ⬈[h] T1 → ] ] ] -qed. +qed-. -(* Basic_2A1: uses: cpx_frees_trans *) -lemma cpx_fsge_comp: ∀h,G. R_fsge_compatible (cpx h G). -/2 width=4 by lfpx_cpx_conf_fsge/ qed-. - -(* Basic_2A1: uses: lpx_frees_trans *) -lemma lfpx_fsge_comp: ∀h,G. lfxs_fsge_compatible (cpx h G). +lemma lfpx_fsge_comp (h) (G): lfxs_fsge_compatible (cpx h G). /2 width=4 by lfpx_cpx_conf_fsge/ qed-. +(**) (* this section concerns cpx *) (* Properties with generic extension on referred entries ********************) +(* Basic_2A1: uses: cpx_frees_trans *) +lemma cpx_fsge_comp (h) (G): R_fsge_compatible (cpx h G). +/2 width=4 by lfpx_cpx_conf_fsge/ qed-. + (* Note: lemma 1000 *) (* Basic_2A1: uses: cpx_llpx_sn_conf *) -lemma cpx_lfxs_conf: ∀R,h,G. s_r_confluent1 … (cpx h G) (lfxs R). +lemma cpx_lfxs_conf (R) (h) (G): s_r_confluent1 … (cpx h G) (lfxs R). /3 width=3 by fsge_lfxs_trans, cpx_fsge_comp/ qed-. (* Advanced properties ******************************************************) -lemma lfpx_cpx_conf: ∀h,G. s_r_confluent1 … (cpx h G) (lfpx h G). +lemma lfpx_cpx_conf (h) (G): s_r_confluent1 … (cpx h G) (lfpx h G). /2 width=5 by cpx_lfxs_conf/ qed-. -lemma lfpx_cpx_conf_fsge_dx: ∀h,G,L0,T0,T1. ⦃G, L0⦄ ⊢ T0 ⬈[h] T1 → - ∀L2. ⦃G, L0⦄ ⊢⬈[h, T0] L2 → ⦃L2, T1⦄ ⊆ ⦃L0, T1⦄. +lemma lfpx_cpx_conf_fsge_dx (h) (G): ∀L0,T0,T1. ⦃G, L0⦄ ⊢ T0 ⬈[h] T1 → + ∀L2. ⦃G, L0⦄ ⊢⬈[h, T0] L2 → ⦃L2, T1⦄ ⊆ ⦃L0, T1⦄. /3 width=5 by lfpx_cpx_conf, lfpx_fsge_comp/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_length.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_length.ma index 6db77f62e..e88d45eef 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_length.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_length.ma @@ -15,11 +15,10 @@ include "basic_2/static/lfxs_length.ma". include "basic_2/rt_transition/lfpx.ma". -(* UNBOUND PARALLEL RT-TRANSITION FOR LOCAL ENV.S ON REFERRED ENTRIES *******) +(* UNBOUND PARALLEL RT-TRANSITION FOR REFERRED LOCAL ENVIRONMENTS ***********) (* Forward lemmas with length for local environments ************************) -(* Basic_2A1: uses: lpx_fwd_length *) lemma lfpx_fwd_length: ∀h,G,L1,L2,T. ⦃G, L1⦄ ⊢ ⬈[h, T] L2 → |L1| = |L2|. /2 width=3 by lfxs_fwd_length/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lfdeq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lfdeq.ma index 090ec1cbf..668246dd1 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lfdeq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lfdeq.ma @@ -16,7 +16,7 @@ include "basic_2/static/lfdeq_fqup.ma". include "basic_2/static/lfdeq_lfdeq.ma". include "basic_2/rt_transition/lfpx_fsle.ma". -(* UNBOUND PARALLEL RT-TRANSITION FOR LOCAL ENV.S ON REFERRED ENTRIES *******) +(* UNBOUND PARALLEL RT-TRANSITION FOR REFERRED LOCAL ENVIRONMENTS ***********) (* Properties with degree-based equivalence for local environments **********) @@ -159,7 +159,6 @@ qed-. lemma lfpx_lfdeq_conf: ∀h,o,G,T. confluent2 … (lfpx h G T) (lfdeq h o T). /3 width=6 by lfpx_fsge_comp, lfdeq_fsge_comp, cpx_tdeq_conf_lexs, lfxs_conf/ qed-. -(* Basic_2A1: uses: lleq_lpx_trans *) lemma lfdeq_lfpx_trans: ∀h,o,G,T,L2,K2. ⦃G, L2⦄ ⊢ ⬈[h, T] K2 → ∀L1. L1 ≛[h, o, T] L2 → ∃∃K1. ⦃G, L1⦄ ⊢ ⬈[h, T] K1 & K1 ≛[h, o, T] K2. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lfpx.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lfpx.ma index 102ae91db..a96910a0c 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lfpx.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lfpx.ma @@ -15,7 +15,7 @@ include "basic_2/static/lfxs_lfxs.ma". include "basic_2/rt_transition/lfpx.ma". -(* UNBOUND PARALLEL RT-TRANSITION FOR LOCAL ENV.S ON REFERRED ENTRIES *******) +(* UNBOUND PARALLEL RT-TRANSITION FOR REFERRED LOCAL ENVIRONMENTS ***********) (* Main properties **********************************************************) diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lpx.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lpx.ma index 7fa9f9508..7ca9a2f28 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lpx.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lfpx_lpx.ma @@ -16,14 +16,19 @@ include "basic_2/static/lfxs_lex.ma". include "basic_2/rt_transition/lfpx_fsle.ma". include "basic_2/rt_transition/lpx.ma". -(* UNBOUND PARALLEL RT-TRANSITION FOR LOCAL ENV.S ON REFERRED ENTRIES *******) +(* UNBOUND PARALLEL RT-TRANSITION FOR REFERRED LOCAL ENVIRONMENTS ***********) -(* Properties with unbound parallel rt-transition for local environments ****) +(* Properties with syntactic equivalence for referred local environments ****) -lemma lfpx_lpx: ∀h,G,L1,L2,T. ⦃G, L1⦄ ⊢ ⬈[h] L2 → ⦃G, L1⦄ ⊢ ⬈[h, T] L2. +lemma fleq_lfpx (h) (G): ∀L1,L2,T. L1 ≡[T] L2 → ⦃G, L1⦄ ⊢ ⬈[h, T] L2. +/2 width=1 by lfeq_fwd_lfxs/ qed. + +(* Properties with unbound parallel rt-transition for full local envs *******) + +lemma lpx_lfpx: ∀h,G,L1,L2,T. ⦃G, L1⦄ ⊢ ⬈[h] L2 → ⦃G, L1⦄ ⊢ ⬈[h, T] L2. /2 width=1 by lfxs_lex/ qed. -(* Inversion lemmas with unbound parallel rt-transition for local envs ******) +(* Inversion lemmas with unbound parallel rt-transition for full local envs *) lemma lfpx_inv_lpx_lfeq: ∀h,G,L1,L2,T. ⦃G, L1⦄ ⊢ ⬈[h, T] L2 → ∃∃L. ⦃G, L1⦄ ⊢ ⬈[h] L & L ≡[T] L2. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr.ma new file mode 100644 index 000000000..e983823c1 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr.ma @@ -0,0 +1,98 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/notation/relations/predsn_4.ma". +include "basic_2/relocation/lex.ma". +include "basic_2/rt_transition/cpr_ext.ma". + +(* PARALLEL R-TRANSITION FOR FULL LOCAL ENVIRONMENTS ************************) + +definition lpr (h) (G): relation lenv ≝ + lex (λL. cpm h G L 0). + +interpretation + "parallel rt-transition (full local environment)" + 'PRedSn h G L1 L2 = (lpr h G L1 L2). + +(* Basic properties *********************************************************) + +lemma lpr_bind (h) (G): ∀K1,K2. ⦃G, K1⦄ ⊢ ➡[h] K2 → + ∀I1,I2. ⦃G, K1⦄ ⊢ I1 ➡[h] I2 → ⦃G, K1.ⓘ{I1}⦄ ⊢ ➡[h] K2.ⓘ{I2}. +/2 width=1 by lex_bind/ qed. + +(* Note: lemma 250 *) +lemma lpr_refl (h) (G): reflexive … (lpr h G). +/2 width=1 by lex_refl/ qed. + +(* Advanced properties ******************************************************) + +lemma lpr_bind_refl_dx (h) (G): ∀K1,K2. ⦃G, K1⦄ ⊢ ➡[h] K2 → + ∀I. ⦃G, K1.ⓘ{I}⦄ ⊢ ➡[h] K2.ⓘ{I}. +/2 width=1 by lex_bind_refl_dx/ qed. + +lemma lpr_pair (h) (G): ∀K1,K2,V1,V2. ⦃G, K1⦄ ⊢ ➡[h] K2 → ⦃G, K1⦄ ⊢ V1 ➡[h] V2 → + ∀I. ⦃G, K1.ⓑ{I}V1⦄ ⊢ ➡[h] K2.ⓑ{I}V2. +/2 width=1 by lex_pair/ qed. + +(* Basic inversion lemmas ***************************************************) + +(* Basic_2A1: was: lpr_inv_atom1 *) +(* Basic_1: includes: wcpr0_gen_sort *) +lemma lpr_inv_atom_sn (h) (G): ∀L2. ⦃G, ⋆⦄ ⊢ ➡[h] L2 → L2 = ⋆. +/2 width=2 by lex_inv_atom_sn/ qed-. + +lemma lpr_inv_bind_sn (h) (G): ∀I1,L2,K1. ⦃G, K1.ⓘ{I1}⦄ ⊢ ➡[h] L2 → + ∃∃I2,K2. ⦃G, K1⦄ ⊢ ➡[h] K2 & ⦃G, K1⦄ ⊢ I1 ➡[h] I2 & + L2 = K2.ⓘ{I2}. +/2 width=1 by lex_inv_bind_sn/ qed-. + +(* Basic_2A1: was: lpr_inv_atom2 *) +lemma lpr_inv_atom_dx (h) (G): ∀L1. ⦃G, L1⦄ ⊢ ➡[h] ⋆ → L1 = ⋆. +/2 width=2 by lex_inv_atom_dx/ qed-. + +lemma lpr_inv_bind_dx (h) (G): ∀I2,L1,K2. ⦃G, L1⦄ ⊢ ➡[h] K2.ⓘ{I2} → + ∃∃I1,K1. ⦃G, K1⦄ ⊢ ➡[h] K2 & ⦃G, K1⦄ ⊢ I1 ➡[h] I2 & + L1 = K1.ⓘ{I1}. +/2 width=1 by lex_inv_bind_dx/ qed-. + +(* Advanced inversion lemmas ************************************************) + +lemma lpr_inv_unit_sn (h) (G): ∀I,L2,K1. ⦃G, K1.ⓤ{I}⦄ ⊢ ➡[h] L2 → + ∃∃K2. ⦃G, K1⦄ ⊢ ➡[h] K2 & L2 = K2.ⓤ{I}. +/2 width=1 by lex_inv_unit_sn/ qed-. + +(* Basic_2A1: was: lpr_inv_pair1 *) +(* Basic_1: includes: wcpr0_gen_head *) +lemma lpr_inv_pair_sn (h) (G): ∀I,L2,K1,V1. ⦃G, K1.ⓑ{I}V1⦄ ⊢ ➡[h] L2 → + ∃∃K2,V2. ⦃G, K1⦄ ⊢ ➡[h] K2 & ⦃G, K1⦄ ⊢ V1 ➡[h] V2 & + L2 = K2.ⓑ{I}V2. +/2 width=1 by lex_inv_pair_sn/ qed-. + +lemma lpr_inv_unit_dx (h) (G): ∀I,L1,K2. ⦃G, L1⦄ ⊢ ➡[h] K2.ⓤ{I} → + ∃∃K1. ⦃G, K1⦄ ⊢ ➡[h] K2 & L1 = K1.ⓤ{I}. +/2 width=1 by lex_inv_unit_dx/ qed-. + +(* Basic_2A1: was: lpr_inv_pair2 *) +lemma lpr_inv_pair_dx (h) (G): ∀I,L1,K2,V2. ⦃G, L1⦄ ⊢ ➡[h] K2.ⓑ{I}V2 → + ∃∃K1,V1. ⦃G, K1⦄ ⊢ ➡[h] K2 & ⦃G, K1⦄ ⊢ V1 ➡[h] V2 & + L1 = K1.ⓑ{I}V1. +/2 width=1 by lex_inv_pair_dx/ qed-. + +lemma lpr_inv_pair (h) (G): ∀I1,I2,L1,L2,V1,V2. ⦃G, L1.ⓑ{I1}V1⦄ ⊢ ➡[h] L2.ⓑ{I2}V2 → + ∧∧ ⦃G, L1⦄ ⊢ ➡[h] L2 & ⦃G, L1⦄ ⊢ V1 ➡[h] V2 & I1 = I2. +/2 width=1 by lex_inv_pair/ qed-. + +(* Basic_1: removed theorems 3: wcpr0_getl wcpr0_getl_back + pr0_subst1_back +*) diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_aaa.ma new file mode 100644 index 000000000..c051cf6d9 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_aaa.ma @@ -0,0 +1,23 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/rt_transition/lpr_lpx.ma". +include "basic_2/rt_transition/lpx_aaa.ma". + +(* PARALLEL R-TRANSITION FOR FULL LOCAL ENVIRONMENTS ************************) + +(* Properties with atomic arity assignment for terms ************************) + +lemma lpr_aaa_conf (h): ∀G,T. Conf3 … (λL. aaa G L T) (lpr h G). +/3 width=5 by lpx_aaa_conf, lpr_fwd_lpx/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_drops.ma new file mode 100644 index 000000000..2deb80367 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_drops.ma @@ -0,0 +1,37 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/relocation/drops_lex.ma". +include "basic_2/rt_transition/cpm_drops.ma". +include "basic_2/rt_transition/lpr.ma". + +(* PARALLEL R-TRANSITION FOR FULL LOCAL ENVIRONMENTS ************************) + +(* Properties with generic slicing for local environments *******************) + +(* Basic_2A1: was: drop_lpr_trans *) +lemma drops_lpr_trans (h) (G): dedropable_sn (λL. cpm h G L 0). +/3 width=6 by lex_liftable_dedropable_sn, cpm_lifts_sn/ qed-. + +(* Inversion lemmas with generic slicing for local environments *************) + +(* Basic_1: includes: wcpr0_drop *) +(* Basic_2A1: was: lpr_drop_conf *) +lemma lpr_drops_conf (h) (G): dropable_sn (λL. cpm h G L 0). +/2 width=3 by lex_dropable_sn/ qed-. + +(* Basic_1: includes: wcpr0_drop_back *) +(* Basic_2A1: was: lpr_drop_trans_O1 *) +lemma lpr_drops_trans (h) (G): dropable_dx (λL. cpm h G L 0). +/2 width=3 by lex_dropable_dx/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_fquq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_fquq.ma new file mode 100644 index 000000000..70c4f676d --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_fquq.ma @@ -0,0 +1,128 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/s_transition/fquq.ma". +include "basic_2/rt_transition/cpm_drops.ma". +include "basic_2/rt_transition/cpm_lsubr.ma". +include "basic_2/rt_transition/cpr.ma". +include "basic_2/rt_transition/lpr.ma". + +(* PARALLEL R-TRANSITION FOR FULL LOCAL ENVIRONMENTS ************************) + +(* Properties with extended structural successor for closures ***************) + +lemma fqu_cpr_trans_sn (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐[b] ⦃G2, L2, T2⦄ → + ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h] U2 → + ∃∃L,U1. ⦃G1, L1⦄ ⊢ ➡[h] L & ⦃G1, L1⦄ ⊢ T1 ➡[h] U1 & ⦃G1, L, U1⦄ ⊐[b] ⦃G2, L2, U2⦄. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 +[ /3 width=5 by lpr_pair, fqu_lref_O, ex3_2_intro/ +| /3 width=5 by cpr_pair_sn, fqu_pair_sn, ex3_2_intro/ +| /3 width=5 by cpm_bind, fqu_bind_dx, ex3_2_intro/ +| /3 width=5 by cpm_bind_unit, fqu_clear, ex3_2_intro/ +| /3 width=5 by cpr_flat, fqu_flat_dx, ex3_2_intro/ +| #I #G #K #U #T #HUT #U2 #HU2 + elim (cpm_lifts_sn … HU2 (Ⓣ) … (K.ⓘ{I}) … HUT) -U + /3 width=5 by lpr_bind_refl_dx, fqu_drop, drops_refl, drops_drop, ex3_2_intro/ +] +qed-. + +lemma fqu_cpr_trans_dx (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐[b] ⦃G2, L2, T2⦄ → + ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h] U2 → + ∃∃L,U1. ⦃G1, L1⦄ ⊢ ➡[h] L & ⦃G1, L⦄ ⊢ T1 ➡[h] U1 & ⦃G1, L, U1⦄ ⊐[b] ⦃G2, L2, U2⦄. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 +[ /3 width=5 by lpr_pair, fqu_lref_O, ex3_2_intro/ +| /3 width=5 by cpr_pair_sn, fqu_pair_sn, ex3_2_intro/ +| /3 width=5 by cpm_bind, fqu_bind_dx, ex3_2_intro/ +| /3 width=5 by cpm_bind_unit, fqu_clear, ex3_2_intro/ +| /3 width=5 by cpr_flat, fqu_flat_dx, ex3_2_intro/ +| #I #G #K #U #T #HUT #U2 #HU2 + elim (cpm_lifts_sn … HU2 (Ⓣ) … (K.ⓘ{I}) … HUT) -U + /3 width=5 by lpr_bind_refl_dx, fqu_drop, drops_refl, drops_drop, ex3_2_intro/ +] +qed-. + +lemma fqu_lpr_trans (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐[b] ⦃G2, L2, T2⦄ → + ∀K2. ⦃G2, L2⦄ ⊢ ➡[h] K2 → + ∃∃K1,T. ⦃G1, L1⦄ ⊢ ➡[h] K1 & ⦃G1, L1⦄ ⊢ T1 ➡[h] T & ⦃G1, K1, T⦄ ⊐[b] ⦃G2, K2, T2⦄. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 +[ /3 width=5 by lpr_bind_refl_dx, fqu_lref_O, ex3_2_intro/ +| /3 width=5 by cpr_pair_sn, fqu_pair_sn, ex3_2_intro/ +| #p #I #G2 #L2 #V2 #T2 #X #H + elim (lpr_inv_pair_sn … H) -H #K2 #W2 #HLK2 #HVW2 #H destruct + /3 width=5 by cpr_pair_sn, fqu_bind_dx, ex3_2_intro/ +| #p #I #G2 #L2 #V2 #T2 #Hb #X #H + elim (lpr_inv_unit_sn … H) -H #K2 #HLK2 #H destruct + /3 width=5 by cpr_pair_sn, fqu_clear, ex3_2_intro/ +| /3 width=5 by cpr_pair_sn, fqu_flat_dx, ex3_2_intro/ +| /3 width=5 by lpr_bind_refl_dx, fqu_drop, ex3_2_intro/ +] +qed-. + +(* Note: does not hold in Basic_2A1 because it requires cpm *) +(* Note: L1 = K0.ⓛV0 and T1 = #0 require n = 1 *) +lemma lpr_fqu_trans (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐[b] ⦃G2, L2, T2⦄ → + ∀K1. ⦃G1, K1⦄ ⊢ ➡[h] L1 → + ∃∃n,K2,T. ⦃G1, K1⦄ ⊢ T1 ➡[n, h] T & ⦃G1, K1, T⦄ ⊐[b] ⦃G2, K2, T2⦄ & ⦃G2, K2⦄ ⊢ ➡[h] L2 & n ≤ 1. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 +[ * #G #K #V #K1 #H + elim (lpr_inv_pair_dx … H) -H #K0 #V0 #HK0 #HV0 #H destruct + elim (lifts_total V (𝐔❴1❵)) #T #HVT + /3 width=7 by cpm_ell, cpm_delta, fqu_drop, ex4_3_intro/ +| /3 width=7 by cpr_pair_sn, fqu_pair_sn, ex4_3_intro/ +| /3 width=7 by lpr_bind_refl_dx, cpr_pair_sn, fqu_bind_dx, ex4_3_intro/ +| /3 width=7 by lpr_bind_refl_dx, cpr_pair_sn, fqu_clear, ex4_3_intro/ +| /3 width=7 by cpr_pair_sn, fqu_flat_dx, ex4_3_intro/ +| #I #G #K #T #U #HTU #K1 #H + elim (lpr_inv_bind_dx … H) -H #I0 #K0 #HK0 #HI0 #H destruct + /3 width=7 by fqu_drop, ex4_3_intro/ +] +qed-. + +(* Properties with extended optional structural successor for closures ******) + +lemma fquq_cpr_trans_sn (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮[b] ⦃G2, L2, T2⦄ → + ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h] U2 → + ∃∃L,U1. ⦃G1, L1⦄ ⊢ ➡[h] L & ⦃G1, L1⦄ ⊢ T1 ➡[h] U1 & ⦃G1, L, U1⦄ ⊐⸮[b] ⦃G2, L2, U2⦄. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H #U2 #HTU2 cases H -H +[ #HT12 elim (fqu_cpr_trans_sn … HT12 … HTU2) /3 width=5 by fqu_fquq, ex3_2_intro/ +| * #H1 #H2 #H3 destruct /2 width=5 by ex3_2_intro/ +] +qed-. + +lemma fquq_cpr_trans_dx (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮[b] ⦃G2, L2, T2⦄ → + ∀U2. ⦃G2, L2⦄ ⊢ T2 ➡[h] U2 → + ∃∃L,U1. ⦃G1, L1⦄ ⊢ ➡[h] L & ⦃G1, L⦄ ⊢ T1 ➡[h] U1 & ⦃G1, L, U1⦄ ⊐⸮[b] ⦃G2, L2, U2⦄. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H #U2 #HTU2 cases H -H +[ #HT12 elim (fqu_cpr_trans_dx … HT12 … HTU2) /3 width=5 by fqu_fquq, ex3_2_intro/ +| * #H1 #H2 #H3 destruct /2 width=5 by ex3_2_intro/ +] +qed-. + +lemma fquq_lpr_trans (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮[b] ⦃G2, L2, T2⦄ → + ∀K2. ⦃G2, L2⦄ ⊢ ➡[h] K2 → + ∃∃K1,T. ⦃G1, L1⦄ ⊢ ➡[h] K1 & ⦃G1, L1⦄ ⊢ T1 ➡[h] T & ⦃G1, K1, T⦄ ⊐⸮[b] ⦃G2, K2, T2⦄. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H #K2 #HLK2 cases H -H +[ #H12 elim (fqu_lpr_trans … H12 … HLK2) /3 width=5 by fqu_fquq, ex3_2_intro/ +| * #H1 #H2 #H3 destruct /2 width=5 by ex3_2_intro/ +] +qed-. + +lemma lpr_fquq_trans (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮[b] ⦃G2, L2, T2⦄ → + ∀K1. ⦃G1, K1⦄ ⊢ ➡[h] L1 → + ∃∃n,K2,T. ⦃G1, K1⦄ ⊢ T1 ➡[n, h] T & ⦃G1, K1, T⦄ ⊐⸮[b] ⦃G2, K2, T2⦄ & ⦃G2, K2⦄ ⊢ ➡[h] L2 & n ≤ 1. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H #K1 #HKL1 cases H -H +[ #H12 elim (lpr_fqu_trans … H12 … HKL1) -L1 /3 width=7 by fqu_fquq, ex4_3_intro/ +| * #H1 #H2 #H3 destruct /2 width=7 by ex4_3_intro/ +] +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_length.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_length.ma new file mode 100644 index 000000000..a00bda146 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_length.ma @@ -0,0 +1,21 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/relocation/lex_length.ma". +include "basic_2/rt_transition/lpr.ma". + +(* PARALLEL R-TRANSITION FOR FULL LOCAL ENVIRONMENTS ************************) + +lemma lpr_fwd_length (h) (G): ∀L1,L2. ⦃G, L1⦄ ⊢ ➡[h] L2 → |L1| = |L2|. +/2 width=2 by lex_fwd_length/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_lpr.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_lpr.ma new file mode 100644 index 000000000..a4b3e42c3 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_lpr.ma @@ -0,0 +1,362 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/relocation/lex_lex.ma". +include "basic_2/rt_transition/cpm_lsubr.ma". +include "basic_2/rt_transition/cpr.ma". +include "basic_2/rt_transition/cpr_drops.ma". +include "basic_2/rt_transition/lpr_drops.ma". + +(* PARALLEL R-TRANSITION FOR FULL LOCAL ENVIRONMENTS ************************) + +(* Main properties with context-sensitive parallel reduction for terms ******) + +fact cpr_conf_lpr_atom_atom (h): + ∀I,G,L1,L2. ∃∃T. ⦃G, L1⦄ ⊢ ⓪{I} ➡[h] T & ⦃G, L2⦄ ⊢ ⓪{I} ➡[h] T. +/2 width=3 by cpr_refl, ex2_intro/ qed-. + +fact cpr_conf_lpr_atom_delta (h): + ∀G,L0,i. ( + ∀L,T. ⦃G, L0, #i⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀K0,V0. ⬇*[i] L0 ≘ K0.ⓓV0 → + ∀V2. ⦃G, K0⦄ ⊢ V0 ➡[h] V2 → ∀T2. ⬆*[↑i] V2 ≘ T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ #i ➡[h] T & ⦃G, L2⦄ ⊢ T2 ➡[h] T. +#h #G0 #L0 #i #IH #K0 #V0 #HLK0 #V2 #HV02 #T2 #HVT2 #L1 #HL01 #L2 #HL02 +elim (lpr_drops_conf … HLK0 … HL01) -HL01 // #X1 #H1 #HLK1 +elim (lpr_inv_pair_sn … H1) -H1 #K1 #V1 #HK01 #HV01 #H destruct +elim (lpr_drops_conf … HLK0 … HL02) -HL02 // #X2 #H2 #HLK2 +elim (lpr_inv_pair_sn … H2) -H2 #K2 #W2 #HK02 #_ #H destruct +lapply (drops_isuni_fwd_drop2 … HLK2) -W2 // #HLK2 +lapply (fqup_lref (Ⓣ) … G0 … HLK0) -HLK0 #HLK0 +elim (IH … HLK0 … HV01 … HV02 … HK01 … HK02) -L0 -K0 -V0 #V #HV1 #HV2 +elim (cpm_lifts_sn … HV2 … HLK2 … HVT2) -V2 -HLK2 #T #HVT #HT2 +/3 width=6 by cpm_delta_drops, ex2_intro/ +qed-. + +(* Basic_1: includes: pr0_delta_delta pr2_delta_delta *) +fact cpr_conf_lpr_delta_delta (h): + ∀G,L0,i. ( + ∀L,T. ⦃G, L0, #i⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀K0,V0. ⬇*[i] L0 ≘ K0.ⓓV0 → + ∀V1. ⦃G, K0⦄ ⊢ V0 ➡[h] V1 → ∀T1. ⬆*[↑i] V1 ≘ T1 → + ∀KX,VX. ⬇*[i] L0 ≘ KX.ⓓVX → + ∀V2. ⦃G, KX⦄ ⊢ VX ➡[h] V2 → ∀T2. ⬆*[↑i] V2 ≘ T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ T1 ➡[h] T & ⦃G, L2⦄ ⊢ T2 ➡[h] T. +#h #G0 #L0 #i #IH #K0 #V0 #HLK0 #V1 #HV01 #T1 #HVT1 +#KX #VX #H #V2 #HV02 #T2 #HVT2 #L1 #HL01 #L2 #HL02 +lapply (drops_mono … H … HLK0) -H #H destruct +elim (lpr_drops_conf … HLK0 … HL01) -HL01 // #X1 #H1 #HLK1 +elim (lpr_inv_pair_sn … H1) -H1 #K1 #W1 #HK01 #_ #H destruct +lapply (drops_isuni_fwd_drop2 … HLK1) -W1 // #HLK1 +elim (lpr_drops_conf … HLK0 … HL02) -HL02 // #X2 #H2 #HLK2 +elim (lpr_inv_pair_sn … H2) -H2 #K2 #W2 #HK02 #_ #H destruct +lapply (drops_isuni_fwd_drop2 … HLK2) -W2 // #HLK2 +lapply (fqup_lref (Ⓣ) … G0 … HLK0) -HLK0 #HLK0 +elim (IH … HLK0 … HV01 … HV02 … HK01 … HK02) -L0 -K0 -V0 #V #HV1 #HV2 +elim (cpm_lifts_sn … HV1 … HLK1 … HVT1) -V1 -HLK1 #T #HVT #HT1 +/3 width=11 by cpm_lifts_bi, ex2_intro/ +qed-. + +fact cpr_conf_lpr_bind_bind (h): + ∀p,I,G,L0,V0,T0. ( + ∀L,T. ⦃G, L0, ⓑ{p,I}V0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀V1. ⦃G, L0⦄ ⊢ V0 ➡[h] V1 → ∀T1. ⦃G, L0.ⓑ{I}V0⦄ ⊢ T0 ➡[h] T1 → + ∀V2. ⦃G, L0⦄ ⊢ V0 ➡[h] V2 → ∀T2. ⦃G, L0.ⓑ{I}V0⦄ ⊢ T0 ➡[h] T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ ⓑ{p,I}V1.T1 ➡[h] T & ⦃G, L2⦄ ⊢ ⓑ{p,I}V2.T2 ➡[h] T. +#h #p #I #G0 #L0 #V0 #T0 #IH #V1 #HV01 #T1 #HT01 +#V2 #HV02 #T2 #HT02 #L1 #HL01 #L2 #HL02 +elim (IH … HV01 … HV02 … HL01 … HL02) // +elim (IH … HT01 … HT02 (L1.ⓑ{I}V1) … (L2.ⓑ{I}V2)) -IH +/3 width=5 by lpr_pair, cpm_bind, ex2_intro/ +qed-. + +fact cpr_conf_lpr_bind_zeta (h): + ∀G,L0,V0,T0. ( + ∀L,T. ⦃G, L0, +ⓓV0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀V1. ⦃G, L0⦄ ⊢ V0 ➡[h] V1 → ∀T1. ⦃G, L0.ⓓV0⦄ ⊢ T0 ➡[h] T1 → + ∀T2. ⦃G, L0.ⓓV0⦄ ⊢ T0 ➡[h] T2 → ∀X2. ⬆*[1] X2 ≘ T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ +ⓓV1.T1 ➡[h] T & ⦃G, L2⦄ ⊢ X2 ➡[h] T. +#h #G0 #L0 #V0 #T0 #IH #V1 #HV01 #T1 #HT01 +#T2 #HT02 #X2 #HXT2 #L1 #HL01 #L2 #HL02 +elim (IH … HT01 … HT02 (L1.ⓓV1) … (L2.ⓓV1)) -IH -HT01 -HT02 /2 width=1 by lpr_pair/ -L0 -V0 -T0 #T #HT1 #HT2 +elim (cpm_inv_lifts_sn … HT2 (Ⓣ) … L2 … HXT2) -T2 +/3 width=3 by cpm_zeta, drops_refl, drops_drop, ex2_intro/ +qed-. + +fact cpr_conf_lpr_zeta_zeta (h): + ∀G,L0,V0,T0. ( + ∀L,T. ⦃G, L0, +ⓓV0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀T1. ⦃G, L0.ⓓV0⦄ ⊢ T0 ➡[h] T1 → ∀X1. ⬆*[1] X1 ≘ T1 → + ∀T2. ⦃G, L0.ⓓV0⦄ ⊢ T0 ➡[h] T2 → ∀X2. ⬆*[1] X2 ≘ T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ X1 ➡[h] T & ⦃G, L2⦄ ⊢ X2 ➡[h] T. +#h #G0 #L0 #V0 #T0 #IH #T1 #HT01 #X1 #HXT1 +#T2 #HT02 #X2 #HXT2 #L1 #HL01 #L2 #HL02 +elim (IH … HT01 … HT02 (L1.ⓓV0) … (L2.ⓓV0)) -IH -HT01 -HT02 /2 width=1 by lpr_pair/ -L0 -T0 #T #HT1 #HT2 +elim (cpm_inv_lifts_sn … HT1 (Ⓣ) … L1 … HXT1) -T1 /3 width=2 by drops_refl, drops_drop/ #T1 #HT1 #HXT1 +elim (cpm_inv_lifts_sn … HT2 (Ⓣ) … L2 … HXT2) -T2 /3 width=2 by drops_refl, drops_drop/ #T2 #HT2 #HXT2 +lapply (lifts_inj … HT2 … HT1) -T #H destruct +/2 width=3 by ex2_intro/ +qed-. + +fact cpr_conf_lpr_flat_flat (h): + ∀I,G,L0,V0,T0. ( + ∀L,T. ⦃G, L0, ⓕ{I}V0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀V1. ⦃G, L0⦄ ⊢ V0 ➡[h] V1 → ∀T1. ⦃G, L0⦄ ⊢ T0 ➡[h] T1 → + ∀V2. ⦃G, L0⦄ ⊢ V0 ➡[h] V2 → ∀T2. ⦃G, L0⦄ ⊢ T0 ➡[h] T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ ⓕ{I}V1.T1 ➡[h] T & ⦃G, L2⦄ ⊢ ⓕ{I}V2.T2 ➡[h] T. +#h #I #G0 #L0 #V0 #T0 #IH #V1 #HV01 #T1 #HT01 +#V2 #HV02 #T2 #HT02 #L1 #HL01 #L2 #HL02 +elim (IH … HV01 … HV02 … HL01 … HL02) // +elim (IH … HT01 … HT02 … HL01 … HL02) // +/3 width=5 by cpr_flat, ex2_intro/ +qed-. + +fact cpr_conf_lpr_flat_eps (h): + ∀G,L0,V0,T0. ( + ∀L,T. ⦃G, L0, ⓝV0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀V1,T1. ⦃G, L0⦄ ⊢ T0 ➡[h] T1 → ∀T2. ⦃G, L0⦄ ⊢ T0 ➡[h] T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ ⓝV1.T1 ➡[h] T & ⦃G, L2⦄ ⊢ T2 ➡[h] T. +#h #G0 #L0 #V0 #T0 #IH #V1 #T1 #HT01 +#T2 #HT02 #L1 #HL01 #L2 #HL02 +elim (IH … HT01 … HT02 … HL01 … HL02) // -L0 -V0 -T0 +/3 width=3 by cpm_eps, ex2_intro/ +qed-. + +fact cpr_conf_lpr_eps_eps (h): + ∀G,L0,V0,T0. ( + ∀L,T. ⦃G, L0, ⓝV0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀T1. ⦃G, L0⦄ ⊢ T0 ➡[h] T1 → ∀T2. ⦃G, L0⦄ ⊢ T0 ➡[h] T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ T1 ➡[h] T & ⦃G, L2⦄ ⊢ T2 ➡[h] T. +#h #G0 #L0 #V0 #T0 #IH #T1 #HT01 +#T2 #HT02 #L1 #HL01 #L2 #HL02 +elim (IH … HT01 … HT02 … HL01 … HL02) // -L0 -V0 -T0 +/2 width=3 by ex2_intro/ +qed-. + +fact cpr_conf_lpr_flat_beta (h): + ∀p,G,L0,V0,W0,T0. ( + ∀L,T. ⦃G, L0, ⓐV0.ⓛ{p}W0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀V1. ⦃G, L0⦄ ⊢ V0 ➡[h] V1 → ∀T1. ⦃G, L0⦄ ⊢ ⓛ{p}W0.T0 ➡[h] T1 → + ∀V2. ⦃G, L0⦄ ⊢ V0 ➡[h] V2 → ∀W2. ⦃G, L0⦄ ⊢ W0 ➡[h] W2 → ∀T2. ⦃G, L0.ⓛW0⦄ ⊢ T0 ➡[h] T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ ⓐV1.T1 ➡[h] T & ⦃G, L2⦄ ⊢ ⓓ{p}ⓝW2.V2.T2 ➡[h] T. +#h #p #G0 #L0 #V0 #W0 #T0 #IH #V1 #HV01 #X #H +#V2 #HV02 #W2 #HW02 #T2 #HT02 #L1 #HL01 #L2 #HL02 +elim (cpm_inv_abst1 … H) -H #W1 #T1 #HW01 #HT01 #H destruct +elim (IH … HV01 … HV02 … HL01 … HL02) -HV01 -HV02 /2 width=1 by/ #V #HV1 #HV2 +elim (IH … HW01 … HW02 … HL01 … HL02) /2 width=1 by/ #W #HW1 #HW2 +elim (IH … HT01 … HT02 (L1.ⓛW1) … (L2.ⓛW2)) /2 width=1 by lpr_pair/ -L0 -V0 -W0 -T0 #T #HT1 #HT2 +lapply (lsubr_cpm_trans … HT2 (L2.ⓓⓝW2.V2) ?) -HT2 /2 width=1 by lsubr_beta/ (**) (* full auto not tried *) +/4 width=5 by cpm_bind, cpr_flat, cpm_beta, ex2_intro/ +qed-. + +(* Basic-1: includes: + pr0_cong_upsilon_refl pr0_cong_upsilon_zeta + pr0_cong_upsilon_cong pr0_cong_upsilon_delta +*) +fact cpr_conf_lpr_flat_theta (h): + ∀p,G,L0,V0,W0,T0. ( + ∀L,T. ⦃G, L0, ⓐV0.ⓓ{p}W0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀V1. ⦃G, L0⦄ ⊢ V0 ➡[h] V1 → ∀T1. ⦃G, L0⦄ ⊢ ⓓ{p}W0.T0 ➡[h] T1 → + ∀V2. ⦃G, L0⦄ ⊢ V0 ➡[h] V2 → ∀U2. ⬆*[1] V2 ≘ U2 → + ∀W2. ⦃G, L0⦄ ⊢ W0 ➡[h] W2 → ∀T2. ⦃G, L0.ⓓW0⦄ ⊢ T0 ➡[h] T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ ⓐV1.T1 ➡[h] T & ⦃G, L2⦄ ⊢ ⓓ{p}W2.ⓐU2.T2 ➡[h] T. +#h #p #G0 #L0 #V0 #W0 #T0 #IH #V1 #HV01 #X #H +#V2 #HV02 #U2 #HVU2 #W2 #HW02 #T2 #HT02 #L1 #HL01 #L2 #HL02 +elim (IH … HV01 … HV02 … HL01 … HL02) -HV01 -HV02 /2 width=1 by/ #V #HV1 #HV2 +elim (cpm_lifts_sn … HV2 (Ⓣ) … (L2.ⓓW2) … HVU2) -HVU2 /3 width=2 by drops_refl, drops_drop/ #U #HVU #HU2 +elim (cpm_inv_abbr1 … H) -H * +[ #W1 #T1 #HW01 #HT01 #H destruct + elim (IH … HW01 … HW02 … HL01 … HL02) /2 width=1 by/ + elim (IH … HT01 … HT02 (L1.ⓓW1) … (L2.ⓓW2)) /2 width=1 by lpr_pair/ -L0 -V0 -W0 -T0 + /4 width=7 by cpm_bind, cpm_appl, cpm_theta, ex2_intro/ +| #T1 #HT01 #HXT1 #H destruct + elim (IH … HT01 … HT02 (L1.ⓓW2) … (L2.ⓓW2)) /2 width=1 by lpr_pair/ -L0 -V0 -W0 -T0 #T #HT1 #HT2 + elim (cpm_inv_lifts_sn … HT1 (Ⓣ) … L1 … HXT1) -HXT1 /3 width=2 by drops_refl, drops_drop/ + /4 width=9 by cpm_appl, cpm_zeta, lifts_flat, ex2_intro/ +] +qed-. + +fact cpr_conf_lpr_beta_beta (h): + ∀p,G,L0,V0,W0,T0. ( + ∀L,T. ⦃G, L0, ⓐV0.ⓛ{p}W0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀V1. ⦃G, L0⦄ ⊢ V0 ➡[h] V1 → ∀W1. ⦃G, L0⦄ ⊢ W0 ➡[h] W1 → ∀T1. ⦃G, L0.ⓛW0⦄ ⊢ T0 ➡[h] T1 → + ∀V2. ⦃G, L0⦄ ⊢ V0 ➡[h] V2 → ∀W2. ⦃G, L0⦄ ⊢ W0 ➡[h] W2 → ∀T2. ⦃G, L0.ⓛW0⦄ ⊢ T0 ➡[h] T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ ⓓ{p}ⓝW1.V1.T1 ➡[h] T & ⦃G, L2⦄ ⊢ ⓓ{p}ⓝW2.V2.T2 ➡[h] T. +#h #p #G0 #L0 #V0 #W0 #T0 #IH #V1 #HV01 #W1 #HW01 #T1 #HT01 +#V2 #HV02 #W2 #HW02 #T2 #HT02 #L1 #HL01 #L2 #HL02 +elim (IH … HV01 … HV02 … HL01 … HL02) -HV01 -HV02 /2 width=1 by/ #V #HV1 #HV2 +elim (IH … HW01 … HW02 … HL01 … HL02) /2 width=1 by/ #W #HW1 #HW2 +elim (IH … HT01 … HT02 (L1.ⓛW1) … (L2.ⓛW2)) /2 width=1 by lpr_pair/ -L0 -V0 -W0 -T0 #T #HT1 #HT2 +lapply (lsubr_cpm_trans … HT1 (L1.ⓓⓝW1.V1) ?) -HT1 /2 width=1 by lsubr_beta/ +lapply (lsubr_cpm_trans … HT2 (L2.ⓓⓝW2.V2) ?) -HT2 /2 width=1 by lsubr_beta/ +/4 width=5 by cpm_bind, cpr_flat, ex2_intro/ (**) (* full auto not tried *) +qed-. + +(* Basic_1: was: pr0_upsilon_upsilon *) +fact cpr_conf_lpr_theta_theta (h): + ∀p,G,L0,V0,W0,T0. ( + ∀L,T. ⦃G, L0, ⓐV0.ⓓ{p}W0.T0⦄ ⊐+ ⦃G, L, T⦄ → + ∀T1. ⦃G, L⦄ ⊢ T ➡[h] T1 → ∀T2. ⦃G, L⦄ ⊢ T ➡[h] T2 → + ∀L1. ⦃G, L⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L⦄ ⊢ ➡[h] L2 → + ∃∃T0. ⦃G, L1⦄ ⊢ T1 ➡[h] T0 & ⦃G, L2⦄ ⊢ T2 ➡[h] T0 + ) → + ∀V1. ⦃G, L0⦄ ⊢ V0 ➡[h] V1 → ∀U1. ⬆*[1] V1 ≘ U1 → + ∀W1. ⦃G, L0⦄ ⊢ W0 ➡[h] W1 → ∀T1. ⦃G, L0.ⓓW0⦄ ⊢ T0 ➡[h] T1 → + ∀V2. ⦃G, L0⦄ ⊢ V0 ➡[h] V2 → ∀U2. ⬆*[1] V2 ≘ U2 → + ∀W2. ⦃G, L0⦄ ⊢ W0 ➡[h] W2 → ∀T2. ⦃G, L0.ⓓW0⦄ ⊢ T0 ➡[h] T2 → + ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → ∀L2. ⦃G, L0⦄ ⊢ ➡[h] L2 → + ∃∃T. ⦃G, L1⦄ ⊢ ⓓ{p}W1.ⓐU1.T1 ➡[h] T & ⦃G, L2⦄ ⊢ ⓓ{p}W2.ⓐU2.T2 ➡[h] T. +#h #p #G0 #L0 #V0 #W0 #T0 #IH #V1 #HV01 #U1 #HVU1 #W1 #HW01 #T1 #HT01 +#V2 #HV02 #U2 #HVU2 #W2 #HW02 #T2 #HT02 #L1 #HL01 #L2 #HL02 +elim (IH … HV01 … HV02 … HL01 … HL02) -HV01 -HV02 /2 width=1 by/ #V #HV1 #HV2 +elim (IH … HW01 … HW02 … HL01 … HL02) /2 width=1 by/ #W #HW1 #HW2 +elim (IH … HT01 … HT02 (L1.ⓓW1) … (L2.ⓓW2)) /2 width=1 by lpr_pair/ -L0 -V0 -W0 -T0 +elim (cpm_lifts_sn … HV1 (Ⓣ) … (L1.ⓓW1) … HVU1) -HVU1 /3 width=2 by drops_refl, drops_drop/ #U #HVU #HU1 +lapply (cpm_lifts_bi … HV2 (Ⓣ) … (L2.ⓓW2) … HVU2 … HVU) -HVU2 /3 width=2 by drops_refl, drops_drop/ +/4 width=7 by cpm_bind, cpm_appl, ex2_intro/ (**) (* full auto not tried *) +qed-. + +theorem cpr_conf_lpr (h): ∀G. lex_confluent (λL.cpm h G L 0) (λL.cpm h G L 0). +#h #G0 #L0 #T0 @(fqup_wf_ind_eq (Ⓣ) … G0 L0 T0) -G0 -L0 -T0 +#G #L #T #IH #G0 #L0 * [| * ] +[ #I0 #HG #HL #HT #T1 #H1 #T2 #H2 #L1 #HL01 #L2 #HL02 destruct + elim (cpr_inv_atom1_drops … H1) -H1 + elim (cpr_inv_atom1_drops … H2) -H2 + [ #H2 #H1 destruct + /2 width=1 by cpr_conf_lpr_atom_atom/ + | * #K0 #V0 #V2 #i2 #HLK0 #HV02 #HVT2 #H2 #H1 destruct + /3 width=10 by cpr_conf_lpr_atom_delta/ + | #H2 * #K0 #V0 #V1 #i1 #HLK0 #HV01 #HVT1 #H1 destruct + /4 width=10 by ex2_commute, cpr_conf_lpr_atom_delta/ + | * #X #Y #V2 #z #H #HV02 #HVT2 #H2 + * #K0 #V0 #V1 #i #HLK0 #HV01 #HVT1 #H1 destruct + /3 width=17 by cpr_conf_lpr_delta_delta/ + ] +| #p #I #V0 #T0 #HG #HL #HT #X1 #H1 #X2 #H2 #L1 #HL01 #L2 #HL02 destruct + elim (cpm_inv_bind1 … H1) -H1 * + [ #V1 #T1 #HV01 #HT01 #H1 + | #T1 #HT01 #HXT1 #H11 #H12 + ] + elim (cpm_inv_bind1 … H2) -H2 * + [1,3: #V2 #T2 #HV02 #HT02 #H2 + |2,4: #T2 #HT02 #HXT2 #H21 #H22 + ] destruct + [ /3 width=10 by cpr_conf_lpr_bind_bind/ + | /4 width=11 by ex2_commute, cpr_conf_lpr_bind_zeta/ + | /3 width=11 by cpr_conf_lpr_bind_zeta/ + | /3 width=12 by cpr_conf_lpr_zeta_zeta/ + ] +| #I #V0 #T0 #HG #HL #HT #X1 #H1 #X2 #H2 #L1 #HL01 #L2 #HL02 destruct + elim (cpr_inv_flat1 … H1) -H1 * + [ #V1 #T1 #HV01 #HT01 #H1 + | #HX1 #H1 + | #p1 #V1 #Y1 #W1 #Z1 #T1 #HV01 #HYW1 #HZT1 #H11 #H12 #H13 + | #p1 #V1 #U1 #Y1 #W1 #Z1 #T1 #HV01 #HVU1 #HYW1 #HZT1 #H11 #H12 #H13 + ] + elim (cpr_inv_flat1 … H2) -H2 * + [1,5,9,13: #V2 #T2 #HV02 #HT02 #H2 + |2,6,10,14: #HX2 #H2 + |3,7,11,15: #p2 #V2 #Y2 #W2 #Z2 #T2 #HV02 #HYW2 #HZT2 #H21 #H22 #H23 + |4,8,12,16: #p2 #V2 #U2 #Y2 #W2 #Z2 #T2 #HV02 #HVU2 #HYW2 #HZT2 #H21 #H22 #H23 + ] destruct + [ /3 width=10 by cpr_conf_lpr_flat_flat/ + | /4 width=8 by ex2_commute, cpr_conf_lpr_flat_eps/ + | /4 width=12 by ex2_commute, cpr_conf_lpr_flat_beta/ + | /4 width=14 by ex2_commute, cpr_conf_lpr_flat_theta/ + | /3 width=8 by cpr_conf_lpr_flat_eps/ + | /3 width=7 by cpr_conf_lpr_eps_eps/ + | /3 width=12 by cpr_conf_lpr_flat_beta/ + | /3 width=13 by cpr_conf_lpr_beta_beta/ + | /3 width=14 by cpr_conf_lpr_flat_theta/ + | /3 width=17 by cpr_conf_lpr_theta_theta/ + ] +] +qed-. + +(* Properties with context-sensitive parallel reduction for terms ***********) + +lemma lpr_cpr_conf_dx (h) (G): ∀L0. ∀T0,T1:term. ⦃G, L0⦄ ⊢ T0 ➡[h] T1 → ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → + ∃∃T. ⦃G, L1⦄ ⊢ T0 ➡[h] T & ⦃G, L1⦄ ⊢ T1 ➡[h] T. +#h #G #L0 #T0 #T1 #HT01 #L1 #HL01 +elim (cpr_conf_lpr … HT01 T0 … HL01 … HL01) -HT01 -HL01 +/2 width=3 by ex2_intro/ +qed-. + +lemma lpr_cpr_conf_sn (h) (G): ∀L0. ∀T0,T1:term. ⦃G, L0⦄ ⊢ T0 ➡[h] T1 → ∀L1. ⦃G, L0⦄ ⊢ ➡[h] L1 → + ∃∃T. ⦃G, L1⦄ ⊢ T0 ➡[h] T & ⦃G, L0⦄ ⊢ T1 ➡[h] T. +#h #G #L0 #T0 #T1 #HT01 #L1 #HL01 +elim (cpr_conf_lpr … HT01 T0 … L0 … HL01) -HT01 -HL01 +/2 width=3 by ex2_intro/ +qed-. + +(* Main properties **********************************************************) + +theorem lpr_conf (h) (G): confluent … (lpr h G). +/3 width=6 by lex_conf, cpr_conf_lpr/ +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_lpx.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_lpx.ma new file mode 100644 index 000000000..484ae046f --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpr_lpx.ma @@ -0,0 +1,25 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/rt_transition/lpx.ma". +include "basic_2/rt_transition/cpm_cpx.ma". +include "basic_2/rt_transition/lpr.ma". + +(* PARALLEL R-TRANSITION FOR FULL LOCAL ENVIRONMENTS ************************) + +(* Forward lemmas with unbound parallel rt-transition for ref local envs ****) + +(* Basic_2A1: was: lpr_lpx *) +lemma lpr_fwd_lpx (h) (G): ∀L1,L2. ⦃G, L1⦄ ⊢ ➡[h] L2 → ⦃G, L1⦄ ⊢ ⬈[h] L2. +/3 width=3 by cpm_fwd_cpx, lex_co/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx.ma index 96305c55b..db127642d 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx.ma @@ -16,68 +16,76 @@ include "basic_2/notation/relations/predtysn_4.ma". include "basic_2/relocation/lex.ma". include "basic_2/rt_transition/cpx_ext.ma". -(* UNBOUND PARALLEL RT-TRANSITION FOR LOCAL ENVIRONMENTS ********************) +(* UNBOUND PARALLEL RT-TRANSITION FOR FULL LOCAL ENVIRONMENTS ***************) -definition lpx: sh → genv → relation lenv ≝ - λh,G. lex (cpx h G). +definition lpx (h) (G): relation lenv ≝ + lex (cpx h G). interpretation - "unbound parallel rt-transition (local environment)" + "unbound parallel rt-transition on all entries (local environment)" 'PRedTySn h G L1 L2 = (lpx h G L1 L2). (* Basic properties *********************************************************) -lemma lpx_bind: ∀h,G,K1,K2. ⦃G, K1⦄ ⊢ ⬈[h] K2 → - ∀I1,I2. ⦃G, K1⦄ ⊢ I1 ⬈[h] I2 → ⦃G, K1.ⓘ{I1}⦄ ⊢ ⬈[h] K2.ⓘ{I2}. +lemma lpx_bind (h) (G): ∀K1,K2. ⦃G, K1⦄ ⊢ ⬈[h] K2 → + ∀I1,I2. ⦃G, K1⦄ ⊢ I1 ⬈[h] I2 → ⦃G, K1.ⓘ{I1}⦄ ⊢ ⬈[h] K2.ⓘ{I2}. /2 width=1 by lex_bind/ qed. -lemma lpx_refl: ∀h,G. reflexive … (lpx h G). +lemma lpx_refl (h) (G): reflexive … (lpx h G). /2 width=1 by lex_refl/ qed. (* Advanced properties ******************************************************) -lemma lpx_bind_refl_dx: ∀h,G,K1,K2. ⦃G, K1⦄ ⊢ ⬈[h] K2 → - ∀I. ⦃G, K1.ⓘ{I}⦄ ⊢ ⬈[h] K2.ⓘ{I}. +lemma lpx_bind_refl_dx (h) (G): ∀K1,K2. ⦃G, K1⦄ ⊢ ⬈[h] K2 → + ∀I. ⦃G, K1.ⓘ{I}⦄ ⊢ ⬈[h] K2.ⓘ{I}. /2 width=1 by lex_bind_refl_dx/ qed. -(* -lemma lpx_pair: ∀h,g,I,G,K1,K2,V1,V2. ⦃G, K1⦄ ⊢ ⬈[h] K2 → ⦃G, K1⦄ ⊢ V1 ⬈[h] V2 → - ⦃G, K1.ⓑ{I}V1⦄ ⊢ ⬈[h] K2.ⓑ{I}V2. -/2 width=1 by lpx_sn_pair/ qed. -*) + +lemma lpx_pair (h) (G): ∀K1,K2. ⦃G, K1⦄ ⊢ ⬈[h] K2 → ∀V1,V2. ⦃G, K1⦄ ⊢ V1 ⬈[h] V2 → + ∀I.⦃G, K1.ⓑ{I}V1⦄ ⊢ ⬈[h] K2.ⓑ{I}V2. +/2 width=1 by lex_pair/ qed. + (* Basic inversion lemmas ***************************************************) (* Basic_2A1: was: lpx_inv_atom1 *) -lemma lpx_inv_atom_sn: ∀h,G,L2. ⦃G, ⋆⦄ ⊢ ⬈[h] L2 → L2 = ⋆. +lemma lpx_inv_atom_sn (h) (G): ∀L2. ⦃G, ⋆⦄ ⊢ ⬈[h] L2 → L2 = ⋆. /2 width=2 by lex_inv_atom_sn/ qed-. -lemma lpx_inv_bind_sn: ∀h,I1,G,L2,K1. ⦃G, K1.ⓘ{I1}⦄ ⊢ ⬈[h] L2 → - ∃∃I2,K2. ⦃G, K1⦄ ⊢ ⬈[h] K2 & ⦃G, K1⦄ ⊢ I1 ⬈[h] I2 & - L2 = K2.ⓘ{I2}. +lemma lpx_inv_bind_sn (h) (G): ∀I1,L2,K1. ⦃G, K1.ⓘ{I1}⦄ ⊢ ⬈[h] L2 → + ∃∃I2,K2. ⦃G, K1⦄ ⊢ ⬈[h] K2 & ⦃G, K1⦄ ⊢ I1 ⬈[h] I2 & + L2 = K2.ⓘ{I2}. /2 width=1 by lex_inv_bind_sn/ qed-. (* Basic_2A1: was: lpx_inv_atom2 *) -lemma lpx_inv_atom_dx: ∀h,G,L1. ⦃G, L1⦄ ⊢ ⬈[h] ⋆ → L1 = ⋆. +lemma lpx_inv_atom_dx: ∀h,G,L1. ⦃G, L1⦄ ⊢ ⬈[h] ⋆ → L1 = ⋆. /2 width=2 by lex_inv_atom_dx/ qed-. -lemma lpx_inv_bind_dx: ∀h,I2,G,L1,K2. ⦃G, L1⦄ ⊢ ⬈[h] K2.ⓘ{I2} → - ∃∃I1,K1. ⦃G, K1⦄ ⊢ ⬈[h] K2 & ⦃G, K1⦄ ⊢ I1 ⬈[h] I2 & - L1 = K1.ⓘ{I1}. +lemma lpx_inv_bind_dx (h) (G): ∀I2,L1,K2. ⦃G, L1⦄ ⊢ ⬈[h] K2.ⓘ{I2} → + ∃∃I1,K1. ⦃G, K1⦄ ⊢ ⬈[h] K2 & ⦃G, K1⦄ ⊢ I1 ⬈[h] I2 & + L1 = K1.ⓘ{I1}. /2 width=1 by lex_inv_bind_dx/ qed-. (* Advanced inversion lemmas ************************************************) +lemma lpx_inv_unit_sn (h) (G): ∀I,L2,K1. ⦃G, K1.ⓤ{I}⦄ ⊢ ⬈[h] L2 → + ∃∃K2. ⦃G, K1⦄ ⊢ ⬈[h] K2 & L2 = K2.ⓤ{I}. +/2 width=1 by lex_inv_unit_sn/ qed-. + (* Basic_2A1: was: lpx_inv_pair1 *) -lemma lpx_inv_pair_sn: ∀h,I,G,L2,K1,V1. ⦃G, K1.ⓑ{I}V1⦄ ⊢ ⬈[h] L2 → - ∃∃K2,V2. ⦃G, K1⦄ ⊢ ⬈[h] K2 & ⦃G, K1⦄ ⊢ V1 ⬈[h] V2 & - L2 = K2.ⓑ{I}V2. +lemma lpx_inv_pair_sn (h) (G): ∀I,L2,K1,V1. ⦃G, K1.ⓑ{I}V1⦄ ⊢ ⬈[h] L2 → + ∃∃K2,V2. ⦃G, K1⦄ ⊢ ⬈[h] K2 & ⦃G, K1⦄ ⊢ V1 ⬈[h] V2 & + L2 = K2.ⓑ{I}V2. /2 width=1 by lex_inv_pair_sn/ qed-. +lemma lpx_inv_unit_dx (h) (G): ∀I,L1,K2. ⦃G, L1⦄ ⊢ ⬈[h] K2.ⓤ{I} → + ∃∃K1. ⦃G, K1⦄ ⊢ ⬈[h] K2 & L1 = K1.ⓤ{I}. +/2 width=1 by lex_inv_unit_dx/ qed-. + (* Basic_2A1: was: lpx_inv_pair2 *) -lemma lpx_inv_pair_dx: ∀h,I,G,L1,K2,V2. ⦃G, L1⦄ ⊢ ⬈[h] K2.ⓑ{I}V2 → - ∃∃K1,V1. ⦃G, K1⦄ ⊢ ⬈[h] K2 & ⦃G, K1⦄ ⊢ V1 ⬈[h] V2 & - L1 = K1.ⓑ{I}V1. +lemma lpx_inv_pair_dx (h) (G): ∀I,L1,K2,V2. ⦃G, L1⦄ ⊢ ⬈[h] K2.ⓑ{I}V2 → + ∃∃K1,V1. ⦃G, K1⦄ ⊢ ⬈[h] K2 & ⦃G, K1⦄ ⊢ V1 ⬈[h] V2 & + L1 = K1.ⓑ{I}V1. /2 width=1 by lex_inv_pair_dx/ qed-. -lemma lpx_inv_pair: ∀h,I1,I2,G,L1,L2,V1,V2. ⦃G, L1.ⓑ{I1}V1⦄ ⊢ ⬈[h] L2.ⓑ{I2}V2 → - ∧∧ ⦃G, L1⦄ ⊢ ⬈[h] L2 & ⦃G, L1⦄ ⊢ V1 ⬈[h] V2 & I1 = I2. +lemma lpx_inv_pair (h) (G): ∀I1,I2,L1,L2,V1,V2. ⦃G, L1.ⓑ{I1}V1⦄ ⊢ ⬈[h] L2.ⓑ{I2}V2 → + ∧∧ ⦃G, L1⦄ ⊢ ⬈[h] L2 & ⦃G, L1⦄ ⊢ V1 ⬈[h] V2 & I1 = I2. /2 width=1 by lex_inv_pair/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_aaa.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_aaa.ma new file mode 100644 index 000000000..1091f0f9a --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_aaa.ma @@ -0,0 +1,80 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/static/aaa_drops.ma". +include "basic_2/static/lsuba_aaa.ma". +include "basic_2/rt_transition/lpx_drops.ma". + +(* UNBOUND PARALLEL RT-TRANSITION FOR FULL LOCAL ENVIRONMENTS ***************) + +(* Properties with atomic arity assignment for terms ************************) + +(* Note: lemma 500 *) +(* Basic_2A1: was: cpx_lpx_aaa_conf *) +lemma cpx_aaa_conf_lpx (h): ∀G,L1,T1,A. ⦃G, L1⦄ ⊢ T1 ⁝ A → + ∀T2. ⦃G, L1⦄ ⊢ T1 ⬈[h] T2 → + ∀L2. ⦃G, L1⦄ ⊢ ⬈[h] L2 → ⦃G, L2⦄ ⊢ T2 ⁝ A. +#h #G #L1 #T1 #A #H elim H -G -L1 -T1 -A +[ #G #L1 #s #X #H + elim (cpx_inv_sort1 … H) -H #H destruct // +| #I #G #K1 #V1 #B #_ #IH #X #HX #Y #HY + elim (lpx_inv_pair_sn … HY) -HY #K2 #V2 #HK12 #HV12 #H destruct + elim (cpx_inv_zero1_pair … HX) -HX + [ #H destruct /3 width=1 by aaa_zero/ + | * #V #HV1 #HVX -HV12 + /4 width=7 by aaa_lifts, drops_refl, drops_drop, true/ + ] +| #I1 #G #K1 #A #i #_ #IH #X #HX #Y #HY + elim (lpx_inv_bind_sn … HY) -HY #I2 #K2 #HK12 #_ #H destruct + elim (cpx_inv_lref1_bind … HX) -HX + [ #H destruct /3 width=1 by aaa_lref/ + | * #T #HT #HTX + /4 width=7 by aaa_lifts, drops_refl, drops_drop, true/ + ] +| #p #G #L1 #V1 #T1 #B #A #_ #_ #IHV1 #IHT1 #X #H #L2 #HL12 + elim (cpx_inv_abbr1 … H) -H * + [ #V2 #T2 #HV12 #HT12 #H destruct /4 width=2 by lpx_pair, aaa_abbr/ + | #T2 #HT12 #HT2 #H destruct -IHV1 + /4 width=8 by lpx_pair, aaa_inv_lifts, drops_refl, drops_drop/ + ] +| #p #G #L1 #V1 #T1 #B #A #_ #_ #IHV1 #IHT1 #X #H #L2 #HL12 + elim (cpx_inv_abst1 … H) -H #V2 #T2 #HV12 #HT12 #H destruct + /4 width=1 by lpx_pair, aaa_abst/ +| #G #L1 #V1 #T1 #B #A #_ #_ #IHV1 #IHT1 #X #H #L2 #HL12 + elim (cpx_inv_appl1 … H) -H * + [ #V2 #T2 #HV12 #HT12 #H destruct /3 width=3 by aaa_appl/ + | #q #V2 #W1 #W2 #U1 #U2 #HV12 #HW12 #HU12 #H1 #H2 destruct + lapply (IHV1 … HV12 … HL12) -IHV1 -HV12 #HV2 + lapply (IHT1 (ⓛ{q}W2.U2) … HL12) -IHT1 /2 width=1 by cpx_bind/ -L1 #H + elim (aaa_inv_abst … H) -H #B0 #A0 #HW1 #HU2 #H destruct + /5 width=6 by lsuba_aaa_trans, lsuba_beta, aaa_abbr, aaa_cast/ + | #q #V #V2 #W1 #W2 #U1 #U2 #HV1 #HV2 #HW12 #HU12 #H1 #H2 destruct + lapply (aaa_lifts G L2 … B … (L2.ⓓW2) … HV2) -HV2 /3 width=2 by drops_refl, drops_drop/ #HV2 + lapply (IHT1 (ⓓ{q}W2.U2) … HL12) -IHT1 /2 width=1 by cpx_bind/ -L1 #H + elim (aaa_inv_abbr … H) -H /3 width=3 by aaa_abbr, aaa_appl/ + ] +| #G #L1 #V1 #T1 #A #_ #_ #IHV1 #IHT1 #X #H #L2 #HL12 + elim (cpx_inv_cast1 … H) -H + [ * #V2 #T2 #HV12 #HT12 #H destruct /3 width=1 by aaa_cast/ + | -IHV1 /2 width=1 by/ + | -IHT1 /2 width=1 by/ + ] +] +qed-. + +lemma cpx_aaa_conf (h): ∀G,L. Conf3 … (aaa G L) (cpx h G L). +/2 width=7 by cpx_aaa_conf_lpx/ qed-. + +lemma lpx_aaa_conf (h): ∀G,T. Conf3 … (λL. aaa G L T) (lpx h G). +/2 width=7 by cpx_aaa_conf_lpx/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_drops.ma new file mode 100644 index 000000000..330ddecc4 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_drops.ma @@ -0,0 +1,35 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/relocation/drops_lex.ma". +include "basic_2/rt_transition/cpx_drops.ma". +include "basic_2/rt_transition/lpx.ma". + +(* UNBOUND PARALLEL RT-TRANSITION FOR FULL LOCAL ENVIRONMENTS ***************) + +(* Properties with generic slicing for local environments *******************) + +(* Basic_2A1: was: drop_lpx_trans *) +lemma drops_lpx_trans (h) (G): dedropable_sn (cpx h G). +/3 width=6 by lex_liftable_dedropable_sn, cpx_lifts_sn/ qed-. + +(* Inversion lemmas with generic slicing for local environments *************) + +(* Basic_2A1: was: lpx_drop_conf *) +lemma lpx_drops_conf (h) (G): dropable_sn (cpx h G). +/2 width=3 by lex_dropable_sn/ qed-. + +(* Basic_2A1: was: lpx_drop_trans_O1 *) +lemma lpx_drops_trans (h) (G): dropable_dx (cpx h G). +/2 width=3 by lex_dropable_dx/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_fquq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_fquq.ma new file mode 100644 index 000000000..2df357c91 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_fquq.ma @@ -0,0 +1,75 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/s_transition/fquq.ma". +include "basic_2/rt_transition/lpx.ma". + +(* UNBOUND PARALLEL RT-TRANSITION FOR FULL LOCAL ENVIRONMENTS ***************) + +(* Properties with extended structural successor for closures ***************) + +lemma lpx_fqu_trans (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐[b] ⦃G2, L2, T2⦄ → + ∀K1. ⦃G1, K1⦄ ⊢ ⬈[h] L1 → + ∃∃K2,T. ⦃G1, K1⦄ ⊢ T1 ⬈[h] T & ⦃G1, K1, T⦄ ⊐[b] ⦃G2, K2, T2⦄ & ⦃G2, K2⦄ ⊢ ⬈[h] L2. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 +[ #I #G #K #V #K1 #H + elim (lpx_inv_pair_dx … H) -H #K0 #V0 #HK0 #HV0 #H destruct + elim (lifts_total V (𝐔❴1❵)) #T #HVT + /3 width=5 by cpx_delta, fqu_drop, ex3_2_intro/ +| /3 width=5 by cpx_pair_sn, fqu_pair_sn, ex3_2_intro/ +| /3 width=5 by lpx_bind_refl_dx, cpx_pair_sn, fqu_bind_dx, ex3_2_intro/ +| /3 width=5 by lpx_bind_refl_dx, cpx_pair_sn, fqu_clear, ex3_2_intro/ +| /3 width=5 by cpx_pair_sn, fqu_flat_dx, ex3_2_intro/ +| #I #G #K #T #U #HTU #K1 #H + elim (lpx_inv_bind_dx … H) -H #I0 #K0 #HK0 #HI0 #H destruct + /3 width=5 by fqu_drop, ex3_2_intro/ +] +qed-. + +lemma fqu_lpx_trans (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐[b] ⦃G2, L2, T2⦄ → + ∀K2. ⦃G2, L2⦄ ⊢ ⬈[h] K2 → + ∃∃K1,T. ⦃G1, L1⦄ ⊢ ⬈[h] K1 & ⦃G1, L1⦄ ⊢ T1 ⬈[h] T & ⦃G1, K1, T⦄ ⊐[b] ⦃G2, K2, T2⦄. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H elim H -G1 -G2 -L1 -L2 -T1 -T2 +[ /3 width=5 by lpx_bind_refl_dx, fqu_lref_O, ex3_2_intro/ +| /3 width=5 by cpx_pair_sn, fqu_pair_sn, ex3_2_intro/ +| #p #I #G2 #L2 #V2 #T2 #X #H + elim (lpx_inv_pair_sn … H) -H #K2 #W2 #HLK2 #HVW2 #H destruct + /3 width=5 by cpx_pair_sn, fqu_bind_dx, ex3_2_intro/ +| #p #I #G2 #L2 #V2 #T2 #Hb #X #H + elim (lpx_inv_unit_sn … H) -H #K2 #HLK2 #H destruct + /3 width=5 by cpx_pair_sn, fqu_clear, ex3_2_intro/ +| /3 width=5 by cpx_pair_sn, fqu_flat_dx, ex3_2_intro/ +| /3 width=5 by lpx_bind_refl_dx, fqu_drop, ex3_2_intro/ +] +qed-. + +(* Properties with extended optional structural successor for closures ******) + +lemma lpx_fquq_trans (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮[b] ⦃G2, L2, T2⦄ → + ∀K1. ⦃G1, K1⦄ ⊢ ⬈[h] L1 → + ∃∃K2,T. ⦃G1, K1⦄ ⊢ T1 ⬈[h] T & ⦃G1, K1, T⦄ ⊐⸮[b] ⦃G2, K2, T2⦄ & ⦃G2, K2⦄ ⊢ ⬈[h] L2. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H #K1 #HKL1 cases H -H +[ #H12 elim (lpx_fqu_trans … H12 … HKL1) -L1 /3 width=5 by fqu_fquq, ex3_2_intro/ +| * #H1 #H2 #H3 destruct /2 width=5 by ex3_2_intro/ +] +qed-. + +lemma fquq_lpx_trans (h) (b): ∀G1,G2,L1,L2,T1,T2. ⦃G1, L1, T1⦄ ⊐⸮[b] ⦃G2, L2, T2⦄ → + ∀K2. ⦃G2, L2⦄ ⊢ ⬈[h] K2 → + ∃∃K1,T. ⦃G1, L1⦄ ⊢ ⬈[h] K1 & ⦃G1, L1⦄ ⊢ T1 ⬈[h] T & ⦃G1, K1, T⦄ ⊐⸮[b] ⦃G2, K2, T2⦄. +#h #b #G1 #G2 #L1 #L2 #T1 #T2 #H #K2 #HLK2 cases H -H +[ #H12 elim (fqu_lpx_trans … H12 … HLK2) /3 width=5 by fqu_fquq, ex3_2_intro/ +| * #H1 #H2 #H3 destruct /2 width=5 by ex3_2_intro/ +] +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_fsle.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_fsle.ma new file mode 100644 index 000000000..7773a081e --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_fsle.ma @@ -0,0 +1,28 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/rt_transition/lfpx_lpx.ma". + +(* UNBOUND PARALLEL RT-TRANSITION FOR FULL LOCAL ENVIRONMENTS ***************) + +(* Forward lemmas with free variables inclusion for restricted closures *****) + +(* Basic_2A1: uses: lpx_cpx_frees_trans *) +lemma lpx_cpx_conf_fsge (h) (G): ∀L0,T0,T1. ⦃G, L0⦄ ⊢ T0 ⬈[h] T1 → + ∀L2. ⦃G, L0⦄ ⊢ ⬈[h] L2 → ⦃L2, T1⦄ ⊆ ⦃L0, T0⦄. +/3 width=4 by lfpx_cpx_conf_fsge, lpx_lfpx/ qed-. + +(* Basic_2A1: uses: lpx_frees_trans *) +lemma lpx_fsge_comp (h) (G): ∀L0,L2,T0. ⦃G, L0⦄ ⊢ ⬈[h] L2 → ⦃L2, T0⦄ ⊆ ⦃L0, T0⦄. +/2 width=4 by lpx_cpx_conf_fsge/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_length.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_length.ma new file mode 100644 index 000000000..1c8a2b9b6 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_length.ma @@ -0,0 +1,23 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/relocation/lex_length.ma". +include "basic_2/rt_transition/lpx.ma". + +(* UNBOUND PARALLEL RT-TRANSITION FOR FULL LOCAL ENVIRONMENTS ***************) + +(* Forward lemmas with length for local environments ************************) + +lemma lpx_fwd_length (h) (G): ∀L1,L2. ⦃G, L1⦄ ⊢ ⬈[h] L2 → |L1| = |L2|. +/2 width=2 by lex_fwd_length/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_lfdeq.ma b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_lfdeq.ma new file mode 100644 index 000000000..0008d2f79 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/rt_transition/lpx_lfdeq.ma @@ -0,0 +1,32 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basic_2/static/lfdeq_lfeq.ma". +include "basic_2/rt_transition/lfpx_lfdeq.ma". +include "basic_2/rt_transition/lfpx_lpx.ma". + +(* UNBOUND PARALLEL RT-TRANSITION FOR FULL LOCAL ENVIRONMENTS ***************) + +(* Properties with degree-based equivalence for local environments **********) + +(* Basic_2A1: uses: lleq_lpx_trans *) +lemma lfdeq_lpx_trans (h) (o) (G): ∀L2,K2. ⦃G, L2⦄ ⊢ ⬈[h] K2 → + ∀L1. ∀T:term. L1 ≛[h, o, T] L2 → + ∃∃K1. ⦃G, L1⦄ ⊢ ⬈[h] K1 & K1 ≛[h, o, T] K2. +#h #o #G #L2 #K2 #HLK2 #L1 #T #HL12 +lapply (lpx_lfpx … T HLK2) -HLK2 #HLK2 +elim (lfdeq_lfpx_trans … HLK2 … HL12) -L2 #K #H #HK2 +elim (lfpx_inv_lpx_lfeq … H) -H #K1 #HLK1 #HK1 +/3 width=5 by lfeq_lfdeq_trans, ex2_intro/ +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/lfdeq_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/static/lfdeq_drops.ma index d9dc626d7..8e0e253e0 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/static/lfdeq_drops.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/static/lfdeq_drops.ma @@ -20,16 +20,16 @@ include "basic_2/static/lfdeq.ma". (* Properties with generic slicing for local environments *******************) -lemma lfdeq_lifts_sn: ∀h,o. dedropable_sn (cdeq h o). +lemma lfdeq_lifts_sn: ∀h,o. f_dedropable_sn (cdeq h o). /3 width=5 by lfxs_liftable_dedropable_sn, tdeq_lifts_sn/ qed-. (* Inversion lemmas with generic slicing for local environments *************) -lemma lfdeq_inv_lifts_sn: ∀h,o. dropable_sn (cdeq h o). +lemma lfdeq_inv_lifts_sn: ∀h,o. f_dropable_sn (cdeq h o). /2 width=5 by lfxs_dropable_sn/ qed-. (* Note: missing in basic_2A1 *) -lemma lfdeq_inv_lifts_dx: ∀h,o. dropable_dx (cdeq h o). +lemma lfdeq_inv_lifts_dx: ∀h,o. f_dropable_dx (cdeq h o). /2 width=5 by lfxs_dropable_dx/ qed-. (* Basic_2A1: uses: lleq_inv_lift_le lleq_inv_lift_be lleq_inv_lift_ge *) diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/lfxs_drops.ma b/matita/matita/contribs/lambdadelta/basic_2/static/lfxs_drops.ma index c37c2d346..8e198ac76 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/static/lfxs_drops.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/static/lfxs_drops.ma @@ -19,30 +19,30 @@ include "basic_2/static/lfxs.ma". (* GENERIC EXTENSION ON REFERRED ENTRIES OF A CONTEXT-SENSITIVE REALTION ****) -definition dedropable_sn: predicate (relation3 lenv term term) ≝ - λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → - ∀K2,T. K1 ⪤*[R, T] K2 → ∀U. ⬆*[f] T ≘ U → - ∃∃L2. L1 ⪤*[R, U] L2 & ⬇*[b, f] L2 ≘ K2 & L1 ≡[f] L2. +definition f_dedropable_sn: predicate (relation3 lenv term term) ≝ + λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → + ∀K2,T. K1 ⪤*[R, T] K2 → ∀U. ⬆*[f] T ≘ U → + ∃∃L2. L1 ⪤*[R, U] L2 & ⬇*[b, f] L2 ≘ K2 & L1 ≡[f] L2. -definition dropable_sn: predicate (relation3 lenv term term) ≝ +definition f_dropable_sn: predicate (relation3 lenv term term) ≝ λR. ∀b,f,L1,K1. ⬇*[b, f] L1 ≘ K1 → 𝐔⦃f⦄ → ∀L2,U. L1 ⪤*[R, U] L2 → ∀T. ⬆*[f] T ≘ U → ∃∃K2. K1 ⪤*[R, T] K2 & ⬇*[b, f] L2 ≘ K2. -definition dropable_dx: predicate (relation3 lenv term term) ≝ - λR. ∀L1,L2,U. L1 ⪤*[R, U] L2 → - ∀b,f,K2. ⬇*[b, f] L2 ≘ K2 → 𝐔⦃f⦄ → ∀T. ⬆*[f] T ≘ U → - ∃∃K1. ⬇*[b, f] L1 ≘ K1 & K1 ⪤*[R, T] K2. +definition f_dropable_dx: predicate (relation3 lenv term term) ≝ + λR. ∀L1,L2,U. L1 ⪤*[R, U] L2 → + ∀b,f,K2. ⬇*[b, f] L2 ≘ K2 → 𝐔⦃f⦄ → ∀T. ⬆*[f] T ≘ U → + ∃∃K1. ⬇*[b, f] L1 ≘ K1 & K1 ⪤*[R, T] K2. -definition lfxs_transitive_next: relation3 … ≝ λR1,R2,R3. - ∀f,L,T. L ⊢ 𝐅*⦃T⦄ ≘ f → - ∀g,I,K,n. ⬇*[n] L ≘ K.ⓘ{I} → ↑g = ⫱*[n] f → - lexs_transitive (cext2 R1) (cext2 R2) (cext2 R3) (cext2 R1) cfull g K I. +definition f_transitive_next: relation3 … ≝ λR1,R2,R3. + ∀f,L,T. L ⊢ 𝐅*⦃T⦄ ≘ f → + ∀g,I,K,n. ⬇*[n] L ≘ K.ⓘ{I} → ↑g = ⫱*[n] f → + lexs_transitive (cext2 R1) (cext2 R2) (cext2 R3) (cext2 R1) cfull g K I. (* Properties with generic slicing for local environments *******************) lemma lfxs_liftable_dedropable_sn: ∀R. (∀L. reflexive ? (R L)) → - d_liftable2_sn … lifts R → dedropable_sn R. + d_liftable2_sn … lifts R → f_dedropable_sn R. #R #H1R #H2R #b #f #L1 #K1 #HLK1 #K2 #T * #f1 #Hf1 #HK12 #U #HTU elim (frees_total L1 U) #f2 #Hf2 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -HTU #Hf @@ -50,7 +50,7 @@ elim (lexs_liftable_co_dedropable_sn … HLK1 … HK12 … Hf) -f1 -K1 /3 width=6 by cext2_d_liftable2_sn, cfull_lift_sn, ext2_refl, ex3_intro, ex2_intro/ qed-. -lemma lfxs_trans_next: ∀R1,R2,R3. lfxs_transitive R1 R2 R3 → lfxs_transitive_next R1 R2 R3. +lemma lfxs_trans_next: ∀R1,R2,R3. lfxs_transitive R1 R2 R3 → f_transitive_next R1 R2 R3. #R1 #R2 #R3 #HR #f #L1 #T #Hf #g #I1 #K1 #n #HLK #Hgf #I #H generalize in match HLK; -HLK elim H -I1 -I [ #I #_ #L2 #_ #I2 #H @@ -67,7 +67,7 @@ qed. (* Basic_2A1: uses: llpx_sn_inv_lift_le llpx_sn_inv_lift_be llpx_sn_inv_lift_ge *) (* Basic_2A1: was: llpx_sn_drop_conf_O *) -lemma lfxs_dropable_sn: ∀R. dropable_sn R. +lemma lfxs_dropable_sn: ∀R. f_dropable_sn R. #R #b #f #L1 #K1 #HLK1 #H1f #L2 #U * #f2 #Hf2 #HL12 #T #HTU elim (frees_total K1 T) #f1 #Hf1 lapply (frees_fwd_coafter … Hf2 … HLK1 … HTU … Hf1) -HTU #H2f @@ -77,7 +77,7 @@ qed-. (* Basic_2A1: was: llpx_sn_drop_trans_O *) (* Note: the proof might be simplified *) -lemma lfxs_dropable_dx: ∀R. dropable_dx R. +lemma lfxs_dropable_dx: ∀R. f_dropable_dx R. #R #L1 #L2 #U * #f2 #Hf2 #HL12 #b #f #K2 #HLK2 #H1f #T #HTU elim (drops_isuni_ex … H1f L1) #K1 #HLK1 elim (frees_total K1 T) #f1 #Hf1 diff --git a/matita/matita/contribs/lambdadelta/basic_2/static/lfxs_fsle.ma b/matita/matita/contribs/lambdadelta/basic_2/static/lfxs_fsle.ma index 000a74e65..514e63def 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/static/lfxs_fsle.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/static/lfxs_fsle.ma @@ -165,7 +165,7 @@ elim (lexs_conf … HL01 … HL02) /2 width=3 by ex2_intro/ [ | -HL01 -HL02 ] qed-. theorem lfxs_trans_fsle: ∀R1,R2,R3. - lfxs_fsle_compatible R1 → lfxs_transitive_next R1 R2 R3 → + lfxs_fsle_compatible R1 → f_transitive_next R1 R2 R3 → ∀L1,L,T. L1 ⪤*[R1, T] L → ∀L2. L ⪤*[R2, T] L2 → L1 ⪤*[R3, T] L2. #R1 #R2 #R3 #H1R #H2R #L1 #L #T #H 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 6cf0a3dac..71ca47a56 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 @@ -9,16 +9,14 @@ table { ] } ] -(* class "wine" - [ { "higher order dynamic typing" * } { - [ { "higher order native type assignment" * } { - [ [ "" ] "ntas ( ⦃?,?⦄ ⊢ ? :* ? )" "nta_lift" * ] + [ { "iterated dynamic typing" * } { + [ { "" (* "higher order native type assignment" *) * } { + [ [ "" ] (* "ntas ( ⦃?,?⦄ ⊢ ? :* ? )" "nta_lift" *) * ] } ] } ] -*) class "magenta" [ { "dynamic typing" * } { (* @@ -112,19 +110,19 @@ table { } ] [ { "context-sensitive parallel r-transition" * } { - [ [ "for lenvs on referred entries" ] "lfpr" + "( ⦃?,?⦄ ⊢ ➡[?,?] ? )" "lfpr_length" + "lfpr_drops" + "lfpr_fquq" + "lfpr_fqup" + "lfpr_aaa" + "lfpr_lfpx" + "lfpr_lfpr" * ] + [ [ "for lenvs on all entries" ] "lpr" + "( ⦃?,?⦄ ⊢ ➡[?] ? )" "lpr_length" + "lpr_drops" + "lpr_fquq" + "lpr_aaa" + "lpr_lpx" (* + "lfpr_lfpr" *) * ] [ [ "for binders" ] "cpr_ext" + "( ⦃?,?⦄ ⊢ ? ➡[?] ? )" * ] - [ [ "for terms" ] "cpr" + "( ⦃?,?⦄ ⊢ ? ➡[?] ? )" "cpr_drops" * ] + [ [ "for terms" ] "cpr" + "( ⦃?,?⦄ ⊢ ? ➡[?] ? )" "cpr_drops" + "cpr_cpr" * ] } ] [ { "t-bound context-sensitive parallel rt-transition" * } { - [ [ "for terms" ] "cpm" + "( ⦃?,?⦄ ⊢ ? ➡[?,?] ? )" "cpm_simple" + "cpm_drops" + "cpm_lsubr" + "cpm_fsle" + "cpm_cpx" * ] + [ [ "for terms" ] "cpm" + "( ⦃?,?⦄ ⊢ ? ➡[?,?] ? )" "cpm_simple" + "cpm_drops" + "cpm_lsubr" + "cpm_fsle" + "cpm_aaa" + "cpm_cpx" * ] } ] [ { "unbound context-sensitive parallel rt-transition" * } { [ [ "normal form for terms" ] "cnx" + "( ⦃?,?⦄ ⊢ ⬈[?,?] 𝐍⦃?⦄ )" "cnx_simple" + "cnx_drops" + "cnx_cnx" * ] - [ [ "for lenvs on referred entries" ] "lfpx" + "( ⦃?,?⦄ ⊢ ⬈[?,?] ? )" "lfpx_length" + "lfpx_drops" + "lfpx_fquq" + "lfpx_fqup" + "lfpx_fsle" + "lfpx_lfdeq" + "lfpx_aaa" + "lfpx_lpx" + "lfpx_lfpx" * ] - [ [ "for lenvs on all entries" ] "lpx" + "( ⦃?,?⦄ ⊢ ⬈[?] ? )" * ] + [ [ "for lenvs on referred entries" ] "lfpx" + "( ⦃?,?⦄ ⊢ ⬈[?,?] ? )" "lfpx_length" + "lfpx_fqup" + "lfpx_fsle" + "lfpx_lfdeq" + "lfpx_lpx" + "lfpx_lfpx" * ] + [ [ "for lenvs on all entries" ] "lpx" + "( ⦃?,?⦄ ⊢ ⬈[?] ? )" "lpx_length" + "lpx_drops" + "lpx_fquq" + "lpx_fsle" + "lpx_lfdeq" + "lpx_aaa" * ] [ [ "for binders" ] "cpx_ext" + "( ⦃?,?⦄ ⊢ ? ⬈[?] ? )" * ] [ [ "for terms" ] "cpx" + "( ⦃?,?⦄ ⊢ ? ⬈[?] ? )" "cpx_simple" + "cpx_drops" + "cpx_fqus" + "cpx_lsubr" + "cpx_lfeq" + "cpx_lfdeq" + "cpx_ffdeq" * ] } @@ -202,7 +200,7 @@ table { class "orange" [ { "relocation" * } { [ { "generic slicing" * } { - [ [ "for lenvs" ] "drops" + "( ⬇*[?,?] ? ≘ ? )" + "( ⬇*[?] ? ≘ ? )" "drops_ctc" + "drops_ltc" + "drops_weight" + "drops_length" + "drops_cext2" + "drops_lexs" + "drops_lreq" + "drops_drops" + "drops_vector" * ] + [ [ "for lenvs" ] "drops" + "( ⬇*[?,?] ? ≘ ? )" + "( ⬇*[?] ? ≘ ? )" "drops_ctc" + "drops_ltc" + "drops_weight" + "drops_length" + "drops_cext2" + "drops_lexs" + "drops_lex" + "drops_lreq" + "drops_drops" + "drops_vector" * ] } ] [ { "generic relocation" * } { @@ -216,7 +214,7 @@ table { } ] [ { "generic entrywise extension" * } { - [ [ "for lenvs of one contex-sensitive relation" ] "lex" + "( ? ⦻[?] ? )" "lex_tc" + "lex_length" * ] + [ [ "for lenvs of one contex-sensitive relation" ] "lex" + "( ? ⦻[?] ? )" "lex_tc" + "lex_length" + "lex_lex" * ] [ [ "for lenvs of two contex-sensitive relations" ] "lexs" + "( ? ⦻*[?,?,?] ? )" "lexs_tc" + "lexs_length" + "lexs_lexs" * ] } ] @@ -292,6 +290,8 @@ class "capitalize italic" { 0 1 } class "italic" { 2 } (* + [ [ "for lenvs on referred entries" ] + "lfpr" + "( ⦃?,?⦄ ⊢ ➡[?,?] ? )" "lfpr_length" + "lfpr_drops" + "lfpr_fquq" + "lfpr_fqup" + "lfpr_aaa" + "lfpr_lfpx" + "lfpr_lfpr" * ] [ { "evaluation for context-sensitive rt-reduction" * } { [ [ "" ] "cpxe ( ⦃?,?⦄ ⊢ ➡*[?,?] 𝐍⦃?⦄ )" * ] } diff --git a/matita/matita/contribs/lambdadelta/ground_2/pull/pull_2.ma b/matita/matita/contribs/lambdadelta/ground_2/pull/pull_2.ma new file mode 100644 index 000000000..dd1411ebb --- /dev/null +++ b/matita/matita/contribs/lambdadelta/ground_2/pull/pull_2.ma @@ -0,0 +1,24 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basics/pts.ma". + +(* GENERATED LIBRARY ********************************************************) + +lemma pull_2 (A1:Type[0]) + (A2:Type[0]) + (A:A1→A2→Type[0]): + (∀x2,x1. A x1 x2) → + (∀x1,x2. A x1 x2). +/2 width=1 by/ qed-. diff --git a/matita/matita/contribs/lambdadelta/ground_2/pull/pull_4.ma b/matita/matita/contribs/lambdadelta/ground_2/pull/pull_4.ma new file mode 100644 index 000000000..4bf66b56e --- /dev/null +++ b/matita/matita/contribs/lambdadelta/ground_2/pull/pull_4.ma @@ -0,0 +1,26 @@ +(**************************************************************************) +(* ___ *) +(* ||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 *) +(* *) +(**************************************************************************) + +include "basics/pts.ma". + +(* GENERATED LIBRARY ********************************************************) + +lemma pull_4 (A1:Type[0]) + (A2:A1→Type[0]) + (A3:∀x1.A2 x1→Type[0]) + (A4:Type[0]) + (A:∀x1:A1.∀x2:A2 x1.A3 x1 x2 → A4 → Type[0]): + (∀x4,x1,x2,x3. A x1 x2 x3 x4) → + (∀x1,x2,x3,x4. A x1 x2 x3 x4). +/2 width=1 by/ qed-. diff --git a/matita/matita/contribs/lambdadelta/ground_2/web/ground_2_src.tbl b/matita/matita/contribs/lambdadelta/ground_2/web/ground_2_src.tbl index 77174d94b..c4ca8f6d2 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/web/ground_2_src.tbl +++ b/matita/matita/contribs/lambdadelta/ground_2/web/ground_2_src.tbl @@ -63,10 +63,14 @@ table { ] class "orange" [ { "generated library" * } { - [ { "equality insertion" * } { + [ { "generalization with equality" * } { [ "insert_eq" * ] } ] + [ { "permutation of quantifiers" * } { + [ "pull" * ] + } + ] [ { "logical decomposables" * } { [ "xoa ( ∃∃ ) ( ∨∨ ) ( ∧∧ )" * ] } -- 2.39.2