Debian Codegraph @

reals/fast/CRIR.v

raw
1 (*
2 Copyright © 2006-2008 Russell O’Connor
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this proof and associated documentation files (the "Proof"), to deal in
6 the Proof without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 the Proof, and to permit persons to whom the Proof is furnished to do so,
9 subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Proof.
13
14 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
20 *)
21
22 Require Import CoRN.algebra.RSetoid.
23 Require Import CoRN.metric2.Metric.
24 Require Import CoRN.metric2.UniformContinuity.
25 Require Export CoRN.reals.CauchySeq.
26 Require Import CoRN.reals.iso_CReals.
27 Require Import CoRN.reals.R_morphism.
28 Require Import CoRN.reals.fast.CRArith.
29 Require Export CoRN.model.reals.CRreal.
30 Require Import CoRN.tactics.CornTac.
31
32 (* Backwards compatibility for Hint Rewrite locality attributes *)
33 Set Warnings "-unsupported-attributes".
34
35 Opaque CR inject_Q.
36 (**
37 ** Isomorphism between CR and IR
38 Because CR and IR are both real number structures, they are isomorphic.
39 This module develops lemmas for translating between expressions over CR
40 and IR. A rewrite database [IRtoCR] contains rewrite lemmas for
41 converting expressions over IR to expressions over CR.
42 *)
43 Lemma CRIR_iso : Isomorphism CRasCReals IR.
44 Proof.
45 apply Canonic_Isomorphism_between_CReals.
46 Qed.
47
48 Definition CRasIR : CR -> IR := iso_map_lft _ _ CRIR_iso.
49 Definition IRasCR : IR -> CR := iso_map_rht _ _ CRIR_iso.
50
51 Lemma CRasIRasCR_id : forall (x:CR), (IRasCR (CRasIR x)==x)%CR.
52 Proof.
53 apply (inversity_rht _ _ CRIR_iso).
54 Qed.
55
56 Lemma IRasCRasIR_id : forall (x:IR), (CRasIR (IRasCR x)[=]x).
57 Proof.
58 apply (inversity_lft _ _ CRIR_iso).
59 Qed.
60
61 Lemma IRasCR_wd : forall x y, x[=]y -> (IRasCR x == IRasCR y)%CR.
62 Proof.
63 apply (map_wd_unfolded _ _ (iso_map_rht _ _ CRIR_iso)).
64 Qed.
65
66 Lemma IR_eq_as_CR : forall x y, x[=]y <-> (IRasCR x == IRasCR y)%CR.
67 Proof.
68 split.
69 apply (map_wd_unfolded _ _ (iso_map_rht _ _ CRIR_iso)).
70 intros H.
71 stepl (CRasIR (IRasCR x)); [| now apply IRasCRasIR_id].
72 stepr (CRasIR (IRasCR y)); [| now apply IRasCRasIR_id].
73 apply map_wd_unfolded.
74 assumption.
75 Qed.
76
77 Lemma CRasIR_wd : forall x y, (x==y)%CR -> CRasIR x [=] CRasIR y.
78 Proof.
79 apply (map_wd_unfolded _ _ (iso_map_lft _ _ CRIR_iso)).
80 Qed.
81
82 Lemma CR_less_as_IR : forall x y, (IRasCR x < IRasCR y -> x[<]y)%CR.
83 Proof.
84 intros x y H.
85 stepl (CRasIR (IRasCR x)); [| now apply IRasCRasIR_id].
86 stepr (CRasIR (IRasCR y)); [| now apply IRasCRasIR_id].
87 apply map_pres_less.
88 assumption.
89 Qed.
90
91 Lemma CR_ap_as_IR : forall x y, (IRasCR x >< IRasCR y -> x[#]y)%CR.
92 Proof.
93 intros.
94 stepl (CRasIR (IRasCR x)); [| now apply IRasCRasIR_id].
95 stepr (CRasIR (IRasCR y)); [| now apply IRasCRasIR_id].
96 apply map_pres_apartness.
97 assumption.
98 Qed.
99
100 Lemma IR_leEq_as_CR : forall x y, x[<=]y <-> (IRasCR x <= IRasCR y)%CR.
101 Proof.
102 intros x y.
103 split;[apply: f_pres_leEq|apply: leEq_pres_f]; solve [ apply map_strext |apply map_pres_less].
104 Qed.
105
106 Lemma IR_Zero_as_CR : (IRasCR [0]==0)%CR.
107 Proof.
108 apply (map_pres_zero_unfolded _ _ (iso_map_rht _ _ CRIR_iso)).
109 Qed.
110
111 #[global]
112 Hint Rewrite IR_Zero_as_CR : IRtoCR.
113
114 Lemma CR_ap_zero_as_IR : forall x, (IRasCR x >< 0 -> x[#][0])%CR.
115 Proof.
116 intros x H.
117 apply CR_ap_as_IR.
118 generalize H.
119 apply CRapartT_wd.
120 reflexivity.
121 symmetry.
122 apply IR_Zero_as_CR.
123 Qed.
124
125 Lemma IR_plus_as_CR : forall x y,
126 (IRasCR (x[+]y)== IRasCR x + IRasCR y)%CR.
127 Proof.
128 apply (map_pres_plus _ _ (iso_map_rht _ _ CRIR_iso)).
129 Qed.
130
131 #[global]
132 Hint Rewrite IR_plus_as_CR : IRtoCR.
133
134 Lemma IR_Sum0_as_CR : forall m x,
135 (IRasCR (Sum0 m x)==@Sum0 CRasCAbGroup m (fun n => IRasCR (x n)))%CR.
136 Proof.
137 intros m x.
138 induction m.
139 apply IR_Zero_as_CR.
140 simpl in *.
141 set (a:=Sum0 (G:=CRasCAbGroup) m (fun n : nat => IRasCR (x n))) in *.
142 clearbody a.
143 rewrite <- IHm.
144 apply IR_plus_as_CR.
145 Qed.
146
147 Lemma IR_opp_as_CR : forall x,
148 (IRasCR ([--]x)== - IRasCR x)%CR.
149 Proof.
150 apply (map_pres_minus _ _ (iso_map_rht _ _ CRIR_iso)).
151 Qed.
152
153 #[global]
154 Hint Rewrite IR_opp_as_CR : IRtoCR.
155
156 Lemma IR_minus_as_CR : forall x y,
157 (IRasCR (x[-]y)== IRasCR x - IRasCR y)%CR.
158 Proof.
159 unfold cg_minus.
160 intros x y.
161 rewrite -> IR_plus_as_CR.
162 rewrite -> IR_opp_as_CR.
163 reflexivity.
164 Qed.
165
166 #[global]
167 Hint Rewrite IR_minus_as_CR : IRtoCR.
168
169 Lemma IR_One_as_CR : (IRasCR [1]==1)%CR.
170 Proof.
171 apply (map_pres_one_unfolded _ _ (iso_map_rht _ _ CRIR_iso)).
172 Qed.
173
174 #[global]
175 Hint Rewrite IR_One_as_CR : IRtoCR.
176
177 Lemma IR_mult_as_CR : forall x y,
178 (IRasCR (x[*]y)==(IRasCR x * IRasCR y))%CR.
179 Proof.
180 apply (map_pres_mult _ _ (iso_map_rht _ _ CRIR_iso)).
181 Qed.
182
183 #[global]
184 Hint Rewrite IR_mult_as_CR : IRtoCR.
185
186 Lemma IR_div_as_CR : forall x y y_ y__,
187 (IRasCR (x[/]y[//]y_) == IRasCR x * CRinvT (IRasCR y) y__)%CR.
188 Proof.
189 intros x y y_ y__.
190 apply (@mult_cancel_lft CRasCField _ _ (IRasCR y)).
191 apply (map_pres_ap_zero _ _ (iso_map_rht _ _ CRIR_iso) y y_).
192 rewrite <- IR_mult_as_CR.
193 transitivity (IRasCR x).
194 apply IRasCR_wd; rational.
195 simpl.
196 rewrite (CRmult_comm (IRasCR x)), <- CRmult_assoc, CRmult_inv_r.
197 rewrite CRmult_1_l. reflexivity.
198 Qed.
199
200 Lemma IR_div_as_CR_1 :forall x y y_,
201 (IRasCR (x[/]y[//]y_)== IRasCR x * CRinvT (IRasCR y) (map_pres_ap_zero _ _ (iso_map_rht _ _ CRIR_iso) y y_))%CR.
202 Proof.
203 intros; apply IR_div_as_CR.
204 Qed.
205
206 Lemma IR_div_as_CR_2 :forall x y y_,
207 (IRasCR (x[/]y[//](CR_ap_zero_as_IR _ y_))== IRasCR x * CRinvT (IRasCR y) y_)%CR.
208 Proof.
209 intros; apply IR_div_as_CR.
210 Qed.
211
212 Lemma IR_recip_as_CR :forall y y_ y__,
213 (IRasCR ([1][/]y[//]y_)==(CRinvT (IRasCR y) y__))%CR.
214 Proof.
215 intros y y_ y__.
216 assert (X:=(IR_div_as_CR [1] y y_ y__)).
217 rewrite -> X.
218 change ((IRasCR [1] * CRinvT (IRasCR y) y__) == (CRinvT (IRasCR y) y__))%CR.
219 rewrite -> IR_One_as_CR.
220 change ((1 * CRinvT (IRasCR y) y__ == CRinvT (IRasCR y) y__)%CR).
221 ring.
222 Qed.
223
224 Lemma IR_recip_as_CR_1 :forall y y_,
225 (IRasCR ([1][/]y[//]y_)==(CRinvT (IRasCR y) (map_pres_ap_zero _ _ (iso_map_rht _ _ CRIR_iso) y y_)))%CR.
226 Proof.
227 intros; apply IR_recip_as_CR.
228 Qed.
229
230 Lemma IR_recip_as_CR_2 :forall y y_,
231 (IRasCR ([1][/]y[//](CR_ap_zero_as_IR _ y_))==(CRinvT (IRasCR y) y_))%CR.
232 Proof.
233 intros; apply IR_recip_as_CR.
234 Qed.
235
236 Lemma IR_nring_as_CR : forall (n:nat),
237 (IRasCR (nring n) == @nring CRasCRing n)%CR.
238 Proof.
239 induction n.
240 apply IR_Zero_as_CR.
241 simpl in *.
242 set (a:= (nring (R:=CRasCRing) n)) in *.
243 clearbody a.
244 rewrite -> IR_plus_as_CR.
245 rewrite -> IHn.
246 rewrite -> IR_One_as_CR.
247 reflexivity.
248 Qed.
249
250 #[global]
251 Hint Rewrite IR_nring_as_CR : IRtoCR.
252
253 Lemma IR_pring_as_CR : forall p,
254 (IRasCR (pring _ p) == @pring CRasCRing p)%CR.
255 Proof.
256 unfold pring.
257 intro p. simpl.
258 cut (IRasCR [1] == 1)%CR;[|apply IR_One_as_CR].
259 generalize ([1]:IR).
260 generalize (1%CR).
261 induction p;intros a b Hab.
262 - simpl.
263 assert (IRasCR (([0][+][1][+][1])[*]b) == (0+1+1)*a)%CR as H.
264 { simpl.
265 rewrite -> IR_mult_as_CR.
266 repeat rewrite -> IR_plus_as_CR.
267 repeat rewrite -> IR_One_as_CR.
268 rewrite -> IR_Zero_as_CR.
269 rewrite -> Hab.
270 reflexivity. }
271 pose proof (IHp _ _ H) as X.
272 simpl in X.
273 set (c:=pring_aux CRasCRing p ((0 + 1 + 1) * a)%CR) in *.
274 clearbody c.
275 rewrite <- X.
276 rewrite -> IR_plus_as_CR.
277 rewrite -> Hab.
278 reflexivity.
279 - simpl.
280 assert (IRasCR (([0][+][1][+][1])[*]b)== (0+1+1)*a)%CR.
281 simpl.
282 rewrite -> IR_mult_as_CR.
283 repeat rewrite -> IR_plus_as_CR.
284 repeat rewrite -> IR_One_as_CR.
285 simpl.
286 rewrite -> IR_Zero_as_CR.
287 simpl.
288 rewrite -> Hab.
289 reflexivity.
290 apply (IHp _ _ H).
291 - simpl.
292 assumption.
293 Qed.
294
295 Lemma IR_zring_as_CR : forall z,
296 (IRasCR (zring z) == @zring CRasCRing z)%CR.
297 Proof.
298 intros [|p|p].
299 apply IR_Zero_as_CR.
300 apply IR_pring_as_CR.
301 change ((IRasCR [--](pring IR p) == - ((pring CRasCRing p):CR))%CR).
302 rewrite -> IR_opp_as_CR.
303 apply CRopp_wd.
304 apply IR_pring_as_CR.
305 Qed.
306
307 #[global]
308 Hint Rewrite IR_zring_as_CR : IRtoCR.
309
310 Lemma IR_inj_Q_as_CR : forall (a:Q), (IRasCR (inj_Q IR a)==('a))%CR.
311 Proof.
312 intros [n d].
313 unfold inj_Q.
314 rewrite -> IR_div_as_CR_1.
315 generalize (map_pres_ap_zero IR CRasCReals (iso_map_rht CRasCReals IR CRIR_iso) (nring (R:=IR) (nat_of_P d))
316 (den_is_nonzero IR (n # d)%Q)).
317 intros d_.
318 setoid_replace (n#d)%Q with ((n # 1) * / (d # 1))%Q
319 by (unfold Qeq; simpl; rewrite Z.mul_1_r; reflexivity).
320 rewrite <- CRmult_Qmult.
321 assert (d__:('d >< 0)%CR).
322 { apply Qap_CRap. discriminate. }
323 rewrite <- (CRinv_Qinv d d__).
324 unfold cf_div.
325 assert (X:(forall (n:positive), IRasCR (nring (R:=IR) (nat_of_P n)) == ' Zpos n)%CR).
326 { intros x.
327 clear -x.
328 rewrite <- convert_is_POS.
329 induction (nat_of_P x); clear x.
330 apply IR_Zero_as_CR.
331 simpl.
332 rewrite -> IR_plus_as_CR.
333 rewrite -> IHn.
334 rewrite -> IR_One_as_CR.
335 simpl.
336 rewrite -> CRplus_Qplus.
337 rewrite -> CReq_Qeq.
338 unfold Qeq.
339 simpl.
340 rewrite Pmult_1_r.
341 rewrite <- POS_anti_convert.
342 ring_simplify.
343 symmetry.
344 rewrite Zplus_comm.
345 apply (inj_plus 1 n). }
346 apply (mult_wd CRasCRing);[|apply: f_rcpcl_wd;apply (X d)].
347 destruct n as [|p|p];[apply IR_Zero_as_CR| |];simpl.
348 transitivity (IRasCR (nring (nat_of_P p))).
349 apply IRasCR_wd.
350 apply pring_convert.
351 apply (X p).
352 transitivity (IRasCR [--](nring (nat_of_P p))).
353 apply IRasCR_wd.
354 apply csf_wd_unfolded.
355 apply pring_convert.
356 rewrite -> IR_opp_as_CR.
357 rewrite -> X.
358 rewrite -> CRopp_Qopp.
359 reflexivity.
360 Qed.
361
362 #[global]
363 Hint Rewrite IR_inj_Q_as_CR : IRtoCR.
364
365 Lemma IR_Cauchy_prop_as_CR : forall (x:CauchySeq IR),
366 (@Cauchy_prop CRasCOrdField (fun n => (IRasCR (x n)))).
367 Proof.
368 intros x.
369 assert (X:=map_pres_Lim _ _ (iso_map_rht CRasCReals IR CRIR_iso) _ _ (Cauchy_complete x)).
370 intros e He.
371 destruct (X _ (pos_div_two _ _ He)) as [n Hn].
372 exists n.
373 intros m Hm.
374 assert (A:=Hn m Hm).
375 assert (B:=Hn n (le_n n)).
376 set (a:=(IRasCR (x m))) in *.
377 set (b:=IRasCR (Lim (IR:=IR) x)) in *.
378 set (c:=IRasCR (x n)) in *.
379 setoid_replace (@cg_minus CRasCGroup a c) with (a-b+(b-c))%CR
380 by (unfold cg_minus; simpl; ring).
381 apply (AbsSmall_eps_div_two CRasCOrdField e (a-b)%CR (b-c)%CR).
382 assumption.
383 apply (AbsSmall_minus CRasCOrdField (e [/]TwoNZ) c b).
384 assumption.
385 Qed.
386
387 Lemma IR_Lim_as_CR : forall (x:CauchySeq IR),
388 (IRasCR (Lim x)==Lim (Build_CauchySeq _ _ (IR_Cauchy_prop_as_CR x)))%CR.
389 Proof.
390 intros x.
391 apply (SeqLimit_unique CRasCReals).
392 apply (map_pres_Lim _ _ (iso_map_rht CRasCReals IR CRIR_iso) _ _ (Cauchy_complete x)).
393 Qed.
394
395 Lemma IR_AbsSmall_as_CR : forall (x y:IR),
396 AbsSmall x y <-> AbsSmall (R:=CRasCOrdField) (IRasCR x) (IRasCR y).
397 Proof.
398 unfold AbsSmall.
399 intros x y.
400 simpl.
401 do 2 rewrite -> IR_leEq_as_CR.
402 rewrite -> IR_opp_as_CR.
403 reflexivity.
404 Qed.