matita/matita/contribs/lambda_delta/Basic_2/reducibility/tnf.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/substitution/tps_lift.ma".
  16 include "Basic_2/reducibility/trf.ma".
  17 include "Basic_2/reducibility/tpr.ma".
  18
  19 (* CONTEXT-FREE NORMAL TERMS ************************************************)
  20
  21 definition tnf: predicate term ≝ NF … tpr (eq …).
  22
  23 interpretation
  24    "context-free normality (term)"
  25    'Normal T = (tnf T).
  26
  27 (* Basic inversion lemmas ***************************************************)
  28
  29 lemma tnf_inv_abst: ∀V,T. ℕ[𝕔{Abst}V.T] → ℕ[V] ∧ ℕ[T].
  30 #V1 #T1 #HVT1 @conj
  31 [ #V2 #HV2 lapply (HVT1 (𝕔{Abst}V2.T1) ?) -HVT1 /2/ -HV2 #H destruct -V1 T1 //
  32 | #T2 #HT2 lapply (HVT1 (𝕔{Abst}V1.T2) ?) -HVT1 /2/ -HT2 #H destruct -V1 T1 //
  33 ]
  34 qed-.
  35
  36 lemma tnf_inv_appl: ∀V,T. ℕ[𝕔{Appl}V.T] → ∧∧ ℕ[V] & ℕ[T] & 𝕊[T].
  37 #V1 #T1 #HVT1 @and3_intro
  38 [ #V2 #HV2 lapply (HVT1 (𝕔{Appl}V2.T1) ?) -HVT1 /2/ -HV2 #H destruct -V1 T1 //
  39 | #T2 #HT2 lapply (HVT1 (𝕔{Appl}V1.T2) ?) -HVT1 /2/ -HT2 #H destruct -V1 T1 //
  40 | generalize in match HVT1 -HVT1; elim T1 -T1 * // * #W1 #U1 #_ #_ #H
  41   [ elim (lift_total V1 0 1) #V2 #HV12
  42     lapply (H (𝕔{Abbr}W1.𝕔{Appl}V2.U1) ?) -H /2/ -HV12 #H destruct
  43   | lapply (H (𝕔{Abbr}V1.U1) ?) -H /2/ #H destruct
  44 ]
  45 qed-.
  46
  47 lemma tnf_inv_abbr: ∀V,T. ℕ[𝕔{Abbr}V.T] → False.
  48 #V #T #H elim (is_lift_dec T 0 1)
  49 [ * #U #HTU
  50   lapply (H U ?) -H /2 width=3/ #H destruct -U;
  51   elim (lift_inv_pair_xy_y … HTU)
  52 | #HT
  53   elim (tps_full (⋆) V T (⋆. 𝕓{Abbr} V) 0 ?) // #T2 #T1 #HT2 #HT12
  54   lapply (H (𝕓{Abbr}V.T2) ?) -H /2/ -HT2 #H destruct -T /3 width=2/
  55 ]
  56 qed.
  57
  58 lemma tnf_inv_cast: ∀V,T. ℕ[𝕔{Cast}V.T] → False.
  59 #V #T #H lapply (H T ?) -H /2 width=1/ #H
  60 @(discr_tpair_xy_y … H)
  61 qed-.
  62
  63 (* Basic properties *********************************************************)
  64
  65 lemma tpr_tif_eq: ∀T1,T2. T1 ⇒ T2 →  𝕀[T1] → T1 = T2.
  66 #T1 #T2 #H elim H -T1 T2
  67 [ //
  68 | * #V1 #V2 #T1 #T2 #_ #_ #IHV1 #IHT1 #H
  69   [ elim (tif_inv_appl … H) -H #HV1 #HT1 #_
  70     >IHV1 -IHV1 // -HV1 >IHT1 -IHT1 //
  71   | elim (tif_inv_cast … H)
  72   ]
  73 | #V1 #V2 #W #T1 #T2 #_ #_ #_ #_ #H
  74   elim (tif_inv_appl … H) -H #_ #_ #H
  75   elim (simple_inv_bind … H)
  76 | * #V1 #V2 #T1 #T #T2 #_ #_ #HT2 #IHV1 #IHT1 #H
  77   [ -HT2 IHV1 IHT1; elim (tif_inv_abbr … H)
  78   | <(tps_inv_refl_SO2 … HT2 ?) -HT2 //
  79     elim (tif_inv_abst … H) -H #HV1 #HT1
  80     >IHV1 -IHV1 // -HV1 >IHT1 -IHT1 //
  81   ]
  82 | #V #V1 #V2 #W1 #W2 #T1 #T2 #_ #_ #_ #_ #_ #_ #_ #H
  83   elim (tif_inv_appl … H) -H #_ #_ #H
  84   elim (simple_inv_bind … H)
  85 | #V1 #T1 #T2 #T #_ #_ #_ #H
  86   elim (tif_inv_abbr … H)
  87 | #V1 #T1 #T #_ #_ #H
  88   elim (tif_inv_cast … H)
  89 ]
  90 qed.
  91
  92 theorem tif_tnf: ∀T1.  𝕀[T1] → ℕ[T1].
  93 /2/ qed.
  94
  95 (* Note: this property is unusual *)
  96 theorem tnf_trf_false: ∀T1. ℝ[T1] → ℕ[T1] → False.
  97 #T1 #H elim H -T1
  98 [ #V #T #_ #IHV #H elim (tnf_inv_abst … H) -H /2/
  99 | #V #T #_ #IHT #H elim (tnf_inv_abst … H) -H /2/
 100 | #V #T #_ #IHV #H elim (tnf_inv_appl … H) -H /2/
 101 | #V #T #_ #IHV #H elim (tnf_inv_appl … H) -H /2/
 102 | #V #T #H elim (tnf_inv_abbr … H)
 103 | #V #T #H elim (tnf_inv_cast … H)
 104 | #V #W #T #H elim (tnf_inv_appl … H) -H #_ #_ #H
 105   elim (simple_inv_bind … H)
 106 ]
 107 qed.
 108
 109 theorem tnf_tif: ∀T1. ℕ[T1] → 𝕀[T1].
 110 /2/ qed.
 111
 112 lemma tnf_abst: ∀V,T. ℕ[V] → ℕ[T] → ℕ[𝕔{Abst}V.T].
 113 /4 width=1/ qed.
 114
 115 lemma tnf_appl: ∀V,T. ℕ[V] → ℕ[T] → 𝕊[T] → ℕ[𝕔{Appl}V.T].
 116 /4 width=1/ qed.