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 "labelled_sequential_reduction.ma".
17 (* KASHIMA'S "HAP" COMPUTATION (LABELLED SINGLE STEP) ***********************)
19 (* Note: this is one step of the "head in application" computation of:
20 R. Kashima: "A proof of the Standization Theorem in λ-Calculus". Typescript note, (2000).
22 inductive lhap1: ptr → relation term ≝
23 | hap1_beta: ∀B,A. lhap1 (◊) (@B.𝛌.A) ([↙B]A)
24 | hap1_appl: ∀p,B,A1,A2. lhap1 p A1 A2 → lhap1 (dx::p) (@B.A1) (@B.A2)
27 interpretation "labelled 'hap' reduction"
28 'HAp M p N = (lhap1 p M N).
30 notation "hvbox( M break ⓗ↦ [ term 46 p ] break term 46 N )"
31 non associative with precedence 45
32 for @{ 'HAp $M $p $N }.
34 lemma lhap1_inv_nil: ∀p,M,N. M ⓗ↦[p] N → ◊ = p →
35 ∃∃B,A. @B.𝛌.A = M & [↙B]A = N.
37 [ #B #A #_ /2 width=4/
38 | #p #B #A1 #A2 #_ #H destruct
42 lemma lhap1_inv_cons: ∀p,M,N. M ⓗ↦[p] N → ∀c,q. c::q = p →
43 ∃∃B,A1,A2. dx = c & A1 ⓗ↦[q] A2 & @B.A1 = M & @B.A2 = N.
45 [ #B #A #c #q #H destruct
46 | #p #B #A1 #A2 #HA12 #c #q #H destruct /2 width=6/
50 lemma lhap1_lift: ∀p. liftable (lhap1 p).
51 #p #h #M1 #M2 #H elim H -p -M1 -M2 normalize /2 width=1/
52 #B #A #d <dsubst_lift_le //
55 lemma lhap1_inv_lift: ∀p. deliftable_sn (lhap1 p).
56 #p #h #N1 #N2 #H elim H -p -N1 -N2
58 elim (lift_inv_appl … H) -H #B #M #H0 #HM #H destruct
59 elim (lift_inv_abst … HM) -HM #A #H0 #H destruct /3 width=3/
60 | #p #D1 #C1 #C2 #_ #IHC12 #d #M1 #H
61 elim (lift_inv_appl … H) -H #B #A1 #H1 #H2 #H destruct
62 elim (IHC12 ???) -IHC12 [4: // |2,3: skip ] #A2 #HA12 #H destruct (**) (* simplify line *)
63 @(ex2_intro … (@B.A2)) // /2 width=1/
67 lemma lhap1_dsubst: ∀p. dsubstable_dx (lhap1 p).
68 #p #D1 #M1 #M2 #H elim H -p -M1 -M2 normalize /2 width=1/
69 #D2 #A #d >dsubst_dsubst_ge //
72 lemma head_lsred_lhap1: ∀p. in_head p → ∀M,N. M ↦[p] N → M ⓗ↦[p] N.
73 #p #H @(in_head_ind … H) -p
74 [ #M #N #H elim (lsred_inv_nil … H ?) -H //
76 elim (lsred_inv_dx … H ??) -H [3: // |2: skip ] /3 width=1/ (**) (* simplify line *)
80 lemma lhap1_inv_head: ∀p,M,N. M ⓗ↦[p] N → in_head p.
81 #p #M #N #H elim H -p -M -N // /2 width=1/
84 lemma lhap1_inv_lsred: ∀p,M,N. M ⓗ↦[p] N → M ↦[p] N.
85 #p #M #N #H elim H -p -M -N // /2 width=1/
88 theorem lhap1_mono: ∀p. singlevalued … (lhap1 p).
89 #p #M #N1 #H elim H -p -M -N1
91 elim (lhap1_inv_nil … H ?) -H // #D #C #H #HN2 destruct //
92 | #p #B #A1 #A2 #_ #IHA12 #N2 #H
93 elim (lhap1_inv_cons … H ???) -H [4: // |2,3: skip ] (**) (* simplify line *)
94 #D #C1 #C2 #_ #HC12 #H #HN2 destruct /3 width=1/