]> matita.cs.unibo.it Git - helm.git/blob - matita/matita/contribs/lambdadelta/ground/relocation/pr_nat_nat.ma
update in delayed_updating
[helm.git] / matita / matita / contribs / lambdadelta / ground / relocation / pr_nat_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.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/arith/nat_lt_pred.ma".
16 include "ground/relocation/pr_nat.ma".
17
18 (* NON-NEGATIVE APPLICATION FOR PARTIAL RELOCATION MAPS *****************************)
19
20 (* Main destructions ********************************************************)
21
22 theorem pr_nat_monotonic (k2) (l2) (f):
23         @↑❨l2,f❩ ≘ k2 → ∀k1,l1. @↑❨l1,f❩ ≘ k1 → l1 < l2 → k1 < k2.
24 #k2 @(nat_ind_succ … k2) -k2
25 [ #l2 #f #H2f elim (pr_nat_inv_zero_dx … H2f) -H2f //
26   #g #H21 #_ #k1 #l1 #_ #Hi destruct
27   elim (nlt_inv_zero_dx … Hi)
28 | #k2 #IH #l2 #f #H2f #k1 @(nat_ind_succ … k1) -k1 //
29   #k1 #_ #l1 #H1f #Hl elim (nlt_inv_gen … Hl)
30   #_ #Hl2 elim (pr_nat_inv_succ_bi … H2f (↓l2)) -H2f [1,3: * |*: // ]
31   #g #H2g #H
32   [ elim (pr_nat_inv_push_succ … H1f … H) -f
33     /4 width=8 by nlt_inv_succ_bi, nlt_succ_bi/
34   | /4 width=8 by pr_nat_inv_next_succ, nlt_succ_bi/
35   ]
36 ]
37 qed-.
38
39 theorem pr_nat_inv_monotonic (k1) (l1) (f):
40         @↑❨l1,f❩ ≘ k1 → ∀k2,l2. @↑❨l2,f❩ ≘ k2 → k1 < k2 → l1 < l2.
41 #k1 @(nat_ind_succ … k1) -k1
42 [ #l1 #f #H1f elim (pr_nat_inv_zero_dx … H1f) -H1f //
43   #g * -l1 #H #k2 #l2 #H2f #Hk
44   lapply (nlt_des_gen … Hk) -Hk #H22
45   elim (pr_nat_inv_push_succ … H2f … (↓k2) H) -f //
46 | #k1 #IH #l1 @(nat_ind_succ … l1) -l1
47   [ #f #H1f elim (pr_nat_inv_zero_succ … H1f) -H1f [ |*: // ]
48     #g #H1g #H #k2 #l2 #H2f #Hj elim (nlt_inv_succ_sn … Hj) -Hj
49     /3 width=7 by pr_nat_inv_next_succ/
50   | #l1 #_ #f #H1f #k2 #l2 #H2f #Hj elim (nlt_inv_succ_sn … Hj) -Hj
51     #Hj #H22 elim (pr_nat_inv_succ_bi … H1f) -H1f [1,4: * |*: // ]
52     #g #Hg #H
53     [ elim (pr_nat_inv_push_succ … H2f … (↓k2) H) -f
54       /3 width=7 by nlt_succ_bi/
55     | /3 width=7 by pr_nat_inv_next_succ/
56     ]
57   ]
58 ]
59 qed-.
60
61 theorem pr_nat_mono (f) (l) (l1) (l2):
62         @↑❨l,f❩ ≘ l1 → @↑❨l,f❩ ≘ l2 → l2 = l1.
63 #f #l #l1 #l2 #H1 #H2 elim (nat_split_lt_eq_gt l2 l1) //
64 #Hi elim (nlt_ge_false l l)
65 /2 width=6 by pr_nat_inv_monotonic/
66 qed-.
67
68 theorem pr_nat_inj (f) (l1) (l2) (l):
69         @↑❨l1,f❩ ≘ l → @↑❨l2,f❩ ≘ l → l1 = l2.
70 #f #l1 #l2 #l #H1 #H2 elim (nat_split_lt_eq_gt l2 l1) //
71 #Hi elim (nlt_ge_false l l)
72 /2 width=6 by pr_nat_monotonic/
73 qed-.