1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| A.Asperti, C.Sacerdoti Coen, *)
8 (* ||A|| E.Tassi, S.Zacchiroli *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU Lesser General Public License Version 2.1 *)
13 (**************************************************************************)
15 set "baseuri" "cic:/matita/Z/times".
17 include "nat/lt_arith.ma".
20 definition Ztimes :Z \to Z \to Z \def
27 | (pos n) \Rightarrow (pos (pred ((S m) * (S n))))
28 | (neg n) \Rightarrow (neg (pred ((S m) * (S n))))]
32 | (pos n) \Rightarrow (neg (pred ((S m) * (S n))))
33 | (neg n) \Rightarrow (pos (pred ((S m) * (S n))))]].
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).
38 theorem Ztimes_z_OZ: \forall z:Z. z*OZ = OZ.
45 theorem Ztimes_neg_Zopp: \forall n:nat.\forall x:Z.
46 neg n * x = - (pos n * x).
52 theorem symmetric_Ztimes : symmetric Z Ztimes.
53 change with (\forall x,y:Z. x*y = y*x).
54 intros.elim x.rewrite > Ztimes_z_OZ.reflexivity.
55 elim y.simplify.reflexivity.
56 change with (pos (pred ((S n) * (S n1))) = pos (pred ((S n1) * (S n)))).
57 rewrite < sym_times.reflexivity.
58 change with (neg (pred ((S n) * (S n1))) = neg (pred ((S n1) * (S n)))).
59 rewrite < sym_times.reflexivity.
60 elim y.simplify.reflexivity.
61 change with (neg (pred ((S n) * (S n1))) = neg (pred ((S n1) * (S n)))).
62 rewrite < sym_times.reflexivity.
63 change with (pos (pred ((S n) * (S n1))) = pos (pred ((S n1) * (S n)))).
64 rewrite < sym_times.reflexivity.
67 variant sym_Ztimes : \forall x,y:Z. x*y = y*x
68 \def symmetric_Ztimes.
70 theorem associative_Ztimes: associative Z Ztimes.
71 change with (\forall x,y,z:Z. (x*y)*z = x*(y*z)).
79 (pos (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
80 pos (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
81 rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
82 apply lt_O_times_S_S.apply lt_O_times_S_S.
84 (neg (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
85 neg (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
86 rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
87 apply lt_O_times_S_S.apply lt_O_times_S_S.
91 (neg (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
92 neg (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
93 rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
94 apply lt_O_times_S_S.apply lt_O_times_S_S.
96 (pos (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
97 pos(pred ((S n) * (S (pred ((S n1) * (S n2))))))).
98 rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
99 apply lt_O_times_S_S.apply lt_O_times_S_S.
101 simplify.reflexivity.
103 simplify.reflexivity.
105 (neg (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
106 neg (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
107 rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
108 apply lt_O_times_S_S.apply lt_O_times_S_S.
110 (pos (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
111 pos (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
112 rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
113 apply lt_O_times_S_S.apply lt_O_times_S_S.
115 simplify.reflexivity.
117 (pos (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
118 pos (pred ((S n) * (S (pred ((S n1) * (S n2))))))).
119 rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
120 apply lt_O_times_S_S.apply lt_O_times_S_S.
122 (neg (pred ((S (pred ((S n) * (S n1)))) * (S n2))) =
123 neg(pred ((S n) * (S (pred ((S n1) * (S n2))))))).
124 rewrite < S_pred.rewrite < S_pred.rewrite < assoc_times.reflexivity.
125 apply lt_O_times_S_S.apply lt_O_times_S_S.
128 variant assoc_Ztimes : \forall x,y,z:Z.
129 (x * y) * z = x * (y * z) \def
132 lemma times_minus1: \forall n,p,q:nat. lt q p \to
133 (S n) * (S (pred ((S p) - (S q)))) =
134 pred ((S n) * (S p)) - pred ((S n) * (S q)).
137 rewrite > minus_pred_pred.
138 rewrite < distr_times_minus.
140 (* we now close all positivity conditions *)
141 apply lt_O_times_S_S.
142 apply lt_O_times_S_S.
144 apply le_SO_minus. exact H.
147 lemma Ztimes_Zplus_pos_neg_pos: \forall n,p,q:nat.
148 (pos n)*((neg p)+(pos q)) = (pos n)*(neg p)+ (pos n)*(pos q).
151 change in match (p + n * (S p)) with (pred ((S n) * (S p))).
152 change in match (q + n * (S q)) with (pred ((S n) * (S q))).
153 rewrite < nat_compare_pred_pred.
154 rewrite < nat_compare_times_l.
155 rewrite < nat_compare_S_S.
156 apply (nat_compare_elim p q).
159 change with (pos (pred ((S n) * (S (pred ((S q) - (S p)))))) =
160 pos (pred ((pred ((S n) * (S q))) - (pred ((S n) * (S p)))))).
161 rewrite < (times_minus1 n q p H).reflexivity.
162 intro.rewrite < H.simplify.reflexivity.
164 change with (neg (pred ((S n) * (S (pred ((S p) - (S q)))))) =
165 neg (pred ((pred ((S n) * (S p))) - (pred ((S n) * (S q)))))).
166 rewrite < (times_minus1 n p q H).reflexivity.
167 (* two more positivity conditions from nat_compare_pred_pred *)
168 apply lt_O_times_S_S.
169 apply lt_O_times_S_S.
172 lemma Ztimes_Zplus_pos_pos_neg: \forall n,p,q:nat.
173 (pos n)*((pos p)+(neg q)) = (pos n)*(pos p)+ (pos n)*(neg q).
176 rewrite > Ztimes_Zplus_pos_neg_pos.
180 lemma distributive2_Ztimes_pos_Zplus:
181 distributive2 nat Z (\lambda n,z. (pos n) * z) Zplus.
182 change with (\forall n,y,z.
183 (pos n) * (y + z) = (pos n) * y + (pos n) * z).
189 (pos (pred ((S n) * ((S n1) + (S n2)))) =
190 pos (pred ((S n) * (S n1) + (S n) * (S n2)))).
191 rewrite < distr_times_plus.reflexivity.
192 apply Ztimes_Zplus_pos_pos_neg.
195 apply Ztimes_Zplus_pos_neg_pos.
197 (neg (pred ((S n) * ((S n1) + (S n2)))) =
198 neg (pred ((S n) * (S n1) + (S n) * (S n2)))).
199 rewrite < distr_times_plus.reflexivity.
202 variant distr_Ztimes_Zplus_pos: \forall n,y,z.
203 (pos n) * (y + z) = ((pos n) * y + (pos n) * z) \def
204 distributive2_Ztimes_pos_Zplus.
206 lemma distributive2_Ztimes_neg_Zplus :
207 distributive2 nat Z (\lambda n,z. (neg n) * z) Zplus.
208 change with (\forall n,y,z.
209 (neg n) * (y + z) = (neg n) * y + (neg n) * z).
211 rewrite > Ztimes_neg_Zopp.
212 rewrite > distr_Ztimes_Zplus_pos.
213 rewrite > Zopp_Zplus.
214 rewrite < Ztimes_neg_Zopp. rewrite < Ztimes_neg_Zopp.
218 variant distr_Ztimes_Zplus_neg: \forall n,y,z.
219 (neg n) * (y + z) = (neg n) * y + (neg n) * z \def
220 distributive2_Ztimes_neg_Zplus.
222 theorem distributive_Ztimes_Zplus: distributive Z Ztimes Zplus.
223 change with (\forall x,y,z:Z. x * (y + z) = x*y + x*z).
226 simplify.reflexivity.
228 apply distr_Ztimes_Zplus_pos.
230 apply distr_Ztimes_Zplus_neg.
233 variant distr_Ztimes_Zplus: \forall x,y,z.
234 x * (y + z) = x*y + x*z \def
235 distributive_Ztimes_Zplus.