matita/matita/contribs/lambdadelta/basic_2/rt_transition/cnr.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "basic_2/notation/relations/prednormal_4.ma".
  16 include "basic_2/rt_transition/cpr.ma".
  17
  18 (* NORMAL TERMS FOR CONTEXT-SENSITIVE R-TRANSITION **************************)
  19
  20 definition cnr (h) (G) (L): predicate term ≝ NF … (cpm h G L 0) (eq …).
  21
  22 interpretation
  23    "normality for context-sensitive r-transition (term)"
  24    'PRedNormal h G L T = (cnr h G L T).
  25
  26 (* Basic inversion lemmas ***************************************************)
  27
  28 lemma cnr_inv_abst (h) (p) (G) (L):
  29       ∀V,T. ❪G,L❫ ⊢ ➡[h] 𝐍❪ⓛ[p]V.T❫ → ∧∧ ❪G,L❫ ⊢ ➡[h] 𝐍❪V❫ & ❪G,L.ⓛV❫ ⊢ ➡[h] 𝐍❪T❫.
  30 #h #p #G #L #V1 #T1 #HVT1 @conj
  31 [ #V2 #HV2 lapply (HVT1 (ⓛ[p]V2.T1) ?) -HVT1 /2 width=2 by cpr_pair_sn/ -HV2 #H destruct //
  32 | #T2 #HT2 lapply (HVT1 (ⓛ[p]V1.T2) ?) -HVT1 /2 width=2 by cpm_bind/ -HT2 #H destruct //
  33 ]
  34 qed-.
  35
  36 (* Basic_2A1: was: cnr_inv_abbr *)
  37 lemma cnr_inv_abbr_neg (h) (G) (L):
  38       ∀V,T. ❪G,L❫ ⊢ ➡[h] 𝐍❪-ⓓV.T❫ → ∧∧ ❪G,L❫ ⊢ ➡[h] 𝐍❪V❫ & ❪G,L.ⓓV❫ ⊢ ➡[h] 𝐍❪T❫.
  39 #h #G #L #V1 #T1 #HVT1 @conj
  40 [ #V2 #HV2 lapply (HVT1 (-ⓓV2.T1) ?) -HVT1 /2 width=2 by cpr_pair_sn/ -HV2 #H destruct //
  41 | #T2 #HT2 lapply (HVT1 (-ⓓV1.T2) ?) -HVT1 /2 width=2 by cpm_bind/ -HT2 #H destruct //
  42 ]
  43 qed-.
  44
  45 (* Basic_2A1: was: cnr_inv_eps *)
  46 lemma cnr_inv_cast (h) (G) (L): ∀V,T. ❪G,L❫ ⊢ ➡[h] 𝐍❪ⓝV.T❫ → ⊥.
  47 #h #G #L #V #T #H lapply (H T ?) -H
  48 /2 width=4 by cpm_eps, discr_tpair_xy_y/
  49 qed-.
  50
  51 (* Basic properties *********************************************************)
  52
  53 (* Basic_1: was: nf2_sort *)
  54 lemma cnr_sort (h) (G) (L): ∀s. ❪G,L❫ ⊢ ➡[h] 𝐍❪⋆s❫.
  55 #h #G #L #s #X #H
  56 >(cpr_inv_sort1 … H) //
  57 qed.
  58
  59 lemma cnr_gref (h) (G) (L): ∀l. ❪G,L❫ ⊢ ➡[h] 𝐍❪§l❫.
  60 #h #G #L #l #X #H
  61 >(cpr_inv_gref1 … H) //
  62 qed.
  63
  64 (* Basic_1: was: nf2_abst *)
  65 lemma cnr_abst (h) (p) (G) (L):
  66       ∀W,T. ❪G,L❫ ⊢ ➡[h] 𝐍❪W❫ → ❪G,L.ⓛW❫ ⊢ ➡[h] 𝐍❪T❫ → ❪G,L❫ ⊢ ➡[h] 𝐍❪ⓛ[p]W.T❫.
  67 #h #p #G #L #W #T #HW #HT #X #H
  68 elim (cpm_inv_abst1 … H) -H #W0 #T0 #HW0 #HT0 #H destruct
  69 <(HW … HW0) -W0 <(HT … HT0) -T0 //
  70 qed.
  71
  72 lemma cnr_abbr_neg (h) (G) (L):
  73       ∀V,T. ❪G,L❫ ⊢ ➡[h] 𝐍❪V❫ → ❪G,L.ⓓV❫ ⊢ ➡[h] 𝐍❪T❫ → ❪G,L❫ ⊢ ➡[h] 𝐍❪-ⓓV.T❫.
  74 #h #G #L #V #T #HV #HT #X #H
  75 elim (cpm_inv_abbr1 … H) -H *
  76 [ #V0 #T0 #HV0 #HT0 #H destruct
  77   <(HV … HV0) -V0 <(HT … HT0) -T0 //
  78 | #T0 #_ #_ #H destruct
  79 ]
  80 qed.
  81
  82
  83 (* Basic_1: removed theorems 1: nf2_abst_shift *)