matita/matita/contribs/lambdadelta/basic_2/rt_transition/cnh.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/preditnormal_4.ma".
  16 include "static_2/syntax/theq.ma".
  17 include "basic_2/rt_transition/cpm.ma".
  18
  19 (* NORMAL TERMS FOR HEAD T-UNUNBOUND RT-TRANSITION **************************)
  20
  21 definition cnh (h) (G) (L): predicate term ≝
  22            λT1. ∀n,T2. ⦃G,L⦄ ⊢ T1 ➡[n,h] T2 → T1 ⩳ T2.
  23
  24 interpretation
  25    "normality for head t-unbound context-sensitive parallel rt-transition (term)"
  26    'PRedITNormal h G L T = (cnh h G L T).
  27
  28 (* Basic properties *********************************************************)
  29
  30 lemma cnh_sort (h) (G) (L): ∀s. ⦃G,L⦄ ⊢ ⥲[h] 𝐍⦃⋆s⦄.
  31 #h #G #L #s1 #n #X #H
  32 elim (cpm_inv_sort1 … H) -H #H #_ destruct //
  33 qed.
  34
  35 lemma cnh_ctop (h) (G): ∀i. ⦃G,⋆⦄ ⊢ ⥲[h] 𝐍⦃#i⦄.
  36 #h #G * [| #i ] #n #X #H
  37 [ elim (cpm_inv_zero1 … H) -H *
  38   [ #H #_ destruct //
  39   | #Y #X1 #X2 #_ #_ #H destruct
  40   | #m #Y #X1 #X2 #_ #_ #H destruct
  41   ]
  42 | elim (cpm_inv_lref1 … H) -H *
  43   [ #H #_ destruct //
  44   | #Z #Y #X0 #_ #_ #H destruct
  45   ]
  46 ]
  47 qed.
  48
  49 lemma cnh_zero (h) (G) (L): ∀I. ⦃G,L.ⓤ{I}⦄ ⊢ ⥲[h] 𝐍⦃#0⦄.
  50 #h #G #L #I #n #X #H
  51 elim (cpm_inv_zero1 … H) -H *
  52 [ #H #_ destruct //
  53 | #Y #X1 #X2 #_ #_ #H destruct
  54 | #m #Y #X1 #X2 #_ #_ #H destruct
  55 ]
  56 qed.
  57
  58 lemma cnh_gref (h) (G) (L): ∀l. ⦃G,L⦄ ⊢ ⥲[h] 𝐍⦃§l⦄.
  59 #h #G #L #l1 #n #X #H
  60 elim (cpm_inv_gref1 … H) -H #H #_ destruct //
  61 qed.
  62
  63 lemma cnh_abst (h) (p) (G) (L): ∀W,T. ⦃G,L⦄ ⊢ ⥲[h] 𝐍⦃ⓛ{p}W.T⦄.
  64 #h #p #G #L #W1 #T1 #n #X #H
  65 elim (cpm_inv_abst1 … H) -H #W2 #T2 #_ #_ #H destruct
  66 /1 width=1 by theq_pair/
  67 qed.
  68
  69 lemma cnh_abbr_neg (h) (G) (L): ∀V,T. ⦃G,L⦄ ⊢ ⥲[h] 𝐍⦃-ⓓV.T⦄.
  70 #h #G #L #V1 #T1 #n #X #H
  71 elim (cpm_inv_abbr1 … H) -H *
  72 [ #W2 #T2 #_ #_ #H destruct /1 width=1 by theq_pair/
  73 | #X1 #_ #_ #H destruct
  74 ]
  75 qed.