matita/library/nat/plus.ma

   1 (**************************************************************************)
   2 (*       ___                                                                *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||       A.Asperti, C.Sacerdoti Coen,                          *)
   8 (*      ||A||       E.Tassi, S.Zacchiroli                                 *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU Lesser General Public License Version 2.1         *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15
  16
  17 include "nat/nat.ma".
  18
  19 let rec plus n m \def
  20  match n with
  21  [ O \Rightarrow m
  22  | (S p) \Rightarrow S (plus p m) ].
  23
  24 (*CSC: the URI must disappear: there is a bug now *)
  25 interpretation "natural plus" 'plus x y = (cic:/matita/nat/plus/plus.con x y).
  26
  27 theorem plus_n_O: \forall n:nat. n = n+O.
  28 intros.elim n.
  29 simplify.reflexivity.
  30 simplify.apply eq_f.assumption.
  31 qed.
  32
  33 theorem plus_n_Sm : \forall n,m:nat. S (n+m) = n+(S m).
  34 intros.elim n.
  35 simplify.reflexivity.
  36 simplify.apply eq_f.assumption.
  37 qed.
  38
  39 theorem plus_n_SO : \forall n:nat. S n = n+(S O).
  40 intro.rewrite > plus_n_O.
  41 apply plus_n_Sm.
  42 qed.
  43
  44 theorem sym_plus: \forall n,m:nat. n+m = m+n.
  45 intros.elim n.
  46 simplify.apply plus_n_O.
  47 simplify.rewrite > H.apply plus_n_Sm.
  48 qed.
  49
  50 theorem associative_plus : associative nat plus.
  51 unfold associative.intros.elim x.
  52 simplify.reflexivity.
  53 simplify.apply eq_f.assumption.
  54 qed.
  55
  56 theorem assoc_plus : \forall n,m,p:nat. (n+m)+p = n+(m+p)
  57 \def associative_plus.
  58
  59 theorem injective_plus_r: \forall n:nat.injective nat nat (\lambda m.n+m).
  60 intro.simplify.intros 2.elim n.
  61 exact H.
  62 apply H.apply inj_S.apply H1.
  63 qed.
  64
  65 theorem inj_plus_r: \forall p,n,m:nat. p+n = p+m \to n=m
  66 \def injective_plus_r.
  67
  68 theorem injective_plus_l: \forall m:nat.injective nat nat (\lambda n.n+m).
  69 intro.simplify.intros.
  70 apply (injective_plus_r m).
  71 rewrite < sym_plus.
  72 rewrite < (sym_plus y).
  73 assumption.
  74 qed.
  75
  76 theorem inj_plus_l: \forall p,n,m:nat. n+p = m+p \to n=m
  77 \def injective_plus_l.