matita/matita/contribs/lambdadelta/ground/relocation/pr_after_pat.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 "ground/relocation/pr_pat_pat.ma".
  16 include "ground/relocation/pr_after.ma".
  17
  18 (* RELATIONAL COMPOSITION FOR PARTIAL RELOCATION MAPS ***********************)
  19
  20 (* Destructions with pr_pat *************************************************)
  21
  22 (*** after_at_fwd *)
  23 lemma pr_after_pat_des (i) (i1):
  24       ∀f. @❨i1, f❩ ≘ i → ∀f2,f1. f2 ⊚ f1 ≘ f →
  25       ∃∃i2. @❨i1, f1❩ ≘ i2 & @❨i2, f2❩ ≘ i.
  26 #i elim i -i [2: #i #IH ] #i1 #f #Hf #f2 #f1 #Hf21
  27 [ elim (pr_pat_inv_succ_dx … Hf) -Hf [1,3:* |*: // ]
  28   [1: #g #j1 #Hg #H0 #H |2,4: #g #Hg #H ]
  29 | elim (pr_pat_inv_unit_dx … Hf) -Hf //
  30   #g #H1 #H
  31 ]
  32 [2: elim (pr_after_inv_next … Hf21 … H) -f *
  33     [ #g2 #g1 #Hg21 #H2 #H1 | #g2 #Hg21 #H2 ]
  34 |*: elim (pr_after_inv_push … Hf21 … H) -f
  35     #g2 #g1 #Hg21 #H2 #H1
  36 ]
  37 [4: -Hg21 |*: elim (IH … Hg … Hg21) -g -IH ]
  38 /3 width=9 by pr_pat_refl, pr_pat_push, pr_pat_next, ex2_intro/
  39 qed-.
  40
  41 (*** after_fwd_at *)
  42 lemma pr_after_des_pat (i) (i2) (i1):
  43       ∀f1,f2. @❨i1, f1❩ ≘ i2 → @❨i2, f2❩ ≘ i →
  44       ∀f. f2 ⊚ f1 ≘ f → @❨i1, f❩ ≘ i.
  45 #i elim i -i [2: #i #IH ] #i2 #i1 #f1 #f2 #Hf1 #Hf2 #f #Hf
  46 [ elim (pr_pat_inv_succ_dx … Hf2) -Hf2 [1,3: * |*: // ]
  47   #g2 [ #j2 ] #Hg2 [ #H22 ] #H20
  48   [ elim (pr_pat_inv_succ_dx … Hf1 … H22) -i2 *
  49     #g1 [ #j1 ] #Hg1 [ #H11 ] #H10
  50     [ elim (pr_after_inv_push_bi … Hf … H20 H10) -f1 -f2 /3 width=7 by pr_pat_push/
  51     | elim (pr_after_inv_push_next … Hf … H20 H10) -f1 -f2 /3 width=6 by pr_pat_next/
  52     ]
  53   | elim (pr_after_inv_next_sn … Hf … H20) -f2 /3 width=7 by pr_pat_next/
  54   ]
  55 | elim (pr_pat_inv_unit_dx … Hf2) -Hf2 // #g2 #H22 #H20
  56   elim (pr_pat_inv_unit_dx … Hf1 … H22) -i2 #g1 #H11 #H10
  57   elim (pr_after_inv_push_bi … Hf … H20 H10) -f1 -f2 /2 width=2 by pr_pat_refl/
  58 ]
  59 qed-.
  60
  61 (*** after_fwd_at2 *)
  62 lemma pr_after_des_pat_sn (i1) (i):
  63       ∀f. @❨i1, f❩ ≘ i → ∀f1,i2. @❨i1, f1❩ ≘ i2 →
  64       ∀f2. f2 ⊚ f1 ≘ f → @❨i2, f2❩ ≘ i.
  65 #i1 #i #f #Hf #f1 #i2 #Hf1 #f2 #H elim (pr_after_pat_des … Hf … H) -f
  66 #j1 #H #Hf2 <(pr_pat_mono … Hf1 … H) -i1 -i2 //
  67 qed-.
  68
  69 (*** after_fwd_at1 *)
  70 lemma pr_after_des_pat_dx (i) (i2) (i1):
  71       ∀f,f2. @❨i1, f❩ ≘ i → @❨i2, f2❩ ≘ i →
  72       ∀f1. f2 ⊚ f1 ≘ f → @❨i1, f1❩ ≘ i2.
  73 #i elim i -i [2: #i #IH ] #i2 #i1 #f #f2 #Hf #Hf2 #f1 #Hf1
  74 [ elim (pr_pat_inv_succ_dx … Hf) -Hf [1,3: * |*: // ]
  75   #g [ #j1 ] #Hg [ #H01 ] #H00
  76   elim (pr_pat_inv_succ_dx … Hf2) -Hf2 [1,3,5,7: * |*: // ]
  77   #g2 [1,3: #j2 ] #Hg2 [1,2: #H22 ] #H20
  78   [ elim (pr_after_inv_push_sn_push … Hf1 … H20 H00) -f2 -f /3 width=7 by pr_pat_push/
  79   | elim (pr_after_inv_push_sn_next … Hf1 … H20 H00) -f2 -f /3 width=5 by pr_pat_next/
  80   | elim (pr_after_inv_next_sn_push … Hf1 … H20 H00)
  81   | /4 width=9 by pr_after_inv_next_sn_next, pr_pat_next/
  82   ]
  83 | elim (pr_pat_inv_unit_dx … Hf) -Hf // #g #H01 #H00
  84   elim (pr_pat_inv_unit_dx … Hf2) -Hf2 // #g2 #H21 #H20
  85   elim (pr_after_inv_push_sn_push … Hf1 … H20 H00) -f2 -f /3 width=2 by pr_pat_refl/
  86 ]
  87 qed-.