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_5.ma".
16 include "basic_2/computation/cpxs.ma".
17 include "basic_2/computation/csx.ma".
19 (* CONTEXT-SENSITIVE EXTENDED STRONGLY NORMALIZING TERMS ********************)
21 (* alternative definition of csx *)
22 definition csxa: ∀h. sd h → relation3 genv lenv term ≝
23 λh,g,G,L. SN … (cpxs h g G L) (eq …).
26 "context-sensitive extended strong normalization (term) alternative"
27 'SNAlt h g G L T = (csxa h g G L T).
29 (* Basic eliminators ********************************************************)
31 lemma csxa_ind: ∀h,g,G,L. ∀R:predicate term.
32 (∀T1. ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T1 →
33 (∀T2. ⦃G, L⦄ ⊢ T1 ➡*[h, g] T2 → (T1 = T2 → ⊥) → R T2) → R T1
35 ∀T. ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T → R T.
36 #h #g #G #L #R #H0 #T1 #H elim H -T1 #T1 #HT1 #IHT1
37 @H0 -H0 /3 width=1/ -IHT1 /4 width=1/
40 (* Basic properties *********************************************************)
42 (* Basic_1: was just: sn3_intro *)
43 lemma csxa_intro: ∀h,g,G,L,T1.
44 (∀T2. ⦃G, L⦄ ⊢ T1 ➡*[h, g] T2 → (T1 = T2 → ⊥) → ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T2) →
45 ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T1.
48 fact csxa_intro_aux: ∀h,g,G,L,T1. (
49 ∀T,T2. ⦃G, L⦄ ⊢ T ➡*[h, g] T2 → T1 = T → (T1 = T2 → ⊥) → ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T2
50 ) → ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T1.
53 (* Basic_1: was just: sn3_pr3_trans (old version) *)
54 lemma csxa_cpxs_trans: ∀h,g,G,L,T1. ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T1 →
55 ∀T2. ⦃G, L⦄ ⊢ T1 ➡*[h, g] T2 → ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T2.
56 #h #g #G #L #T1 #H elim H -T1 #T1 #HT1 #IHT1 #T2 #HLT12
57 @csxa_intro #T #HLT2 #HT2
58 elim (term_eq_dec T1 T2) #HT12
59 [ -IHT1 -HLT12 destruct /3 width=1/
60 | -HT1 -HT2 /3 width=4/
63 (* Basic_1: was just: sn3_pr2_intro (old version) *)
64 lemma csxa_intro_cpx: ∀h,g,G,L,T1. (
65 ∀T2. ⦃G, L⦄ ⊢ T1 ➡[h, g] T2 → (T1 = T2 → ⊥) → ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T2
66 ) → ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T1.
68 @csxa_intro_aux #T #T2 #H @(cpxs_ind_dx … H) -T
71 | #T0 #T #HLT1 #HLT2 #IHT #HT10 #HT12 destruct
72 elim (term_eq_dec T0 T) #HT0
73 [ -HLT1 -HLT2 -H /3 width=1/
74 | -IHT -HT12 /4 width=3/
79 (* Main properties **********************************************************)
81 theorem csx_csxa: ∀h,g,G,L,T. ⦃G, L⦄ ⊢ ⬊*[h, g] T → ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T.
82 #h #g #G #L #T #H @(csx_ind … H) -T /4 width=1/
85 theorem csxa_csx: ∀h,g,G,L,T. ⦃G, L⦄ ⊢ ⬊⬊*[h, g] T → ⦃G, L⦄ ⊢ ⬊*[h, g] T.
86 #h #g #G #L #T #H @(csxa_ind … H) -T /4 width=1/
89 (* Basic_1: was just: sn3_pr3_trans *)
90 lemma csx_cpxs_trans: ∀h,g,G,L,T1. ⦃G, L⦄ ⊢ ⬊*[h, g] T1 →
91 ∀T2. ⦃G, L⦄ ⊢ T1 ➡*[h, g] T2 → ⦃G, L⦄ ⊢ ⬊*[h, g] T2.
92 #h #g #G #L #T1 #HT1 #T2 #H @(cpxs_ind … H) -T2 // /2 width=3 by csx_cpx_trans/
95 (* Main eliminators *********************************************************)
97 lemma csx_ind_alt: ∀h,g,G,L. ∀R:predicate term.
98 (∀T1. ⦃G, L⦄ ⊢ ⬊*[h, g] T1 →
99 (∀T2. ⦃G, L⦄ ⊢ T1 ➡*[h, g] T2 → (T1 = T2 → ⊥) → R T2) → R T1
101 ∀T. ⦃G, L⦄ ⊢ ⬊*[h, g] T → R T.
102 #h #g #G #L #R #H0 #T1 #H @(csxa_ind … (csx_csxa … H)) -T1 #T1 #HT1 #IHT1
103 @H0 -H0 /2 width=1/ -HT1 /3 width=1/