matita/matita/contribs/lambdadelta/ground/relocation/pr_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/notation/relations/rat_3.ma".
  16 include "ground/xoa/ex_3_2.ma".
  17 include "ground/arith/pnat.ma".
  18 include "ground/relocation/pr_tl.ma".
  19
  20 (* POSITIVE APPLICATION FOR PARTIAL RELOCATION MAPS *************************)
  21
  22 (*** at *)
  23 coinductive pr_pat: relation3 pr_map pnat pnat ≝
  24 (*** at_refl *)
  25 | pr_pat_refl (f) (g) (j1) (j2):
  26   ⫯f = g → 𝟏 = j1 → 𝟏 = j2 → pr_pat g j1 j2
  27 (*** at_push *)
  28 | pr_pat_push (f) (i1) (i2):
  29   pr_pat f i1 i2 → ∀g,j1,j2. ⫯f = g → ↑i1 = j1 → ↑i2 = j2 → pr_pat g j1 j2
  30 (*** at_next *)
  31 | pr_pat_next (f) (i1) (i2):
  32   pr_pat f i1 i2 → ∀g,j2. ↑f = g → ↑i2 = j2 → pr_pat g i1 j2
  33 .
  34
  35 interpretation
  36   "relational positive application (partial relocation maps)"
  37   'RAt i1 f i2 = (pr_pat f i1 i2).
  38
  39 (*** H_at_div *)
  40 definition H_pr_pat_div: relation4 pr_map pr_map pr_map pr_map ≝
  41            λf2,g2,f1,g1.
  42            ∀jf,jg,j. @❨jf,f2❩ ≘ j → @❨jg,g2❩ ≘ j →
  43            ∃∃j0. @❨j0,f1❩ ≘ jf & @❨j0,g1❩ ≘ jg.
  44
  45 (* Basic inversions *********************************************************)
  46
  47 (*** at_inv_ppx *)
  48 lemma pr_pat_inv_unit_push (f) (i1) (i2):
  49       @❨i1,f❩ ≘ i2 → ∀g. 𝟏 = i1 → ⫯g = f → 𝟏 = i2.
  50 #f #i1 #i2 * -f -i1 -i2 //
  51 [ #f #i1 #i2 #_ #g #j1 #j2 #_ * #_ #x #H destruct
  52 | #f #i1 #i2 #_ #g #j2 * #_ #x #_ #H elim (eq_inv_pr_push_next … H)
  53 ]
  54 qed-.
  55
  56 (*** at_inv_npx *)
  57 lemma pr_pat_inv_succ_push (f) (i1) (i2):
  58       @❨i1,f❩ ≘ i2 → ∀g,j1. ↑j1 = i1 → ⫯g = f →
  59       ∃∃j2. @❨j1,g❩ ≘ j2 & ↑j2 = i2.
  60 #f #i1 #i2 * -f -i1 -i2
  61 [ #f #g #j1 #j2 #_ * #_ #x #x1 #H destruct
  62 | #f #i1 #i2 #Hi #g #j1 #j2 * * * #x #x1 #H #Hf >(eq_inv_pr_push_bi … Hf) -g destruct /2 width=3 by ex2_intro/
  63 | #f #i1 #i2 #_ #g #j2 * #_ #x #x1 #_ #H elim (eq_inv_pr_push_next … H)
  64 ]
  65 qed-.
  66
  67 (*** at_inv_xnx *)
  68 lemma pr_pat_inv_next (f) (i1) (i2):
  69       @❨i1,f❩ ≘ i2 → ∀g. ↑g = f →
  70       ∃∃j2. @❨i1,g❩ ≘ j2 & ↑j2 = i2.
  71 #f #i1 #i2 * -f -i1 -i2
  72 [ #f #g #j1 #j2 * #_ #_ #x #H elim (eq_inv_pr_next_push … H)
  73 | #f #i1 #i2 #_ #g #j1 #j2 * #_ #_ #x #H elim (eq_inv_pr_next_push … H)
  74 | #f #i1 #i2 #Hi #g #j2 * * #x #H >(eq_inv_pr_next_bi … H) -g /2 width=3 by ex2_intro/
  75 ]
  76 qed-.
  77
  78 (* Advanced inversions ******************************************************)
  79
  80 (*** at_inv_ppn *)
  81 lemma pr_pat_inv_unit_push_succ (f) (i1) (i2):
  82       @❨i1,f❩ ≘ i2 → ∀g,j2. 𝟏 = i1 → ⫯g = f → ↑j2 = i2 → ⊥.
  83 #f #i1 #i2 #Hf #g #j2 #H1 #H <(pr_pat_inv_unit_push … Hf … H1 H) -f -g -i1 -i2
  84 #H destruct
  85 qed-.
  86
  87 (*** at_inv_npp *)
  88 lemma pr_pat_inv_succ_push_unit (f) (i1) (i2):
  89       @❨i1,f❩ ≘ i2 → ∀g,j1. ↑j1 = i1 → ⫯g = f → 𝟏 = i2 → ⊥.
  90 #f #i1 #i2 #Hf #g #j1 #H1 #H elim (pr_pat_inv_succ_push … Hf … H1 H) -f -i1
  91 #x2 #Hg * -i2 #H destruct
  92 qed-.
  93
  94 (*** at_inv_npn *)
  95 lemma pr_pat_inv_succ_push_succ (f) (i1) (i2):
  96       @❨i1,f❩ ≘ i2 → ∀g,j1,j2. ↑j1 = i1 → ⫯g = f → ↑j2 = i2 → @❨j1,g❩ ≘ j2.
  97 #f #i1 #i2 #Hf #g #j1 #j2 #H1 #H elim (pr_pat_inv_succ_push … Hf … H1 H) -f -i1
  98 #x2 #Hg * -i2 #H destruct //
  99 qed-.
 100
 101 (*** at_inv_xnp *)
 102 lemma pr_pat_inv_next_unit (f) (i1) (i2):
 103       @❨i1,f❩ ≘ i2 → ∀g. ↑g = f → 𝟏 = i2 → ⊥.
 104 #f #i1 #i2 #Hf #g #H elim (pr_pat_inv_next … Hf … H) -f
 105 #x2 #Hg * -i2 #H destruct
 106 qed-.
 107
 108 (*** at_inv_xnn *)
 109 lemma pr_pat_inv_next_succ (f) (i1) (i2):
 110       @❨i1,f❩ ≘ i2 → ∀g,j2. ↑g = f → ↑j2 = i2 → @❨i1,g❩ ≘ j2.
 111 #f #i1 #i2 #Hf #g #j2 #H elim (pr_pat_inv_next … Hf … H) -f
 112 #x2 #Hg * -i2 #H destruct //
 113 qed-.
 114
 115 (*** at_inv_pxp *)
 116 lemma pr_pat_inv_unit_bi (f) (i1) (i2):
 117       @❨i1,f❩ ≘ i2 → 𝟏 = i1 → 𝟏 = i2 → ∃g. ⫯g = f.
 118 #f elim (pr_map_split_tl … f) /2 width=2 by ex_intro/
 119 #H #i1 #i2 #Hf #H1 #H2 cases (pr_pat_inv_next_unit … Hf … H H2)
 120 qed-.
 121
 122 (*** at_inv_pxn *)
 123 lemma pr_pat_inv_unit_succ (f) (i1) (i2):
 124       @❨i1,f❩ ≘ i2 → ∀j2. 𝟏 = i1 → ↑j2 = i2 →
 125       ∃∃g. @❨i1,g❩ ≘ j2 & ↑g = f.
 126 #f elim (pr_map_split_tl … f)
 127 #H #i1 #i2 #Hf #j2 #H1 #H2
 128 [ elim (pr_pat_inv_unit_push_succ … Hf … H1 H H2)
 129 | /3 width=5 by pr_pat_inv_next_succ, ex2_intro/
 130 ]
 131 qed-.
 132
 133 (*** at_inv_nxp *)
 134 lemma pr_pat_inv_succ_unit (f) (i1) (i2):
 135       @❨i1,f❩ ≘ i2 → ∀j1. ↑j1 = i1 → 𝟏 = i2 → ⊥.
 136 #f elim (pr_map_split_tl f)
 137 #H #i1 #i2 #Hf #j1 #H1 #H2
 138 [ elim (pr_pat_inv_succ_push_unit … Hf … H1 H H2)
 139 | elim (pr_pat_inv_next_unit … Hf … H H2)
 140 ]
 141 qed-.
 142
 143 (*** at_inv_nxn *)
 144 lemma pr_pat_inv_succ_bi (f) (i1) (i2):
 145       @❨i1,f❩ ≘ i2 → ∀j1,j2. ↑j1 = i1 → ↑j2 = i2 →
 146       ∨∨ ∃∃g. @❨j1,g❩ ≘ j2 & ⫯g = f
 147        | ∃∃g. @❨i1,g❩ ≘ j2 & ↑g = f.
 148 #f elim (pr_map_split_tl f) *
 149 /4 width=7 by pr_pat_inv_next_succ, pr_pat_inv_succ_push_succ, ex2_intro, or_intror, or_introl/
 150 qed-.
 151
 152 (* Note: the following inversion lemmas must be checked *)
 153 (*** at_inv_xpx *)
 154 lemma pr_pat_inv_push (f) (i1) (i2):
 155       @❨i1,f❩ ≘ i2 → ∀g. ⫯g = f →
 156       ∨∨ ∧∧ 𝟏 = i1 & 𝟏 = i2
 157        | ∃∃j1,j2. @❨j1,g❩ ≘ j2 & ↑j1 = i1 & ↑j2 = i2.
 158 #f * [2: #i1 ] #i2 #Hf #g #H
 159 [ elim (pr_pat_inv_succ_push … Hf … H) -f /3 width=5 by or_intror, ex3_2_intro/
 160 | >(pr_pat_inv_unit_push … Hf … H) -f /3 width=1 by conj, or_introl/
 161 ]
 162 qed-.
 163
 164 (*** at_inv_xpp *)
 165 lemma pr_pat_inv_push_unit (f) (i1) (i2):
 166       @❨i1,f❩ ≘ i2 → ∀g. ⫯g = f → 𝟏 = i2 → 𝟏 = i1.
 167 #f #i1 #i2 #Hf #g #H elim (pr_pat_inv_push … Hf … H) -f * //
 168 #j1 #j2 #_ #_ * -i2 #H destruct
 169 qed-.
 170
 171 (*** at_inv_xpn *)
 172 lemma pr_pat_inv_push_succ (f) (i1) (i2):
 173       @❨i1,f❩ ≘ i2 → ∀g,j2. ⫯g = f → ↑j2 = i2 →
 174       ∃∃j1. @❨j1,g❩ ≘ j2 & ↑j1 = i1.
 175 #f #i1 #i2 #Hf #g #j2 #H elim (pr_pat_inv_push … Hf … H) -f *
 176 [ #_ * -i2 #H destruct
 177 | #x1 #x2 #Hg #H1 * -i2 #H destruct /2 width=3 by ex2_intro/
 178 ]
 179 qed-.
 180
 181 (*** at_inv_xxp *)
 182 lemma pr_pat_inv_unit_dx (f) (i1) (i2):
 183       @❨i1,f❩ ≘ i2 → 𝟏 = i2 →
 184       ∃∃g. 𝟏 = i1 & ⫯g = f.
 185 #f elim (pr_map_split_tl f)
 186 #H #i1 #i2 #Hf #H2
 187 [ /3 width=6 by pr_pat_inv_push_unit, ex2_intro/
 188 | elim (pr_pat_inv_next_unit … Hf … H H2)
 189 ]
 190 qed-.
 191
 192 (*** at_inv_xxn *)
 193 lemma pr_pat_inv_succ_dx (f) (i1) (i2):
 194       @❨i1,f❩ ≘ i2 → ∀j2.  ↑j2 = i2 →
 195       ∨∨ ∃∃g,j1. @❨j1,g❩ ≘ j2 & ↑j1 = i1 & ⫯g = f
 196        | ∃∃g. @❨i1,g❩ ≘ j2 & ↑g = f.
 197 #f elim (pr_map_split_tl f)
 198 #H #i1 #i2 #Hf #j2 #H2
 199 [ elim (pr_pat_inv_push_succ … Hf … H H2) -i2 /3 width=5 by or_introl, ex3_2_intro/
 200 | lapply (pr_pat_inv_next_succ … Hf … H H2) -i2 /3 width=3 by or_intror, ex2_intro/
 201 ]
 202 qed-.