matita/matita/contribs/lambda_delta/basic_2/reducibility/cpr_cpr.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/reducibility/tpr_tpr.ma".
  16 include "basic_2/reducibility/cpr.ma".
  17
  18 (* CONTEXT-SENSITIVE PARALLEL REDUCTION ON TERMS ****************************)
  19
  20 (* Advanced properties ******************************************************)
  21
  22 lemma cpr_bind_sn: ∀I,L,V1,V2,T1,T2. L ⊢ V1 ➡ V2 → T1 ➡ T2 →
  23                    L ⊢ ⓑ{I} V1. T1 ➡ ⓑ{I} V2. T2.
  24 #I #L #V1 #V2 #T1 #T2 * #V #HV1 #HV2 #HT12
  25 @ex2_1_intro [2: @(tpr_delta … HV1 HT12) | skip ] /2 width=3/ (* /3 width=5/ is too slow *)
  26 qed.
  27
  28 (* Basic_1: was only: pr2_gen_cbind *)
  29 lemma cpr_bind_dx: ∀I,L,V1,V2,T1,T2. V1 ➡ V2 → L. ⓑ{I} V2 ⊢ T1 ➡ T2 →
  30                    L ⊢ ⓑ{I} V1. T1 ➡ ⓑ{I} V2. T2.
  31 #I #L #V1 #V2 #T1 #T2 #HV12 * #T #HT1 normalize #HT2
  32 elim (tpss_split_up … HT2 1 ? ?) -HT2 // #T0 <minus_n_O #HT0 normalize <minus_plus_m_m #HT02
  33 lapply (tpss_lsubs_conf … HT0 (⋆. ⓑ{I} V2) ?) -HT0 /2 width=1/ #HT0
  34 lapply (tpss_tps … HT0) -HT0 #HT0
  35 @ex2_1_intro [2: @(tpr_delta … HV12 HT1 HT0) | skip | /2 width=1/ ] (**) (* /3 width=5/ is too slow *)
  36 qed.
  37
  38 (* Basic_1: was only: pr2_head_1 *)
  39 lemma cpr_pair_sn: ∀I,L,V1,V2,T1,T2. L ⊢ V1 ➡ V2 → T1 ➡ T2 →
  40                    L ⊢ ②{I} V1. T1 ➡ ②{I} V2. T2.
  41 * /2 width=1/ /3 width=1/
  42 qed.
  43
  44 (* Advanced forward lemmas **************************************************)
  45
  46 lemma cpr_shift_fwd: ∀L,T1,T2. L ⊢ T1 ➡ T2 → L @ T1 ➡ L @ T2.
  47 #L elim L -L
  48 [ #T1 #T2 #HT12 @(cpr_inv_atom … HT12)
  49 | normalize /3 width=1/
  50 ].
  51 qed-.
  52
  53 (* Main properties **********************************************************)
  54
  55 (* Basic_1: was: pr2_confluence *)
  56 theorem cpr_conf: ∀L,U0,T1,T2. L ⊢ U0 ➡ T1 → L ⊢ U0 ➡ T2 →
  57                   ∃∃T. L ⊢ T1 ➡ T & L ⊢ T2 ➡ T.
  58 #L #U0 #T1 #T2 * #U1 #HU01 #HUT1 * #U2 #HU02 #HUT2
  59 elim (tpr_conf … HU01 HU02) -U0 #U #HU1 #HU2
  60 elim (tpr_tpss_ltpr ? L … HU1 … HUT1) -U1 // #U1 #HTU1 #HU1
  61 elim (tpr_tpss_ltpr ? L … HU2 … HUT2) -U2 // #U2 #HTU2 #HU2
  62 elim (tpss_conf_eq … HU1 … HU2) -U /3 width=5/
  63 qed.