1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "basic_2/notation/relations/cosn_5.ma".
16 include "basic_2/computation/lsx.ma".
18 (* SN EXTENDED STRONGLY CONORMALIZING LOCAL ENVIRONMENTS ********************)
20 inductive lcosx (h) (g) (G): relation2 ynat lenv ≝
21 | lcosx_sort: ∀d. lcosx h g G d (⋆)
22 | lcosx_skip: ∀I,L,T. lcosx h g G 0 L → lcosx h g G 0 (L.ⓑ{I}T)
23 | lcosx_pair: ∀I,L,T,d. G ⊢ ⬊*[h, g, T, d] L →
24 lcosx h g G d L → lcosx h g G (⫯d) (L.ⓑ{I}T)
28 "sn extended strong conormalization (local environment)"
29 'CoSN h g d G L = (lcosx h g G d L).
31 (* Basic properties *********************************************************)
33 lemma lcosx_O: ∀h,g,G,L. G ⊢ ~⬊*[h, g, 0] L.
34 #h #g #G #L elim L /2 width=1 by lcosx_skip/
37 lemma lcosx_drop_trans_lt: ∀h,g,G,L,d. G ⊢ ~⬊*[h, g, d] L →
38 ∀I,K,V,i. ⇩[i] L ≡ K.ⓑ{I}V → i < d →
39 G ⊢ ~⬊*[h, g, ⫰(d-i)] K ∧ G ⊢ ⬊*[h, g, V, ⫰(d-i)] K.
40 #h #g #G #L #d #H elim H -L -d
41 [ #d #J #K #V #i #H elim (drop_inv_atom1 … H) -H #H destruct
42 | #I #L #T #_ #_ #J #K #V #i #_ #H elim (ylt_yle_false … H) -H //
43 | #I #L #T #d #HT #HL #IHL #J #K #V #i #H #Hid
44 elim (drop_inv_O1_pair1 … H) -H * #Hi #HLK destruct
45 [ >ypred_succ /2 width=1 by conj/
46 | lapply (ylt_pred … Hid ?) -Hid /2 width=1 by ylt_inj/ >ypred_succ #Hid
47 elim (IHL … HLK ?) -IHL -HLK <yminus_inj >yminus_SO2 //
48 <(ypred_succ d) in ⊢ (%→%→?); >yminus_pred /2 width=1 by ylt_inj, conj/
53 (* Basic inversion lemmas ***************************************************)
55 fact lcosx_inv_succ_aux: ∀h,g,G,L,x. G ⊢ ~⬊*[h, g, x] L → ∀d. x = ⫯d →
57 ∃∃I,K,V. L = K.ⓑ{I}V & G ⊢ ~⬊*[h, g, d] K &
59 #h #g #G #L #d * -L -d /2 width=1 by or_introl/
60 [ #I #L #T #_ #x #H elim (ysucc_inv_O_sn … H)
61 | #I #L #T #d #HT #HL #x #H <(ysucc_inj … H) -x
62 /3 width=6 by ex3_3_intro, or_intror/
66 lemma lcosx_inv_succ: ∀h,g,G,L,d. G ⊢ ~⬊*[h, g, ⫯d] L → L = ⋆ ∨
67 ∃∃I,K,V. L = K.ⓑ{I}V & G ⊢ ~⬊*[h, g, d] K &
69 /2 width=3 by lcosx_inv_succ_aux/ qed-.
71 lemma lcosx_inv_pair: ∀h,g,I,G,L,T,d. G ⊢ ~⬊*[h, g, ⫯d] L.ⓑ{I}T →
72 G ⊢ ~⬊*[h, g, d] L ∧ G ⊢ ⬊*[h, g, T, d] L.
73 #h #g #I #G #L #T #d #H elim (lcosx_inv_succ … H) -H
75 | * #Z #Y #X #H destruct /2 width=1 by conj/