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/computation/cprs.ma".
16 include "basic_2/computation/csn.ma".
18 (* CONTEXT-SENSITIVE STRONGLY NORMALIZING TERMS *****************************)
20 (* alternative definition of csn *)
21 definition csna: lenv → predicate term ≝ λL. SN … (cprs L) (eq …).
24 "context-sensitive strong normalization (term) alternative"
25 'SNAlt L T = (csna L T).
27 (* Basic eliminators ********************************************************)
29 lemma csna_ind: ∀L. ∀R:predicate term.
31 (∀T2. L ⊢ T1 ➡* T2 → (T1 = T2 → ⊥) → R T2) → R T1
34 #L #R #H0 #T1 #H elim H -T1 #T1 #HT1 #IHT1
35 @H0 -H0 /3 width=1/ -IHT1 /4 width=1/
38 (* Basic properties *********************************************************)
40 (* Basic_1: was: sn3_intro *)
41 lemma csna_intro: ∀L,T1.
42 (∀T2. L ⊢ T1 ➡* T2 → (T1 = T2 → ⊥) → L ⊢ ⬊⬊* T2) → L ⊢ ⬊⬊* T1.
45 fact csna_intro_aux: ∀L,T1.
46 (∀T,T2. L ⊢ T ➡* T2 → T1 = T → (T1 = T2 → ⊥) → L ⊢ ⬊⬊* T2) → L ⊢ ⬊⬊* T1.
49 (* Basic_1: was: sn3_pr3_trans (old version) *)
50 lemma csna_cprs_trans: ∀L,T1. L ⊢ ⬊⬊* T1 → ∀T2. L ⊢ T1 ➡* T2 → L ⊢ ⬊⬊* T2.
51 #L #T1 #H elim H -T1 #T1 #HT1 #IHT1 #T2 #HLT12
52 @csna_intro #T #HLT2 #HT2
53 elim (term_eq_dec T1 T2) #HT12
54 [ -IHT1 -HLT12 destruct /3 width=1/
55 | -HT1 -HT2 /3 width=4/
58 (* Basic_1: was: sn3_pr2_intro (old version) *)
59 lemma csna_intro_cpr: ∀L,T1.
60 (∀T2. L ⊢ T1 ➡ T2 → (T1 = T2 → ⊥) → L ⊢ ⬊⬊* T2) →
63 @csna_intro_aux #T #T2 #H @(cprs_ind_dx … H) -T
66 | #T0 #T #HLT1 #HLT2 #IHT #HT10 #HT12 destruct
67 elim (term_eq_dec T0 T) #HT0
68 [ -HLT1 -HLT2 -H /3 width=1/
69 | -IHT -HT12 /4 width=3/
74 (* Main properties **********************************************************)
76 theorem csn_csna: ∀L,T. L ⊢ ⬊* T → L ⊢ ⬊⬊* T.
77 #L #T #H @(csn_ind … H) -T /4 width=1/
80 theorem csna_csn: ∀L,T. L ⊢ ⬊⬊* T → L ⊢ ⬊* T.
81 #L #T #H @(csna_ind … H) -T /4 width=1/
84 (* Basic_1: was: sn3_pr3_trans *)
85 lemma csn_cprs_trans: ∀L,T1. L ⊢ ⬊* T1 → ∀T2. L ⊢ T1 ➡* T2 → L ⊢ ⬊* T2.
88 (* Main eliminators *********************************************************)
90 lemma csn_ind_alt: ∀L. ∀R:predicate term.
92 (∀T2. L ⊢ T1 ➡* T2 → (T1 = T2 → ⊥) → R T2) → R T1
95 #L #R #H0 #T1 #H @(csna_ind … (csn_csna … H)) -T1 #T1 #HT1 #IHT1
96 @H0 -H0 /2 width=1/ -HT1 /3 width=1/