matita/matita/contribs/lambda_delta/basic_2/equivalence/cpcs_delift.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 "basic_2/unfold/delift_lift.ma".
  16 include "basic_2/unfold/delift_delift.ma".
  17 include "basic_2/computation/cprs_delift.ma".
  18 include "basic_2/equivalence/cpcs_cpcs.ma".
  19
  20 (* CONTEXT-SENSITIVE PARALLEL EQUIVALENCE ON TERMS **************************)
  21
  22 (* Advanced inversion lemmas ************************************************)
  23 (* does not holds
  24 axiom cprs_inv_appl1_cpcs: ∀L,V1,T1,U2. L ⊢ ⓐV1. T1 ➡* U2 → (
  25                            ∃∃V2,T2.    L ⊢ V1 ➡* V2 & L ⊢ T1 ➡* T2 &
  26                                        L ⊢ U2 ➡* ⓐV2. T2
  27                            ) ∨
  28                            ∃∃a,V2,W,T. L ⊢ V1 ➡* V2 &
  29                                        L ⊢ T1 ➡* ⓛ{a}W. T & L ⊢ ⓓ{a}V2. T ⬌* U2.
  30 #L #V1 #T1 #U2 #H @(cprs_ind … H) -U2 /3 width=5/
  31 #U #U2 #_ #HU2 * *
  32 [ #V0 #T0 #HV10 #HT10 #HUT0
  33   elim (cprs_strip … HUT0 … HU2) -U #U #H #HU2
  34   elim (cpr_inv_appl1 … H) -H *
  35   [ #V2 #T2 #HV02 #HT02 #H destruct /4 width=5/
  36   | #b #V2 #W2 #T #T2 #HV02 #HT2 #H1 #H2 destruct
  37     lapply (cprs_strap1 … HV10 HV02) -V0 #HV12
  38     lapply (cprs_div ? (ⓓ{b}V2.T) ? ? ? HU2) -HU2 /2 width=1/ /3 width=7/
  39   | #b #V #V2 #W0 #W2 #T #T2 #HV0 #HW02 #HT2 #HV2 #H1 #H2 destruct
  40     lapply (cprs_strap1 … HV10 HV0) -V0 #HV1
  41     lapply (cprs_trans … HT10 (ⓓ{b}W2.T2) ?) -HT10 /2 width=1/ -W0 -T #HT1
  42     elim (sfr_delift (L.ⓓW2) (ⓐV2.T2) 0 1 ? ?) // #X #H1
  43     lapply (cprs_zeta_delift … H1) #H2
  44     lapply (cprs_trans … HU2 … H2) -HU2 -H2 #HU2T3
  45     elim (delift_inv_flat1 … H1) -H1 #V3 #T3 #HV23 #HT23 #H destruct
  46     lapply (delift_inv_lift1_eq … HV23 … HV2) -V2 [ /2 width=1/ | skip ] #H destruct
  47     lapply (cprs_zeta_delift … HT23) -HT23 #H
  48     lapply (cprs_trans … HT1 … H) -W2 -T2 /3 width=5/
  49   ]
  50 | /4 width=8/
  51 ]
  52 qed-.
  53 *)
  54 (* maybe holds
  55 axiom cprs_inv_appl_abst: ∀L,V,T,W,U. L ⊢ ⓐV.T ➡* ⓛW.U →
  56                           ∃∃W0,T0,V1,T1. L ⊢ T ➡* ⓛW0.T0 &
  57                                          L ⊢ ⓓV.T0 ➡* ⓛV1.T1 &
  58                                          L ⊢ ⓛW.U ➡* ⓛV1.T1.
  59 #L #V #T #W #U #H
  60 elim (cprs_inv_appl1_cpcs … H) -H *
  61 [ #V0 #T0 #HV0 #HT0 #H
  62   elim (cprs_inv_abst1 Abst W … H) -H #W0 #U0 #_ #_ #H destruct
  63 | #V0 #W0 #T0 #HV0 #HT0 #H
  64   elim (cpcs_inv_abst2 … H) -H #V1 #T1 #H1 #H2
  65   lapply (cprs_trans … (ⓓV.T0) … H1) -H1 /2 width=1/ -V0 /2 width=7/
  66 ]
  67 qed-.
  68 *)
  69 (* Properties on inverse basic term relocation ******************************)
  70
  71 lemma cpcs_zeta_delift_comm: ∀L,V,T1,T2. L.ⓓV ⊢ ▼*[O, 1] T1 ≡ T2 →
  72                              L ⊢ T2 ⬌* +ⓓV.T1.
  73 /3 width=1/ qed.
  74
  75 (* Basic_1: was only: pc3_gen_cabbr *)
  76 lemma thin_cpcs_delift_mono: ∀L,U1,U2. L ⊢ U1 ⬌* U2 →
  77                              ∀K,d,e. ▼*[d, e] L ≡ K → ∀T1. L ⊢ ▼*[d, e] U1 ≡ T1 →
  78                              ∀T2. L ⊢ ▼*[d, e] U2 ≡ T2 → K ⊢ T1 ⬌* T2.
  79 #L #U1 #U2 #H #K #d #e #HLK #T1 #HTU1 #T2 #HTU2
  80 elim (cpcs_inv_cprs … H) -H #U #HU1 #HU2
  81 elim (thin_cprs_delift_conf … HU1 … HLK … HTU1) -U1 #T #HT1 #HUT
  82 elim (thin_cprs_delift_conf … HU2 … HLK … HTU2) -U2 -HLK #X #HT2 #H
  83 lapply (delift_mono … H … HUT) -L #H destruct /2 width=3/
  84 qed.