]> matita.cs.unibo.it Git - helm.git/blob - helm/software/matita/library/R/r.ma
...
[helm.git] / helm / software / matita / library / R / r.ma
1 (**************************************************************************)
2 (*       ___                                                              *)
3 (*      ||M||                                                             *)
4 (*      ||A||       A project by Andrea Asperti                           *)
5 (*      ||T||                                                             *)
6 (*      ||I||       Developers:                                           *)
7 (*      ||T||         The HELM team.                                      *)
8 (*      ||A||         http://helm.cs.unibo.it                             *)
9 (*      \   /                                                             *)
10 (*       \ /        This file is distributed under the terms of the       *)
11 (*        v         GNU General Public License Version 2                  *)
12 (*                                                                        *)
13 (**************************************************************************)
14
15 include "logic/equality.ma".
16 include "logic/coimplication.ma".
17 include "logic/cprop_connectives.ma".
18 include "datatypes/constructors.ma".
19 include "nat/orders.ma".
20 include "Z/z.ma". 
21
22 axiom choose : ∀A:Type.∀P:A → Prop.(∃x.P x) → exP ? P.
23 alias symbol "plus" = "Disjoint union".
24 axiom decide : ∀A,B.A ∨ B → A + B.
25
26 axiom R : Type.
27
28 axiom R0 : R.
29 axiom R1 : R.
30
31 axiom Rplus : R → R → R.
32 axiom Rtimes : R → R → R.
33 axiom Ropp : R → R.
34 axiom Rinv : R → R.
35 axiom Rlt : R → R → Prop.
36 definition Rle : R → R → Prop ≝ λx,y:R.Rlt x y ∨ x = y.
37
38 interpretation "real numbers" 'R = R.
39
40 interpretation "real numbers plus" 'plus x y = (Rplus x y).
41 interpretation "real numbers times" 'times x y = (Rtimes x y).
42 interpretation "real numbers opposite" 'uminus x = (Ropp x).
43 interpretation "real numbers reciprocal" 'invert x = (Rinv x).
44 interpretation "real numbers less than" 'lt x y = (Rlt x y).
45 interpretation "real numbers less eq" 'leq x y = (Rle x y).
46
47 axiom not_eq_R0_R1 : ¬ R0 = R1.
48
49 (* commutative ring with unity *)
50
51 axiom sym_Rplus : ∀x,y:R. x + y = y + x.
52 axiom assoc_Rplus : ∀x,y,z:R.(x+y)+z = x+(y+z).
53 axiom Rplus_x_R0 : ∀x.x + R0 = x.
54 axiom Rplus_Ropp : ∀x.x + (-x) = R0.
55
56 axiom sym_Rtimes : ∀x,y:R. x * y = y * x.
57 axiom assoc_Rtimes : ∀x,y,z:R.(x*y)*z = x*(y*z).
58 axiom Rtimes_x_R1 : ∀x.x * R1 = x.
59 axiom distr_Rtimes_Rplus_l : ∀x,y,z:R.x*(y+z) = x*y + x*z.
60
61 (*pump 200.*)
62
63 lemma distr_Rtimes_Rplus_r : ∀x,y,z:R.(x+y)*z = x*z + y*z.
64 intros; autobatch; 
65 qed.
66
67 (* commutative field *)
68
69 axiom Rinv_Rtimes_l : ∀x. ¬ x = R0 → x * (Rinv x) = R1.
70
71 (* ordered commutative field *)
72
73 axiom irrefl_Rlt : ∀x:R.¬ x < x.
74 axiom asym_Rlt : ∀x,y:R. x < y → ¬ y < x.
75 axiom trans_Rlt : ∀x,y,z:R.x < y → y < z → x < z.
76 axiom trichotomy_Rlt : ∀x,y.x < y ∨ y < x ∨ x = y.
77
78 lemma trans_Rle : ∀x,y,z:R.x ≤ y → y ≤ z → x ≤ z.
79 intros;cases H
80 [cases H1; unfold; autobatch;
81 |autobatch;]
82 (*
83  [left;autobatch
84  |rewrite < H3;assumption]
85 |rewrite > H2;assumption]*)
86 qed.
87
88 axiom Rlt_plus_l : ∀x,y,z:R.x < y → z + x < z + y.
89 axiom Rlt_times_l : ∀x,y,z:R.x < y → R0 < z → z*x < z*y.
90
91 (* FIXME: these should be lemmata *)
92 axiom Rle_plus_l : ∀x,y,z:R.x ≤ y → z + x ≤ z + y.
93 axiom Rle_times_l : ∀x,y,z:R.x ≤ y → R0 < z → z*x ≤ z*y.
94
95 lemma Rle_plus_r : ∀x,y,z:R.x ≤ y → x + z ≤ y + z.
96 intros;
97 applyS Rle_plus_l;
98 autobatch;
99 (*rewrite > sym_Rplus;rewrite > sym_Rplus in ⊢ (??%);*)
100 (*applyS Rle_plus_l;
101 applyS*) 
102 cut ((x+z ≤ y+z) = (λx.(x+?≤ x+?)) ?);[5:simplify;
103   demodulate all;
104   autobatch paramodulation by sym_Rplus;
105
106 applyS Rle_plus_l by sym_Rplus;
107
108 cut ((x ≤ y) = (x+z ≤ y+z)); [2:
109   lapply (Rle_plus_l ?? z H); 
110   autobatch paramodulation by sym_Rplus,Hletin;
111 qed.
112
113 lemma Rle_times_r : ∀x,y,z:R.x ≤ y → R0 < z → x*z ≤ y*z.
114 intros;
115 rewrite > sym_Rtimes;rewrite > sym_Rtimes in ⊢ (??%);
116 autobatch;
117 qed.
118
119 (* Dedekind-completeness *)
120
121 definition ub ≝ λS: R → Prop.λx:R.∀y.S y → y ≤ x.
122 definition lub ≝ λS: R → Prop.λx:R.ub S x ∧ ∀y. ub S y → x ≤ y. 
123
124 axiom R_dedekind : ∀S:R → Prop.(∃x.S x) → (∃x.ub S x) → ∃x.lub S x.
125
126 (* coercions *)
127
128 definition R_of_nat : nat → R ≝
129  λn.match n with
130  [ O ⇒ R0
131  | S p ⇒ let rec aux m ≝
132    match m with
133    [ O ⇒ R1
134    | S q ⇒ (aux q) + R1] in aux p].
135
136 definition R_of_Z ≝
137 λz.match z with
138 [ pos n ⇒ R_of_nat (S n)
139 | neg n ⇒ Ropp (R_of_nat (S n))
140 | OZ ⇒ R0 ].
141
142 (* FIXME!!! coercion clash! *)
143 coercion R_of_Z.
144
145 (*coercion R_of_nat.*)
146
147 (* archimedean property *)
148
149 axiom R_archimedean : ∀x,y:R.R0 < x → ∃n:nat.y < n*x.
150
151 (*definition Rminus : R → R → R ≝
152  λx,y.x + (-y).*)
153  
154 interpretation "real numbers minus" 'minus x y = (Rplus x (Ropp y)).
155 interpretation "real numbers divide" 'divide x y = (Rtimes x (Rinv y)).
156
157 (* basic properties *)
158
159 (* equality *)
160
161 (* 
162 lemma Rplus_eq_l : ∀x,y,z.x = y → z + x= z + y.
163 intros;autobatch;
164 qed.
165
166 lemma Rplus_eq_r Rtimes_eq_l Rtimes_eq_r analogamente *)
167
168 lemma eq_Rplus_l_to_r : ∀a,b,c:R.a+b=c → a = c-b.
169 intros;lapply (eq_f ? ? (λx:R.x-b) ? ? H);
170 rewrite > assoc_Rplus in Hletin;rewrite > Rplus_Ropp in Hletin;
171 rewrite > Rplus_x_R0 in Hletin;assumption;
172 qed.
173
174 lemma eq_Rplus_r_to_l : ∀a,b,c:R.a=b+c → a-c = b.
175 intros;symmetry;apply eq_Rplus_l_to_r;symmetry;assumption;
176 qed.
177
178 lemma eq_Rminus_l_to_r : ∀a,b,c:R.a-b=c → a = c+b.
179 intros;lapply (eq_f ? ? (λx:R.x+b) ? ? H);
180 rewrite > assoc_Rplus in Hletin;rewrite > sym_Rplus in Hletin:(??(??%)?);
181 rewrite > Rplus_Ropp in Hletin;rewrite > Rplus_x_R0 in Hletin;assumption;
182 qed.
183
184 lemma eq_Rminus_r_to_l : ∀a,b,c:R.a=b-c → a+c = b.
185 intros;symmetry;apply eq_Rminus_l_to_r;autobatch paramodulation;
186 qed.
187
188 lemma eq_Rtimes_l_to_r : ∀a,b,c:R.b ≠ R0 → a*b=c → a = c/b.
189 intros;lapply (eq_f ? ? (λx:R.x/b) ? ? H1);
190 rewrite > assoc_Rtimes in Hletin;rewrite > Rinv_Rtimes_l in Hletin
191 [rewrite > Rtimes_x_R1 in Hletin;assumption
192 |assumption]
193 qed.
194
195 lemma eq_Rtimes_r_to_l : ∀a,b,c:R.c ≠ R0 → a=b*c → a/c = b.
196 intros;symmetry;apply eq_Rtimes_l_to_r
197 [assumption
198 |symmetry;assumption]
199 qed.
200
201 lemma eq_Rdiv_l_to_r : ∀a,b,c:R.b ≠ R0 → a/b=c → a = c*b.
202 intros;lapply (eq_f ? ? (λx:R.x*b) ? ? H1);
203 rewrite > assoc_Rtimes in Hletin;rewrite > sym_Rtimes in Hletin:(??(??%)?);
204 rewrite > Rinv_Rtimes_l in Hletin
205 [rewrite > Rtimes_x_R1 in Hletin;assumption
206 |assumption]
207 qed.
208
209 lemma eq_Rdiv_r_to_l : ∀a,b,c:R.c ≠ R0 → a=b/c → a*c = b.
210 intros;symmetry;apply eq_Rdiv_l_to_r
211 [assumption
212 |symmetry;assumption]
213 qed.
214
215 (* lemma unique_Ropp : ∀x,y.x + y = R0 → y = -x.
216 intros;autobatch paramodulation;
217 qed. *)
218
219 lemma Rtimes_x_R0 : ∀x.x * R0 = R0.
220 intro; demodulate all.
221 (*
222 rewrite < Rplus_x_R0 in ⊢ (? ? % ?);
223 rewrite < (Rplus_Ropp (x*R0)) in ⊢ (? ? (? ? %) %);
224 rewrite < assoc_Rplus;
225 apply eq_f2;autobatch paramodulation;
226 *)
227 qed.
228
229 lemma eq_Rtimes_Ropp_R1_Ropp : ∀x.x*(-R1) = -x.
230 intro. demodulate all. (*
231 auto paramodulation.
232 rewrite < Rplus_x_R0 in ⊢ (? ? % ?);
233 rewrite < Rplus_x_R0 in ⊢ (? ? ? %);
234 rewrite < (Rplus_Ropp x) in ⊢ (? ? % ?);
235 rewrite < assoc_Rplus;
236 rewrite < sym_Rplus in ⊢ (? ? % ?);
237 rewrite < sym_Rplus in ⊢ (? ? (? ? %) ?);
238 apply eq_f2 [reflexivity]
239 rewrite < Rtimes_x_R1 in ⊢ (? ? (? % ?) ?);
240 rewrite < distr_Rtimes_Rplus_l;autobatch paramodulation;
241 *)
242 qed.
243
244 lemma Ropp_inv : ∀x.x = Ropp (Ropp x).
245 intro;autobatch;
246 qed.
247
248 lemma Rinv_inv : ∀x.x ≠ R0 → x = Rinv (Rinv x).
249 intros;rewrite < Rtimes_x_R1 in ⊢ (???%);rewrite > sym_Rtimes;
250 apply eq_Rtimes_l_to_r
251 [intro;lapply (eq_f ? ? (λy:R.x*y) ? ? H1);
252  rewrite > Rinv_Rtimes_l in Hletin
253  [rewrite > Rtimes_x_R0 in Hletin;apply not_eq_R0_R1;symmetry;assumption
254  |assumption]
255 |apply Rinv_Rtimes_l;assumption] 
256 qed.
257
258 lemma Ropp_R0 : R0 = - R0. demodulate all. (*
259 rewrite < eq_Rtimes_Ropp_R1_Ropp;autobatch paramodulation; *)
260 qed.
261
262 lemma distr_Ropp_Rplus : ∀x,y:R.-(x + y) = -x -y.
263 intros; demodulate all; (*rewrite < eq_Rtimes_Ropp_R1_Ropp;
264 rewrite > sym_Rtimes;rewrite > distr_Rtimes_Rplus_l;
265 autobatch paramodulation;*)
266 qed.
267
268 lemma Ropp_Rtimes_l : ∀x,y:R.-(x*y) = -x*y.
269 intros; demodulate all; (*rewrite < eq_Rtimes_Ropp_R1_Ropp;
270 rewrite > sym_Rtimes;rewrite < assoc_Rtimes;autobatch paramodulation;*)
271 qed.
272
273 lemma Ropp_Rtimes_r : ∀x,y:R.-(x*y) = x*-y.
274 intros; demodulate all; (*rewrite > sym_Rtimes;rewrite > sym_Rtimes in ⊢ (???%);
275 autobatch;*)
276 qed.
277
278 (* less than *)
279
280 lemma Rlt_to_Rlt_Ropp_Ropp : ∀x,y.x < y → -y < -x.
281 intros;rewrite < Rplus_x_R0 in ⊢ (??%);
282 rewrite < (Rplus_Ropp y);rewrite < Rplus_x_R0 in ⊢ (?%?);
283 rewrite < assoc_Rplus;rewrite < sym_Rplus in ⊢ (??%);
284 apply Rlt_plus_l;
285 rewrite < (Rplus_Ropp x);rewrite < sym_Rplus in ⊢ (?%?);autobatch;
286 qed.
287
288 lemma lt_R0_R1 : R0 < R1.
289 elim (trichotomy_Rlt R0 R1) [|elim (not_eq_R0_R1 H)]
290 elim H [assumption]
291 rewrite > Ropp_inv in ⊢ (??%);rewrite < eq_Rtimes_Ropp_R1_Ropp;
292 rewrite < (Rtimes_x_R0 (-R1));
293 apply Rlt_times_l;rewrite < (Rtimes_x_R0 (-R1));
294 rewrite > sym_Rtimes;rewrite > eq_Rtimes_Ropp_R1_Ropp;autobatch;
295 qed.
296
297 lemma pos_z_to_lt_Rtimes_Rtimes_to_lt : ∀x,y,z.R0 < z → z*x < z*y → x < y.
298 intros;elim (trichotomy_Rlt x y)
299 [elim H2 [assumption]
300  elim (asym_Rlt (z*y) (z*x));autobatch
301 |rewrite > H2 in H1;elim (irrefl_Rlt ? H1)]
302 qed.
303
304 lemma pos_z_to_le_Rtimes_Rtimes_to_lt : ∀x,y,z.R0 < z → z*x ≤ z*y → x ≤ y.
305 intros;cases H1
306 [left;autobatch
307 |right; rewrite < Rtimes_x_R1;rewrite < Rtimes_x_R1 in ⊢ (???%);
308  rewrite < sym_Rtimes;rewrite < sym_Rtimes in ⊢ (???%);
309  rewrite < (Rinv_Rtimes_l z)
310  [demodulate all; (*rewrite < sym_Rtimes in ⊢ (??(?%?)?);rewrite < sym_Rtimes in ⊢ (???(?%?));
311   autobatch paramodulation*)
312  |intro;rewrite > H3 in H;apply (irrefl_Rlt R0);assumption]] 
313 qed.
314
315 lemma neg_z_to_lt_Rtimes_Rtimes_to_lt : ∀x,y,z.z < R0 → z*x < z*y → y < x.
316 intros;rewrite > Ropp_inv in ⊢ (?%?);
317 rewrite > Ropp_inv in ⊢ (??%);
318 apply Rlt_to_Rlt_Ropp_Ropp;apply (pos_z_to_lt_Rtimes_Rtimes_to_lt ?? (-z))
319 [rewrite > Ropp_R0;autobatch
320 |applyS H1; (*
321  rewrite < (eq_Rtimes_Ropp_R1_Ropp) in ⊢ (?(??%)?);
322  rewrite < (eq_Rtimes_Ropp_R1_Ropp) in ⊢ (??(??%));
323  do 2 rewrite < assoc_Rtimes;
324  rewrite > eq_Rtimes_Ropp_R1_Ropp;
325  rewrite > eq_Rtimes_Ropp_R1_Ropp in ⊢ (??%);
326  rewrite > sym_Rtimes;rewrite > sym_Rtimes in ⊢ (??%);
327  rewrite < (eq_Rtimes_Ropp_R1_Ropp) in ⊢ (?%?);
328  rewrite < (eq_Rtimes_Ropp_R1_Ropp) in ⊢ (??%);
329  do 2 rewrite > assoc_Rtimes;
330  rewrite > eq_Rtimes_Ropp_R1_Ropp;
331  rewrite < Ropp_inv;
332  rewrite > sym_Rtimes;rewrite > sym_Rtimes in ⊢ (??%);
333  assumption*)]
334 qed.
335
336 lemma lt_R0_Rinv : ∀x.R0 < x → R0 < Rinv x.
337 intros;apply (pos_z_to_lt_Rtimes_Rtimes_to_lt ?? x H);rewrite > Rinv_Rtimes_l;
338 [rewrite > Rtimes_x_R0;autobatch
339 |intro;apply (irrefl_Rlt x);rewrite < H1 in H;assumption]
340 qed.
341
342 lemma pos_times_pos_pos : ∀x,y.R0 < x → R0 < y → R0 < x*y.
343 intros;rewrite < (Rtimes_x_R0 x);autobatch;
344 qed.
345
346 lemma pos_plus_pos_pos : ∀x,y.R0 < x → R0 < y → R0 < x+y.
347 intros;rewrite < (Rplus_Ropp x);apply Rlt_plus_l;
348 apply (trans_Rlt ???? H1);rewrite > Ropp_R0;
349 apply Rlt_to_Rlt_Ropp_Ropp;assumption;
350 qed.
351
352 lemma Rlt_to_neq : ∀x,y:R.x < y → x ≠ y.
353 intros;intro;rewrite > H1 in H;apply (irrefl_Rlt ? H);
354 qed.
355
356 lemma lt_Rinv : ∀x,y.R0 < x → x < y → Rinv y < Rinv x.
357 intros;
358 lapply (Rlt_times_l ? ? (Rinv x * Rinv y) H1)
359 [ lapply (Rinv_Rtimes_l x);[2: intro; destruct H2; autobatch;]
360   lapply (Rinv_Rtimes_l y);[2: intro; destruct H2; autobatch;]
361   cut ((x \sup -1/y*x<x \sup -1/y*y) = (y^-1 < x ^-1));[2:
362     demodulate all;]
363   rewrite < Hcut; assumption;
364  (*
365  rewrite > sym_Rtimes in Hletin;rewrite < assoc_Rtimes in Hletin;
366  rewrite > assoc_Rtimes in Hletin:(??%);
367  rewrite > sym_Rtimes in Hletin:(??(??%));
368  rewrite > Rinv_Rtimes_l in Hletin
369  [rewrite > Rinv_Rtimes_l in Hletin
370   [applyS Hletin;(*rewrite > Rtimes_x_R1 in Hletin;rewrite > sym_Rtimes in Hletin;
371    rewrite > Rtimes_x_R1 in Hletin;assumption*)
372   |intro;rewrite > H2 in H1;apply (asym_Rlt ? ? H H1)]
373  |intro;rewrite > H2 in H;apply (irrefl_Rlt ? H)]*)
374 |apply pos_times_pos_pos;apply lt_R0_Rinv;autobatch]
375 qed.
376
377 lemma Rlt_plus_l_to_r : ∀a,b,c.a + b < c → a < c - b.
378 intros; lapply (Rlt_plus_l ?? (-b) H); applyS Hletin;
379 (*
380 rewrite < Rplus_x_R0;rewrite < (Rplus_Ropp b);
381 rewrite < assoc_Rplus;
382 rewrite < sym_Rplus;rewrite < sym_Rplus in ⊢ (??%);
383 apply Rlt_plus_l;assumption;
384 *)
385 qed.
386
387 lemma Rlt_plus_r_to_l : ∀a,b,c.a < b + c → a - c < b.
388 intros;
389 rewrite > Ropp_inv;rewrite > Ropp_inv in ⊢ (??%);
390 apply Rlt_to_Rlt_Ropp_Ropp;rewrite > distr_Ropp_Rplus;
391 apply Rlt_plus_l_to_r;rewrite < distr_Ropp_Rplus;apply Rlt_to_Rlt_Ropp_Ropp;
392 assumption;
393 qed.
394
395 lemma Rlt_minus_l_to_r : ∀a,b,c.a - b < c → a < c + b.
396 intros;rewrite > (Ropp_inv b);apply Rlt_plus_l_to_r;assumption;
397 qed.
398
399 lemma Rlt_minus_r_to_l : ∀a,b,c.a < b - c → a + c < b.
400 intros;rewrite > (Ropp_inv c);apply Rlt_plus_r_to_l;assumption;
401 qed.
402
403 lemma Rlt_div_r_to_l : ∀a,b,c.R0 < c → a < b/c → a*c < b.
404 intros;rewrite < sym_Rtimes;
405 rewrite < Rtimes_x_R1 in ⊢ (??%);rewrite < sym_Rtimes in ⊢ (??%);
406 rewrite < (Rinv_Rtimes_l c)
407 [rewrite > assoc_Rtimes;apply Rlt_times_l
408  [rewrite > sym_Rtimes;assumption
409  |autobatch]
410 |intro;elim (Rlt_to_neq ?? H);symmetry;assumption]
411 qed.
412
413 lemma Rlt_times_l_to_r : ∀a,b,c.R0 < b → a*b < c → a < c/b.
414 intros;rewrite < sym_Rtimes;
415 rewrite < Rtimes_x_R1;rewrite < sym_Rtimes;
416 rewrite < (Rinv_Rtimes_l b)
417 [rewrite < sym_Rtimes in ⊢ (? (? % ?) ?);
418  rewrite > assoc_Rtimes;apply Rlt_times_l
419  [rewrite > sym_Rtimes;assumption
420  |autobatch]
421 |intro;elim (Rlt_to_neq ?? H);symmetry;assumption]
422 qed.
423
424 lemma Rle_plus_l_to_r : ∀a,b,c.a + b ≤ c → a ≤ c - b.
425 intros;cases H
426 [left;autobatch
427 |right;autobatch]
428 qed.
429
430 lemma Rle_plus_r_to_l : ∀a,b,c.a ≤ b + c → a - c ≤ b.
431 intros;cases H
432 [left;autobatch
433 |right;autobatch]
434 qed.
435
436 lemma Rle_minus_l_to_r : ∀a,b,c.a - b ≤ c → a ≤ c + b.
437 intros;cases H
438 [left;autobatch
439 |right;autobatch]
440 qed.
441
442 lemma Rle_minus_r_to_l : ∀a,b,c.a ≤ b - c → a + c ≤ b.
443 intros;cases H
444 [left;autobatch
445 |right;autobatch]
446 qed.
447
448 lemma R_OF_nat_S : ∀n.R_OF_nat (S n) = R_OF_nat n + R1.
449 intros;elim n;simplify
450 [autobatch paramodulation
451 |reflexivity]
452 qed.
453
454 lemma nat_lt_to_R_lt : ∀m,n:nat.m < n → R_OF_nat m < R_OF_nat n.
455 intros;elim H
456 [cases m;simplify
457  [autobatch
458  |rewrite < Rplus_x_R0 in ⊢ (?%?);apply Rlt_plus_l;autobatch]
459 |apply (trans_Rlt ??? H2);cases n1;simplify
460  [autobatch
461  |rewrite < Rplus_x_R0 in ⊢ (?%?);apply Rlt_plus_l;autobatch]]
462 qed.