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/reducible_3.ma".
16 include "basic_2/grammar/genv.ma".
17 include "basic_2/relocation/ldrop.ma".
19 (* CONTEXT-SENSITIVE REDUCIBLE TERMS ****************************************)
21 (* reducible binary items *)
22 definition ri2: predicate item2 ≝
23 λI. I = Bind2 true Abbr ∨ I = Flat2 Cast.
25 (* irreducible binary binders *)
26 definition ib2: relation2 bool bind2 ≝
27 λa,I. I = Abst ∨ Bind2 a I = Bind2 false Abbr.
31 inductive crr (G:genv): relation2 lenv term ≝
32 | crr_delta : ∀L,K,V,i. ⇩[0, i] L ≡ K.ⓓV → crr G L (#i)
33 | crr_appl_sn: ∀L,V,T. crr G L V → crr G L (ⓐV.T)
34 | crr_appl_dx: ∀L,V,T. crr G L T → crr G L (ⓐV.T)
35 | crr_ri2 : ∀I,L,V,T. ri2 I → crr G L (②{I}V.T)
36 | crr_ib2_sn : ∀a,I,L,V,T. ib2 a I → crr G L V → crr G L (ⓑ{a,I}V.T)
37 | crr_ib2_dx : ∀a,I,L,V,T. ib2 a I → crr G (L.ⓑ{I}V) T → crr G L (ⓑ{a,I}V.T)
38 | crr_beta : ∀a,L,V,W,T. crr G L (ⓐV.ⓛ{a}W.T)
39 | crr_theta : ∀a,L,V,W,T. crr G L (ⓐV.ⓓ{a}W.T)
43 "context-sensitive reducibility (term)"
44 'Reducible G L T = (crr G L T).
46 (* Basic inversion lemmas ***************************************************)
48 fact crr_inv_sort_aux: ∀G,L,T,k. ⦃G, L⦄ ⊢ 𝐑⦃T⦄ → T = ⋆k → ⊥.
50 [ #L #K #V #i #HLK #H destruct
51 | #L #V #T #_ #H destruct
52 | #L #V #T #_ #H destruct
53 | #I #L #V #T #_ #H destruct
54 | #a #I #L #V #T #_ #_ #H destruct
55 | #a #I #L #V #T #_ #_ #H destruct
56 | #a #L #V #W #T #H destruct
57 | #a #L #V #W #T #H destruct
61 lemma crr_inv_sort: ∀G,L,k. ⦃G, L⦄ ⊢ 𝐑⦃⋆k⦄ → ⊥.
62 /2 width=6 by crr_inv_sort_aux/ qed-.
64 fact crr_inv_lref_aux: ∀G,L,T,i. ⦃G, L⦄ ⊢ 𝐑⦃T⦄ → T = #i →
65 ∃∃K,V. ⇩[0, i] L ≡ K.ⓓV.
67 [ #L #K #V #i #HLK #H destruct /2 width=3/
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 crr_inv_lref: ∀G,L,i. ⦃G, L⦄ ⊢ 𝐑⦃#i⦄ → ∃∃K,V. ⇩[0, i] L ≡ K.ⓓV.
79 /2 width=4 by crr_inv_lref_aux/ qed-.
81 fact crr_inv_gref_aux: ∀G,L,T,p. ⦃G, L⦄ ⊢ 𝐑⦃T⦄ → T = §p → ⊥.
83 [ #L #K #V #i #HLK #H destruct
84 | #L #V #T #_ #H destruct
85 | #L #V #T #_ #H destruct
86 | #I #L #V #T #_ #H destruct
87 | #a #I #L #V #T #_ #_ #H destruct
88 | #a #I #L #V #T #_ #_ #H destruct
89 | #a #L #V #W #T #H destruct
90 | #a #L #V #W #T #H destruct
94 lemma crr_inv_gref: ∀G,L,p. ⦃G, L⦄ ⊢ 𝐑⦃§p⦄ → ⊥.
95 /2 width=6 by crr_inv_gref_aux/ qed-.
97 lemma trr_inv_atom: ∀G,I. ⦃G, ⋆⦄ ⊢ 𝐑⦃⓪{I}⦄ → ⊥.
99 [ elim (crr_inv_sort … H)
100 | elim (crr_inv_lref … H) -H #L #V #H
101 elim (ldrop_inv_atom1 … H) -H #H destruct
102 | elim (crr_inv_gref … H)
106 fact crr_inv_ib2_aux: ∀a,I,G,L,W,U,T. ib2 a I → ⦃G, L⦄ ⊢ 𝐑⦃T⦄ → T = ⓑ{a,I}W.U →
107 ⦃G, L⦄ ⊢ 𝐑⦃W⦄ ∨ ⦃G, L.ⓑ{I}W⦄ ⊢ 𝐑⦃U⦄.
108 #G #b #J #L #W0 #U #T #HI * -L -T
109 [ #L #K #V #i #_ #H destruct
110 | #L #V #T #_ #H destruct
111 | #L #V #T #_ #H destruct
112 | #I #L #V #T #H1 #H2 destruct
113 elim H1 -H1 #H destruct
114 elim HI -HI #H destruct
115 | #a #I #L #V #T #_ #HV #H destruct /2 width=1/
116 | #a #I #L #V #T #_ #HT #H destruct /2 width=1/
117 | #a #L #V #W #T #H destruct
118 | #a #L #V #W #T #H destruct
122 lemma crr_inv_ib2: ∀a,I,G,L,W,T. ib2 a I → ⦃G, L⦄ ⊢ 𝐑⦃ⓑ{a,I}W.T⦄ →
123 ⦃G, L⦄ ⊢ 𝐑⦃W⦄ ∨ ⦃G, L.ⓑ{I}W⦄ ⊢ 𝐑⦃T⦄.
124 /2 width=5 by crr_inv_ib2_aux/ qed-.
126 fact crr_inv_appl_aux: ∀G,L,W,U,T. ⦃G, L⦄ ⊢ 𝐑⦃T⦄ → T = ⓐW.U →
127 ∨∨ ⦃G, L⦄ ⊢ 𝐑⦃W⦄ | ⦃G, L⦄ ⊢ 𝐑⦃U⦄ | (𝐒⦃U⦄ → ⊥).
128 #G #L #W0 #U #T * -L -T
129 [ #L #K #V #i #_ #H destruct
130 | #L #V #T #HV #H destruct /2 width=1/
131 | #L #V #T #HT #H destruct /2 width=1/
132 | #I #L #V #T #H1 #H2 destruct
133 elim H1 -H1 #H destruct
134 | #a #I #L #V #T #_ #_ #H destruct
135 | #a #I #L #V #T #_ #_ #H destruct
136 | #a #L #V #W #T #H destruct
137 @or3_intro2 #H elim (simple_inv_bind … H)
138 | #a #L #V #W #T #H destruct
139 @or3_intro2 #H elim (simple_inv_bind … H)
143 lemma crr_inv_appl: ∀G,L,V,T. ⦃G, L⦄ ⊢ 𝐑⦃ⓐV.T⦄ →
144 ∨∨ ⦃G, L⦄ ⊢ 𝐑⦃V⦄ | ⦃G, L⦄ ⊢ 𝐑⦃T⦄ | (𝐒⦃T⦄ → ⊥).
145 /2 width=3 by crr_inv_appl_aux/ qed-.