matita/matita/contribs/lambdadelta/ground/relocation/rtmap_nat.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.tcs.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/ratsucc_3.ma".
  16 include "ground/arith/nat_lt_pred.ma".
  17 include "ground/relocation/rtmap_at.ma".
  18
  19 (* NON-NEGATIVE APPLICATION FOR RELOCATION MAPS *****************************)
  20
  21 definition rm_nat: relation3 rtmap nat nat ≝
  22            λf,l1,l2. @❪↑l1,f❫ ≘ ↑l2.
  23
  24 interpretation
  25   "relational non-negative application (relocation maps)"
  26   'RAtSucc l1 f l2 = (rm_nat f l1 l2).
  27
  28 (* Basic properties *********************************************************)
  29
  30 lemma rm_nat_refl (f) (g) (k1) (k2):
  31       (⫯f) = g → 𝟎 = k1 → 𝟎 = k2 → @↑❪k1,g❫ ≘ k2.
  32 #f #g #k1 #k2 #H1 #H2 #H3 destruct
  33 /2 width=2 by at_refl/
  34 qed.
  35
  36 lemma rm_nat_push (f) (l1) (l2) (g) (k1) (k2):
  37       @↑❪l1,f❫ ≘ l2 → ⫯f = g → ↑l1 = k1 → ↑l2 = k2 → @↑❪k1,g❫ ≘ k2.
  38 #f #l1 #l2 #g #k1 #k2 #Hf #H1 #H2 #H3 destruct
  39 /2 width=7 by at_push/
  40 qed.
  41
  42 lemma rm_nat_next (f) (l1) (l2) (g) (k2):
  43       @↑❪l1,f❫ ≘ l2 → ↑f = g → ↑l2 = k2 → @↑❪l1,g❫ ≘ k2.
  44 #f #l1 #l2 #g #k2 #Hf #H1 #H2 destruct
  45 /2 width=5 by at_next/
  46 qed.
  47
  48 lemma rm_nat_pred_bi (f) (i1) (i2):
  49       @❪i1,f❫ ≘ i2 → @↑❪↓i1,f❫ ≘ ↓i2.
  50 #f #i1 #i2
  51 >(npsucc_pred i1) in ⊢ (%→?); >(npsucc_pred i2) in ⊢ (%→?);
  52 //
  53 qed.
  54
  55 (* Basic inversion lemmas ***************************************************)
  56
  57 lemma rm_nat_inv_ppx (f) (l1) (l2):
  58       @↑❪l1,f❫ ≘ l2 → ∀g. 𝟎 = l1 → ⫯g = f → 𝟎 = l2.
  59 #f #l1 #l2 #H #g #H1 #H2 destruct
  60 lapply (at_inv_ppx … H ???) -H
  61 /2 width=2 by eq_inv_npsucc_bi/
  62 qed-.
  63
  64 lemma rm_nat_inv_npx (f) (l1) (l2):
  65       @↑❪l1,f❫ ≘ l2 → ∀g,k1. ↑k1 = l1 → ⫯g = f →
  66       ∃∃k2. @↑❪k1,g❫ ≘ k2 & ↑k2 = l2.
  67 #f #l1 #l2 #H #g #k1 #H1 #H2 destruct
  68 elim (at_inv_npx … H) -H [|*: // ] #k2 #Hg
  69 >(npsucc_pred (↑l2)) #H
  70 @(ex2_intro … (↓k2)) //
  71 <pnpred_psucc //
  72 qed-.
  73
  74 lemma rm_nat_inv_xnx (f) (l1) (l2):
  75       @↑❪l1,f❫ ≘ l2 → ∀g. ↑g = f →
  76       ∃∃k2. @↑❪l1,g❫ ≘ k2 & ↑k2 = l2.
  77 #f #l1 #l2 #H #g #H1 destruct
  78 elim (at_inv_xnx … H) -H [|*: // ] #k2
  79 >(npsucc_pred (k2)) in ⊢ (%→?→?); #Hg #H
  80 @(ex2_intro … (↓k2)) //
  81 <pnpred_psucc //
  82 qed-.
  83
  84 (* Advanced inversion lemmas ************************************************)
  85
  86 lemma rm_nat_inv_ppn (f) (l1) (l2):
  87       @↑❪l1,f❫ ≘ l2 → ∀g,k2. 𝟎 = l1 → ⫯g = f → ↑k2 = l2 → ⊥.
  88 #f #l1 #l2 #Hf #g #k2 #H1 #H <(rm_nat_inv_ppx … Hf … H1 H) -f -g -l1 -l2
  89 /2 width=3 by eq_inv_nsucc_zero/
  90 qed-.
  91
  92 lemma rm_nat_inv_npp (f) (l1) (l2):
  93       @↑❪l1,f❫ ≘ l2 → ∀g,k1. ↑k1 = l1 → ⫯g = f → 𝟎 = l2 → ⊥.
  94 #f #l1 #l2 #Hf #g #k1 #H1 #H elim (rm_nat_inv_npx … Hf … H1 H) -f -l1
  95 #x2 #Hg * -l2 /2 width=3 by eq_inv_zero_nsucc/
  96 qed-.
  97
  98 lemma rm_nat_inv_npn (f) (l1) (l2):
  99       @↑❪l1,f❫ ≘ l2 → ∀g,k1,k2. ↑k1 = l1 → ⫯g = f → ↑k2 = l2 → @↑❪k1,g❫ ≘ k2.
 100 #f #l1 #l2 #Hf #g #k1 #k2 #H1 #H elim (rm_nat_inv_npx … Hf … H1 H) -f -l1
 101 #x2 #Hg * -l2 #H >(eq_inv_nsucc_bi … H) -k2 //
 102 qed-.
 103
 104 lemma rm_nat_inv_xnp (f) (l1) (l2):
 105       @↑❪l1,f❫ ≘ l2 → ∀g. ↑g = f → 𝟎 = l2 → ⊥.
 106 #f #l1 #l2 #Hf #g #H elim (rm_nat_inv_xnx … Hf … H) -f
 107 #x2 #Hg * -l2 /2 width=3 by eq_inv_zero_nsucc/
 108 qed-.
 109
 110 lemma rm_nat_inv_xnn (f) (l1) (l2):
 111       @↑❪l1,f❫ ≘ l2 → ∀g,k2. ↑g = f → ↑k2 = l2 → @↑❪l1,g❫ ≘ k2.
 112 #f #l1 #l2 #Hf #g #k2 #H elim (rm_nat_inv_xnx … Hf … H) -f
 113 #x2 #Hg * -l2 #H >(eq_inv_nsucc_bi … H) -k2 //
 114 qed-.
 115
 116 lemma rm_nat_inv_pxp (f) (l1) (l2):
 117       @↑❪l1,f❫ ≘ l2 → 𝟎 = l1 → 𝟎 = l2 → ∃g. ⫯g = f.
 118 #f elim (pn_split … f) * /2 width=2 by ex_intro/
 119 #g #H #l1 #l2 #Hf #H1 #H2 cases (rm_nat_inv_xnp … Hf … H H2)
 120 qed-.
 121
 122 lemma rm_nat_inv_pxn (f) (l1) (l2):
 123       @↑❪l1,f❫ ≘ l2 → ∀k2. 𝟎 = l1 → ↑k2 = l2 →
 124       ∃∃g. @↑❪l1,g❫ ≘ k2 & ↑g = f.
 125 #f elim (pn_split … f) *
 126 #g #H #l1 #l2 #Hf #k2 #H1 #H2
 127 [ elim (rm_nat_inv_ppn … Hf … H1 H H2)
 128 | /3 width=5 by rm_nat_inv_xnn, ex2_intro/
 129 ]
 130 qed-.
 131
 132 lemma rm_nat_inv_nxp (f) (l1) (l2):
 133       @↑❪l1,f❫ ≘ l2 → ∀k1. ↑k1 = l1 → 𝟎 = l2 → ⊥.
 134 #f elim (pn_split f) *
 135 #g #H #l1 #l2 #Hf #k1 #H1 #H2
 136 [ elim (rm_nat_inv_npp … Hf … H1 H H2)
 137 | elim (rm_nat_inv_xnp … Hf … H H2)
 138 ]
 139 qed-.
 140
 141 lemma rm_nat_inv_nxn (f) (l1) (l2):
 142       @↑❪l1,f❫ ≘ l2 → ∀k1,k2. ↑k1 = l1 → ↑k2 = l2 →
 143       ∨∨ ∃∃g. @↑❪k1,g❫ ≘ k2 & ⫯g = f
 144        | ∃∃g. @↑❪l1,g❫ ≘ k2 & ↑g = f.
 145 #f elim (pn_split f) *
 146 /4 width=7 by rm_nat_inv_xnn, rm_nat_inv_npn, ex2_intro, or_intror, or_introl/
 147 qed-.
 148
 149 (* Note: the following inversion lemmas must be checked *)
 150 lemma rm_nat_inv_xpx (f) (l1) (l2):
 151       @↑❪l1,f❫ ≘ l2 → ∀g. ⫯g = f →
 152       ∨∨ ∧∧ 𝟎 = l1 & 𝟎 = l2
 153        | ∃∃k1,k2. @↑❪k1,g❫ ≘ k2 & ↑k1 = l1 & ↑k2 = l2.
 154 #f * [2: #l1 ] #l2 #Hf #g #H
 155 [ elim (rm_nat_inv_npx … Hf … H) -f /3 width=5 by or_intror, ex3_2_intro/
 156 | >(rm_nat_inv_ppx … Hf … H) -f /3 width=1 by conj, or_introl/
 157 ]
 158 qed-.
 159
 160 lemma rm_nat_inv_xpp (f) (l1) (l2):
 161       @↑❪l1,f❫ ≘ l2 → ∀g. ⫯g = f → 𝟎 = l2 → 𝟎 = l1.
 162 #f #l1 #l2 #Hf #g #H elim (rm_nat_inv_xpx … Hf … H) -f * //
 163 #k1 #k2 #_ #_ * -l2 #H elim (eq_inv_zero_nsucc … H)
 164 qed-.
 165
 166 lemma rm_nat_inv_xpn (f) (l1) (l2):
 167       @↑❪l1,f❫ ≘ l2 → ∀g,k2. ⫯g = f → ↑k2 = l2 →
 168       ∃∃k1. @↑❪k1,g❫ ≘ k2 & ↑k1 = l1.
 169 #f #l1 #l2 #Hf #g #k2 #H elim (rm_nat_inv_xpx … Hf … H) -f *
 170 [ #_ * -l2 #H elim (eq_inv_nsucc_zero … H)
 171 | #x1 #x2 #Hg #H1 * -l2 #H
 172   lapply (eq_inv_nsucc_bi … H) -H #H destruct
 173   /2 width=3 by ex2_intro/
 174 ]
 175 qed-.
 176
 177 lemma rm_nat_inv_xxp (f) (l1) (l2):
 178       @↑❪l1,f❫ ≘ l2 → 𝟎 = l2 → ∃∃g. 𝟎 = l1 & ⫯g = f.
 179 #f elim (pn_split f) *
 180 #g #H #l1 #l2 #Hf #H2
 181 [ /3 width=6 by rm_nat_inv_xpp, ex2_intro/
 182 | elim (rm_nat_inv_xnp … Hf … H H2)
 183 ]
 184 qed-.
 185
 186 lemma rm_nat_inv_xxn (f) (l1) (l2): @↑❪l1,f❫ ≘ l2 → ∀k2.  ↑k2 = l2 →
 187       ∨∨ ∃∃g,k1. @↑❪k1,g❫ ≘ k2 & ↑k1 = l1 & ⫯g = f
 188        | ∃∃g. @↑❪l1,g❫ ≘ k2 & ↑g = f.
 189 #f elim (pn_split f) *
 190 #g #H #l1 #l2 #Hf #k2 #H2
 191 [ elim (rm_nat_inv_xpn … Hf … H H2) -l2 /3 width=5 by or_introl, ex3_2_intro/
 192 | lapply (rm_nat_inv_xnn … Hf … H H2) -l2 /3 width=3 by or_intror, ex2_intro/
 193 ]
 194 qed-.
 195
 196 (* Main destructions ********************************************************)
 197
 198 theorem rm_nat_monotonic (k2) (l2) (f):
 199         @↑❪l2,f❫ ≘ k2 → ∀k1,l1. @↑❪l1,f❫ ≘ k1 → l1 < l2 → k1 < k2.
 200 #k2 @(nat_ind_succ … k2) -k2
 201 [ #l2 #f #H2f elim (rm_nat_inv_xxp … H2f) -H2f //
 202   #g #H21 #_ #k1 #l1 #_ #Hi destruct
 203   elim (nlt_inv_zero_dx … Hi)
 204 | #k2 #IH #l2 #f #H2f #k1 @(nat_ind_succ … k1) -k1 //
 205   #k1 #_ #l1 #H1f #Hl elim (nlt_inv_gen … Hl)
 206   #_ #Hl2 elim (rm_nat_inv_nxn … H2f (↓l2)) -H2f [1,3: * |*: // ]
 207   #g #H2g #H
 208   [ elim (rm_nat_inv_xpn … H1f … H) -f
 209     /4 width=8 by nlt_inv_succ_bi, nlt_succ_bi/
 210   | /4 width=8 by rm_nat_inv_xnn, nlt_succ_bi/
 211   ]
 212 ]
 213 qed-.
 214
 215 theorem rm_nat_inv_monotonic (k1) (l1) (f):
 216         @↑❪l1,f❫ ≘ k1 → ∀k2,l2. @↑❪l2,f❫ ≘ k2 → k1 < k2 → l1 < l2.
 217 #k1 @(nat_ind_succ … k1) -k1
 218 [ #l1 #f #H1f elim (rm_nat_inv_xxp … H1f) -H1f //
 219   #g * -l1 #H #k2 #l2 #H2f #Hk
 220   lapply (nlt_des_gen … Hk) -Hk #H22
 221   elim (rm_nat_inv_xpn … H2f … (↓k2) H) -f //
 222 | #k1 #IH #l1 @(nat_ind_succ … l1) -l1
 223   [ #f #H1f elim (rm_nat_inv_pxn … H1f) -H1f [ |*: // ]
 224     #g #H1g #H #k2 #l2 #H2f #Hj elim (nlt_inv_succ_sn … Hj) -Hj
 225     /3 width=7 by rm_nat_inv_xnn/
 226   | #l1 #_ #f #H1f #k2 #l2 #H2f #Hj elim (nlt_inv_succ_sn … Hj) -Hj
 227     #Hj #H22 elim (rm_nat_inv_nxn … H1f) -H1f [1,4: * |*: // ]
 228     #g #Hg #H
 229     [ elim (rm_nat_inv_xpn … H2f … (↓k2) H) -f
 230       /3 width=7 by nlt_succ_bi/
 231     | /3 width=7 by rm_nat_inv_xnn/
 232     ]
 233   ]
 234 ]
 235 qed-.
 236
 237 theorem rm_nat_mono (f) (l) (l1) (l2):
 238         @↑❪l,f❫ ≘ l1 → @↑❪l,f❫ ≘ l2 → l2 = l1.
 239 #f #l #l1 #l2 #H1 #H2 elim (nat_split_lt_eq_gt l2 l1) //
 240 #Hi elim (nlt_ge_false l l) /3 width=6 by rm_nat_inv_monotonic, eq_sym/
 241 qed-.
 242
 243 theorem rm_nat_inj (f) (l1) (l2) (l):
 244         @↑❪l1,f❫ ≘ l → @↑❪l2,f❫ ≘ l → l1 = l2.
 245 #f #l1 #l2 #l #H1 #H2 elim (nat_split_lt_eq_gt l2 l1) //
 246 #Hi elim (nlt_ge_false l l) /2 width=6 by rm_nat_monotonic/
 247 qed-.