]> matita.cs.unibo.it Git - helm.git/blob - helm/software/matita/library/Z/times.ma
Proof of the moebius inversion theorem
[helm.git] / helm / software / matita / library / Z / times.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/Z/times".
16
17 include "nat/lt_arith.ma".
18 include "Z/plus.ma".
19
20 definition Ztimes :Z \to Z \to Z \def
21 \lambda x,y.
22   match x with
23     [ OZ \Rightarrow OZ
24     | (pos m) \Rightarrow
25         match y with
26          [ OZ \Rightarrow OZ
27          | (pos n) \Rightarrow (pos (pred ((S m) * (S n))))
28          | (neg n) \Rightarrow (neg (pred ((S m) * (S n))))]
29     | (neg m) \Rightarrow
30         match y with
31          [ OZ \Rightarrow OZ
32          | (pos n) \Rightarrow (neg (pred ((S m) * (S n))))
33          | (neg n) \Rightarrow (pos (pred ((S m) * (S n))))]].
34          
35 (*CSC: the URI must disappear: there is a bug now *)
36 interpretation "integer times" 'times x y = (cic:/matita/Z/times/Ztimes.con x y).
37
38 theorem Ztimes_z_OZ:  \forall z:Z. z*OZ = OZ.
39 intro.elim z.
40 simplify.reflexivity.
41 simplify.reflexivity.
42 simplify.reflexivity.
43 qed.
44
45 theorem Ztimes_neg_Zopp: \forall n:nat.\forall x:Z.
46 neg n * x = - (pos n * x).
47 intros.elim x.
48 simplify.reflexivity.
49 simplify.reflexivity.
50 simplify.reflexivity.
51 qed.
52
53 theorem symmetric_Ztimes : symmetric Z Ztimes.
54 change with (\forall x,y:Z. x*y = y*x).
55 intros.elim x.rewrite > Ztimes_z_OZ.reflexivity.
56 elim y.simplify.reflexivity. 
57 change with (pos (pred ((S n) * (S n1))) = pos (pred ((S n1) * (S n)))).
58 rewrite < sym_times.reflexivity.
59 change with (neg (pred ((S n) * (S n1))) = neg (pred ((S n1) * (S n)))).
60 rewrite < sym_times.reflexivity.
61 elim y.simplify.reflexivity.
62 change with (neg (pred ((S n) * (S n1))) = neg (pred ((S n1) * (S n)))).
63 rewrite < sym_times.reflexivity.
64 change with (pos (pred ((S n) * (S n1))) = pos (pred ((S n1) * (S n)))).
65 rewrite < sym_times.reflexivity.
66 qed.
67
68 variant sym_Ztimes : \forall x,y:Z. x*y = y*x
69 \def symmetric_Ztimes.
70
71 theorem associative_Ztimes: associative Z Ztimes.
72 unfold associative.
73 intros.elim x.
74   simplify.reflexivity. 
75   elim y.
76     simplify.reflexivity.
77     elim z.
78       simplify.reflexivity.
79       change with 
80        (pos (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
81        pos (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
82         rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
83          apply lt_O_times_S_S.apply lt_O_times_S_S.
84       change with 
85        (neg (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
86        neg (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
87         rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
88          apply lt_O_times_S_S.apply lt_O_times_S_S.
89     elim z.
90       simplify.reflexivity.
91       change with 
92        (neg (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
93        neg (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
94         rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
95          apply lt_O_times_S_S.apply lt_O_times_S_S.
96       change with 
97        (pos (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
98        pos(pred ((S n) * (S (pred ((S n1) * (S n2))))))).
99         rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
100         apply lt_O_times_S_S.apply lt_O_times_S_S.
101   elim y.
102     simplify.reflexivity.
103     elim z.
104       simplify.reflexivity.
105       change with 
106        (neg (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
107        neg (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
108         rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
109          apply lt_O_times_S_S.apply lt_O_times_S_S.
110       change with 
111        (pos (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
112        pos (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
113         rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
114          apply lt_O_times_S_S.apply lt_O_times_S_S.
115     elim z.
116       simplify.reflexivity.
117       change with 
118        (pos (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
119        pos (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
120         rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
121          apply lt_O_times_S_S.apply lt_O_times_S_S.
122       change with 
123        (neg (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
124        neg(pred ((S n) * (S (pred ((S n1) * (S n2))))))).
125         rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
126          apply lt_O_times_S_S.apply lt_O_times_S_S.
127 qed.
128
129 variant assoc_Ztimes : \forall x,y,z:Z. 
130 (x * y) * z = x * (y * z) \def 
131 associative_Ztimes.
132
133 lemma times_minus1: \forall n,p,q:nat. lt q p \to
134 (S n) * (S (pred ((S p) - (S q)))) =
135 pred ((S n) * (S p)) - pred ((S n) * (S q)).
136 intros.
137 rewrite < S_pred.  
138 rewrite > minus_pred_pred.
139 rewrite < distr_times_minus. 
140 reflexivity.
141 (* we now close all positivity conditions *)
142 apply lt_O_times_S_S.                    
143 apply lt_O_times_S_S.
144 simplify.unfold lt.
145 apply le_SO_minus.  exact H.
146 qed.
147
148 lemma Ztimes_Zplus_pos_neg_pos: \forall n,p,q:nat.
149 (pos n)*((neg p)+(pos q)) = (pos n)*(neg p)+ (pos n)*(pos q). 
150 intros.
151 simplify. 
152 change in match (p + n * (S p)) with (pred ((S n) * (S p))).
153 change in match (q + n * (S q)) with (pred ((S n) * (S q))).
154 rewrite < nat_compare_pred_pred.
155 rewrite < nat_compare_times_l.
156 rewrite < nat_compare_S_S.
157 apply (nat_compare_elim p q).
158 intro.
159 (* uff *)
160 change with (pos (pred ((S n) * (S (pred ((S q) - (S p)))))) =
161             pos (pred ((pred ((S n) * (S q))) - (pred ((S n) * (S p)))))).
162 rewrite < (times_minus1 n q p H).reflexivity.
163 intro.rewrite < H.simplify.reflexivity.
164 intro.
165 change with (neg (pred ((S n) * (S (pred ((S p) - (S q)))))) =
166             neg (pred ((pred ((S n) * (S p))) - (pred ((S n) * (S q)))))). 
167 rewrite < (times_minus1 n p q H).reflexivity.                                 
168 (* two more positivity conditions from nat_compare_pred_pred *)   
169 apply lt_O_times_S_S.  
170 apply lt_O_times_S_S. 
171 qed. 
172
173 lemma Ztimes_Zplus_pos_pos_neg: \forall n,p,q:nat.
174 (pos n)*((pos p)+(neg q)) = (pos n)*(pos p)+ (pos n)*(neg q).
175 intros.
176 rewrite < sym_Zplus.
177 rewrite > Ztimes_Zplus_pos_neg_pos.
178 apply sym_Zplus.
179 qed.
180
181 lemma distributive2_Ztimes_pos_Zplus: 
182 distributive2 nat Z (\lambda n,z. (pos n) * z) Zplus.
183 change with (\forall n,y,z.
184 (pos n) * (y + z) = (pos n) * y + (pos n) * z).  
185 intros.elim y.
186   reflexivity.
187   elim z.
188     reflexivity.
189     change with
190      (pos (pred ((S n) * ((S n1) + (S n2)))) =
191      pos (pred ((S n) * (S n1) + (S n) * (S n2)))).
192       rewrite < distr_times_plus.reflexivity.
193     apply Ztimes_Zplus_pos_pos_neg.
194   elim z.
195     reflexivity.
196     apply Ztimes_Zplus_pos_neg_pos.
197     change with
198      (neg (pred ((S n) * ((S n1) + (S n2)))) =
199      neg (pred ((S n) * (S n1) + (S n) * (S n2)))).
200     rewrite < distr_times_plus.reflexivity.
201 qed.
202
203 variant distr_Ztimes_Zplus_pos: \forall n,y,z.
204 (pos n) * (y + z) = ((pos n) * y + (pos n) * z) \def
205 distributive2_Ztimes_pos_Zplus.
206
207 lemma distributive2_Ztimes_neg_Zplus : 
208 distributive2 nat Z (\lambda n,z. (neg n) * z) Zplus.
209 change with (\forall n,y,z.
210 (neg n) * (y + z) = (neg n) * y + (neg n) * z).  
211 intros.
212 rewrite > Ztimes_neg_Zopp. 
213 rewrite > distr_Ztimes_Zplus_pos.
214 rewrite > Zopp_Zplus.
215 rewrite < Ztimes_neg_Zopp. rewrite < Ztimes_neg_Zopp.
216 reflexivity.
217 qed.
218
219 variant distr_Ztimes_Zplus_neg: \forall n,y,z.
220 (neg n) * (y + z) = (neg n) * y + (neg n) * z \def
221 distributive2_Ztimes_neg_Zplus.
222
223 theorem distributive_Ztimes_Zplus: distributive Z Ztimes Zplus.
224 change with (\forall x,y,z:Z. x * (y + z) = x*y + x*z).
225 intros.elim x.
226 (* case x = OZ *)
227 simplify.reflexivity.
228 (* case x = pos n *)
229 apply distr_Ztimes_Zplus_pos.
230 (* case x = neg n *)
231 apply distr_Ztimes_Zplus_neg.
232 qed.
233
234 variant distr_Ztimes_Zplus: \forall x,y,z.
235 x * (y + z) = x*y + x*z \def
236 distributive_Ztimes_Zplus.