@@("html/documentation.html#bibtex" "BibTeX entry") ^ "."
* }
]
+ [ { name "ldP3a" "<span class=\"emph alpha\">P3a.</span>" "" } {
+ "F. Guidi:" +
+ @@("download/ld_talk_10s.pdf"
+ "Adding Schematic Abstraction to λP") +
+ "(revised <span class=\"emph gamma\">2018-02</span>)." +
+ "Presentation at University of Bologna (slides)."
+ * }
+ ]
}
class "top" [ * ]
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/isidentity_2.ma".
+include "basic_2/static/frees.ma".
+
+(* FREE VARIABLES IDENTITY FOR RESTRICTED CLOSURES **************************)
+
+definition fid: relation2 … ≝ λL,T.
+ ∀f. L ⊢ 𝐅*⦃T⦄ ≡ f → 𝐈⦃f⦄.
+
+interpretation "free variables identity (restricted closure)"
+ 'IsIdentity L T = (fid L T).
+
+(* Basic properties *********************************************************)
+
+lemma fid_sort: ∀L,s. 𝐈⦃L, ⋆s⦄.
+/2 width=3 by frees_inv_sort/ qed.
+
+lemma fid_gref: ∀L,l. 𝐈⦃L, §l⦄.
+/2 width=3 by frees_inv_gref/ qed.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/fid.ma".
+include "basic_2/static/fle_fqup.ma".
+
+(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
+
+(* Properties with free variables identity for restricted closures **********)
+
+lemma fle_fid_sn: ∀L1,L2. |L1| = |L2| →
+ ∀T1,T2. 𝐈⦃L1, T1⦄ → ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄.
+#L1 #L2 #HL #T1 #T2 #HT1
+elim (frees_total L1 T1) #f1 #Hf1
+elim (frees_total L2 T2) #f2 #Hf2
+/4 width=8 by lveq_length_eq, sle_isid_sn, ex4_4_intro/
+qed.
+
+(* Inversion lemmas with free variables identity for restricted closures ****)
+
+lemma fle_inv_fid_dx: ∀L1,L2. |L1| = |L2| →
+ ∀T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ → 𝐈⦃L2, T2⦄ → 𝐈⦃L1, T1⦄.
+#L1 #L2 #HL #T1 #T2
+* #n1 #n2 #f1 #f2 #Hf1 #Hf2 #HL12 #Hf12 #HT2 #g1 #Hg1
+elim (lveq_inj_length … HL12) // -HL -HL12 #H1 #H2 destruct
+lapply (frees_mono … Hf1 … Hg1) -Hg1 #Hfg1
+/4 width=5 by sle_inv_isid_dx, isid_eq_repl_back/
+qed-.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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 L, break term 46 T ⦄ )"
+ non associative with precedence 45
+ for @{ 'IsIdentity $L $T }.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/lexs_length.ma".
+include "basic_2/static/frees_fqup.ma".
+include "basic_2/static/fid.ma".
+include "basic_2/static/lfeq.ma".
+
+(* SYNTACTIC EQUIVALENCE FOR LOCAL ENVIRONMENTS ON REFERRED ENTRIES *********)
+
+(* properties with free variables identity for restricted closures **********)
+
+lemma fid_lfeq: ∀L1,L2. |L1| = |L2| → ∀T. 𝐈⦃L1, T⦄ → L1 ≡[T] L2.
+#L1 #L2 #HL1 #T #HT
+elim (frees_total L1 T) #f #Hf
+/4 width=3 by lexs_length_isid, ex2_intro/
+qed.
+
+(* Advanced properties with free variables identity for restricted closures *)
+
+lemma fid_length: ∀L1,L2. |L1| = |L2| → ∀T. 𝐈⦃L1, T⦄ → 𝐈⦃L2, T⦄.
+#L1 #L2 #HL #T #HT #g #Hg
+elim (frees_total L1 T) #f #Hf
+lapply (frees_mono f … Hg) -Hg
+[ /3 width=4 by fid_lfeq, frees_lfeq_conf/
+| /3 width=3 by isid_eq_repl_back/
+]
+qed-.
\ No newline at end of file
--- /dev/null
+include "basic_2/static/frees_drops.ma".
+
+axiom frees_inv_drops_next_sle: ∀f1,L1,T1. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 → ∀f2. f1 ⊆ f2 →
+ ∀I2,L2,V2,n. ⬇*[n] L1 ≡ L2.ⓑ{I2}V2 →
+ ∀g1. ⫯g1 = ⫱*[n] f1 →
+ ∀g2. L2 ⊢ 𝐅*⦃V2⦄ ≡ g2 → ↑*[n]⫯g2 ⊆ f2.
+
+lemma frees_drops_next_sle: ∀f1,L1,T1. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 → ∀f2. (
+ ∀n. ⬇*[Ⓕ, 𝐔❴n❵] L1 ≡ ⋆ →
+ ∀g1. ⫯g1 = ⫱*[n] f1 →
+ ∀g2. 𝐈⦃g2⦄ → ↑*[n]⫯g2 ⊆ f2
+ ) → (
+ ∀I2,L2,V2,n. ⬇*[n] L1 ≡ L2.ⓑ{I2}V2 →
+ ∀g1. ⫯g1 = ⫱*[n] f1 →
+ ∀g2. L2 ⊢ 𝐅*⦃V2⦄ ≡ g2 → ↑*[n]⫯g2 ⊆ f2
+ ) → (
+ ∀I2,L2,n. ⬇*[n] L1 ≡ L2.ⓤ{I2} →
+ ∀g1. ⫯g1 = ⫱*[n] f1 →
+ ∀g2. 𝐈⦃g2⦄ → ↑*[n]⫯g2 ⊆ f2
+ ) → f1 ⊆ f2.
+#f1 #L1 #T1 #H @(frees_ind_void … H) -f1 -L1 -T1
+[ /2 width=1 by sle_isid_sn/
+| /2 width=2 by/
+| /3 width=5 by drops_refl/
+| /3 width=3 by drops_refl/
+| /6 width=5 by drops_drop, sle_inv_tl_dx, sle_px_tl/
+| /2 width=1 by sle_isid_sn/
+| #f1a #f1b #f1 #p #I1 #L1 #V1 #T1 #_ #_ #Hf1 #IHa #IHb #f2 #H1 #H2 #H3
+ lapply (sor_tls … Hf1) #Hn
+ @(sor_inv_sle … Hf1) -Hf1
+ [ @IHa -IHa -IHb [| #I2 #L2 #V2 | #I2 #L2 ] #n #HL #g1a #Hg1a #g2 #Hg2
+ lapply (Hn n) -Hn <Hg1a -Hg1a #H
+ elim (sor_nxx_tl … H) -H /2 width=5 by/
+ | @sle_xn_tl [2: |*: // ]
+ @IHb -IHa -IHb [| #I2 #L2 #V2 | #I2 #L2 ] * [1,3,5: |*: #n ] #HL #g1b #Hg1b #g2 #Hg2
+ [1,2,3:
+ lapply (drops_fwd_isid … HL ?) -HL // #H destruct -H1 -H2 -H3
+ /3 width=5 by sle_isid_sn, sle_next/
+ |4,5,6:
+ lapply (drops_inv_drop1 … HL) -HL #HL
+ lapply (Hn n) -Hn >tls_xn <Hg1b -Hg1b #H
+ elim (sor_xnx_tl … H) -H /3 width=5 by sle_weak/
+ ]
+ ]
+| #f1a #f1b #f1 #I1 #L1 #V1 #T1 #_ #_ #Hf1 #IHa #IHb #f2 #H1 #H2 #H3
+ lapply (sor_tls … Hf1) #H
+ @(sor_inv_sle … Hf1) -Hf1
+ [ @IHa -IHa -IHb [| #I2 #L2 #V2 | #I2 #L2 ] #n #HL #g1a #Hg1a #g2 #Hg2
+ lapply (H n) -H <Hg1a -Hg1a #H
+ elim (sor_nxx_tl … H) -H /2 width=5 by/
+ | @IHb -IHa -IHb [| #I2 #L2 #V2 | #I2 #L2 ] #n #HL #g1b #Hg1b #g2 #Hg2
+ lapply (H n) -H <Hg1b -Hg1b #H
+ elim (sor_xnx_tl … H) -H /2 width=5 by/
+ ]
+]
+qed-.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/fle_fqup.ma".
+include "basic_2/static/fle_fid.ma".
+include "basic_2/static/lfxs_length.ma".
+include "basic_2/static/lfxs_fqup.ma".
+include "basic_2/static/lfeq_fid.ma".
+
+(* Note: "⦃L2, T1⦄ ⊆ ⦃L0, T1⦄" may not hold *)
+definition R_lfxs_fle_compatible: predicate (relation3 …) ≝ λR.
+ ∀L0,T0,T1. R L0 T0 T1 →
+ ∀L2. L0 ⪤*[R, T0] L2 →
+ ∧∧ ⦃L2, T0⦄ ⊆ ⦃L0, T0⦄ & ⦃L2, T1⦄ ⊆ ⦃L2, T0⦄
+ & ⦃L0, T1⦄ ⊆ ⦃L0, T0⦄.
+
+axiom fle_inv_zero_bind_dx: ∀I,K,V,X. ⦃K.ⓑ{I}V, X⦄ ⊆ ⦃K.ⓑ{I}V, #O⦄ →
+ ∨∨ 𝐈⦃K.ⓑ{I}V, #O⦄ | ⦃K.ⓑ{I}V, X⦄ ⊆ ⦃K, V⦄.
+
+lemma fle_lfxs_conf_fle: ∀R. (* c_reflexive … R → *)
+ R_lfxs_fle_compatible R →
+ ∀L0,T0,T1. ⦃L0, T1⦄ ⊆ ⦃L0, T0⦄ →
+ ∀L2. L0 ⪤*[R, T0] L2 →
+ ∧∧ ⦃L2, T0⦄ ⊆ ⦃L0, T0⦄ & ⦃L2, T1⦄ ⊆ ⦃L2, T0⦄.
+#R #HR #L0 #T0 @(fqup_wf_ind_eq (Ⓕ) … (⋆) L0 T0) -L0 -T0
+#G #L #T #IH #G0 #L0 * *
+[ #s #HG #HL #HT #X #HX #Y #HY destruct -HR -IH
+ lapply (lfxs_fwd_length … HY) -HY #H0
+ lapply (fle_inv_fid_dx … HX ?) -HX
+ /4 width=6 by fle_sort_length, fid_length, fle_fid_sn, conj/
+| * [| #i ] #HG #HL #HT #X #HX #Y #HY destruct
+ [ elim (lfxs_inv_zero … HY) -HY *
+ [ #H1 #H2 destruct -IH /2 width=1 by conj/
+ | #I #K0 #K2 #V0 #V1 #HK02 #HV01 #H1 #H2 destruct -IH
+ elim (HR … HV01 … HK02) -HR -HV01 -HK02 #HKV1 #HKV2 #HKV3
+ @conj
+ [
+ |
+(*
+ elim H2R -H2R #H2R
+ [ <(H2R G0) in HV02; -H2R #HV02
+ elim (IH … HV02 … HK02) /2 width=2 by fqu_fqup, fqu_lref_O/ -IH -HV02 -HK02 #H1V #H2V #H3V
+ | lapply (H2R … HV02) -H2R -HV02 #HV20
+ elim (IH … V0 … HK02) [|*: /2 width=4 by fqu_fqup, fqu_lref_O/ ] -IH -HK02 #H1V #_ #_
+ ]
+ | #f #I #K0 #K2 #Hf #HK02 #H1 #H2 destruct
+ ]
+ | * #I0 #K0 #V0 #V1 #HV01 #HV1X #H destruct
+ elim (lfxs_inv_zero_pair_sn … HY) -HY #K2 #V2 #HK02 #HV02 #H destruct
+ ]
+ | elim (cpx_inv_lref1 … HX) -HX
+ [ #H destruct
+ elim (lfxs_inv_lref … HY) -HY *
+ [ #H0 #H1 destruct /2 width=1 by and3_intro/
+ | #I0 #I2 #K0 #K2 #HK02 #H1 #H2 destruct
+ lapply (lfxs_fwd_length … HK02) #HK
+ elim (IH … HK02) [|*: /2 width=4 by fqu_fqup/ ] -IH -HK02
+ /3 width=5 by and3_intro, fle_lifts_SO/
+ ]
+ | * #I0 #K0 #V1 #HV1 #HV1X #H0 destruct
+ elim (lfxs_inv_lref_bind_sn … HY) -HY #I2 #K2 #HK02 #H destruct
+ lapply (lfxs_fwd_length … HK02) #HK
+ elim (IH … HK02) [|*: /2 width=4 by fqu_fqup/ ] -IH -HV1 -HK02
+ /3 width=5 by fle_lifts_SO, and3_intro/
+ ]
+ ]
+| #l #HG #HL #HT #X #HX #Y #HY destruct -IH
+ lapply (lfxs_fwd_length … HY) -HY #H0
+ >(cpx_inv_gref1 … HX) -X
+ /3 width=1 by fle_gref_length, and3_intro/
+| #p #I #V0 #T0 #HG #HL #HT #X #HX #Y #HY destruct
+ lapply (lfxs_fwd_length … HY) #H0
+ elim (lfxs_inv_bind … V0 ? HY) -HY // #HV0 #HT0
+ elim (cpx_inv_bind1 … HX) -HX *
+ [ #V1 #T1 #HV01 #HT01 #H destruct
+ elim (IH … HV01 … HV0) -HV01 -HV0 // #H1V #H2V #H3V
+ elim (IH … HT01 … HT0) -HT01 -HT0 -IH // #H1T #H2T #H3T
+ /4 width=3 by fle_bind_eq, fle_fwd_pair_sn, and3_intro/
+ | #T #HT #HXT #H1 #H2 destruct
+ elim (IH G0 … V0… V0 … HV0) -HV0 // #H1V #H2V #H3V
+ elim (IH … HT … HT0) -HT -HT0 -IH // #H1T #H2T #H3T
+ /3 width=5 by fle_bind, fle_inv_lifts_sn, and3_intro/
+ ]
+| #I #V0 #X0 #HG #HL #HT #X #HX #Y #HY destruct
+ elim (lfxs_inv_flat … HY) -HY #HV0 #HX0
+ elim (cpx_inv_flat1 … HX) -HX *
+ [ #V1 #T1 #HV01 #HT01 #H destruct
+ elim (IH … HV01 … HV0) -HV01 -HV0 // #H1V #H2V #H3V
+ elim (IH … HT01 … HX0) -HT01 -HX0 -IH // #H1T #H2T #H3T
+ /3 width=3 by fle_flat, and3_intro/
+ | #HX #H destruct
+ elim (IH G0 … V0… V0 … HV0) -HV0 // #H1V #H2V #H3V
+ elim (IH … HX … HX0) -HX -HX0 -IH // #H1T #H2T #H3T
+ /4 width=3 by fle_flat_sn, fle_flat_dx_dx, fle_flat_dx_sn, and3_intro/
+ | #HX #H destruct
+ elim (IH … HX … HV0) -HX -HV0 // #H1V #H2V #H3V
+ elim (IH G0 … X0… X0 … HX0) -HX0 -IH // #H1T #H2T #H3T
+ /4 width=3 by fle_flat_sn, fle_flat_dx_dx, fle_flat_dx_sn, and3_intro/
+ | #p #V1 #W0 #W1 #T0 #T1 #HV01 #HW01 #HT01 #H1 #H2 #H3 destruct
+ elim (lfxs_inv_bind … W0 ? HX0) -HX0 // #HW0 #HT0
+ elim (IH … HV01 … HV0) -HV01 -HV0 // #H1V #H2V #H3V
+ elim (IH … HW01 … HW0) -HW01 -HW0 // #H1W #H2W #H3W
+ elim (IH … HT01 … HT0) -HT01 -HT0 -IH // #H1T #H2T #H3T
+ lapply (fle_fwd_pair_sn … H2T) -H2T #H2T
+ lapply (fle_fwd_pair_sn … H3T) -H3T #H3T
+ @and3_intro [ /3 width=5 by fle_flat, fle_bind/ ] (**) (* full auto too slow *)
+ @fle_bind_sn_ge /4 width=1 by fle_shift, fle_flat_sn, fle_flat_dx_dx, fle_flat_dx_sn, fle_bind_dx_sn/
+ | #p #V1 #X1 #W0 #W1 #T0 #T1 #HV01 #HVX1 #HW01 #HT01 #H1 #H2 #H3 destruct
+ elim (lfxs_inv_bind … W0 ? HX0) -HX0 // #HW0 #HT0
+ elim (IH … HV01 … HV0) -HV01 -HV0 // #H1V #H2V #H3V
+ elim (IH … HW01 … HW0) -HW01 -HW0 // #H1W #H2W #H3W
+ elim (IH … HT01 … HT0) -HT01 -HT0 -IH // #H1T #H2T #H3T
+ lapply (fle_fwd_pair_sn … H2T) -H2T #H2T
+ lapply (fle_fwd_pair_sn … H3T) -H3T #H3T
+ @and3_intro[ /3 width=5 by fle_flat, fle_bind/ ] (**) (* full auto too slow *)
+ @fle_bind_sn_ge //
+ [1,3: /3 width=1 by fle_flat_dx_dx, fle_bind_dx_sn/
+ |2,4: /4 width=3 by fle_flat_sn, fle_flat_dx_sn, fle_flat_dx_dx, fle_shift, fle_lifts_sn/
+ ]
+ ]
+]
+*)
(* Note: s_rs_transitive_lex_inv_isid could be invoked in the last auto but makes it too slow *)
lemma tc_lfxs_inv_lex_lfeq: ∀R. c_reflexive … R →
- lfxs_fle_compatible R →
+ lfxs_fsle_compatible R →
s_rs_transitive … R (λ_.lex R) →
lfeq_transitive R →
∀L1,L2,T. L1 ⪤**[R, T] L2 →
(* Advanced properties ******************************************************)
-lemma tc_lfxs_sym: ∀R. lfxs_fle_compatible R →
+lemma tc_lfxs_sym: ∀R. lfxs_fsle_compatible R →
(∀L1,L2,T1,T2. R L1 T1 T2 → R L2 T2 T1) →
∀T. symmetric … (tc_lfxs R T).
#R #H1R #H2R #T #L1 #L2 #H elim H -L2
(* *)
(**************************************************************************)
+include "ground_2/relocation/rtmap_id.ma".
include "basic_2/syntax/ext2_tc.ma".
include "basic_2/relocation/lexs_tc.ma".
include "basic_2/relocation/lex.ma".
+alias symbol "subseteq" = "relation inclusion".
+
(* GENERIC EXTENSION OF A CONTEXT-SENSITIVE REALTION FOR TERMS **************)
(* Inversion lemmas with transitive closure *********************************)
+(* Basic_2A1: was: lpx_sn_LTC_TC_lpx_sn *)
+lemma lex_inv_ltc: ∀R. c_reflexive … R →
+ lex (LTC … R) ⊆ TC … (lex R).
+#R #HR #L1 #L2 *
+/5 width=11 by lexs_inv_tc_dx, lexs_co, ext2_inv_tc, ext2_refl, monotonic_TC, ex2_intro/
+qed-.
+
lemma s_rs_transitive_lex_inv_isid: ∀R. s_rs_transitive … R (λ_.lex R) →
s_rs_transitive_isid cfull (cext2 R).
#R #HR #f #Hf #L2 #T1 #T2 #H #L1 #HL12
@(HR … HV12) -HV12 /2 width=3 by ex2_intro/ (**) (* auto fails *)
]
qed-.
+
+(* Properties with transitive closure ***************************************)
+
+(* Basic_2A1: was: TC_lpx_sn_inv_lpx_sn_LTC *)
+lemma lex_ltc: ∀R. s_rs_transitive … R (λ_. lex R) →
+ TC … (lex R) ⊆ lex (LTC … R).
+#R #HR #L1 #L2 #HL12
+lapply (monotonic_TC … (lexs cfull (cext2 R) 𝐈𝐝) … HL12) -HL12
+[ #L1 #L2 * /3 width=3 by lexs_eq_repl_fwd, eq_id_inv_isid/
+| /5 width=9 by s_rs_transitive_lex_inv_isid, lexs_tc_dx, lexs_co, ext2_tc, ex2_intro/
+]
+qed-.
+
elim (pn_split f) * #g #H destruct /3 width=1 by lexs_next, lexs_push/
]
qed.
+
+lemma lexs_length_isid: ∀R,L1,L2. |L1| = |L2| →
+ ∀f. 𝐈⦃f⦄ → L1 ⪤*[R, cfull, f] L2.
+#R #L1 elim L1 -L1
+[ #Y2 #H >(length_inv_zero_sn … H) -Y2 //
+| #L1 #I1 #IH #Y2 #H #f #Hf
+ elim (length_inv_succ_sn … H) -H #I2 #L2 #HL12 #H destruct
+ elim (isid_inv_gen … Hf) -Hf #g #Hg #H destruct /3 width=1 by lexs_push/
+]
+qed.
(* Advanced properties ******************************************************)
-(* Basic_2A1: uses: TC_lpx_sn_inv_lpx_sn_LTC *)
lemma lexs_tc_dx: ∀RN,RP. s_rs_transitive_isid RN RP →
∀f. 𝐈⦃f⦄ → ∀L1,L2. TC … (lexs RN RP f) L1 L2 → L1 ⪤*[RN, LTC … RP, f] L2.
#RN #RP #HRP #f #Hf #L1 #L2 #H @(TC_ind_dx ??????? H) -L1
/2 width=1 by lexs_tc_next, lexs_tc_push_sn, lexs_atom, inj/
qed-.
-(* Basic_2A1: uses: lpx_sn_LTC_TC_lpx_sn *)
lemma lexs_inv_tc_dx: ∀RN,RP. c_reflexive … RN → c_reflexive … RP →
∀f,L1,L2. L1 ⪤*[RN, LTC … RP, f] L2 → TC … (lexs RN RP f) L1 L2.
#RN #RP #HRN #HRP #f #L1 #L2 #H elim H -f -L1 -L2
#R #HR #L #T1 #T2 #H elim H -T2
/3 width=3 by fle_trans_dx/
qed-.
+
lemma lfpxs_cpx_conf: ∀h,G. s_r_confluent1 … (cpx h G) (lfpxs h G).
#h #G #L1 #T1 #T2 #HT12 #L2 #H
elim (tc_lfxs_inv_lex_lfeq … H) -H #L #HL1 #HL2
--- /dev/null
+
+include "basic_2/static/lfxs_lex.ma".
+include "basic_2/rt_transition/cpx_etc.ma".
+include "basic_2/rt_computation/lfpxs_lpxs.ma".
+
+axiom fle_trans: ∀L1,L,T1,T. ⦃L1, T1⦄ ⊆ ⦃L, T⦄ →
+ ∀L2,T2. ⦃L, T⦄ ⊆ ⦃L2, T2⦄ → ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄.
+
+axiom pippo: ∀h,G,L1,T1,T2. ⦃G, L1⦄ ⊢ T1 ⬈[h] T2 → ∀L. ⦃G, L1⦄ ⊢⬈[h] L →
+ ∧∧ ⦃L, T1⦄ ⊆ ⦃L1, T1⦄ & ⦃L, T2⦄ ⊆ ⦃L, T1⦄ & ⦃L1, T2⦄ ⊆ ⦃L1, T1⦄.
+(*
+lemma pippos: ∀h,G,L1,L. ⦃G, L1⦄ ⊢⬈*[h] L → ∀T1,T2. ⦃G, L1⦄ ⊢ T1 ⬈[h] T2 →
+ ∧∧ ⦃L, T1⦄ ⊆ ⦃L1, T1⦄ & ⦃L, T2⦄ ⊆ ⦃L, T1⦄.
+#h #G #L1 #L #H
+lapply (lex_inv_ltc … H) -H // #H
+@(TC_star_ind ???????? H) -L //
+[ #T1 #T2 #H elim (pippo … H) -H /2 width=3 by conj/
+| #L #L0 #HL1 #HL0 #IH #T1 #T2 #HT12
+ elim (IH … HT12) -IH #HT1 #HT21
+ elim (pippo … T1 T1 … HL0) // #H1 #_ #_
+ @conj
+ [ @(fle_trans … H1) //
+
+*)(*
+lemma pippos: ∀h,G,L1,L. ⦃G, L1⦄ ⊢⬈*[h] L → ∀T1,T2. ⦃G, L1⦄ ⊢ T1 ⬈[h] T2 →
+ ∧∧ ⦃L, T1⦄ ⊆ ⦃L1, T1⦄ & ⦃L, T2⦄ ⊆ ⦃L, T1⦄ & ⦃L1, T2⦄ ⊆ ⦃L1, T1⦄.
+#h #G #L1 #L #H
+lapply (lex_inv_ltc … H) -H // #H
+@(TC_star_ind_dx ???????? H) -L1 /2 width=5 by pippo/
+#L1 #L0 #HL10 #HL0 #IH #T1 #T2 #HT12
+elim (IH … HT12) -IH #HT1 #HT21 #H1T21
+@and3_intro
+[2:
+*)
+
+axiom pippos: ∀h,G,L1,L. ⦃G, L1⦄ ⊢⬈*[h] L → ∀T1,T2. ⦃G, L1⦄ ⊢ T1 ⬈[h] T2 →
+ ∃∃T. ⦃G, L⦄ ⊢ T1 ⬈[h] T & ⦃L, T2⦄ ⊆ ⦃L, T⦄.
+
+lemma fle_tc_lfxs_trans: ∀h,G,L1,L2,T1. ⦃G, L1⦄ ⊢⬈*[h, T1] L2 →
+ ∀T2. ⦃L1, T2⦄ ⊆ ⦃L1, T1⦄ → ⦃G, L1⦄ ⊢⬈* [h, T2] L2.
+#h #G #L1 #L2 #T1 #H
+@(TC_star_ind_dx ???????? H) -L1 /2 width=1 by tc_lfxs_refl, lfxs_refl/
+#L1 #L #HL1 #_ #IH #T2 #HT21
+lapply (fle_lfxs_trans … HT21 … HL1) -HL1 #HL1
+@(TC_strap … HL1) @IH -IH
+
+
+lemma lfpxs_cpx_conf: ∀h,G. s_r_confluent1 … (cpx h G) (lfpxs h G).
+#h #G #L1 #T1 #T2 #HT12 #L2 #H
+lapply (cpx_fle_comp … HT12) -HT12 #HT21
+
+elim (tc_lfxs_inv_lex_lfeq … H) -H #L #HL1 #HL2
+@(lfpxs_lpxs_lfeq … HL1) -HL1
+
+
+@(fle_lfxs_trans
+
+elim (pippos … HL1 … HT12) -HT12 #T #H #HT21
+@(lfpxs_lpxs_lfeq … HL1) -HL1
+@(fle_lfxs_trans … HL2) -HL2 //
+qed-.
+
+
lemma tc_lfxs_inv_lex_lfeq: ∀h,G,L1,L2,T. ⦃G, L1⦄ ⊢ ⬈*[h, T] L2 →
∃∃L. ⦃G, L1⦄ ⊢ ⬈*[h] L & L ≡[T] L2.
-/3 width=5 by lfpx_fle_comp, lpx_cpxs_trans, lfeq_cpx_trans, tc_lfxs_inv_lex_lfeq/ qed-.
+/3 width=5 by lfpx_fsle_comp, lpx_cpxs_trans, lfeq_cpx_trans, tc_lfxs_inv_lex_lfeq/ qed-.
(* Properties with context-sensitive free variables *************************)
-lemma cpm_fle_comp: ∀n,h,G. R_fle_compatible (cpm n h G).
-/3 width=6 by cpm_fwd_cpx, cpx_fle_comp/ qed-.
+lemma cpm_fsle_comp: ∀n,h,G. R_fsle_compatible (cpm n h G).
+/3 width=6 by cpm_fwd_cpx, cpx_fsle_comp/ qed-.
-lemma lfpr_fle_comp: ∀h,G. lfxs_fle_compatible (cpm 0 h G).
-/4 width=5 by cpm_fwd_cpx, lfpx_fle_comp, lfxs_co/ qed-.
+lemma lfpr_fsle_comp: ∀h,G. lfxs_fsle_compatible (cpm 0 h G).
+/4 width=5 by cpm_fwd_cpx, lfpx_fsle_comp, lfxs_co/ qed-.
(* Properties with generic extension on referred entries ********************)
(* *)
(**************************************************************************)
-include "basic_2/static/fle_drops.ma".
-include "basic_2/static/fle_fqup.ma".
-include "basic_2/static/fle_fle.ma".
+include "basic_2/static/fsle_drops.ma".
+include "basic_2/static/fsle_fqup.ma".
+include "basic_2/static/fsle_fsle.ma".
include "basic_2/static/lfxs_length.ma".
+include "basic_2/static/lfxs_fsle.ma".
include "basic_2/rt_transition/cpx.ma".
-
-lemma fle_zero_bi: ∀K1,K2. |K1| = |K2| → ∀V1,V2. ⦃K1, V1⦄ ⊆ ⦃K2, V2⦄ →
- ∀I1,I2. ⦃K1.ⓑ{I1}V1, #O⦄ ⊆ ⦃K2.ⓑ{I2}V2, #O⦄.
-#K1 #K2 #HK #V1 #V2
-* #n1 #n2 #f1 #f2 #Hf1 #Hf2 #HK12 #Hf12
-#I1 #I2
-elim (lveq_inj_length … HK12) // -HK #H1 #H2 destruct
-/3 width=12 by frees_pair, lveq_bind, sle_next, ex4_4_intro/
-qed.
-
(* UNCOUNTED CONTEXT-SENSITIVE PARALLEL RT-TRANSITION FOR TERMS *************)
(* Properties with context-sensitive free variables *************************)
(* Note: "⦃L2, T1⦄ ⊆ ⦃L0, T1⦄" may not hold *)
-axiom cpx_lfxs_conf_fle: ∀R,h. c_reflexive … R →
- (∨∨ (∀G. (cpx h G) = R) | R_fle_compatible R) →
- ∀G,L0,T0,T1. ⦃G, L0⦄ ⊢ T0 ⬈[h] T1 →
- ∀L2. L0 ⪤*[R, T0] L2 →
- ∧∧ ⦃L2, T0⦄ ⊆ ⦃L0, T0⦄ & ⦃L2, T1⦄ ⊆ ⦃L2, T0⦄
- & ⦃L0, T1⦄ ⊆ ⦃L0, T0⦄.
+axiom cpx_lfxs_conf_fsle: ∀R,h. c_reflexive … R →
+ (∨∨ (∀G. (cpx h G) = R) | R_fsle_compatible R) →
+ ∀G,L0,T0,T1. ⦃G, L0⦄ ⊢ T0 ⬈[h] T1 →
+ ∀L2. L0 ⪤*[R, T0] L2 →
+ ∧∧ ⦃L2, T0⦄ ⊆ ⦃L0, T0⦄ & ⦃L2, T1⦄ ⊆ ⦃L2, T0⦄
+ & ⦃L0, T1⦄ ⊆ ⦃L0, T0⦄.
(*
#R #h #H1R #H2R #G #L0 #T0 @(fqup_wf_ind_eq (Ⓕ) … G L0 T0) -G -L0 -T0
#G #L #T #IH #G0 #L0 * *
[ #s #HG #HL #HT #X #HX #Y #HY destruct -IH
lapply (lfxs_fwd_length … HY) -HY #H0
elim (cpx_inv_sort1 … HX) -HX #H destruct
- /3 width=1 by fle_sort_length, and3_intro/
+ /3 width=1 by fsle_sort_length, and3_intro/
| * [| #i ] #HG #HL #HT #X #HX #Y #HY destruct
[ elim (cpx_inv_zero1 … HX) -HX
[ #H destruct
elim H2R -H2R #H2R
[ <(H2R G0) in HV02; -H2R #HV02
elim (IH … HV02 … HK02) /2 width=2 by fqu_fqup, fqu_lref_O/ -IH -HV02 -HK02 #H1V #H2V #_
- /4 width=1 by fle_trans_tc, fle_zero_bi, and3_intro/
+ /4 width=1 by fsle_trans_tc, fsle_zero_bi, and3_intro/
| lapply (H2R … HV02 … HK02) -H2R -HV02 -HK02 -IH #HKV20
- /3 width=1 by fle_zero_bi, and3_intro/
+ /3 width=1 by fsle_zero_bi, and3_intro/
]
| #f #I #K0 #K2 #Hf #HK02 #H1 #H2 destruct
]
| #I0 #I2 #K0 #K2 #HK02 #H1 #H2 destruct
lapply (lfxs_fwd_length … HK02) #HK
elim (IH … HK02) [|*: /2 width=4 by fqu_fqup/ ] -IH -HK02
- /3 width=5 by and3_intro, fle_lifts_SO/
+ /3 width=5 by and3_intro, fsle_lifts_SO/
]
| * #I0 #K0 #V1 #HV1 #HV1X #H0 destruct
elim (lfxs_inv_lref_bind_sn … HY) -HY #I2 #K2 #HK02 #H destruct
lapply (lfxs_fwd_length … HK02) #HK
elim (IH … HK02) [|*: /2 width=4 by fqu_fqup/ ] -IH -HV1 -HK02
- /3 width=5 by fle_lifts_SO, and3_intro/
+ /3 width=5 by fsle_lifts_SO, and3_intro/
]
]
| #l #HG #HL #HT #X #HX #Y #HY destruct -IH
lapply (lfxs_fwd_length … HY) -HY #H0
>(cpx_inv_gref1 … HX) -X
- /3 width=1 by fle_gref_length, and3_intro/
+ /3 width=1 by fsle_gref_length, and3_intro/
| #p #I #V0 #T0 #HG #HL #HT #X #HX #Y #HY destruct
lapply (lfxs_fwd_length … HY) #H0
elim (lfxs_inv_bind … V0 ? HY) -HY // #HV0 #HT0
[ #V1 #T1 #HV01 #HT01 #H destruct
elim (IH … HV01 … HV0) -HV01 -HV0 // #H1V #H2V #H3V
elim (IH … HT01 … HT0) -HT01 -HT0 -IH // #H1T #H2T #H3T
- /4 width=3 by fle_bind_eq, fle_fwd_pair_sn, and3_intro/
+ /4 width=3 by fsle_bind_eq, fsle_fwd_pair_sn, and3_intro/
| #T #HT #HXT #H1 #H2 destruct
elim (IH G0 … V0… V0 … HV0) -HV0 // #H1V #H2V #H3V
elim (IH … HT … HT0) -HT -HT0 -IH // #H1T #H2T #H3T
- /3 width=5 by fle_bind, fle_inv_lifts_sn, and3_intro/
+ /3 width=5 by fsle_bind, fsle_inv_lifts_sn, and3_intro/
]
| #I #V0 #X0 #HG #HL #HT #X #HX #Y #HY destruct
elim (lfxs_inv_flat … HY) -HY #HV0 #HX0
[ #V1 #T1 #HV01 #HT01 #H destruct
elim (IH … HV01 … HV0) -HV01 -HV0 // #H1V #H2V #H3V
elim (IH … HT01 … HX0) -HT01 -HX0 -IH // #H1T #H2T #H3T
- /3 width=3 by fle_flat, and3_intro/
+ /3 width=3 by fsle_flat, and3_intro/
| #HX #H destruct
elim (IH G0 … V0… V0 … HV0) -HV0 // #H1V #H2V #H3V
elim (IH … HX … HX0) -HX -HX0 -IH // #H1T #H2T #H3T
- /4 width=3 by fle_flat_sn, fle_flat_dx_dx, fle_flat_dx_sn, and3_intro/
+ /4 width=3 by fsle_flat_sn, fsle_flat_dx_dx, fsle_flat_dx_sn, and3_intro/
| #HX #H destruct
elim (IH … HX … HV0) -HX -HV0 // #H1V #H2V #H3V
elim (IH G0 … X0… X0 … HX0) -HX0 -IH // #H1T #H2T #H3T
- /4 width=3 by fle_flat_sn, fle_flat_dx_dx, fle_flat_dx_sn, and3_intro/
+ /4 width=3 by fsle_flat_sn, fsle_flat_dx_dx, fsle_flat_dx_sn, and3_intro/
| #p #V1 #W0 #W1 #T0 #T1 #HV01 #HW01 #HT01 #H1 #H2 #H3 destruct
elim (lfxs_inv_bind … W0 ? HX0) -HX0 // #HW0 #HT0
elim (IH … HV01 … HV0) -HV01 -HV0 // #H1V #H2V #H3V
elim (IH … HW01 … HW0) -HW01 -HW0 // #H1W #H2W #H3W
elim (IH … HT01 … HT0) -HT01 -HT0 -IH // #H1T #H2T #H3T
- lapply (fle_fwd_pair_sn … H2T) -H2T #H2T
- lapply (fle_fwd_pair_sn … H3T) -H3T #H3T
- @and3_intro [ /3 width=5 by fle_flat, fle_bind/ ] (**) (* full auto too slow *)
- @fle_bind_sn_ge /4 width=1 by fle_shift, fle_flat_sn, fle_flat_dx_dx, fle_flat_dx_sn, fle_bind_dx_sn/
+ lapply (fsle_fwd_pair_sn … H2T) -H2T #H2T
+ lapply (fsle_fwd_pair_sn … H3T) -H3T #H3T
+ @and3_intro [ /3 width=5 by fsle_flat, fsle_bind/ ] (**) (* full auto too slow *)
+ @fsle_bind_sn_ge /4 width=1 by fsle_shift, fsle_flat_sn, fsle_flat_dx_dx, fsle_flat_dx_sn, fsle_bind_dx_sn/
| #p #V1 #X1 #W0 #W1 #T0 #T1 #HV01 #HVX1 #HW01 #HT01 #H1 #H2 #H3 destruct
elim (lfxs_inv_bind … W0 ? HX0) -HX0 // #HW0 #HT0
elim (IH … HV01 … HV0) -HV01 -HV0 // #H1V #H2V #H3V
elim (IH … HW01 … HW0) -HW01 -HW0 // #H1W #H2W #H3W
elim (IH … HT01 … HT0) -HT01 -HT0 -IH // #H1T #H2T #H3T
- lapply (fle_fwd_pair_sn … H2T) -H2T #H2T
- lapply (fle_fwd_pair_sn … H3T) -H3T #H3T
- @and3_intro[ /3 width=5 by fle_flat, fle_bind/ ] (**) (* full auto too slow *)
- @fle_bind_sn_ge //
- [1,3: /3 width=1 by fle_flat_dx_dx, fle_bind_dx_sn/
- |2,4: /4 width=3 by fle_flat_sn, fle_flat_dx_sn, fle_flat_dx_dx, fle_shift, fle_lifts_sn/
+ lapply (fsle_fwd_pair_sn … H2T) -H2T #H2T
+ lapply (fsle_fwd_pair_sn … H3T) -H3T #H3T
+ @and3_intro[ /3 width=5 by fsle_flat, fsle_bind/ ] (**) (* full auto too slow *)
+ @fsle_bind_sn_ge //
+ [1,3: /3 width=1 by fsle_flat_dx_dx, fsle_bind_dx_sn/
+ |2,4: /4 width=3 by fsle_flat_sn, fsle_flat_dx_sn, fsle_flat_dx_dx, fsle_shift, fsle_lifts_sn/
]
]
]
include "basic_2/relocation/drops_lexs.ma".
include "basic_2/static/frees_drops.ma".
include "basic_2/static/lsubf_frees.ma".
-include "basic_2/static/lfxs.ma".
+include "basic_2/static/lfxs_fsle.ma".
include "basic_2/rt_transition/cpx_drops.ma".
include "basic_2/rt_transition/cpx_ext.ma".
qed-.
(* Basic_2A1: uses: cpx_frees_trans *)
-lemma cpx_fle_comp: ∀h,G. R_fle_compatible (cpx h G).
+lemma cpx_fsle_comp: ∀h,G. R_fsle_compatible (cpx h G).
#h #G #L #T1 #T2 #HT12
elim (frees_total L T1) #f1 #Hf1
elim (cpx_frees_conf_lexs … Hf1 L … HT12) -HT12
qed-.
(* Basic_2A1: uses: lpx_frees_trans *)
-lemma lfpx_fle_comp: ∀h,G. lfxs_fle_compatible (cpx h G).
+lemma lfpx_fsle_comp: ∀h,G. lfxs_fsle_compatible (cpx h G).
#h #G #L1 #L2 #T * #f1 #Hf1 #HL12
elim (cpx_frees_conf_lexs h … Hf1 … HL12 T) // #f2 #Hf2
lapply (lexs_fwd_length … HL12)
(* Main properties **********************************************************)
theorem lfpr_conf: ∀h,G,T. confluent … (lfpr h G T).
-/3 width=6 by cpr_conf_lfpr, lfpr_fle_comp, lfxs_conf/ qed-.
+/3 width=6 by cpr_conf_lfpr, lfpr_fsle_comp, lfxs_conf/ qed-.
theorem lfpr_bind: ∀h,G,L1,L2,V1. ⦃G, L1⦄ ⊢ ➡[h, V1] L2 →
∀I,V2,T. ⦃G, L1.ⓑ{I}V1⦄ ⊢ ➡[h, T] L2.ⓑ{I}V2 →
lemma lfpx_pair_sn_split: ∀h,G,L1,L2,V. ⦃G, L1⦄ ⊢ ⬈[h, V] L2 → ∀o,I,T.
∃∃L. ⦃G, L1⦄ ⊢ ⬈[h, ②{I}V.T] L & L ≛[h, o, V] L2.
-/3 width=5 by lfpx_fle_comp, lfxs_pair_sn_split/ qed-.
+/3 width=5 by lfpx_fsle_comp, lfxs_pair_sn_split/ qed-.
lemma lfpx_flat_dx_split: ∀h,G,L1,L2,T. ⦃G, L1⦄ ⊢ ⬈[h, T] L2 → ∀o,I,V.
∃∃L. ⦃G, L1⦄ ⊢ ⬈[h, ⓕ{I}V.T] L & L ≛[h, o, T] L2.
-/3 width=5 by lfpx_fle_comp, lfxs_flat_dx_split/ qed-.
+/3 width=5 by lfpx_fsle_comp, lfxs_flat_dx_split/ qed-.
lemma lfpx_bind_dx_split: ∀h,I,G,L1,L2,V1,T. ⦃G, L1.ⓑ{I}V1⦄ ⊢ ⬈[h, T] L2 → ∀o,p.
∃∃L,V. ⦃G, L1⦄ ⊢ ⬈[h, ⓑ{p,I}V1.T] L & L.ⓑ{I}V ≛[h, o, T] L2 & ⦃G, L1⦄ ⊢ V1 ⬈[h] V.
-/3 width=5 by lfpx_fle_comp, lfxs_bind_dx_split/ qed-.
+/3 width=5 by lfpx_fsle_comp, lfxs_bind_dx_split/ qed-.
lemma lfpx_bind_dx_split_void: ∀h,G,K1,L2,T. ⦃G, K1.ⓧ⦄ ⊢ ⬈[h, T] L2 → ∀o,p,I,V.
∃∃K2. ⦃G, K1⦄ ⊢ ⬈[h, ⓑ{p,I}V.T] K2 & K2.ⓧ ≛[h, o, T] L2.
-/3 width=5 by lfpx_fle_comp, lfxs_bind_dx_split_void/ qed-.
+/3 width=5 by lfpx_fsle_comp, lfxs_bind_dx_split_void/ qed-.
lemma cpx_tdeq_conf_lexs: ∀h,o,G. R_confluent2_lfxs … (cpx h G) (cdeq h o) (cpx h G) (cdeq h o).
#h #o #G #L0 #T0 #T1 #H @(cpx_ind … H) -G -L0 -T0 -T1 /2 width=3 by ex2_intro/
qed-.
lemma lfpx_lfdeq_conf: ∀h,o,G,T. confluent2 … (lfpx h G T) (lfdeq h o T).
-/3 width=6 by lfpx_fle_comp, lfdeq_fle_comp, cpx_tdeq_conf_lexs, lfxs_conf/ qed-.
+/3 width=6 by lfpx_fsle_comp, lfdeq_fsle_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 →
(* *)
(**************************************************************************)
-include "ground_2/relocation/rtmap_id.ma".
-include "basic_2/notation/relations/subseteq_4.ma".
-include "basic_2/syntax/lveq.ma".
-include "basic_2/static/frees.ma".
+include "basic_2/static/fsle.ma".
-(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
+(* FREE VARIABLES INCLUSION FOR TERMS ***************************************)
-definition fle: bi_relation lenv term ≝ λL1,T1,L2,T2.
- ∃∃n1,n2,f1,f2. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 & L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 &
- L1 ≋ⓧ*[n1, n2] L2 & ⫱*[n1]f1 ⊆ ⫱*[n2]f2.
-
-interpretation "free variables inclusion (restricted closure)"
- 'SubSetEq L1 T1 L2 T2 = (fle L1 T1 L2 T2).
-
-(* Basic properties *********************************************************)
-
-lemma fle_sort: ∀L,s1,s2. ⦃L, ⋆s1⦄ ⊆ ⦃L, ⋆s2⦄.
-/3 width=8 by frees_sort, sle_refl, ex4_4_intro/ qed.
-
-lemma fle_gref: ∀L,l1,l2. ⦃L, §l1⦄ ⊆ ⦃L, §l2⦄.
-/3 width=8 by frees_gref, sle_refl, ex4_4_intro/ qed.
+interpretation "free variables inclusion (term)"
+ 'subseteq T1 T2 = (fsle LAtom T1 LAtom T2).
+++ /dev/null
-(**************************************************************************)
-(* ___ *)
-(* ||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/lveq_length.ma".
-include "basic_2/static/frees_drops.ma".
-include "basic_2/static/fle.ma".
-
-(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
-
-(* Advanced properties ******************************************************)
-
-lemma fle_lifts_sn: ∀T1,U1. ⬆*[1] T1 ≡ U1 → ∀L1,L2. |L2| ≤ |L1| →
- ∀T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ → ⦃L1.ⓧ, U1⦄ ⊆ ⦃L2, T2⦄.
-#T1 #U1 #HTU1 #L1 #L2 #H1L #T2
-* #n #m #f #g #Hf #Hg #H2L #Hfg
-lapply (lveq_length_fwd_dx … H2L ?) // -H1L #H destruct
-lapply (frees_lifts_SO (Ⓣ) (L1.ⓧ) … HTU1 … Hf)
-[ /3 width=4 by drops_refl, drops_drop/ ] -T1 #Hf
-@(ex4_4_intro … Hf Hg) /2 width=4 by lveq_void_sn/ (**) (* explict constructor *)
-qed-.
-
-lemma fle_lifts_SO: ∀K1,K2. |K1| = |K2| → ∀T1,T2. ⦃K1, T1⦄ ⊆ ⦃K2, T2⦄ →
- ∀U1,U2. ⬆*[1] T1 ≡ U1 → ⬆*[1] T2 ≡ U2 →
- ∀I1,I2. ⦃K1.ⓘ{I1}, U1⦄ ⊆ ⦃K2.ⓘ{I2}, U2⦄.
-#K1 #K2 #HK #T1 #T2
-* #n1 #n2 #f1 #f2 #Hf1 #Hf2 #HK12 #Hf12
-#U1 #U2 #HTU1 #HTU2 #I1 #I2
-elim (lveq_inj_length … HK12) // -HK #H1 #H2 destruct
-/5 width=12 by frees_lifts_SO, drops_refl, drops_drop, lveq_bind, sle_push, ex4_4_intro/
-qed.
-
-(* Advanced inversion lemmas ************************************************)
-
-lemma fle_inv_lifts_sn: ∀T1,U1. ⬆*[1] T1 ≡ U1 →
- ∀I1,I2,L1,L2,V1,V2,U2. ⦃L1.ⓑ{I1}V1,U1⦄ ⊆ ⦃L2.ⓑ{I2}V2, U2⦄ →
- ∀p. ⦃L1, T1⦄ ⊆ ⦃L2, ⓑ{p,I2}V2.U2⦄.
-#T1 #U1 #HTU1 #I1 #I2 #L1 #L2 #V1 #V2 #U2
-* #n #m #f2 #g2 #Hf2 #Hg2 #HL #Hfg2 #p
-elim (lveq_inv_pair_pair … HL) -HL #HL #H1 #H2 destruct
-elim (frees_total L2 V2) #g1 #Hg1
-elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
-lapply (frees_inv_lifts_SO (Ⓣ) … Hf2 … HTU1)
-[1,2: /3 width=4 by drops_refl, drops_drop/ ] -U1 #Hf2
-lapply (sor_inv_sle_dx … Hg) #H0g
-/5 width=10 by frees_bind, sle_tl, sle_trans, ex4_4_intro/
-qed-.
+++ /dev/null
-(**************************************************************************)
-(* ___ *)
-(* ||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/lveq_lveq.ma".
-include "basic_2/static/fle_fqup.ma".
-
-(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
-
-(* Advanced inversion lemmas ************************************************)
-
-lemma fle_frees_trans: ∀L1,L2,T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ →
- ∀f2. L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 →
- ∃∃n1,n2,f1. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 &
- L1 ≋ⓧ*[n1, n2] L2 & ⫱*[n1]f1 ⊆ ⫱*[n2]f2.
-#L1 #L2 #T1 #T2 * #n1 #n2 #f1 #g2 #Hf1 #Hg2 #HL #Hn #f2 #Hf2
-lapply (frees_mono … Hg2 … Hf2) -Hg2 -Hf2 #Hgf2
-lapply (tls_eq_repl n2 … Hgf2) -Hgf2 #Hgf2
-lapply (sle_eq_repl_back2 … Hn … Hgf2) -g2
-/2 width=6 by ex3_3_intro/
-qed-.
-
-lemma fle_frees_trans_eq: ∀L1,L2. |L1| = |L2| →
- ∀T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ → ∀f2. L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 →
- ∃∃f1. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 & f1 ⊆ f2.
-#L1 #L2 #H1L #T1 #T2 #H2L #f2 #Hf2
-elim (fle_frees_trans … H2L … Hf2) -T2 #n1 #n2 #f1 #Hf1 #H2L #Hf12
-elim (lveq_inj_length … H2L) // -L2 #H1 #H2 destruct
-/2 width=3 by ex2_intro/
-qed-.
-
-(* Main properties **********************************************************)
-
-theorem fle_trans_sn: ∀L1,L2,T1,T. ⦃L1, T1⦄ ⊆ ⦃L2, T⦄ →
- ∀T2. ⦃L2, T⦄ ⊆ ⦃L2, T2⦄ → ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄.
-#L1 #L2 #T1 #T
-* #m1 #m0 #g1 #g0 #Hg1 #Hg0 #Hm #Hg
-#T2
-* #n0 #n2 #f0 #f2 #Hf0 #Hf2 #Hn #Hf
-lapply (frees_mono … Hf0 … Hg0) -Hf0 -Hg0 #Hfg0
-elim (lveq_inj_length … Hn) // -Hn #H1 #H2 destruct
-lapply (sle_eq_repl_back1 … Hf … Hfg0) -f0
-/4 width=10 by sle_tls, sle_trans, ex4_4_intro/
-qed-.
-
-theorem fle_trans_dx: ∀L1,T1,T. ⦃L1, T1⦄ ⊆ ⦃L1, T⦄ →
- ∀L2,T2. ⦃L1, T⦄ ⊆ ⦃L2, T2⦄ → ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄.
-#L1 #T1 #T
-* #m1 #m0 #g1 #g0 #Hg1 #Hg0 #Hm #Hg
-#L2 #T2
-* #n0 #n2 #f0 #f2 #Hf0 #Hf2 #Hn #Hf
-lapply (frees_mono … Hg0 … Hf0) -Hg0 -Hf0 #Hgf0
-elim (lveq_inj_length … Hm) // -Hm #H1 #H2 destruct
-lapply (sle_eq_repl_back2 … Hg … Hgf0) -g0
-/4 width=10 by sle_tls, sle_trans, ex4_4_intro/
-qed-.
-
-theorem fle_bind_sn_ge: ∀L1,L2. |L2| ≤ |L1| →
- ∀V1,T1,T. ⦃L1, V1⦄ ⊆ ⦃L2, T⦄ → ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2, T⦄ →
- ∀p,I. ⦃L1, ⓑ{p,I}V1.T1⦄ ⊆ ⦃L2, T⦄.
-#L1 #L2 #HL #V1 #T1 #T * #n1 #x #f1 #g #Hf1 #Hg #H1n1 #H2n1 #H #p #I
-elim (fle_frees_trans … H … Hg) -H #n2 #n #f2 #Hf2 #H1n2 #H2n2
-elim (lveq_inj_void_sn_ge … H1n1 … H1n2) -H1n2 // #H1 #H2 #H3 destruct
-elim (sor_isfin_ex f1 (⫱f2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #f #Hf #_
-<tls_xn in H2n2; #H2n2
-/4 width=12 by frees_bind_void, sor_inv_sle, sor_tls, ex4_4_intro/
-qed.
-
-theorem fle_flat_sn: ∀L1,L2,V1,T1,T. ⦃L1, V1⦄ ⊆ ⦃L2, T⦄ → ⦃L1, T1⦄ ⊆ ⦃L2, T⦄ →
- ∀I. ⦃L1, ⓕ{I}V1.T1⦄ ⊆ ⦃L2, T⦄.
-#L1 #L2 #V1 #T1 #T * #n1 #x #f1 #g #Hf1 #Hg #H1n1 #H2n1 #H #I
-elim (fle_frees_trans … H … Hg) -H #n2 #n #f2 #Hf2 #H1n2 #H2n2
-elim (lveq_inj … H1n1 … H1n2) -H1n2 #H1 #H2 destruct
-elim (sor_isfin_ex f1 f2) /2 width=3 by frees_fwd_isfin/ #f #Hf #_
-/4 width=12 by frees_flat, sor_inv_sle, sor_tls, ex4_4_intro/
-qed.
-
-theorem fle_bind_eq: ∀L1,L2. |L1| = |L2| → ∀V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
- ∀I2,T1,T2. ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2.ⓑ{I2}V2, T2⦄ →
- ∀p,I1. ⦃L1, ⓑ{p,I1}V1.T1⦄ ⊆ ⦃L2, ⓑ{p,I2}V2.T2⦄.
-#L1 #L2 #HL #V1 #V2
-* #n1 #m1 #f1 #g1 #Hf1 #Hg1 #H1L #Hfg1 #I2 #T1 #T2
-* #n2 #m2 #f2 #g2 #Hf2 #Hg2 #H2L #Hfg2 #p #I1
-elim (lveq_inj_length … H1L) // #H1 #H2 destruct
-elim (lveq_inj_length … H2L) // -HL -H2L #H1 #H2 destruct
-elim (sor_isfin_ex f1 (⫱f2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #f #Hf #_
-elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
-/4 width=15 by frees_bind_void, frees_bind, monotonic_sle_sor, sle_tl, ex4_4_intro/
-qed.
-
-theorem fle_bind: ∀L1,L2,V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
- ∀I1,I2,T1,T2. ⦃L1.ⓑ{I1}V1, T1⦄ ⊆ ⦃L2.ⓑ{I2}V2, T2⦄ →
- ∀p. ⦃L1, ⓑ{p,I1}V1.T1⦄ ⊆ ⦃L2, ⓑ{p,I2}V2.T2⦄.
-#L1 #L2 #V1 #V2
-* #n1 #m1 #f1 #g1 #Hf1 #Hg1 #H1L #Hfg1 #I1 #I2 #T1 #T2
-* #n2 #m2 #f2 #g2 #Hf2 #Hg2 #H2L #Hfg2 #p
-elim (lveq_inv_pair_pair … H2L) -H2L #H2L #H1 #H2 destruct
-elim (lveq_inj … H2L … H1L) -H1L #H1 #H2 destruct
-elim (sor_isfin_ex f1 (⫱f2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #f #Hf #_
-elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
-/4 width=15 by frees_bind, monotonic_sle_sor, sle_tl, ex4_4_intro/
-qed.
-
-theorem fle_flat: ∀L1,L2,V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
- ∀T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ →
- ∀I1,I2. ⦃L1, ⓕ{I1}V1.T1⦄ ⊆ ⦃L2, ⓕ{I2}V2.T2⦄.
-/3 width=1 by fle_flat_sn, fle_flat_dx_dx, fle_flat_dx_sn/ qed-.
+++ /dev/null
-(**************************************************************************)
-(* ___ *)
-(* ||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/lveq_length.ma".
-include "basic_2/static/frees_fqup.ma".
-include "basic_2/static/fle.ma".
-
-(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
-
-(* Advanced properties ******************************************************)
-
-lemma fle_refl: bi_reflexive … fle.
-#L #T
-elim (frees_total L T) #f #Hf
-/2 width=8 by sle_refl, ex4_4_intro/
-qed.
-
-lemma fle_sort_length: ∀L1,L2,s1,s2. |L1| = |L2| → ⦃L1, ⋆s1⦄ ⊆ ⦃L2, ⋆s2⦄.
-/3 width=8 by lveq_length_eq, frees_sort, sle_refl, ex4_4_intro/ qed.
-
-lemma fle_gref_length: ∀L1,L2,l1,l2. |L1| = |L2| → ⦃L1, §l1⦄ ⊆ ⦃L2, §l2⦄.
-/3 width=8 by lveq_length_eq, frees_gref, sle_refl, ex4_4_intro/ qed.
-
-lemma fle_shift: ∀L1,L2. |L1| = |L2| →
- ∀I,T1,T2,V. ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2.ⓑ{I}V, T2⦄ →
- ∀p. ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2, ⓑ{p,I}V.T2⦄.
-#L1 #L2 #H1L #I #T1 #T2 #V
-* #n #m #f2 #g2 #Hf2 #Hg2 #H2L #Hfg2 #p
-elim (lveq_inj_length … H2L) // -H1L #H1 #H2 destruct
-lapply (lveq_inv_bind … H2L) -H2L #HL
-elim (frees_total L2 V) #g1 #Hg1
-elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
-lapply (sor_inv_sle_dx … Hg) #H0g
-/4 width=10 by frees_bind, lveq_void_sn, sle_tl, sle_trans, ex4_4_intro/
-qed.
-
-lemma fle_bind_dx_sn: ∀L1,L2,V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
- ∀p,I,T2. ⦃L1, V1⦄ ⊆ ⦃L2, ⓑ{p,I}V2.T2⦄.
-#L1 #L2 #V1 #V2 * #n1 #m1 #f1 #g1 #Hf1 #Hg1 #HL12 #Hfg1 #p #I #T2
-elim (frees_total (L2.ⓧ) T2) #g2 #Hg2
-elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
-@(ex4_4_intro … g Hf1 … HL12) (**) (* full auto too slow *)
-/4 width=5 by frees_bind_void, sor_inv_sle_sn, sor_tls, sle_trans/
-qed.
-
-lemma fle_bind_dx_dx: ∀L1,L2,T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2.ⓧ, T2⦄ → |L1| ≤ |L2| →
- ∀p,I,V2. ⦃L1, T1⦄ ⊆ ⦃L2, ⓑ{p,I}V2.T2⦄.
-#L1 #L2 #T1 #T2 * #n1 #x1 #f2 #g2 #Hf2 #Hg2 #H #Hfg2 #HL12 #p #I #V2
-elim (lveq_inv_void_dx_length … H HL12) -H -HL12 #m1 #HL12 #H1 #H2 destruct
-<tls_xn in Hfg2; #Hfg2
-elim (frees_total L2 V2) #g1 #Hg1
-elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
-@(ex4_4_intro … g Hf2 … HL12) (**) (* full auto too slow *)
-/4 width=5 by frees_bind_void, sor_inv_sle_dx, sor_tls, sle_trans/
-qed.
-
-lemma fle_flat_dx_sn: ∀L1,L2,V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
- ∀I,T2. ⦃L1, V1⦄ ⊆ ⦃L2, ⓕ{I}V2.T2⦄.
-#L1 #L2 #V1 #V2 * #n1 #m1 #f1 #g1 #Hf1 #Hg1 #HL12 #Hfg1 #I #T2
-elim (frees_total L2 T2) #g2 #Hg2
-elim (sor_isfin_ex g1 g2) /2 width=3 by frees_fwd_isfin/ #g #Hg #_
-@(ex4_4_intro … g Hf1 … HL12) (**) (* full auto too slow *)
-/4 width=5 by frees_flat, sor_inv_sle_sn, sor_tls, sle_trans/
-qed.
-
-lemma fle_flat_dx_dx: ∀L1,L2,T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ →
- ∀I,V2. ⦃L1, T1⦄ ⊆ ⦃L2, ⓕ{I}V2.T2⦄.
-#L1 #L2 #T1 #T2 * #n1 #m1 #f2 #g2 #Hf2 #Hg2 #HL12 #Hfg2 #I #V2
-elim (frees_total L2 V2) #g1 #Hg1
-elim (sor_isfin_ex g1 g2) /2 width=3 by frees_fwd_isfin/ #g #Hg #_
-@(ex4_4_intro … g Hf2 … HL12) (**) (* full auto too slow *)
-/4 width=5 by frees_flat, sor_inv_sle_dx, sor_tls, sle_trans/
-qed.
-
-(* Advanced forward lemmas ***************************************************)
-
-lemma fle_fwd_pair_sn: ∀I1,I2,L1,L2,V1,V2,T1,T2. ⦃L1.ⓑ{I1}V1, T1⦄ ⊆ ⦃L2.ⓑ{I2}V2, T2⦄ →
- ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2.ⓑ{I2}V2, T2⦄.
-#I1 #I2 #L1 #L2 #V1 #V2 #T1 #T2 *
-#n1 #n2 #f1 #f2 #Hf1 #Hf2 #HL12 #Hf12
-elim (lveq_inv_pair_pair … HL12) -HL12 #HL12 #H1 #H2 destruct
-elim (frees_total (L1.ⓧ) T1) #g1 #Hg1
-lapply (lsubr_lsubf … Hg1 … Hf1) -Hf1 /2 width=1 by lsubr_unit/ #Hfg1
-/5 width=10 by lsubf_fwd_sle, lveq_bind, sle_trans, ex4_4_intro/ (**) (* full auto too slow *)
-qed-.
/3 width=7 by frees_eq_repl_back, coafter_inj/
qed-.
+(* Note: this is used by lfxs_conf and might be modified *)
lemma frees_inv_drops_next: ∀f1,L1,T1. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 →
∀I2,L2,V2,n. ⬇*[n] L1 ≡ L2.ⓑ{I2}V2 →
∀g1. ⫯g1 = ⫱*[n] f1 →
/2 width=3 by sor_comm_23_idem/
]
qed-.
+
+lemma frees_ind_void: ∀R:relation3 ….
+ (
+ ∀f,L,s. 𝐈⦃f⦄ → R L (⋆s) f
+ ) → (
+ ∀f,i. 𝐈⦃f⦄ → R (⋆) (#i) (↑*[i]⫯f)
+ ) → (
+ ∀f,I,L,V.
+ L ⊢ 𝐅*⦃V⦄ ≡ f → R L V f→ R (L.ⓑ{I}V) (#O) (⫯f)
+ ) → (
+ ∀f,I,L. 𝐈⦃f⦄ → R (L.ⓤ{I}) (#O) (⫯f)
+ ) → (
+ ∀f,I,L,i.
+ L ⊢ 𝐅*⦃#i⦄ ≡ f → R L (#i) f → R (L.ⓘ{I}) (#(⫯i)) (↑f)
+ ) → (
+ ∀f,L,l. 𝐈⦃f⦄ → R L (§l) f
+ ) → (
+ ∀f1,f2,f,p,I,L,V,T.
+ L ⊢ 𝐅*⦃V⦄ ≡ f1 → L.ⓧ ⊢𝐅*⦃T⦄≡ f2 → f1 ⋓ ⫱f2 ≡ f →
+ R L V f1 →R (L.ⓧ) T f2 → R L (ⓑ{p,I}V.T) f
+ ) → (
+ ∀f1,f2,f,I,L,V,T.
+ L ⊢ 𝐅*⦃V⦄ ≡ f1 → L ⊢𝐅*⦃T⦄ ≡ f2 → f1 ⋓ f2 ≡ f →
+ R L V f1 → R L T f2 → R L (ⓕ{I}V.T) f
+ ) →
+ ∀L,T,f. L ⊢ 𝐅*⦃T⦄ ≡ f → R L T f.
+#R #IH1 #IH2 #IH3 #IH4 #IH5 #IH6 #IH7 #IH8 #L #T
+@(fqup_wf_ind_eq (Ⓕ) … (⋆) L T) -L -T #G0 #L0 #T0 #IH #G #L * *
+[ #s #HG #HL #HT #f #H destruct -IH
+ lapply (frees_inv_sort … H) -H /2 width=1 by/
+| cases L -L
+ [ #i #HG #HL #HT #f #H destruct -IH
+ elim (frees_inv_atom … H) -H #g #Hg #H destruct /2 width=1 by/
+ | #L #I * [ cases I -I #I [ | #V ] | #i ] #HG #HL #HT #f #H destruct
+ [ elim (frees_inv_unit … H) -H #g #Hg #H destruct /2 width=1 by/
+ | elim (frees_inv_pair … H) -H #g #Hg #H destruct
+ /4 width=2 by fqu_fqup, fqu_lref_O/
+ | elim (frees_inv_lref … H) -H #g #Hg #H destruct
+ /4 width=2 by fqu_fqup/
+ ]
+ ]
+| #l #HG #HL #HT #f #H destruct -IH
+ lapply (frees_inv_gref … H) -H /2 width=1 by/
+| #p #I #V #T #HG #HL #HT #f #H destruct
+ elim (frees_inv_bind_void … H) -H /3 width=7 by/
+| #I #V #T #HG #HL #HT #f #H destruct
+ elim (frees_inv_flat … H) -H /3 width=7 by/
+]
+qed-.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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 "ground_2/relocation/rtmap_id.ma".
+include "basic_2/notation/relations/subseteq_4.ma".
+include "basic_2/syntax/lveq.ma".
+include "basic_2/static/frees.ma".
+
+(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
+
+definition fsle: bi_relation lenv term ≝ λL1,T1,L2,T2.
+ ∃∃n1,n2,f1,f2. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 & L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 &
+ L1 ≋ⓧ*[n1, n2] L2 & ⫱*[n1]f1 ⊆ ⫱*[n2]f2.
+
+interpretation "free variables inclusion (restricted closure)"
+ 'SubSetEq L1 T1 L2 T2 = (fsle L1 T1 L2 T2).
+
+interpretation "free variables inclusion (term)"
+ 'subseteq T1 T2 = (fsle LAtom T1 LAtom T2).
+
+(* Basic properties *********************************************************)
+
+lemma fsle_sort: ∀L,s1,s2. ⦃L, ⋆s1⦄ ⊆ ⦃L, ⋆s2⦄.
+/3 width=8 by frees_sort, sle_refl, ex4_4_intro/ qed.
+
+lemma fsle_gref: ∀L,l1,l2. ⦃L, §l1⦄ ⊆ ⦃L, §l2⦄.
+/3 width=8 by frees_gref, sle_refl, ex4_4_intro/ qed.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/frees_drops.ma".
+include "basic_2/static/fsle_length.ma".
+
+(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
+
+(* Advanced properties ******************************************************)
+
+lemma fsle_lifts_sn: ∀T1,U1. ⬆*[1] T1 ≡ U1 → ∀L1,L2. |L2| ≤ |L1| →
+ ∀T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ → ⦃L1.ⓧ, U1⦄ ⊆ ⦃L2, T2⦄.
+#T1 #U1 #HTU1 #L1 #L2 #H1L #T2
+* #n #m #f #g #Hf #Hg #H2L #Hfg
+lapply (lveq_length_fwd_dx … H2L ?) // -H1L #H destruct
+lapply (frees_lifts_SO (Ⓣ) (L1.ⓧ) … HTU1 … Hf)
+[ /3 width=4 by drops_refl, drops_drop/ ] -T1 #Hf
+@(ex4_4_intro … Hf Hg) /2 width=4 by lveq_void_sn/ (**) (* explict constructor *)
+qed-.
+
+lemma fsle_lifts_SO: ∀K1,K2. |K1| = |K2| → ∀T1,T2. ⦃K1, T1⦄ ⊆ ⦃K2, T2⦄ →
+ ∀U1,U2. ⬆*[1] T1 ≡ U1 → ⬆*[1] T2 ≡ U2 →
+ ∀I1,I2. ⦃K1.ⓘ{I1}, U1⦄ ⊆ ⦃K2.ⓘ{I2}, U2⦄.
+#K1 #K2 #HK #T1 #T2
+* #n1 #n2 #f1 #f2 #Hf1 #Hf2 #HK12 #Hf12
+#U1 #U2 #HTU1 #HTU2 #I1 #I2
+elim (lveq_inj_length … HK12) // -HK #H1 #H2 destruct
+/5 width=12 by frees_lifts_SO, drops_refl, drops_drop, lveq_bind, sle_push, ex4_4_intro/
+qed.
+
+(* Advanced inversion lemmas ************************************************)
+
+lemma fsle_inv_lifts_sn: ∀T1,U1. ⬆*[1] T1 ≡ U1 →
+ ∀I1,I2,L1,L2,V1,V2,U2. ⦃L1.ⓑ{I1}V1,U1⦄ ⊆ ⦃L2.ⓑ{I2}V2, U2⦄ →
+ ∀p. ⦃L1, T1⦄ ⊆ ⦃L2, ⓑ{p,I2}V2.U2⦄.
+#T1 #U1 #HTU1 #I1 #I2 #L1 #L2 #V1 #V2 #U2
+* #n #m #f2 #g2 #Hf2 #Hg2 #HL #Hfg2 #p
+elim (lveq_inv_pair_pair … HL) -HL #HL #H1 #H2 destruct
+elim (frees_total L2 V2) #g1 #Hg1
+elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
+lapply (frees_inv_lifts_SO (Ⓣ) … Hf2 … HTU1)
+[1,2: /3 width=4 by drops_refl, drops_drop/ ] -U1 #Hf2
+lapply (sor_inv_sle_dx … Hg) #H0g
+/5 width=10 by frees_bind, sle_tl, sle_trans, ex4_4_intro/
+qed-.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/frees_fqup.ma".
+include "basic_2/static/fsle_length.ma".
+
+(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
+
+(* Advanced properties ******************************************************)
+
+lemma fsle_refl: bi_reflexive … fsle.
+#L #T
+elim (frees_total L T) #f #Hf
+/2 width=8 by sle_refl, ex4_4_intro/
+qed.
+
+lemma fsle_shift: ∀L1,L2. |L1| = |L2| →
+ ∀I,T1,T2,V. ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2.ⓑ{I}V, T2⦄ →
+ ∀p. ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2, ⓑ{p,I}V.T2⦄.
+#L1 #L2 #H1L #I #T1 #T2 #V
+* #n #m #f2 #g2 #Hf2 #Hg2 #H2L #Hfg2 #p
+elim (lveq_inj_length … H2L) // -H1L #H1 #H2 destruct
+lapply (lveq_inv_bind … H2L) -H2L #HL
+elim (frees_total L2 V) #g1 #Hg1
+elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
+lapply (sor_inv_sle_dx … Hg) #H0g
+/4 width=10 by frees_bind, lveq_void_sn, sle_tl, sle_trans, ex4_4_intro/
+qed.
+
+lemma fsle_bind_dx_sn: ∀L1,L2,V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
+ ∀p,I,T2. ⦃L1, V1⦄ ⊆ ⦃L2, ⓑ{p,I}V2.T2⦄.
+#L1 #L2 #V1 #V2 * #n1 #m1 #f1 #g1 #Hf1 #Hg1 #HL12 #Hfg1 #p #I #T2
+elim (frees_total (L2.ⓧ) T2) #g2 #Hg2
+elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
+@(ex4_4_intro … g Hf1 … HL12) (**) (* full auto too slow *)
+/4 width=5 by frees_bind_void, sor_inv_sle_sn, sor_tls, sle_trans/
+qed.
+
+lemma fsle_bind_dx_dx: ∀L1,L2,T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2.ⓧ, T2⦄ → |L1| ≤ |L2| →
+ ∀p,I,V2. ⦃L1, T1⦄ ⊆ ⦃L2, ⓑ{p,I}V2.T2⦄.
+#L1 #L2 #T1 #T2 * #n1 #x1 #f2 #g2 #Hf2 #Hg2 #H #Hfg2 #HL12 #p #I #V2
+elim (lveq_inv_void_dx_length … H HL12) -H -HL12 #m1 #HL12 #H1 #H2 destruct
+<tls_xn in Hfg2; #Hfg2
+elim (frees_total L2 V2) #g1 #Hg1
+elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
+@(ex4_4_intro … g Hf2 … HL12) (**) (* full auto too slow *)
+/4 width=5 by frees_bind_void, sor_inv_sle_dx, sor_tls, sle_trans/
+qed.
+
+lemma fsle_flat_dx_sn: ∀L1,L2,V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
+ ∀I,T2. ⦃L1, V1⦄ ⊆ ⦃L2, ⓕ{I}V2.T2⦄.
+#L1 #L2 #V1 #V2 * #n1 #m1 #f1 #g1 #Hf1 #Hg1 #HL12 #Hfg1 #I #T2
+elim (frees_total L2 T2) #g2 #Hg2
+elim (sor_isfin_ex g1 g2) /2 width=3 by frees_fwd_isfin/ #g #Hg #_
+@(ex4_4_intro … g Hf1 … HL12) (**) (* full auto too slow *)
+/4 width=5 by frees_flat, sor_inv_sle_sn, sor_tls, sle_trans/
+qed.
+
+lemma fsle_flat_dx_dx: ∀L1,L2,T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ →
+ ∀I,V2. ⦃L1, T1⦄ ⊆ ⦃L2, ⓕ{I}V2.T2⦄.
+#L1 #L2 #T1 #T2 * #n1 #m1 #f2 #g2 #Hf2 #Hg2 #HL12 #Hfg2 #I #V2
+elim (frees_total L2 V2) #g1 #Hg1
+elim (sor_isfin_ex g1 g2) /2 width=3 by frees_fwd_isfin/ #g #Hg #_
+@(ex4_4_intro … g Hf2 … HL12) (**) (* full auto too slow *)
+/4 width=5 by frees_flat, sor_inv_sle_dx, sor_tls, sle_trans/
+qed.
+
+(* Advanced forward lemmas ***************************************************)
+
+lemma fsle_fwd_pair_sn: ∀I1,I2,L1,L2,V1,V2,T1,T2. ⦃L1.ⓑ{I1}V1, T1⦄ ⊆ ⦃L2.ⓑ{I2}V2, T2⦄ →
+ ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2.ⓑ{I2}V2, T2⦄.
+#I1 #I2 #L1 #L2 #V1 #V2 #T1 #T2 *
+#n1 #n2 #f1 #f2 #Hf1 #Hf2 #HL12 #Hf12
+elim (lveq_inv_pair_pair … HL12) -HL12 #HL12 #H1 #H2 destruct
+elim (frees_total (L1.ⓧ) T1) #g1 #Hg1
+lapply (lsubr_lsubf … Hg1 … Hf1) -Hf1 /2 width=1 by lsubr_unit/ #Hfg1
+/5 width=10 by lsubf_fwd_sle, lveq_bind, sle_trans, ex4_4_intro/ (**) (* full auto too slow *)
+qed-.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/lveq_lveq.ma".
+include "basic_2/static/fsle_fqup.ma".
+
+(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
+
+(* Advanced inversion lemmas ************************************************)
+
+lemma fsle_frees_trans: ∀L1,L2,T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ →
+ ∀f2. L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 →
+ ∃∃n1,n2,f1. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 &
+ L1 ≋ⓧ*[n1, n2] L2 & ⫱*[n1]f1 ⊆ ⫱*[n2]f2.
+#L1 #L2 #T1 #T2 * #n1 #n2 #f1 #g2 #Hf1 #Hg2 #HL #Hn #f2 #Hf2
+lapply (frees_mono … Hg2 … Hf2) -Hg2 -Hf2 #Hgf2
+lapply (tls_eq_repl n2 … Hgf2) -Hgf2 #Hgf2
+lapply (sle_eq_repl_back2 … Hn … Hgf2) -g2
+/2 width=6 by ex3_3_intro/
+qed-.
+
+lemma fsle_frees_trans_eq: ∀L1,L2. |L1| = |L2| →
+ ∀T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ → ∀f2. L2 ⊢ 𝐅*⦃T2⦄ ≡ f2 →
+ ∃∃f1. L1 ⊢ 𝐅*⦃T1⦄ ≡ f1 & f1 ⊆ f2.
+#L1 #L2 #H1L #T1 #T2 #H2L #f2 #Hf2
+elim (fsle_frees_trans … H2L … Hf2) -T2 #n1 #n2 #f1 #Hf1 #H2L #Hf12
+elim (lveq_inj_length … H2L) // -L2 #H1 #H2 destruct
+/2 width=3 by ex2_intro/
+qed-.
+
+(* Main properties **********************************************************)
+
+theorem fsle_trans_sn: ∀L1,L2,T1,T. ⦃L1, T1⦄ ⊆ ⦃L2, T⦄ →
+ ∀T2. ⦃L2, T⦄ ⊆ ⦃L2, T2⦄ → ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄.
+#L1 #L2 #T1 #T
+* #m1 #m0 #g1 #g0 #Hg1 #Hg0 #Hm #Hg
+#T2
+* #n0 #n2 #f0 #f2 #Hf0 #Hf2 #Hn #Hf
+lapply (frees_mono … Hf0 … Hg0) -Hf0 -Hg0 #Hfg0
+elim (lveq_inj_length … Hn) // -Hn #H1 #H2 destruct
+lapply (sle_eq_repl_back1 … Hf … Hfg0) -f0
+/4 width=10 by sle_tls, sle_trans, ex4_4_intro/
+qed-.
+
+theorem fsle_trans_dx: ∀L1,T1,T. ⦃L1, T1⦄ ⊆ ⦃L1, T⦄ →
+ ∀L2,T2. ⦃L1, T⦄ ⊆ ⦃L2, T2⦄ → ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄.
+#L1 #T1 #T
+* #m1 #m0 #g1 #g0 #Hg1 #Hg0 #Hm #Hg
+#L2 #T2
+* #n0 #n2 #f0 #f2 #Hf0 #Hf2 #Hn #Hf
+lapply (frees_mono … Hg0 … Hf0) -Hg0 -Hf0 #Hgf0
+elim (lveq_inj_length … Hm) // -Hm #H1 #H2 destruct
+lapply (sle_eq_repl_back2 … Hg … Hgf0) -g0
+/4 width=10 by sle_tls, sle_trans, ex4_4_intro/
+qed-.
+
+theorem fsle_bind_sn_ge: ∀L1,L2. |L2| ≤ |L1| →
+ ∀V1,T1,T. ⦃L1, V1⦄ ⊆ ⦃L2, T⦄ → ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2, T⦄ →
+ ∀p,I. ⦃L1, ⓑ{p,I}V1.T1⦄ ⊆ ⦃L2, T⦄.
+#L1 #L2 #HL #V1 #T1 #T * #n1 #x #f1 #g #Hf1 #Hg #H1n1 #H2n1 #H #p #I
+elim (fsle_frees_trans … H … Hg) -H #n2 #n #f2 #Hf2 #H1n2 #H2n2
+elim (lveq_inj_void_sn_ge … H1n1 … H1n2) -H1n2 // #H1 #H2 #H3 destruct
+elim (sor_isfin_ex f1 (⫱f2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #f #Hf #_
+<tls_xn in H2n2; #H2n2
+/4 width=12 by frees_bind_void, sor_inv_sle, sor_tls, ex4_4_intro/
+qed.
+
+theorem fsle_flat_sn: ∀L1,L2,V1,T1,T. ⦃L1, V1⦄ ⊆ ⦃L2, T⦄ → ⦃L1, T1⦄ ⊆ ⦃L2, T⦄ →
+ ∀I. ⦃L1, ⓕ{I}V1.T1⦄ ⊆ ⦃L2, T⦄.
+#L1 #L2 #V1 #T1 #T * #n1 #x #f1 #g #Hf1 #Hg #H1n1 #H2n1 #H #I
+elim (fsle_frees_trans … H … Hg) -H #n2 #n #f2 #Hf2 #H1n2 #H2n2
+elim (lveq_inj … H1n1 … H1n2) -H1n2 #H1 #H2 destruct
+elim (sor_isfin_ex f1 f2) /2 width=3 by frees_fwd_isfin/ #f #Hf #_
+/4 width=12 by frees_flat, sor_inv_sle, sor_tls, ex4_4_intro/
+qed.
+
+theorem fsle_bind_eq: ∀L1,L2. |L1| = |L2| → ∀V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
+ ∀I2,T1,T2. ⦃L1.ⓧ, T1⦄ ⊆ ⦃L2.ⓑ{I2}V2, T2⦄ →
+ ∀p,I1. ⦃L1, ⓑ{p,I1}V1.T1⦄ ⊆ ⦃L2, ⓑ{p,I2}V2.T2⦄.
+#L1 #L2 #HL #V1 #V2
+* #n1 #m1 #f1 #g1 #Hf1 #Hg1 #H1L #Hfg1 #I2 #T1 #T2
+* #n2 #m2 #f2 #g2 #Hf2 #Hg2 #H2L #Hfg2 #p #I1
+elim (lveq_inj_length … H1L) // #H1 #H2 destruct
+elim (lveq_inj_length … H2L) // -HL -H2L #H1 #H2 destruct
+elim (sor_isfin_ex f1 (⫱f2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #f #Hf #_
+elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
+/4 width=15 by frees_bind_void, frees_bind, monotonic_sle_sor, sle_tl, ex4_4_intro/
+qed.
+
+theorem fsle_bind: ∀L1,L2,V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
+ ∀I1,I2,T1,T2. ⦃L1.ⓑ{I1}V1, T1⦄ ⊆ ⦃L2.ⓑ{I2}V2, T2⦄ →
+ ∀p. ⦃L1, ⓑ{p,I1}V1.T1⦄ ⊆ ⦃L2, ⓑ{p,I2}V2.T2⦄.
+#L1 #L2 #V1 #V2
+* #n1 #m1 #f1 #g1 #Hf1 #Hg1 #H1L #Hfg1 #I1 #I2 #T1 #T2
+* #n2 #m2 #f2 #g2 #Hf2 #Hg2 #H2L #Hfg2 #p
+elim (lveq_inv_pair_pair … H2L) -H2L #H2L #H1 #H2 destruct
+elim (lveq_inj … H2L … H1L) -H1L #H1 #H2 destruct
+elim (sor_isfin_ex f1 (⫱f2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #f #Hf #_
+elim (sor_isfin_ex g1 (⫱g2)) /3 width=3 by frees_fwd_isfin, isfin_tl/ #g #Hg #_
+/4 width=15 by frees_bind, monotonic_sle_sor, sle_tl, ex4_4_intro/
+qed.
+
+theorem fsle_flat: ∀L1,L2,V1,V2. ⦃L1, V1⦄ ⊆ ⦃L2, V2⦄ →
+ ∀T1,T2. ⦃L1, T1⦄ ⊆ ⦃L2, T2⦄ →
+ ∀I1,I2. ⦃L1, ⓕ{I1}V1.T1⦄ ⊆ ⦃L2, ⓕ{I2}V2.T2⦄.
+/3 width=1 by fsle_flat_sn, fsle_flat_dx_dx, fsle_flat_dx_sn/ qed-.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/lveq_length.ma".
+include "basic_2/static/fsle.ma".
+
+(* FREE VARIABLES INCLUSION FOR RESTRICTED CLOSURES *************************)
+
+(* Properties with length for local environments ****************************)
+
+lemma fsle_sort_bi: ∀L1,L2,s1,s2. |L1| = |L2| → ⦃L1, ⋆s1⦄ ⊆ ⦃L2, ⋆s2⦄.
+/3 width=8 by lveq_length_eq, frees_sort, sle_refl, ex4_4_intro/ qed.
+
+lemma fsle_gref_bi: ∀L1,L2,l1,l2. |L1| = |L2| → ⦃L1, §l1⦄ ⊆ ⦃L2, §l2⦄.
+/3 width=8 by lveq_length_eq, frees_gref, sle_refl, ex4_4_intro/ qed.
+
+lemma fsle_zero_bi: ∀K1,K2. |K1| = |K2| → ∀V1,V2. ⦃K1, V1⦄ ⊆ ⦃K2, V2⦄ →
+ ∀I1,I2. ⦃K1.ⓑ{I1}V1, #O⦄ ⊆ ⦃K2.ⓑ{I2}V2, #O⦄.
+#K1 #K2 #HK #V1 #V2
+* #n1 #n2 #f1 #f2 #Hf1 #Hf2 #HK12 #Hf12
+#I1 #I2
+elim (lveq_inj_length … HK12) // -HK #H1 #H2 destruct
+/3 width=12 by frees_pair, lveq_bind, sle_next, ex4_4_intro/
+qed.
include "basic_2/syntax/lveq_length.ma".
include "basic_2/relocation/lifts_tdeq.ma".
include "basic_2/static/lfxs_length.ma".
+include "basic_2/static/lfxs_fsle.ma".
include "basic_2/static/lfdeq.ma".
(* DEGREE-BASED EQUIVALENCE FOR LOCAL ENVIRONMENTS ON REFERRED ENTRIES ******)
-(* Advanved properties ******************************************************)
+(* Advanved properties with free variables inclusion ************************)
-lemma lfdeq_fle_comp: ∀h,o. lfxs_fle_compatible (cdeq h o).
+lemma lfdeq_fsle_comp: ∀h,o. lfxs_fsle_compatible (cdeq h o).
#h #o #L1 #L2 #T * #f1 #Hf1 #HL12
lapply (frees_lfdeq_conf h o … Hf1 … HL12)
lapply (lexs_fwd_length … HL12)
(* Basic_2A1: uses: lleq_sym *)
lemma lfdeq_sym: ∀h,o,T. symmetric … (lfdeq h o T).
-/3 width=3 by lfdeq_fle_comp, lfxs_sym, tdeq_sym/ qed-.
+/3 width=3 by lfdeq_fsle_comp, lfxs_sym, tdeq_sym/ qed-.
(* Basic_2A1: uses: lleq_dec *)
lemma lfdeq_dec: ∀h,o,L1,L2. ∀T:term. Decidable (L1 ≛[h, o, T] L2).
definition lfeq_transitive: predicate (relation3 lenv term term) ≝
λR. ∀L2,T1,T2. R L2 T1 T2 → ∀L1. L1 ≡[T1] L2 → R L1 T1 T2.
-(* Basic_properties *********************************************************)
-
-lemma lfxs_transitive_lfeq: ∀R. lfxs_transitive ceq R R → lfeq_transitive R.
-/2 width=5 by/ qed.
-
(* Basic inversion lemmas ***************************************************)
lemma lfeq_transitive_inv_lfxs: ∀R. lfeq_transitive R → lfxs_transitive ceq R R.
/4 width=7 by lexs_co, cext2_co, ex2_intro/
qed-.
+(* Basic_properties *********************************************************)
+
+lemma lfxs_transitive_lfeq: ∀R. lfxs_transitive ceq R R → lfeq_transitive R.
+/2 width=5 by/ qed.
+
+lemma frees_lfeq_conf: ∀f,L1,T. L1 ⊢ 𝐅*⦃T⦄ ≡ f →
+ ∀L2. L1 ≡[T] L2 → L2 ⊢ 𝐅*⦃T⦄ ≡ f.
+#f #L1 #T #H elim H -f -L1 -T
+[ /2 width=3 by frees_sort/
+| #f #i #Hf #L2 #H2
+ >(lfxs_inv_atom_sn … H2) -L2
+ /2 width=1 by frees_atom/
+| #f #I #L1 #V1 #_ #IH #Y #H2
+ elim (lfeq_inv_zero_pair_sn … H2) -H2 #L2 #HL12 #H destruct
+ /3 width=1 by frees_pair/
+| #f #I #L1 #Hf #Y #H2
+ elim (lfxs_inv_zero_unit_sn … H2) -H2 #g #L2 #_ #_ #H destruct
+ /2 width=1 by frees_unit/
+| #f #I #L1 #i #_ #IH #Y #H2
+ elim (lfeq_inv_lref_bind_sn … H2) -H2 #J #L2 #HL12 #H destruct
+ /3 width=1 by frees_lref/
+| /2 width=1 by frees_gref/
+| #f1V #f1T #f1 #p #I #L1 #V1 #T1 #_ #_ #Hf1 #IHV #IHT #L2 #H2
+ elim (lfeq_inv_bind … H2) -H2 /3 width=5 by frees_bind/
+| #f1V #f1T #f1 #I #L1 #V1 #T1 #_ #_ #Hf1 #IHV #IHT #L2 #H2
+ elim (lfeq_inv_flat … H2) -H2 /3 width=5 by frees_flat/
+]
+qed-.
+
(* Basic_2A1: removed theorems 10:
lleq_ind lleq_fwd_lref
lleq_fwd_drop_sn lleq_fwd_drop_dx
(* *)
(**************************************************************************)
+include "ground_2/relocation/rtmap_id.ma".
include "basic_2/notation/relations/relationstar_4.ma".
include "basic_2/syntax/cext2.ma".
include "basic_2/relocation/lexs.ma".
-include "basic_2/static/fle.ma".
+include "basic_2/static/frees.ma".
(* GENERIC EXTENSION ON REFERRED ENTRIES OF A CONTEXT-SENSITIVE REALTION ****)
interpretation "generic extension on referred entries (local environment)"
'RelationStar R T L1 L2 = (lfxs R T L1 L2).
-definition R_fle_compatible: predicate (relation3 …) ≝ λRN.
- ∀L,T1,T2. RN L T1 T2 → ⦃L, T2⦄ ⊆ ⦃L, T1⦄.
-
-definition lfxs_fle_compatible: predicate (relation3 …) ≝ λRN.
- ∀L1,L2,T. L1 ⪤*[RN, T] L2 → ⦃L2, T⦄ ⊆ ⦃L1, T⦄.
-
definition R_confluent2_lfxs: relation4 (relation3 lenv term term)
(relation3 lenv term term) … ≝
λR1,R2,RP1,RP2.
--- /dev/null
+(**************************************************************************)
+(* ___ *)
+(* ||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/fsle.ma".
+include "basic_2/static/lfxs.ma".
+
+(* GENERIC EXTENSION ON REFERRED ENTRIES OF A CONTEXT-SENSITIVE REALTION ****)
+
+definition R_fsle_compatible: predicate (relation3 …) ≝ λRN.
+ ∀L,T1,T2. RN L T1 T2 → ⦃L, T2⦄ ⊆ ⦃L, T1⦄.
+
+definition lfxs_fsle_compatible: predicate (relation3 …) ≝ λRN.
+ ∀L1,L2,T. L1 ⪤*[RN, T] L2 → ⦃L2, T⦄ ⊆ ⦃L1, T⦄.
include "basic_2/relocation/lexs_length.ma".
include "basic_2/relocation/lexs_lexs.ma".
include "basic_2/static/frees_drops.ma".
-include "basic_2/static/fle_fle.ma".
-include "basic_2/static/lfxs.ma".
+include "basic_2/static/fsle_fsle.ma".
+include "basic_2/static/lfxs_fsle.ma".
(* GENERIC EXTENSION ON REFERRED ENTRIES OF A CONTEXT-SENSITIVE REALTION ****)
#R #L1 #L2 #T * /3 width=6 by frees_mono, lexs_eq_repl_back/
qed-.
-lemma frees_lexs_conf: ∀R. lfxs_fle_compatible R →
+lemma frees_lexs_conf: ∀R. lfxs_fsle_compatible R →
∀L1,T,f1. L1 ⊢ 𝐅*⦃T⦄ ≡ f1 →
∀L2. L1 ⪤*[cext2 R, cfull, f1] L2 →
∃∃f2. L2 ⊢ 𝐅*⦃T⦄ ≡ f2 & f2 ⊆ f1.
#R #HR #L1 #T #f1 #Hf1 #L2 #H1L
lapply (HR L1 L2 T ?) /2 width=3 by ex2_intro/ #H2L
-@(fle_frees_trans_eq … H2L … Hf1) /3 width=4 by lexs_fwd_length, sym_eq/
+@(fsle_frees_trans_eq … H2L … Hf1) /3 width=4 by lexs_fwd_length, sym_eq/
qed-.
(* Properties with free variables inclusion for restricted closures *********)
(* Advanced properties ******************************************************)
-lemma lfxs_sym: ∀R. lfxs_fle_compatible R →
+lemma lfxs_sym: ∀R. lfxs_fsle_compatible R →
(∀L1,L2,T1,T2. R L1 T1 T2 → R L2 T2 T1) →
∀T. symmetric … (lfxs R T).
#R #H1R #H2R #T #L1 #L2
qed-.
lemma lfxs_pair_sn_split: ∀R1,R2. (∀L. reflexive … (R1 L)) → (∀L. reflexive … (R2 L)) →
- lfxs_fle_compatible R1 →
+ lfxs_fsle_compatible R1 →
∀L1,L2,V. L1 ⪤*[R1, V] L2 → ∀I,T.
∃∃L. L1 ⪤*[R1, ②{I}V.T] L & L ⪤*[R2, V] L2.
#R1 #R2 #HR1 #HR2 #HR #L1 #L2 #V * #f #Hf #HL12 * [ #p ] #I #T
qed-.
lemma lfxs_flat_dx_split: ∀R1,R2. (∀L. reflexive … (R1 L)) → (∀L. reflexive … (R2 L)) →
- lfxs_fle_compatible R1 →
+ lfxs_fsle_compatible R1 →
∀L1,L2,T. L1 ⪤*[R1, T] L2 → ∀I,V.
∃∃L. L1 ⪤*[R1, ⓕ{I}V.T] L & L ⪤*[R2, T] L2.
#R1 #R2 #HR1 #HR2 #HR #L1 #L2 #T * #f #Hf #HL12 #I #V
qed-.
lemma lfxs_bind_dx_split: ∀R1,R2. (∀L. reflexive … (R1 L)) → (∀L. reflexive … (R2 L)) →
- lfxs_fle_compatible R1 →
+ lfxs_fsle_compatible R1 →
∀I,L1,L2,V1,T. L1.ⓑ{I}V1 ⪤*[R1, T] L2 → ∀p.
∃∃L,V. L1 ⪤*[R1, ⓑ{p,I}V1.T] L & L.ⓑ{I}V ⪤*[R2, T] L2 & R1 L1 V1 V.
#R1 #R2 #HR1 #HR2 #HR #I #L1 #L2 #V1 #T * #f #Hf #HL12 #p
qed-.
lemma lfxs_bind_dx_split_void: ∀R1,R2. (∀L. reflexive … (R1 L)) → (∀L. reflexive … (R2 L)) →
- lfxs_fle_compatible R1 →
+ lfxs_fsle_compatible R1 →
∀L1,L2,T. L1.ⓧ ⪤*[R1, T] L2 → ∀p,I,V.
∃∃L. L1 ⪤*[R1, ⓑ{p,I}V.T] L & L.ⓧ ⪤*[R2, T] L2.
#R1 #R2 #HR1 #HR2 #HR #L1 #L2 #T * #f #Hf #HL12 #p #I #V
qed.
theorem lfxs_conf: ∀R1,R2.
- lfxs_fle_compatible R1 →
- lfxs_fle_compatible R2 →
+ lfxs_fsle_compatible R1 →
+ lfxs_fsle_compatible R2 →
R_confluent2_lfxs R1 R2 R1 R2 →
∀T. confluent2 … (lfxs R1 T) (lfxs R2 T).
#R1 #R2 #HR1 #HR2 #HR12 #T #L0 #L1 * #f1 #Hf1 #HL01 #L2 * #f #Hf #HL02
lemma sor_xnx_tl: ∀g1,g2,g. g1 ⋓ g2 ≡ g → ∀f2. ⫯f2 = g2 →
∃∃f1,f. f1 ⋓ f2 ≡ f & ⫱g1 = f1 & ⫯f = g.
#g1 elim (pn_split g1) * #f1 #H1 #g2 #g #H #f2 #H2
-[ elim (sor_inv_pnx … H … H1 H2) | elim (sor_inv_nnx … H … H1 H2) ] -g2 #f #Hf #H0
+[ elim (sor_inv_pnx … H … H1 H2) | elim (sor_inv_nnx … H … H1 H2) ] -g2
+/3 width=5 by ex3_2_intro/
+qed-.
+
+lemma sor_nxx_tl: ∀g1,g2,g. g1 ⋓ g2 ≡ g → ∀f1. ⫯f1 = g1 →
+ ∃∃f2,f. f1 ⋓ f2 ≡ f & ⫱g2 = f2 & ⫯f = g.
+#g1 #g2 elim (pn_split g2) * #f2 #H2 #g #H #f1 #H1
+[ elim (sor_inv_npx … H … H1 H2) | elim (sor_inv_nnx … H … H1 H2) ] -g1
/3 width=5 by ex3_2_intro/
qed-.
<keyword>axiom</keyword>
<!-- tactics -->
- <keyword>apply</keyword>
- <keyword>applyS</keyword>
- <keyword>cases</keyword>
- <keyword>letin</keyword>
- <keyword>auto</keyword>
- <keyword>elim</keyword>
- <keyword>whd</keyword>
- <keyword>normalize</keyword>
- <keyword>assumption</keyword>
- <keyword>generalize</keyword>
- <keyword>change</keyword>
- <keyword>rewrite</keyword>
- <keyword>cut</keyword>
+ <keyword>apply</keyword>
+ <keyword>applyS</keyword>
+ <keyword>cases</keyword>
+ <keyword>letin</keyword>
+ <keyword>auto</keyword>
+ <keyword>elim</keyword>
+ <keyword>whd</keyword>
+ <keyword>normalize</keyword>
+ <keyword>assumption</keyword>
+ <keyword>generalize</keyword>
+ <keyword>change</keyword>
+ <keyword>rewrite</keyword>
+ <keyword>cut</keyword>
<keyword>inversion</keyword>
<keyword>lapply</keyword>
- <keyword>destruct</keyword>
+ <keyword>destruct</keyword>
<!-- commands -->
<keyword>alias</keyword>
<keyword>prefer</keyword>
<keyword>nocomposites</keyword>
<keyword>coinductive</keyword>
- <keyword>constraint</keyword>
+ <keyword>constraint</keyword>
<keyword>corec</keyword>
<keyword>cyclic</keyword>
<keyword>default</keyword>
<keyword>discriminator</keyword>
<keyword>for</keyword>
+ <keyword>id</keyword>
<keyword>include</keyword>
<keyword>include'</keyword>
<keyword>inductive</keyword>
<keyword>inverter</keyword>
<keyword>in</keyword>
<keyword>interpretation</keyword>
- <keyword>left</keyword>
+ <keyword>left</keyword>
<keyword>let</keyword>
<keyword>match</keyword>
<keyword>names</keyword>
- <keyword>non</keyword>
+ <keyword>non</keyword>
<keyword>notation</keyword>
<keyword>on</keyword>
<keyword>precedence</keyword>
<keyword>rec</keyword>
<keyword>record</keyword>
<keyword>return</keyword>
- <keyword>right</keyword>
- <keyword>source</keyword>
+ <keyword>right</keyword>
+ <keyword>source</keyword>
+ <keyword>symbol</keyword>
<keyword>to</keyword>
- <keyword>universe</keyword>
+ <keyword>universe</keyword>
<keyword>using</keyword>
<keyword>with</keyword>
-
-
+
+
<!-- commands -->
<keyword>unification</keyword>
<keyword>hint</keyword>
<keyword>coercions</keyword>
<keyword>comments</keyword>
<keyword>debug</keyword>
-
+
<!-- tinycals -->
<keyword>try</keyword>
<keyword>solve</keyword>
projects / helm.git / commitdiff