∀J,W. L1 ≡[W, 0] L2 → L1.ⓑ{J}W ≡[T, 0] L2.ⓑ{J}W.
/2 width=7 by llpx_sn_bind_repl_O/ qed-.
-lemma lleq_dec: ∀T,L1,L2,l. Decidable (L1 ≡[T, l] L2).
-/3 width=1 by llpx_sn_dec, eq_term_dec/ qed-.
-
lemma lleq_llpx_sn_trans: ∀R. lleq_transitive R →
∀L1,L2,T,l. L1 ≡[T, l] L2 →
∀L. llpx_sn R l T L2 L → llpx_sn R l T L1 L.
∀J,W1,W2. llpx_sn R 0 W1 L1 L2 → R L1 W1 W2 → llpx_sn R 0 T (L1.ⓑ{J}W1) (L2.ⓑ{J}W2).
/3 width=9 by llpx_sn_bind_repl_SO, llpx_sn_inv_S/ qed-.
-lemma llpx_sn_dec: ∀R. (∀L,T1,T2. Decidable (R L T1 T2)) →
- ∀T,L1,L2,l. Decidable (llpx_sn R l T L1 L2).
-#R #HR #T #L1 @(f2_ind … rfw … L1 T) -L1 -T
-#x #IH #L1 * *
-[ #s #Hx #L2 elim (eq_nat_dec (|L1|) (|L2|)) /3 width=1 by or_introl, llpx_sn_sort/
-| #i #Hx #L2 elim (eq_nat_dec (|L1|) (|L2|))
- [ #HL12 #l elim (ylt_split i l) /3 width=1 by llpx_sn_skip, or_introl/
- #Hli elim (lt_or_ge i (|L1|)) #HiL1
- elim (lt_or_ge i (|L2|)) #HiL2 /3 width=1 by or_introl, llpx_sn_free/
- elim (drop_O1_lt (Ⓕ) … HiL2) #I2 #K2 #V2 #HLK2
- elim (drop_O1_lt (Ⓕ) … HiL1) #I1 #K1 #V1 #HLK1
- elim (eq_bind2_dec I2 I1)
- [ #H2 elim (HR K1 V1 V2) -HR
- [ #H3 elim (IH K1 V1 … K2 0) destruct
- /3 width=9 by llpx_sn_lref, drop_fwd_rfw, or_introl/
- ]
- ]
- -IH #H3 @or_intror
- #H elim (llpx_sn_fwd_lref … H) -H [1,3,4,6,7,9: * ]
- [1,3,5: /3 width=4 by lt_to_le_to_lt, lt_refl_false/
- |7,8,9: /2 width=4 by ylt_yle_false/
- ]
- #Z #Y1 #Y2 #X1 #X2 #HLY1 #HLY2 #HY12 #HX12
- lapply (drop_mono … HLY1 … HLK1) -HLY1 -HLK1
- lapply (drop_mono … HLY2 … HLK2) -HLY2 -HLK2
- #H #H0 destruct /2 width=1 by/
- ]
-| #p #Hx #L2 elim (eq_nat_dec (|L1|) (|L2|)) /3 width=1 by or_introl, llpx_sn_gref/
-| #a #I #V #T #Hx #L2 #l destruct
- elim (IH L1 V … L2 l) /2 width=1 by/
- elim (IH (L1.ⓑ{I}V) T … (L2.ⓑ{I}V) (⫯l)) -IH /3 width=1 by or_introl, llpx_sn_bind/
- #H1 #H2 @or_intror
- #H elim (llpx_sn_inv_bind … H) -H /2 width=1 by/
-| #I #V #T #Hx #L2 #l destruct
- elim (IH L1 V … L2 l) /2 width=1 by/
- elim (IH L1 T … L2 l) -IH /3 width=1 by or_introl, llpx_sn_flat/
- #H1 #H2 @or_intror
- #H elim (llpx_sn_inv_flat … H) -H /2 width=1 by/
-]
--x /4 width=4 by llpx_sn_fwd_length, or_intror/
-qed-.
-
(* Inversion lemmas on negated lazy pointwise extension *********************)
lemma nllpx_sn_inv_bind: ∀R. (∀L,T1,T2. Decidable (R L T1 T2)) →
--- /dev/null
+lemma lsx_lreq_conf: ∀h,o,G,L1,T,l. G ⊢ ⬊*[h, o, T, l] L1 →
+ ∀L2. L1 ⩬[l, ∞] L2 → G ⊢ ⬊*[h, o, T, l] L2.
+#h #o #G #L1 #T #l #H @(lsx_ind … H) -L1
+#L1 #_ #IHL1 #L2 #HL12 @lsx_intro
+#L3 #HL23 #HnL23 elim (lreq_lpx_trans_lleq … HL12 … HL23) -HL12 -HL23
+#L0 #HL03 #HL10 #H elim (H T) -H /4 width=4 by/
+qed-.
+
+(* these two are better expressed with the binder \chi *)
+
+lemma lsx_fwd_bind_dx: ∀h,o,a,I,G,L,V,T,l. G ⊢ ⬈*[h, o, ⓑ{a,I}V.T, l] L →
+ G ⊢ ⬈*[h, o, T, ⫯l] L.ⓑ{I}V.
+#h #o #a #I #G #L #V1 #T #l #H @(lsx_ind … H) -L
+#L1 #_ #IHL1 @lsx_intro
+#Y #H #HT elim (lpx_inv_pair1 … H) -H
+#L2 #V2 #HL12 #_ #H destruct
+@(lsx_lreq_conf … (L2.ⓑ{I}V1)) /2 width=1 by lreq_succ/
+@IHL1 // #H @HT -IHL1 -HL12 -HT
+@(lleq_lreq_trans … (L2.ⓑ{I}V1))
+/2 width=2 by lleq_fwd_bind_dx, lreq_succ/
+qed-.
+
+lemma lsx_inv_bind: ∀h,o,a,I,G,L,V,T,l. G ⊢ ⬈*[h, o, ⓑ{a, I}V.T, l] L →
+ G ⊢ ⬈*[h, o, V, l] L ∧ G ⊢ ⬈*[h, o, T, ⫯l] L.ⓑ{I}V.
+/3 width=4 by lsx_fwd_bind_sn, lsx_fwd_bind_dx, conj/ qed-.
elim (IH … Hfg) -IH -Hfg /3 width=5 by lexs_next, lexs_push, ex2_intro/
]
qed-.
+
+lemma lexs_dec: ∀RN,RP.
+ (∀L,T1,T2. Decidable (RN L T1 T2)) →
+ (∀L,T1,T2. Decidable (RP L T1 T2)) →
+ ∀L1,L2,f. Decidable (L1 ⦻*[RN, RP, f] L2).
+#RN #RP #HRN #HRP #L1 elim L1 -L1 [ * | #L1 #I1 #V1 #IH * ]
+[ /2 width=1 by lexs_atom, or_introl/
+| #L2 #I2 #V2 #f @or_intror #H
+ lapply (lexs_inv_atom1 … H) -H #H destruct
+| #f @or_intror #H
+ lapply (lexs_inv_atom2 … H) -H #H destruct
+| #L2 #I2 #V2 #f elim (eq_bind2_dec I1 I2) #H destruct
+ [2: @or_intror #H elim (lexs_fwd_pair … H) -H /2 width=1 by/ ]
+ elim (IH L2 (⫱f)) -IH #HL12
+ [2: @or_intror #H elim (lexs_fwd_pair … H) -H /2 width=1 by/ ]
+ elim (pn_split f) * #g #H destruct
+ [ elim (HRP L1 V1 V2) | elim (HRN L1 V1 V2) ] -HRP -HRN #HV12
+ [1,3: /3 width=1 by lexs_push, lexs_next, or_introl/ ]
+ @or_intror #H
+ [ elim (lexs_inv_push … H) | elim (lexs_inv_next … H) ] -H
+ /2 width=1 by/
+]
+qed-.
(* Advanced properties ******************************************************)
+(* Basic_2A1: was just: lsx_lleq_trans *)
lemma lfsx_lfdeq_trans: ∀h,o,G,L1,T. G ⊢ ⬈*[h, o, T] 𝐒⦃L1⦄ →
∀L2. L1 ≡[h, o, T] L2 → G ⊢ ⬈*[h, o, T] 𝐒⦃L2⦄.
#h #o #G #L1 #T #H @(lfsx_ind … H) -L1
/4 width=5 by lfdeq_repl/
qed-.
+(* Basic_2A1: was: lsx_lpx_trans *)
+lemma lfsx_lfpx_trans: ∀h,o,G,L1,T. G ⊢ ⬈*[h, o, T] 𝐒⦃L1⦄ →
+ ∀L2. ⦃G, L1⦄ ⊢ ⬈[h, T] L2 → G ⊢ ⬈*[h, o, T] 𝐒⦃L2⦄.
+#h #o #G #L1 #T #H @(lfsx_ind … H) -L1 #L1 #HL1 #IHL1 #L2 #HL12
+elim (lfdeq_dec h o L1 L2 T) /3 width=4 by lfsx_lfdeq_trans, lfxs_refl/
+qed-.
+
(* Advanced forward lemmas **************************************************)
(* Basic_2A1: includes: lsx_fwd_bind_sn lsx_fwd_flat_sn *)
/6 width=4 by lfsx_lfdeq_trans, lfdeq_trans, lfdeq_fwd_pair_sn/
qed-.
-
(* Basic_2A1: was: lsx_fwd_flat_dx *)
lemma lfsx_fwd_flat_dx: ∀h,o,I,G,L,V,T. G ⊢ ⬈*[h, o, ⓕ{I}V.T] 𝐒⦃L⦄ →
G ⊢ ⬈*[h, o, T] 𝐒⦃L⦄.
+++ /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/multiple/lleq_lleq.ma".
-include "basic_2/reduction/lpx_lleq.ma".
-include "basic_2/computation/lsx.ma".
-
-(* SN EXTENDED STRONGLY NORMALIZING LOCAL ENVIRONMENTS **********************)
-
-(* Advanced properties ******************************************************)
-
-lemma lsx_lleq_trans: ∀h,o,T,G,L1,l. G ⊢ ⬊*[h, o, T, l] L1 →
- ∀L2. L1 ≡[T, l] L2 → G ⊢ ⬊*[h, o, T, l] L2.
-#h #o #T #G #L1 #l #H @(lsx_ind … H) -L1
-#L1 #_ #IHL1 #L2 #HL12 @lsx_intro
-#K2 #HLK2 #HnLK2 elim (lleq_lpx_trans … HLK2 … HL12) -HLK2
-/5 width=4 by lleq_canc_sn, lleq_trans/
-qed-.
-
-lemma lsx_lpx_trans: ∀h,o,T,G,L1,l. G ⊢ ⬊*[h, o, T, l] L1 →
- ∀L2. ⦃G, L1⦄ ⊢ ➡[h, o] L2 → G ⊢ ⬊*[h, o, T, l] L2.
-#h #o #T #G #L1 #l #H @(lsx_ind … H) -L1 #L1 #HL1 #IHL1 #L2 #HL12
-elim (lleq_dec T L1 L2 l) /3 width=4 by lsx_lleq_trans/
-qed-.
-
-lemma lsx_lreq_conf: ∀h,o,G,L1,T,l. G ⊢ ⬊*[h, o, T, l] L1 →
- ∀L2. L1 ⩬[l, ∞] L2 → G ⊢ ⬊*[h, o, T, l] L2.
-#h #o #G #L1 #T #l #H @(lsx_ind … H) -L1
-#L1 #_ #IHL1 #L2 #HL12 @lsx_intro
-#L3 #HL23 #HnL23 elim (lreq_lpx_trans_lleq … HL12 … HL23) -HL12 -HL23
-#L0 #HL03 #HL10 #H elim (H T) -H /4 width=4 by/
-qed-.
-
-(* Advanced forward lemmas **************************************************)
-
-lemma lsx_fwd_bind_dx: ∀h,o,a,I,G,L,V,T,l. G ⊢ ⬊*[h, o, ⓑ{a,I}V.T, l] L →
- G ⊢ ⬊*[h, o, T, ⫯l] L.ⓑ{I}V.
-#h #o #a #I #G #L #V1 #T #l #H @(lsx_ind … H) -L
-#L1 #_ #IHL1 @lsx_intro
-#Y #H #HT elim (lpx_inv_pair1 … H) -H
-#L2 #V2 #HL12 #_ #H destruct
-@(lsx_lreq_conf … (L2.ⓑ{I}V1)) /2 width=1 by lreq_succ/
-@IHL1 // #H @HT -IHL1 -HL12 -HT
-@(lleq_lreq_trans … (L2.ⓑ{I}V1))
-/2 width=2 by lleq_fwd_bind_dx, lreq_succ/
-qed-.
-
-(* Advanced inversion lemmas ************************************************)
-
-lemma lsx_inv_bind: ∀h,o,a,I,G,L,V,T,l. G ⊢ ⬊*[h, o, ⓑ{a, I}V.T, l] L →
- G ⊢ ⬊*[h, o, V, l] L ∧ G ⊢ ⬊*[h, o, T, ⫯l] L.ⓑ{I}V.
-/3 width=4 by lsx_fwd_bind_sn, lsx_fwd_bind_dx, conj/ qed-.
∃∃K1,V1. L1 = K1.ⓑ{I}V1.
/2 width=5 by lfxs_fwd_dx/ qed-.
-(* Basic_2A1: removed theorems 30:
+(* Basic_2A1: removed theorems 31:
lleq_ind lleq_inv_bind lleq_inv_flat lleq_fwd_length lleq_fwd_lref
lleq_fwd_drop_sn lleq_fwd_drop_dx
lleq_fwd_bind_sn lleq_fwd_bind_dx lleq_fwd_flat_sn lleq_fwd_flat_dx
lleq_sort lleq_skip lleq_lref lleq_free lleq_gref lleq_bind lleq_flat
lleq_refl lleq_Y lleq_sym lleq_ge_up lleq_ge lleq_bind_O llpx_sn_lrefl
lleq_trans lleq_canc_sn lleq_canc_dx lleq_nlleq_trans nlleq_lleq_div
+ lleq_dec
*)
(* DEGREE-BASED EQUIVALENCE FOR LOCAL ENVIRONMENTS ON REFERRED ENTRIES ******)
+(* Advanced properties ******************************************************)
+
+lemma lfdeq_dec: ∀h,o,L1,L2. ∀T:term. Decidable (L1 ≡[h, o, T] L2).
+/3 width=1 by lfxs_dec, tdeq_dec/ qed-.
+
(* Main properties **********************************************************)
theorem lfdeq_bind: ∀h,o,p,I,L1,L2,V1,V2,T.
/2 width=3 by ex1_2_intro/
qed-.
-(* Basic_2A1: removed theorems 24:
+(* Basic_2A1: removed theorems 25:
llpx_sn_sort llpx_sn_skip llpx_sn_lref llpx_sn_free llpx_sn_gref
llpx_sn_bind llpx_sn_flat
llpx_sn_inv_bind llpx_sn_inv_flat
llpx_sn_fwd_lref llpx_sn_fwd_pair_sn llpx_sn_fwd_length
llpx_sn_fwd_bind_sn llpx_sn_fwd_bind_dx llpx_sn_fwd_flat_sn llpx_sn_fwd_flat_dx
llpx_sn_refl llpx_sn_Y llpx_sn_bind_O llpx_sn_ge_up llpx_sn_ge llpx_sn_co
- llpx_sn_fwd_drop_sn llpx_sn_fwd_drop_dx
+ llpx_sn_fwd_drop_sn llpx_sn_fwd_drop_dx
+ llpx_sn_dec
*)
(* Advanced properties ******************************************************)
+lemma lfxs_inv_frees: ∀R,L1,L2,T. L1 ⦻*[R, T] L2 →
+ ∀f. L1 ⊢ 𝐅*⦃T⦄ ≡ f → L1 ⦻*[R, cfull, f] L2.
+#R #L1 #L2 #T * /3 width=6 by frees_mono, lexs_eq_repl_back/
+qed-.
+
+lemma lfxs_dec: ∀R. (∀L,T1,T2. Decidable (R L T1 T2)) →
+ ∀L1,L2,T. Decidable (L1 ⦻*[R, T] L2).
+#R #HR #L1 #L2 #T
+elim (frees_total L1 T) #f #Hf
+elim (lexs_dec R cfull HR … L1 L2 f)
+/4 width=3 by lfxs_inv_frees, cfull_dec, ex2_intro, or_intror, or_introl/
+qed-.
+
lemma lfxs_pair_sn_split: ∀R1,R2. (∀L. reflexive … (R1 L)) → (∀L. reflexive … (R2 L)) →
lexs_frees_confluent … R1 cfull →
∀L1,L2,V. L1 ⦻*[R1, V] L2 → ∀I,T.
]
qed-.
+lemma cfull_dec: ∀L,T1,T2. Decidable (cfull L T1 T2).
+/2 width=1 by or_introl/ qed-.
+
(* Basic inversion lemmas ***************************************************)
fact destruct_lpair_lpair_aux: ∀I1,I2,L1,L2,V1,V2. L1.ⓑ{I1}V1 = L2.ⓑ{I2}V2 →
]
qed-.
-lemma discr_lpair_xy_x: ∀I,V,L. L.ⓑ{I}V = L→ ⊥.
+lemma discr_lpair_xy_x: ∀I,V,L. L.ⓑ{I}V = L → ⊥.
/2 width=4 by discr_lpair_x_xy/ qed-.
projects / helm.git / commitdiff