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/static/sd.ma".
16 include "basic_2/reduction/crr.ma".
18 (* CONTEXT-SENSITIVE EXTENDED REDUCIBLE TERMS *******************************)
20 (* extended reducible terms *)
21 inductive crx (h) (g): lenv → predicate term ≝
22 | crx_sort : ∀L,k,l. deg h g k (l+1) → crx h g L (⋆k)
23 | crx_delta : ∀I,L,K,V,i. ⇩[0, i] L ≡ K.ⓑ{I}V → crx h g L (#i)
24 | crx_appl_sn: ∀L,V,T. crx h g L V → crx h g L (ⓐV.T)
25 | crx_appl_dx: ∀L,V,T. crx h g L T → crx h g L (ⓐV.T)
26 | crx_ri2 : ∀I,L,V,T. ri2 I → crx h g L (②{I}V.T)
27 | crx_ib2_sn : ∀a,I,L,V,T. ib2 a I → crx h g L V → crx h g L (ⓑ{a,I}V.T)
28 | crx_ib2_dx : ∀a,I,L,V,T. ib2 a I → crx h g (L.ⓑ{I}V) T → crx h g L (ⓑ{a,I}V.T)
29 | crx_beta : ∀a,L,V,W,T. crx h g L (ⓐV. ⓛ{a}W.T)
30 | crx_theta : ∀a,L,V,W,T. crx h g L (ⓐV. ⓓ{a}W.T)
34 "context-sensitive extended reducibility (term)"
35 'Reducible h g L T = (crx h g L T).
37 (* Basic properties *********************************************************)
39 lemma crr_crx: ∀h,g,L,T. L ⊢ 𝐑⦃T⦄ → ⦃h, L⦄ ⊢ 𝐑[g]⦃T⦄.
40 #h #g #L #T #H elim H -L -T // /2 width=1/ /2 width=4/
43 (* Basic inversion lemmas ***************************************************)
45 fact crx_inv_sort_aux: ∀h,g,L,T,k. ⦃h, L⦄ ⊢ 𝐑[g]⦃T⦄ → T = ⋆k →
47 #h #g #L #T #k0 * -L -T
48 [ #L #k #l #Hkl #H destruct /2 width=2/
49 | #I #L #K #V #i #HLK #H destruct
50 | #L #V #T #_ #H destruct
51 | #L #V #T #_ #H destruct
52 | #I #L #V #T #_ #H destruct
53 | #a #I #L #V #T #_ #_ #H destruct
54 | #a #I #L #V #T #_ #_ #H destruct
55 | #a #L #V #W #T #H destruct
56 | #a #L #V #W #T #H destruct
60 lemma crx_inv_sort: ∀h,g,L,k. ⦃h, L⦄ ⊢ 𝐑[g]⦃⋆k⦄ → ∃l. deg h g k (l+1).
61 /2 width=4 by crx_inv_sort_aux/ qed-.
63 fact crx_inv_lref_aux: ∀h,g,L,T,i. ⦃h, L⦄ ⊢ 𝐑[g]⦃T⦄ → T = #i →
64 ∃∃I,K,V. ⇩[0, i] L ≡ K.ⓑ{I}V.
65 #h #g #L #T #j * -L -T
66 [ #L #k #l #_ #H destruct
67 | #I #L #K #V #i #HLK #H destruct /2 width=4/
68 | #L #V #T #_ #H destruct
69 | #L #V #T #_ #H destruct
70 | #I #L #V #T #_ #H destruct
71 | #a #I #L #V #T #_ #_ #H destruct
72 | #a #I #L #V #T #_ #_ #H destruct
73 | #a #L #V #W #T #H destruct
74 | #a #L #V #W #T #H destruct
78 lemma crx_inv_lref: ∀h,g,L,i. ⦃h, L⦄ ⊢ 𝐑[g]⦃#i⦄ → ∃∃I,K,V. ⇩[0, i] L ≡ K.ⓑ{I}V.
79 /2 width=5 by crx_inv_lref_aux/ qed-.
81 fact crx_inv_gref_aux: ∀h,g,L,T,p. ⦃h, L⦄ ⊢ 𝐑[g]⦃T⦄ → T = §p → ⊥.
82 #h #g #L #T #q * -L -T
83 [ #L #k #l #_ #H destruct
84 | #I #L #K #V #i #HLK #H destruct
85 | #L #V #T #_ #H destruct
86 | #L #V #T #_ #H destruct
87 | #I #L #V #T #_ #H destruct
88 | #a #I #L #V #T #_ #_ #H destruct
89 | #a #I #L #V #T #_ #_ #H destruct
90 | #a #L #V #W #T #H destruct
91 | #a #L #V #W #T #H destruct
95 lemma crx_inv_gref: ∀h,g,L,p. ⦃h, L⦄ ⊢ 𝐑[g]⦃§p⦄ → ⊥.
96 /2 width=7 by crx_inv_gref_aux/ qed-.
98 lemma trx_inv_atom: ∀h,g,I. ⦃h, ⋆⦄ ⊢ 𝐑[g]⦃⓪{I}⦄ →
99 ∃∃k,l. deg h g k (l+1) & I = Sort k.
101 [ elim (crx_inv_sort … H) -H /2 width=4/
102 | elim (crx_inv_lref … H) -H #I #L #V #H
103 elim (ldrop_inv_atom1 … H) -H #H destruct
104 | elim (crx_inv_gref … H)
108 fact crx_inv_ib2_aux: ∀h,g,a,I,L,W,U,T. ib2 a I → ⦃h, L⦄ ⊢ 𝐑[g]⦃T⦄ →
109 T = ⓑ{a,I}W.U → ⦃h, L⦄ ⊢ 𝐑[g]⦃W⦄ ∨ ⦃h, L.ⓑ{I}W⦄ ⊢ 𝐑[g]⦃U⦄.
110 #h #g #b #J #L #W0 #U #T #HI * -L -T
111 [ #L #k #l #_ #H destruct
112 | #I #L #K #V #i #_ #H destruct
113 | #L #V #T #_ #H destruct
114 | #L #V #T #_ #H destruct
115 | #I #L #V #T #H1 #H2 destruct
116 elim H1 -H1 #H destruct
117 elim HI -HI #H destruct
118 | #a #I #L #V #T #_ #HV #H destruct /2 width=1/
119 | #a #I #L #V #T #_ #HT #H destruct /2 width=1/
120 | #a #L #V #W #T #H destruct
121 | #a #L #V #W #T #H destruct
125 lemma crx_inv_ib2: ∀h,g,a,I,L,W,T. ib2 a I → ⦃h, L⦄ ⊢ 𝐑[g]⦃ⓑ{a,I}W.T⦄ →
126 ⦃h, L⦄ ⊢ 𝐑[g]⦃W⦄ ∨ ⦃h, L.ⓑ{I}W⦄ ⊢ 𝐑[g]⦃T⦄.
127 /2 width=5 by crx_inv_ib2_aux/ qed-.
129 fact crx_inv_appl_aux: ∀h,g,L,W,U,T. ⦃h, L⦄ ⊢ 𝐑[g]⦃T⦄ → T = ⓐW.U →
130 ∨∨ ⦃h, L⦄ ⊢ 𝐑[g]⦃W⦄ | ⦃h, L⦄ ⊢ 𝐑[g]⦃U⦄ | (𝐒⦃U⦄ → ⊥).
131 #h #g #L #W0 #U #T * -L -T
132 [ #L #k #l #_ #H destruct
133 | #I #L #K #V #i #_ #H destruct
134 | #L #V #T #HV #H destruct /2 width=1/
135 | #L #V #T #HT #H destruct /2 width=1/
136 | #I #L #V #T #H1 #H2 destruct
137 elim H1 -H1 #H destruct
138 | #a #I #L #V #T #_ #_ #H destruct
139 | #a #I #L #V #T #_ #_ #H destruct
140 | #a #L #V #W #T #H destruct
141 @or3_intro2 #H elim (simple_inv_bind … H)
142 | #a #L #V #W #T #H destruct
143 @or3_intro2 #H elim (simple_inv_bind … H)
147 lemma crx_inv_appl: ∀h,g,L,V,T. ⦃h, L⦄ ⊢ 𝐑[g]⦃ⓐV.T⦄ →
148 ∨∨ ⦃h, L⦄ ⊢ 𝐑[g]⦃V⦄ | ⦃h, L⦄ ⊢ 𝐑[g]⦃T⦄ | (𝐒⦃T⦄ → ⊥).
149 /2 width=3 by crx_inv_appl_aux/ qed-.