helm/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 set "baseuri" "cic:/matita/nat/plus.ma".
  16
  17 include "logic/equality.ma".
  18 include "nat/nat.ma".
  19
  20 let rec plus n m \def
  21  match n with
  22  [ O \Rightarrow m
  23  | (S p) \Rightarrow S (plus p m) ].
  24
  25 theorem plus_n_O: \forall n:nat. eq nat n (plus n O).
  26 intros.elim n.
  27 simplify.reflexivity.
  28 simplify.apply eq_f.assumption.
  29 qed.
  30
  31 theorem plus_n_Sm : \forall n,m:nat. eq nat (S (plus n  m)) (plus n (S m)).
  32 intros.elim n.
  33 simplify.reflexivity.
  34 simplify.apply eq_f.assumption.
  35 qed.
  36
  37 (* some problem here: confusion between relations/symmetric
  38 and functions/symmetric; functions symmetric is not in
  39 functions.moo why?
  40 theorem symmetric_plus: symmetric nat plus. *)
  41
  42 theorem sym_plus: \forall n,m:nat. eq nat (plus n m) (plus m n).
  43 intros.elim n.
  44 simplify.apply plus_n_O.
  45 simplify.rewrite > H.apply plus_n_Sm.
  46 qed.
  47
  48 theorem associative_plus : associative nat plus.
  49 simplify.intros.elim x.
  50 simplify.reflexivity.
  51 simplify.apply eq_f.assumption.
  52 qed.
  53
  54 theorem assoc_plus : \forall n,m,p:nat. eq nat (plus (plus n m) p) (plus n (plus m p))
  55 \def associative_plus.
  56
  57 theorem injective_plus_r: \forall n:nat.injective nat nat (\lambda m.plus n m).
  58 intro.simplify.intros 2.elim n.
  59 exact H.
  60 apply H.apply inj_S.apply H1.
  61 qed.
  62
  63 theorem inj_plus_r: \forall p,n,m:nat.eq nat (plus p n) (plus p m) \to (eq nat n m)
  64 \def injective_plus_r.
  65
  66 theorem injective_plus_l: \forall m:nat.injective nat nat (\lambda n.plus n m).
  67 intro.simplify.intros.
  68 (* qui vorrei applicare injective_plus_r *)
  69 apply inj_plus_r m.
  70 rewrite < sym_plus.
  71 rewrite < sym_plus y.
  72 assumption.
  73 qed.
  74
  75 theorem inj_plus_l: \forall p,n,m:nat.eq nat (plus n p) (plus m p) \to (eq nat n m)
  76 \def injective_plus_l.