matita/matita/contribs/lambda/labelled_hap_reduction.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 "labelled_sequential_reduction.ma".
  16
  17 (* KASHIMA'S "HAP" COMPUTATION (LABELLED SINGLE STEP) ***********************)
  18
  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).
  21 *)
  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)
  25 .
  26
  27 interpretation "labelled 'hap' reduction"
  28    'HAp M p N = (lhap1 p M N).
  29
  30 notation "hvbox( M break ⓗ↦ [ term 46 p ] break term 46 N )"
  31    non associative with precedence 45
  32    for @{ 'HAp $M $p $N }.
  33
  34 lemma lhap1_inv_nil: ∀p,M,N. M ⓗ↦[p] N → ◊ = p →
  35                      ∃∃B,A. @B.𝛌.A = M & [↙B]A = N.
  36 #p #M #N * -p -M -N
  37 [ #B #A #_ /2 width=4/
  38 | #p #B #A1 #A2 #_ #H destruct
  39 ]
  40 qed-.
  41
  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.
  44 #p #M #N * -p -M -N
  45 [ #B #A #c #q #H destruct
  46 | #p #B #A1 #A2 #HA12 #c #q #H destruct /2 width=6/
  47 ]
  48 qed-.
  49
  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 //
  53 qed.
  54
  55 lemma lhap1_inv_lift: ∀p. deliftable_sn (lhap1 p).
  56 #p #h #N1 #N2 #H elim H -p -N1 -N2
  57 [ #D #C #d #M1 #H
  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/
  64 ]
  65 qed-.
  66
  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 //
  70 qed.
  71
  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 //
  75 | #p #_ #IHp #M #N #H
  76   elim (lsred_inv_dx … H ??) -H [3: // |2: skip ] /3 width=1/ (**) (* simplify line *)
  77 ]
  78 qed.
  79
  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/
  82 qed-.
  83
  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/
  86 qed-.
  87
  88 theorem lhap1_mono: ∀p. singlevalued … (lhap1 p).
  89 #p #M #N1 #H elim H -p -M -N1
  90 [ #B #A #N2 #H
  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/
  95 ]
  96 qed-.