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