1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "basic_2/notation/relations/snalt_6.ma".
16 include "basic_2/substitution/lleq_lleq.ma".
17 include "basic_2/computation/lpxs_lleq.ma".
18 include "basic_2/computation/lsx.ma".
20 (* SN EXTENDED STRONGLY NORMALIZING LOCAL ENVIRONMENTS **********************)
22 (* alternative definition of lsx *)
23 definition lsxa: ∀h. sd h → relation4 ynat term genv lenv ≝
24 λh,g,d,T,G. SN … (lpxs h g G) (lleq d T).
27 "extended strong normalization (local environment) alternative"
28 'SNAlt h g d T G L = (lsxa h g T d G L).
30 (* Basic eliminators ********************************************************)
32 lemma lsxa_ind: ∀h,g,G,T,d. ∀R:predicate lenv.
33 (∀L1. G ⊢ ⬊⬊*[h, g, T, d] L1 →
34 (∀L2. ⦃G, L1⦄ ⊢ ➡*[h, g] L2 → (L1 ≡[T, d] L2 → ⊥) → R L2) →
37 ∀L. G ⊢ ⬊⬊*[h, g, T, d] L → R L.
38 #h #g #G #T #d #R #H0 #L1 #H elim H -L1
39 /5 width=1 by lleq_sym, SN_intro/
42 (* Basic properties *********************************************************)
44 lemma lsxa_intro: ∀h,g,G,L1,T,d.
45 (∀L2. ⦃G, L1⦄ ⊢ ➡*[h, g] L2 → (L1 ≡[T, d] L2 → ⊥) → G ⊢ ⬊⬊*[h, g, T, d] L2) →
46 G ⊢ ⬊⬊*[h, g, T, d] L1.
47 /5 width=1 by lleq_sym, SN_intro/ qed.
49 fact lsxa_intro_aux: ∀h,g,G,L1,T,d.
50 (∀L,L2. ⦃G, L⦄ ⊢ ➡*[h, g] L2 → L1 ≡[T, d] L → (L1 ≡[T, d] L2 → ⊥) → G ⊢ ⬊⬊*[h, g, T, d] L2) →
51 G ⊢ ⬊⬊*[h, g, T, d] L1.
52 /4 width=3 by lsxa_intro/ qed-.
54 lemma lsxa_lleq_trans: ∀h,g,T,G,L1,d. G ⊢ ⬊⬊*[h, g, T, d] L1 →
55 ∀L2. L1 ≡[T, d] L2 → G ⊢ ⬊⬊*[h, g, T, d] L2.
56 #h #g #T #G #L1 #d #H @(lsxa_ind … H) -L1
57 #L1 #_ #IHL1 #L2 #HL12 @lsxa_intro
58 #K2 #HLK2 #HnLK2 elim (lleq_lpxs_trans … HLK2 … HL12) -HLK2
59 /5 width=4 by lleq_canc_sn, lleq_trans/
62 lemma lsxa_lpxs_trans: ∀h,g,T,G,L1,d. G ⊢ ⬊⬊*[h, g, T, d] L1 →
63 ∀L2. ⦃G, L1⦄ ⊢ ➡*[h, g] L2 → G ⊢ ⬊⬊*[h, g, T, d] L2.
64 #h #g #T #G #L1 #d #H @(lsxa_ind … H) -L1 #L1 #HL1 #IHL1 #L2 #HL12
65 elim (lleq_dec T L1 L2 d) /3 width=4 by lsxa_lleq_trans/
68 lemma lsxa_intro_lpx: ∀h,g,G,L1,T,d.
69 (∀L2. ⦃G, L1⦄ ⊢ ➡[h, g] L2 → (L1 ≡[T, d] L2 → ⊥) → G ⊢ ⬊⬊*[h, g, T, d] L2) →
70 G ⊢ ⬊⬊*[h, g, T, d] L1.
71 #h #g #G #L1 #T #d #IH @lsxa_intro_aux
72 #L #L2 #H @(lpxs_ind_dx … H) -L
73 [ #H destruct #H elim H //
74 | #L0 #L elim (lleq_dec T L1 L d) /3 width=1 by/
75 #HnT #HL0 #HL2 #_ #HT #_ elim (lleq_lpx_trans … HL0 … HT) -L0
76 #L0 #HL10 #HL0 @(lsxa_lpxs_trans … HL2) -HL2
77 /5 width=3 by lsxa_lleq_trans, lleq_trans/
81 (* Main properties **********************************************************)
83 theorem lsx_lsxa: ∀h,g,G,L,T,d. G ⊢ ⬊*[h, g, T, d] L → G ⊢ ⬊⬊*[h, g, T, d] L.
84 #h #g #G #L #T #d #H @(lsx_ind … H) -L
85 /4 width=1 by lsxa_intro_lpx/
88 (* Main inversion lemmas ****************************************************)
90 theorem lsxa_inv_lsx: ∀h,g,G,L,T,d. G ⊢ ⬊⬊*[h, g, T, d] L → G ⊢ ⬊*[h, g, T, d] L.
91 #h #g #G #L #T #d #H @(lsxa_ind … H) -L
92 /4 width=1 by lsx_intro, lpx_lpxs/
95 (* Advanced properties ******************************************************)
97 lemma lsx_intro_alt: ∀h,g,G,L1,T,d.
98 (∀L2. ⦃G, L1⦄ ⊢ ➡*[h, g] L2 → (L1 ≡[T, d] L2 → ⊥) → G ⊢ ⬊*[h, g, T, d] L2) →
99 G ⊢ ⬊*[h, g, T, d] L1.
100 /6 width=1 by lsxa_inv_lsx, lsx_lsxa, lsxa_intro/ qed.
102 lemma lsx_lpxs_trans: ∀h,g,G,L1,T,d. G ⊢ ⬊*[h, g, T, d] L1 →
103 ∀L2. ⦃G, L1⦄ ⊢ ➡*[h, g] L2 → G ⊢ ⬊*[h, g, T, d] L2.
104 /4 width=3 by lsxa_inv_lsx, lsx_lsxa, lsxa_lpxs_trans/ qed-.
106 (* Advanced eliminators *****************************************************)
108 lemma lsx_ind_alt: ∀h,g,G,T,d. ∀R:predicate lenv.
109 (∀L1. G ⊢ ⬊*[h, g, T, d] L1 →
110 (∀L2. ⦃G, L1⦄ ⊢ ➡*[h, g] L2 → (L1 ≡[T, d] L2 → ⊥) → R L2) →
113 ∀L. G ⊢ ⬊*[h, g, T, d] L → R L.
114 #h #g #G #T #d #R #IH #L #H @(lsxa_ind h g G T d … L)
115 /4 width=1 by lsxa_inv_lsx, lsx_lsxa/