From 8eae36a5d21821a23f287798e5e2a3ab37255b25 Mon Sep 17 00:00:00 2001 From: Ferruccio Guidi Date: Thu, 25 May 2017 10:30:15 +0000 Subject: [PATCH] extension of a relation to binders --- .../basic_2/etc/frees/frees_bind.etc | 51 +++++++++++++ .../basic_2/etc/frees/frees_drops.etc | 73 ++++++++++++++++++ .../lambdadelta/basic_2/syntax/bind_ext2.ma | 74 +++++++++++++++++++ .../lambdadelta/basic_2/syntax/lenv_ext2.ma | 33 +++++++++ .../lambdadelta/basic_2/web/basic_2_src.tbl | 2 + 5 files changed, 233 insertions(+) create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/frees/frees_bind.etc create mode 100644 matita/matita/contribs/lambdadelta/basic_2/etc/frees/frees_drops.etc create mode 100644 matita/matita/contribs/lambdadelta/basic_2/syntax/bind_ext2.ma create mode 100644 matita/matita/contribs/lambdadelta/basic_2/syntax/lenv_ext2.ma diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/frees/frees_bind.etc b/matita/matita/contribs/lambdadelta/basic_2/etc/frees/frees_bind.etc new file mode 100644 index 000000000..ffa75a1fb --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/frees/frees_bind.etc @@ -0,0 +1,51 @@ +(**************************************************************************) +(* ___ *) +(* ||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/syntax/bind.ma". +include "basic_2/static/frees.ma". + +(* CONTEXT-SENSITIVE FREE VARIABLES FOR BINDERS *****************************) + +inductive freesb (L): relation2 … ≝ +| freesb_pair: ∀I,V,f. L ⊢ 𝐅*⦃V⦄ ≡ f → freesb L (BPair I V) f +| freesb_unit: ∀I,f. 𝐈⦃f⦄ → freesb L (BUnit I) f +. + +interpretation + "context-sensitive free variables (binder)" + 'FreeStar L I f = (freesb L I f). + +(* Basic inversion lemmas ***************************************************) + +fact frees_inv_pair_aux: ∀L,Z,f. L ⊢ 𝐅*⦃Z⦄ ≡ f → + ∀I,V. Z = BPair I V → L ⊢ 𝐅*⦃V⦄ ≡ f. +#L #Z #f * -Z -f +[ #I #V #f #Hf #Z #X #H destruct // +| #I #f #_ #Z #X #H destruct +] +qed-. + +lemma frees_inv_pair: ∀L,I,V,f. L ⊢ 𝐅*⦃BPair I V⦄ ≡ f → L ⊢ 𝐅*⦃V⦄ ≡ f. +/2 width=4 by frees_inv_pair_aux/ qed-. + +fact frees_inv_unit_aux: ∀L,Z,f. L ⊢ 𝐅*⦃Z⦄ ≡ f → + ∀I. Z = BUnit I → 𝐈⦃f⦄. +#L #Z #f * -Z -f +[ #I #V #f #_ #Z #H destruct +| #I #f #Hf #Z #H destruct // +] +qed-. + +lemma frees_inv_unit: ∀L,I,f. L ⊢ 𝐅*⦃BUnit I⦄ ≡ f → 𝐈⦃f⦄. +/2 width=5 by frees_inv_unit_aux/ qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/etc/frees/frees_drops.etc b/matita/matita/contribs/lambdadelta/basic_2/etc/frees/frees_drops.etc new file mode 100644 index 000000000..c0e55af23 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/etc/frees/frees_drops.etc @@ -0,0 +1,73 @@ +(* Note: this does not hold since L = Y.ⓧ, U = #0, f = ⫯g requires T = #(-1) *) +lemma frees_inv_drops: ∀f2,L,U. L ⊢ 𝐅*⦃U⦄ ≡ f2 → + ∀f,K. ⬇*[Ⓣ, f] L ≡ K → ∀f1. f ~⊚ f1 ≡ f2 → + ∃∃T. K ⊢ 𝐅*⦃T⦄ ≡ f1 & ⬆*[f] T ≡ U. +#f2 #L #U #H lapply (frees_fwd_isfin … H) elim H -f2 -L -U +[ #f2 #I #Hf2 #_ #f #K #H1 #f1 #H2 + lapply (coafter_fwd_isid2 … H2 ??) -H2 // -Hf2 #Hf1 + elim (drops_inv_atom1 … H1) -H1 #H #Hf destruct + /4 width=3 by frees_atom, lifts_refl, ex2_intro/ +| #f2 #I #L #s #_ #IH #Hf2 #f #Y #H1 #f1 #H2 + lapply (isfin_fwd_push … Hf2 ??) -Hf2 [3: |*: // ] #Hf2 + elim (coafter_inv_xxp … H2) -H2 [1,3: * |*: // ] + [ #g #g1 #Hf2 #H #H0 destruct + elim (drops_inv_skip1 … H1) -H1 #Z #K #HLK #_ #H destruct + | #g #Hf2 #H destruct + lapply (drops_inv_drop1 … H1) -H1 #HLK + ] + elim (IH … HLK … Hf2) -L // -f2 #X #Hg1 #HX + lapply (lifts_inv_sort2 … HX) -HX #H destruct + /3 width=3 by frees_sort, lifts_sort, ex2_intro/ +| #f2 #I #L #W #_ #IH #Hf2 #f #Y #H1 #f1 #H2 + lapply (isfin_inv_next … Hf2 ??) -Hf2 [3: |*: // ] #Hf2 + elim (coafter_inv_xxn … H2) -H2 [ |*: // ] #g #g1 #Hf2 #H0 #H destruct + elim (drops_inv_skip1 … H1) -H1 #J #K #HLK #HJI #H destruct + elim (liftsb_inv_pair_dx … HJI) -HJI #V #HVW #H destruct + elim (IH … HLK … Hf2) -L // -f2 #X #Hg1 #HX + lapply (lifts_inj … HX … HVW) -W #H destruct + /3 width=3 by frees_zero, lifts_lref, ex2_intro/ +| #f2 #L #Hf2 #_ #f #Y #H1 #f1 #H2 + lapply (coafter_fwd_isid2 … H2 ??) -H2 // -Hf2 #Hf1 + elim (pn_split f) * #g #H destruct + [ elim (drops_inv_skip1 … H1) -H1 #J #K #HLK #HJI #H destruct + lapply (liftsb_inv_unit_dx … HJI) -HJI #H destruct + /3 width=3 by frees_void, lifts_lref, ex2_intro/ + | lapply (drops_inv_drop1 … H1) -H1 #H1 +| #f2 #I #L #j #_ #IH #Hf2 #f #Y #H1 #f1 #H2 + lapply (isfin_fwd_push … Hf2 ??) -Hf2 [3: |*: // ] #Hf2 + elim (coafter_inv_xxp … H2) -H2 [1,3: * |*: // ] + [ #g #g1 #Hf2 #H #H0 destruct + elim (drops_inv_skip1 … H1) -H1 #J #K #HLK #_ #H destruct + | #g #Hf2 #H destruct + lapply (drops_inv_drop1 … H1) -H1 #HLK (* cannot continue *) + ] + elim (IH … HLK … Hf2) -L // -f2 #X #Hg1 #HX + elim (lifts_inv_lref2 … HX) -HX #i #Hij #H destruct + /4 width=7 by frees_lref, lifts_lref, at_S1, at_next, ex2_intro/ +| #f2 #I #L #l #_ #IH #Hf2 #f #Y #H1 #f1 #H2 + lapply (isfin_fwd_push … Hf2 ??) -Hf2 [3: |*: // ] #Hf2 + elim (coafter_inv_xxp … H2) -H2 [1,3: * |*: // ] + [ #g #g1 #Hf2 #H #H0 destruct + elim (drops_inv_skip1 … H1) -H1 #J #K #HLK #_ #H destruct + | #g #Hf2 #H destruct + lapply (drops_inv_drop1 … H1) -H1 #HLK + ] + elim (IH … HLK … Hf2) -L // -f2 #X #Hg1 #HX + lapply (lifts_inv_gref2 … HX) -HX #H destruct + /3 width=3 by frees_gref, lifts_gref, ex2_intro/ +| #f2W #f2U #f2 #p #I #L #W #U #_ #_ #H1f2 #IHW #IHU #H2f2 #f #K #H1 #f1 #H2 + elim (sor_inv_isfin3 … H1f2) // #H1f2W #H + lapply (isfin_inv_tl … H) -H #H1f2U + elim (coafter_inv_sor … H2 … H1f2) -H2 -H1f2 // #f1W #f1U #H2f2W #H #Hf1 + elim (coafter_inv_tl0 … H) -H #g1 #H2f2U #H destruct + elim (IHW … H1 … H2f2W) -IHW -H2f2W // -H1f2W #V #Hf1W #HVW + elim (IHU … H2f2U) -IHU -H2f2U + /3 width=5 by frees_bind, drops_skip, lifts_bind, ext2_pair, ex2_intro/ +| #f2W #f2U #f2 #I #L #W #U #_ #_ #H1f2 #IHW #IHU #H2f2 #f #K #H1 #f1 #H2 + elim (sor_inv_isfin3 … H1f2) // #H1f2W #H1f2U + elim (coafter_inv_sor … H2 … H1f2) -H2 -H1f2 // #f1W #f1U #H2f2W #H2f2U #Hf1 + elim (IHW … H1 … H2f2W) -IHW -H2f2W // -H1f2W + elim (IHU … H1 … H2f2U) -L -H2f2U + /3 width=5 by frees_flat, lifts_flat, ex2_intro/ +] +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/syntax/bind_ext2.ma b/matita/matita/contribs/lambdadelta/basic_2/syntax/bind_ext2.ma new file mode 100644 index 000000000..c9850ef2e --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/syntax/bind_ext2.ma @@ -0,0 +1,74 @@ +(**************************************************************************) +(* ___ *) +(* ||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/syntax/bind.ma". + +(* EXTENSION TO BINDERS OF A RELATION FOR TERMS *****************************) + +inductive ext2 (R:relation term): relation bind ≝ +| ext2_unit: ∀I. ext2 R (BUnit I) (BUnit I) +| ext2_pair: ∀I,V1,V2. R V1 V2 → ext2 R (BPair I V1) (BPair I V2) +. + +(* Basic_inversion lemmas **************************************************) + +fact ext2_inv_unit_sn_aux: ∀R,Z1,Z2. ext2 R Z1 Z2 → + ∀I. Z1 = BUnit I → Z2 = BUnit I. +#R #Z1 #Z2 * -Z1 -Z2 #I [2: #V1 #V2 #_ ] +#J #H destruct // +qed-. + +lemma ext2_inv_unit_sn: ∀R,I,Z2. ext2 R (BUnit I) Z2 → Z2 = BUnit I. +/2 width=4 by ext2_inv_unit_sn_aux/ qed-. + +fact ext2_inv_pair_sn_aux: ∀R,Z1,Z2. ext2 R Z1 Z2 → + ∀I,V1. Z1 = BPair I V1 → + ∃∃V2. R V1 V2 & Z2 = BPair I V2. +#R #Z1 #Z2 * -Z1 -Z2 #I [2: #V1 #V2 #HV12 ] +#J #W1 #H destruct /2 width=3 by ex2_intro/ +qed-. + +lemma ext2_inv_pair_sn: ∀R,Z2,I,V1. ext2 R (BPair I V1) Z2 → + ∃∃V2. R V1 V2 & Z2 = BPair I V2. +/2 width=3 by ext2_inv_pair_sn_aux/ qed-. + +fact ext2_inv_unit_dx_aux: ∀R,Z1,Z2. ext2 R Z1 Z2 → + ∀I. Z2 = BUnit I → Z1 = BUnit I. +#R #Z1 #Z2 * -Z1 -Z2 #I [2: #V1 #V2 #_ ] +#J #H destruct // +qed-. + +lemma ext2_inv_unit_dx: ∀R,I,Z1. ext2 R Z1 (BUnit I) → Z1 = BUnit I. +/2 width=4 by ext2_inv_unit_dx_aux/ qed-. + +fact ext2_inv_pair_dx_aux: ∀R,Z1,Z2. ext2 R Z1 Z2 → + ∀I,V2. Z2 = BPair I V2 → + ∃∃V1. R V1 V2 & Z1 = BPair I V1. +#R #Z1 #Z2 * -Z1 -Z2 #I [2: #V1 #V2 #HV12 ] +#J #W2 #H destruct /2 width=3 by ex2_intro/ +qed-. + +lemma ext2_inv_pair_dx: ∀R,Z1,I,V2. ext2 R Z1 (BPair I V2) → + ∃∃V1. R V1 V2 & Z1 = BPair I V1. +/2 width=3 by ext2_inv_pair_dx_aux/ qed-. + +(* Basic properties ********************************************************) + +lemma ext2_refl: ∀R. reflexive … R → reflexive … (ext2 R). +#R #HR * /2 width=1 by ext2_pair/ +qed. + +lemma ext2_sym: ∀R. symmetric … R → symmetric … (ext2 R). +#R #HR #T1 #T2 * /3 width=1 by ext2_unit, ext2_pair/ +qed-. diff --git a/matita/matita/contribs/lambdadelta/basic_2/syntax/lenv_ext2.ma b/matita/matita/contribs/lambdadelta/basic_2/syntax/lenv_ext2.ma new file mode 100644 index 000000000..87795b548 --- /dev/null +++ b/matita/matita/contribs/lambdadelta/basic_2/syntax/lenv_ext2.ma @@ -0,0 +1,33 @@ +(**************************************************************************) +(* ___ *) +(* ||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/syntax/bind_ext2.ma". +include "basic_2/syntax/lenv.ma". + +(* EXTENSION TO BINDERS OF A CONTEXT-SENSITIVE RELATION FOR TERMS ***********) + +definition cext2: (lenv → relation term) → lenv → relation bind ≝ + λR,L. ext2 (R L). + +(* Basic properties *********************************************************) + +lemma cext2_sym: ∀R. (∀L1,L2,T1,T2. R L1 T1 T2 → R L2 T2 T1) → + ∀L1,L2,I1,I2. cext2 R L1 I1 I2 → cext2 R L2 I2 I1. +#R #HR #L1 #L2 #I1 #I2 * /3 width=2 by ext2_pair/ +qed-. + +lemma cext2_co: ∀R1,R2. (∀L,T1,T2. R1 L T1 T2 → R2 L T1 T2) → + ∀L,I1,I2. cext2 R1 L I1 I2 → cext2 R2 L I1 I2. +#R1 #R2 #HR #L #I1 #I2 * /3 width=2 by ext2_unit, ext2_pair/ +qed-. 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 bd75595b6..3a2a50c3e 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 @@ -253,12 +253,14 @@ table { } ] [ { "local environments" * } { + [ "lenv_ext2" * ] [ "lenv_length ( |?| )" * ] [ "lenv_weight ( ♯{?} )" * ] [ "lenv" * ] } ] [ { "binders for local environments" * } { + [ "bind_ext2" * ] [ "bind" "bind_weight" * ] } ] -- 2.39.2