matita/matita/contribs/lambdadelta/basic_2A/reduction/crx.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_2A/notation/relations/predreducible_5.ma".
  16 include "basic_2A/static/sd.ma".
  17 include "basic_2A/reduction/crr.ma".
  18
  19 (* REDUCIBLE TERMS FOR CONTEXT-SENSITIVE EXTENDED REDUCTION *****************)
  20
  21 (* activate genv *)
  22 (* extended reducible terms *)
  23 inductive crx (h) (g) (G:genv): relation2 lenv term ≝
  24 | crx_sort   : ∀L,k,d. deg h g k (d+1) → crx h g G L (⋆k)
  25 | crx_delta  : ∀I,L,K,V,i. ⬇[i] L ≡ K.ⓑ{I}V → crx h g G L (#i)
  26 | crx_appl_sn: ∀L,V,T. crx h g G L V → crx h g G L (ⓐV.T)
  27 | crx_appl_dx: ∀L,V,T. crx h g G L T → crx h g G L (ⓐV.T)
  28 | crx_ri2    : ∀I,L,V,T. ri2 I → crx h g G L (②{I}V.T)
  29 | crx_ib2_sn : ∀a,I,L,V,T. ib2 a I → crx h g G L V → crx h g G L (ⓑ{a,I}V.T)
  30 | crx_ib2_dx : ∀a,I,L,V,T. ib2 a I → crx h g G (L.ⓑ{I}V) T → crx h g G L (ⓑ{a,I}V.T)
  31 | crx_beta   : ∀a,L,V,W,T. crx h g G L (ⓐV. ⓛ{a}W.T)
  32 | crx_theta  : ∀a,L,V,W,T. crx h g G L (ⓐV. ⓓ{a}W.T)
  33 .
  34
  35 interpretation
  36    "reducibility for context-sensitive extended reduction (term)"
  37    'PRedReducible h g G L T = (crx h g G L T).
  38
  39 (* Basic properties *********************************************************)
  40
  41 lemma crr_crx: ∀h,g,G,L,T. ⦃G, L⦄ ⊢ ➡ 𝐑⦃T⦄ → ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃T⦄.
  42 #h #g #G #L #T #H elim H -L -T
  43 /2 width=4 by crx_delta, crx_appl_sn, crx_appl_dx, crx_ri2, crx_ib2_sn, crx_ib2_dx, crx_beta, crx_theta/
  44 qed.
  45
  46 (* Basic inversion lemmas ***************************************************)
  47
  48 fact crx_inv_sort_aux: ∀h,g,G,L,T,k. ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃T⦄ → T = ⋆k →
  49                        ∃d. deg h g k (d+1).
  50 #h #g #G #L #T #k0 * -L -T
  51 [ #L #k #d #Hkd #H destruct /2 width=2 by ex_intro/
  52 | #I #L #K #V #i #HLK #H destruct
  53 | #L #V #T #_ #H destruct
  54 | #L #V #T #_ #H destruct
  55 | #I #L #V #T #_ #H destruct
  56 | #a #I #L #V #T #_ #_ #H destruct
  57 | #a #I #L #V #T #_ #_ #H destruct
  58 | #a #L #V #W #T #H destruct
  59 | #a #L #V #W #T #H destruct
  60 ]
  61 qed-.
  62
  63 lemma crx_inv_sort: ∀h,g,G,L,k. ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃⋆k⦄ → ∃d. deg h g k (d+1).
  64 /2 width=5 by crx_inv_sort_aux/ qed-.
  65
  66 fact crx_inv_lref_aux: ∀h,g,G,L,T,i. ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃T⦄ → T = #i →
  67                        ∃∃I,K,V. ⬇[i] L ≡ K.ⓑ{I}V.
  68 #h #g #G #L #T #j * -L -T
  69 [ #L #k #d #_ #H destruct
  70 | #I #L #K #V #i #HLK #H destruct /2 width=4 by ex1_3_intro/
  71 | #L #V #T #_ #H destruct
  72 | #L #V #T #_ #H destruct
  73 | #I #L #V #T #_ #H destruct
  74 | #a #I #L #V #T #_ #_ #H destruct
  75 | #a #I #L #V #T #_ #_ #H destruct
  76 | #a #L #V #W #T #H destruct
  77 | #a #L #V #W #T #H destruct
  78 ]
  79 qed-.
  80
  81 lemma crx_inv_lref: ∀h,g,G,L,i. ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃#i⦄ → ∃∃I,K,V. ⬇[i] L ≡ K.ⓑ{I}V.
  82 /2 width=6 by crx_inv_lref_aux/ qed-.
  83
  84 fact crx_inv_gref_aux: ∀h,g,G,L,T,p. ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃T⦄ → T = §p → ⊥.
  85 #h #g #G #L #T #q * -L -T
  86 [ #L #k #d #_ #H destruct
  87 | #I #L #K #V #i #HLK #H destruct
  88 | #L #V #T #_ #H destruct
  89 | #L #V #T #_ #H destruct
  90 | #I #L #V #T #_ #H destruct
  91 | #a #I #L #V #T #_ #_ #H destruct
  92 | #a #I #L #V #T #_ #_ #H destruct
  93 | #a #L #V #W #T #H destruct
  94 | #a #L #V #W #T #H destruct
  95 ]
  96 qed-.
  97
  98 lemma crx_inv_gref: ∀h,g,G,L,p. ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃§p⦄ → ⊥.
  99 /2 width=8 by crx_inv_gref_aux/ qed-.
 100
 101 lemma trx_inv_atom: ∀h,g,I,G. ⦃G, ⋆⦄ ⊢ ➡[h, g] 𝐑⦃⓪{I}⦄ →
 102                     ∃∃k,d. deg h g k (d+1) & I = Sort k.
 103 #h #g * #i #G #H
 104 [ elim (crx_inv_sort … H) -H /2 width=4 by ex2_2_intro/
 105 | elim (crx_inv_lref … H) -H #I #L #V #H
 106   elim (drop_inv_atom1 … H) -H #H destruct
 107 | elim (crx_inv_gref … H)
 108 ]
 109 qed-.
 110
 111 fact crx_inv_ib2_aux: ∀h,g,a,I,G,L,W,U,T. ib2 a I → ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃T⦄ →
 112                       T = ⓑ{a,I}W.U → ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃W⦄ ∨ ⦃G, L.ⓑ{I}W⦄ ⊢ ➡[h, g] 𝐑⦃U⦄.
 113 #h #g #b #J #G #L #W0 #U #T #HI * -L -T
 114 [ #L #k #d #_ #H destruct
 115 | #I #L #K #V #i #_ #H destruct
 116 | #L #V #T #_ #H destruct
 117 | #L #V #T #_ #H destruct
 118 | #I #L #V #T #H1 #H2 destruct
 119   elim H1 -H1 #H destruct
 120   elim HI -HI #H destruct
 121 | #a #I #L #V #T #_ #HV #H destruct /2 width=1 by or_introl/
 122 | #a #I #L #V #T #_ #HT #H destruct /2 width=1 by or_intror/
 123 | #a #L #V #W #T #H destruct
 124 | #a #L #V #W #T #H destruct
 125 ]
 126 qed-.
 127
 128 lemma crx_inv_ib2: ∀h,g,a,I,G,L,W,T. ib2 a I → ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃ⓑ{a,I}W.T⦄ →
 129                    ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃W⦄ ∨ ⦃G, L.ⓑ{I}W⦄ ⊢ ➡[h, g] 𝐑⦃T⦄.
 130 /2 width=5 by crx_inv_ib2_aux/ qed-.
 131
 132 fact crx_inv_appl_aux: ∀h,g,G,L,W,U,T. ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃T⦄ → T = ⓐW.U →
 133                        ∨∨ ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃W⦄ | ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃U⦄ | (𝐒⦃U⦄ → ⊥).
 134 #h #g #G #L #W0 #U #T * -L -T
 135 [ #L #k #d #_ #H destruct
 136 | #I #L #K #V #i #_ #H destruct
 137 | #L #V #T #HV #H destruct /2 width=1 by or3_intro0/
 138 | #L #V #T #HT #H destruct /2 width=1 by or3_intro1/
 139 | #I #L #V #T #H1 #H2 destruct
 140   elim H1 -H1 #H destruct
 141 | #a #I #L #V #T #_ #_ #H destruct
 142 | #a #I #L #V #T #_ #_ #H destruct
 143 | #a #L #V #W #T #H destruct
 144   @or3_intro2 #H elim (simple_inv_bind … H)
 145 | #a #L #V #W #T #H destruct
 146   @or3_intro2 #H elim (simple_inv_bind … H)
 147 ]
 148 qed-.
 149
 150 lemma crx_inv_appl: ∀h,g,G,L,V,T. ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃ⓐV.T⦄ →
 151                     ∨∨ ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃V⦄ | ⦃G, L⦄ ⊢ ➡[h, g] 𝐑⦃T⦄ | (𝐒⦃T⦄ → ⊥).
 152 /2 width=3 by crx_inv_appl_aux/ qed-.