matita/matita/contribs/lambdadelta/basic_2A/computation/lcosx.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 "ground_2/ynat/ynat_minus_sn.ma".
  16 include "basic_2A/notation/relations/cosn_5.ma".
  17 include "basic_2A/computation/lsx.ma".
  18
  19 (* SN EXTENDED STRONGLY CONORMALIZING LOCAL ENVIRONMENTS ********************)
  20
  21 inductive lcosx (h) (g) (G): relation2 ynat lenv ≝
  22 | lcosx_sort: ∀l. lcosx h g G l (⋆)
  23 | lcosx_skip: ∀I,L,T. lcosx h g G 0 L → lcosx h g G 0 (L.ⓑ{I}T)
  24 | lcosx_pair: ∀I,L,T,l. G ⊢ ⬊*[h, g, T, l] L →
  25               lcosx h g G l L → lcosx h g G (↑l) (L.ⓑ{I}T)
  26 .
  27
  28 interpretation
  29    "sn extended strong conormalization (local environment)"
  30    'CoSN h g l G L = (lcosx h g G l L).
  31
  32 (* Basic properties *********************************************************)
  33
  34 lemma lcosx_O: ∀h,g,G,L. G ⊢ ~⬊*[h, g, 0] L.
  35 #h #g #G #L elim L /2 width=1 by lcosx_skip/
  36 qed.
  37
  38 lemma lcosx_drop_trans_lt: ∀h,g,G,L,l. G ⊢ ~⬊*[h, g, l] L →
  39                             ∀I,K,V,i. ⬇[i] L ≡ K.ⓑ{I}V → i < l →
  40                             G ⊢ ~⬊*[h, g, ↓(l-i)] K ∧ G ⊢ ⬊*[h, g, V, ↓(l-i)] K.
  41 #h #g #G #L #l #H elim H -L -l
  42 [ #l #J #K #V #i #H elim (drop_inv_atom1 … H) -H #H destruct
  43 | #I #L #T #_ #_ #J #K #V #i #_ #H elim (ylt_yle_false … H) -H //
  44 | #I #L #T #l #HT #HL #IHL #J #K #V #i #H #Hil
  45   elim (drop_inv_O1_pair1 … H) -H * #Hi #HLK destruct
  46   [ >ypred_succ /2 width=1 by conj/
  47   | lapply (ylt_pred … Hil ?) -Hil /2 width=1 by ylt_inj/ >ypred_succ #Hil
  48     elim (IHL … HLK ?) -IHL -HLK >minus_SO_dx //
  49     <(ypred_succ l) in ⊢ (%→%→?); >yminus_pred /2 width=1 by ylt_inj, conj/
  50   ]
  51 ]
  52 qed-.
  53
  54 (* Basic inversion lemmas ***************************************************)
  55
  56 fact lcosx_inv_succ_aux: ∀h,g,G,L,x. G ⊢ ~⬊*[h, g, x] L → ∀l. x = ↑l →
  57                          L = ⋆ ∨
  58                          ∃∃I,K,V. L = K.ⓑ{I}V & G ⊢ ~⬊*[h, g, l] K &
  59                                   G ⊢ ⬊*[h, g, V, l] K.
  60 #h #g #G #L #l * -L -l /2 width=1 by or_introl/
  61 [ #I #L #T #_ #x #H elim (ysucc_inv_O_sn … H)
  62 | #I #L #T #l #HT #HL #x #H <(ysucc_inv_inj … H) -x
  63   /3 width=6 by ex3_3_intro, or_intror/
  64 ]
  65 qed-.
  66
  67 lemma lcosx_inv_succ: ∀h,g,G,L,l. G ⊢ ~⬊*[h, g, ↑l] L → L = ⋆ ∨
  68                       ∃∃I,K,V. L = K.ⓑ{I}V & G ⊢ ~⬊*[h, g, l] K &
  69                                G ⊢ ⬊*[h, g, V, l] K.
  70 /2 width=3 by lcosx_inv_succ_aux/ qed-.
  71
  72 lemma lcosx_inv_pair: ∀h,g,I,G,L,T,l. G ⊢ ~⬊*[h, g, ↑l] L.ⓑ{I}T →
  73                       G ⊢ ~⬊*[h, g, l] L ∧ G ⊢ ⬊*[h, g, T, l] L.
  74 #h #g #I #G #L #T #l #H elim (lcosx_inv_succ … H) -H
  75 [ #H destruct
  76 | * #Z #Y #X #H destruct /2 width=1 by conj/
  77 ]
  78 qed-.