| 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. |