matita/library/nat/sigma_and_pi.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 (*       \ /        Matita 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/sigma_and_pi".
  16
  17 include "nat/factorial.ma".
  18 include "nat/exp.ma".
  19
  20 let rec sigma n f m \def
  21   match n with
  22   [ O \Rightarrow (f m)
  23   | (S p) \Rightarrow (f (S p+m))+(sigma p f m)].
  24
  25 let rec pi n f m \def
  26   match n with
  27   [ O \Rightarrow f m
  28   | (S p) \Rightarrow (f (S p+m))*(pi p f m)].
  29
  30 theorem eq_sigma: \forall f,g:nat \to nat.
  31 \forall n,m:nat.
  32 (\forall i:nat. m \le i \to i \le m+n \to f i = g i) \to
  33 (sigma n f m) = (sigma n g m).
  34 intros 3.elim n.
  35 simplify.apply H.apply le_n.rewrite < plus_n_O.apply le_n.
  36 simplify.
  37 apply eq_f2.apply H1.
  38 change with (m \le (S n1)+m).apply le_plus_n.
  39 rewrite > (sym_plus m).apply le_n.
  40 apply H.intros.apply H1.assumption.
  41 rewrite < plus_n_Sm.
  42 apply le_S.assumption.
  43 qed.
  44
  45 theorem eq_pi: \forall f,g:nat \to nat.
  46 \forall n,m:nat.
  47 (\forall i:nat. m \le i \to i \le m+n \to f i = g i) \to
  48 (pi n f m) = (pi n g m).
  49 intros 3.elim n.
  50 simplify.apply H.apply le_n.rewrite < plus_n_O.apply le_n.
  51 simplify.
  52 apply eq_f2.apply H1.
  53 change with (m \le (S n1)+m).apply le_plus_n.
  54 rewrite > (sym_plus m).apply le_n.
  55 apply H.intros.apply H1.assumption.
  56 rewrite < plus_n_Sm.
  57 apply le_S.assumption.
  58 qed.
  59
  60 theorem eq_fact_pi: \forall n. (S n)! = pi n (\lambda m.m) (S O).
  61 intro.elim n.
  62 simplify.reflexivity.
  63 change with ((S(S n1))*(S n1)! = ((S n1)+(S O))*(pi n1 (\lambda m.m) (S O))).
  64 rewrite < plus_n_Sm.rewrite < plus_n_O.
  65 apply eq_f.assumption.
  66 qed.
  67
  68 theorem exp_pi_l: \forall f:nat\to nat.\forall n,m,a:nat.
  69 (exp a (S n))*pi n f m= pi n (\lambda p.a*(f p)) m.
  70 intros.elim n.simplify.rewrite < times_n_SO.reflexivity.
  71 simplify.
  72 rewrite < H.
  73 rewrite > assoc_times.
  74 rewrite > assoc_times in\vdash (? ?  ? %).
  75 apply eq_f.rewrite < assoc_times.
  76 rewrite < assoc_times.
  77 apply eq_f2.apply sym_times.reflexivity.
  78 qed.