| 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 Import CoRN.model.totalorder.QposMinMax. |
| 26 |
Require Import CoRN.model.reals.Cauchy_IR. |
| 27 |
Require Import CoRN.tactics.CornTac. |
| 28 |
From Coq Require Import Lia. |
| 29 |
Require Import CoRN.model.metric2.Qmetric. |
| 30 |
Require Import CoRN.model.totalorder.QMinMax. |
| 31 |
From Coq Require Import Qabs. |
| 32 |
Require Export CoRN.reals.fast.CRFieldOps. |
| 33 |
|
| 34 |
(* Backwards compatibility for Hint Rewrite locality attributes *) |
| 35 |
Set Warnings "-unsupported-attributes". |
| 36 |
|
| 37 |
|
| 38 |
Local Open Scope nat_scope. |
| 39 |
|
| 40 |
Opaque Qmin Qmax. |
| 41 |
|
| 42 |
(** |
| 43 |
** Isomorphism between CR and Cauchy_IR |
| 44 |
In prove that CR is a real number structure, we must climb the algebraic |
| 45 |
heirarchy. The easiest way of doing this is to construct an isomorphism |
| 46 |
between Cauchy_IR and CR because they are similar strucutres. |
| 47 |
Then we can leverage the proofs that Cauchy_IR is a real number structure. |
| 48 |
|
| 49 |
*** CR to Cauchy_IR |
| 50 |
*) |
| 51 |
|
| 52 |
Definition CRasCauchy_IR_raw (x:CR) (n:nat) |
| 53 |
:= approximate x (Qpos2QposInf (1 # P_of_succ_nat n)). |
| 54 |
|
| 55 |
Lemma CRasCauchy_IR_raw_is_Cauchy : forall (x:CR), |
| 56 |
Cauchy_prop (R:=Q_as_COrdField) (CRasCauchy_IR_raw x). |
| 57 |
Proof. |
| 58 |
intros x e He. |
| 59 |
destruct e as [en ed]. |
| 60 |
destruct en as [|en|en]. inversion He. 2: inversion He. |
| 61 |
unfold CRasCauchy_IR_raw. |
| 62 |
exists (pred (nat_of_P (2*ed))). |
| 63 |
rewrite <- anti_convert_pred_convert. |
| 64 |
intros m Hm. |
| 65 |
change (ball (en#ed) (approximate x (Qpos2QposInf (1 # P_of_succ_nat m))) |
| 66 |
(approximate x (Qpos2QposInf (1#(2*ed))))). |
| 67 |
eapply ball_weak_le ;[|apply regFun_prf]. |
| 68 |
simpl. |
| 69 |
apply Qle_trans with (((1 # P_of_succ_nat (pred (nat_of_P (2*ed)))) + (1 # 2 * ed)))%Q. |
| 70 |
eapply plus_resp_leEq. |
| 71 |
change (P_of_succ_nat (pred (nat_of_P (2*ed))) <= P_of_succ_nat m)%Z. |
| 72 |
rewrite <-!POS_anti_convert. apply inj_le. lia. |
| 73 |
rewrite <- anti_convert_pred_convert. |
| 74 |
stepl ((2#1)*(1#(2*ed)))%Q; [|simpl; ring]. |
| 75 |
change ((2#1)*((1/2)*(1/ed)) <= en#ed)%Q. |
| 76 |
ring_simplify. |
| 77 |
change ((2#2)*(1/ed)<=en#ed)%Q. |
| 78 |
setoid_replace (2#2)%Q with 1%Q by constructor. |
| 79 |
ring_simplify. |
| 80 |
auto with *. |
| 81 |
Qed. |
| 82 |
|
| 83 |
Definition CRasCauchy_IR (x:CR) : Cauchy_IR := |
| 84 |
Build_CauchySeq _ _ (CRasCauchy_IR_raw_is_Cauchy x). |
| 85 |
|
| 86 |
Lemma CRasCauchy_IR_wd : forall (x y:CR), (x==y)%CR -> CRasCauchy_IR x[=]CRasCauchy_IR y. |
| 87 |
Proof. |
| 88 |
intros x y Hxy. |
| 89 |
eapply Eq_alt_2_2. |
| 90 |
intros e He. |
| 91 |
destruct e as [en ed]. |
| 92 |
destruct en as [|en|en]. inversion He. 2: inversion He. |
| 93 |
exists (pred(nat_of_P (2*ed))). |
| 94 |
intros m Hm. |
| 95 |
simpl. |
| 96 |
unfold CRasCauchy_IR_raw. |
| 97 |
set (d:=(1 # P_of_succ_nat m)%Qpos). |
| 98 |
change (ball (en#ed) (approximate x (Qpos2QposInf d)) (approximate y (Qpos2QposInf d))). |
| 99 |
eapply ball_weak_le;[|apply Hxy]. |
| 100 |
unfold d. simpl. |
| 101 |
ring_simplify. |
| 102 |
apply Qle_trans with ((2#1)*(1#(2 * ed)))%Q. |
| 103 |
eapply mult_resp_leEq_lft;try discriminate. |
| 104 |
change ((2*ed)<=P_of_succ_nat m)%Z. |
| 105 |
rewrite <- Zpos_mult_morphism. |
| 106 |
rewrite (anti_convert_pred_convert (2*ed)). |
| 107 |
do 2 rewrite <- POS_anti_convert. |
| 108 |
apply inj_le. |
| 109 |
auto with *. |
| 110 |
change (1#2*ed)%Q with ((1#2)*(1#ed))%Q. |
| 111 |
ring_simplify. |
| 112 |
auto with *. |
| 113 |
Qed. |
| 114 |
|
| 115 |
(** |
| 116 |
*** Cauchy_IR to CR |
| 117 |
*) |
| 118 |
|
| 119 |
Definition Cauchy_IRasCR_raw (x:Cauchy_IR) (e:QposInf) : Q. |
| 120 |
Proof. |
| 121 |
revert e. |
| 122 |
intros [e|];[|exact 0%Q]. |
| 123 |
destruct x as [f Hf]. |
| 124 |
unfold Cauchy_prop in Hf. |
| 125 |
destruct (Hf (proj1_sig e) (Qpos_ispos e)) as [n Hn]. |
| 126 |
exact (f n). |
| 127 |
Defined. |
| 128 |
|
| 129 |
Lemma Cauchy_IRasCR_is_Regular : forall (x:Cauchy_IR), |
| 130 |
is_RegularFunction Qball (Cauchy_IRasCR_raw x). |
| 131 |
Proof. |
| 132 |
intros [f Hf] e1 e2. |
| 133 |
simpl. |
| 134 |
destruct (Hf (proj1_sig e1) (Qpos_ispos e1)) as [n1 Hn1]. |
| 135 |
destruct (Hf (proj1_sig e2) (Qpos_ispos e2)) as [n2 Hn2]. |
| 136 |
cut (forall (e1 e2:Qpos) n1 n2, n2 <= n1 -> |
| 137 |
(forall m : nat, n1 <= m -> AbsSmall (R:=Q_as_COrdField) (proj1_sig e1) (f m[-]f n1)) -> |
| 138 |
(forall m : nat, n2 <= m -> AbsSmall (R:=Q_as_COrdField) (proj1_sig e2) (f m[-]f n2)) -> |
| 139 |
Qball (proj1_sig e1 + proj1_sig e2) (f n1) (f n2)). |
| 140 |
intros H. |
| 141 |
destruct (le_ge_dec n1 n2). |
| 142 |
eapply ball_sym;simpl. |
| 143 |
assert (QposEq (e1+e2) (e2+e1)) by (unfold QposEq; simpl; ring). |
| 144 |
apply (ball_wd _ H0 _ _ (reflexivity _) _ _ (reflexivity _)). clear H0. |
| 145 |
apply H; assumption. |
| 146 |
auto. |
| 147 |
clear - Hf. |
| 148 |
intros e1 e2 n1 n2 H Hn1 Hn2. |
| 149 |
assert (QposEq (e1+e2) (e2+e1)) by (unfold QposEq; simpl; ring). |
| 150 |
apply (ball_wd _ H0 _ _ (reflexivity _) _ _ (reflexivity _)). clear H0. |
| 151 |
eapply ball_weak. apply Qpos_nonneg. |
| 152 |
eapply Hn2. |
| 153 |
assumption. |
| 154 |
Qed. |
| 155 |
|
| 156 |
Definition Cauchy_IRasCR (x:Cauchy_IR) : CR := |
| 157 |
Build_RegularFunction (Cauchy_IRasCR_is_Regular x). |
| 158 |
|
| 159 |
Lemma Cauchy_IRasCR_wd |
| 160 |
: forall (x y:Cauchy_IR), x[=]y -> (Cauchy_IRasCR x==Cauchy_IRasCR y)%CR. |
| 161 |
Proof. |
| 162 |
intros [x Hx] [y Hy] Hxy. |
| 163 |
apply regFunEq_equiv, regFunEq_e. |
| 164 |
intros e. |
| 165 |
apply ball_closed. |
| 166 |
intros d dpos. |
| 167 |
simpl. |
| 168 |
destruct (Hx (proj1_sig e) (Qpos_ispos e)) as [a Ha]. |
| 169 |
destruct (Hy (proj1_sig e) (Qpos_ispos e)) as [b Hb]. |
| 170 |
destruct (Eq_alt_2_1 _ _ _ Hxy _ dpos) as [c Hc]. |
| 171 |
simpl in Hc. |
| 172 |
unfold Qball. |
| 173 |
set (n:= Nat.max (Nat.max a b) c). |
| 174 |
unfold QAbsSmall. |
| 175 |
setoid_replace (x a - y b)%Q |
| 176 |
with ((x a - x n) + (y n - y b) + (x n - y n))%Q. |
| 177 |
2: ring. |
| 178 |
autorewrite with QposElim. |
| 179 |
repeat (eapply AbsSmall_plus). |
| 180 |
apply AbsSmall_minus. |
| 181 |
apply Ha;unfold n;apply Nat.le_trans with (Nat.max a b); auto with *. |
| 182 |
apply Hb; unfold n;apply Nat.le_trans with (Nat.max a b); auto with *. |
| 183 |
apply Hc; unfold n;auto with *. |
| 184 |
Qed. |
| 185 |
|
| 186 |
(** Composition is the identity *) |
| 187 |
Lemma CRasCR : forall x:CR, (Cauchy_IRasCR (CRasCauchy_IR x)==x)%CR. |
| 188 |
Proof. |
| 189 |
intros x. |
| 190 |
apply regFunEq_equiv, regFunEq_e. |
| 191 |
intros e. |
| 192 |
simpl. |
| 193 |
destruct (CRasCauchy_IR_raw_is_Cauchy x (proj1_sig e) (Qpos_ispos e)) as [n Hn]. |
| 194 |
unfold CRasCauchy_IR_raw in *. |
| 195 |
apply ball_closed. |
| 196 |
intros d dpos. |
| 197 |
setoid_replace (proj1_sig e+proj1_sig e+d)%Q |
| 198 |
with (proj1_sig (e+(exist _ _ dpos+e))%Qpos) |
| 199 |
by (simpl; ring). |
| 200 |
destruct d as [dn dd]. |
| 201 |
destruct dn as [|dn|dn]. inversion dpos. 2: inversion dpos. |
| 202 |
apply ball_triangle with (approximate x (Qpos2QposInf (1#P_of_succ_nat (n+(nat_of_P dd)))))%Qpos. |
| 203 |
- apply ball_sym. |
| 204 |
eapply Hn;auto with *. |
| 205 |
- eapply ball_weak_le;[|apply regFun_prf]. |
| 206 |
simpl. |
| 207 |
eapply plus_resp_leEq;simpl. |
| 208 |
apply Qle_trans with (1#dd)%Q. |
| 209 |
change (dd <= P_of_succ_nat (n + nat_of_P dd))%Z. |
| 210 |
destruct n. |
| 211 |
simpl. |
| 212 |
rewrite P_of_succ_nat_o_nat_of_P_eq_succ. |
| 213 |
rewrite Pplus_one_succ_r. |
| 214 |
rewrite Zpos_plus_distr. |
| 215 |
auto with *. |
| 216 |
rewrite <- nat_of_P_o_P_of_succ_nat_eq_succ. |
| 217 |
rewrite <- nat_of_P_plus_morphism. |
| 218 |
rewrite P_of_succ_nat_o_nat_of_P_eq_succ. |
| 219 |
rewrite Pplus_one_succ_r. |
| 220 |
repeat rewrite Zpos_plus_distr. |
| 221 |
rewrite <- Zplus_assoc. |
| 222 |
rewrite Zplus_comm. |
| 223 |
rewrite <- Zplus_assoc. |
| 224 |
rewrite <- Zpos_plus_distr. |
| 225 |
rewrite <- Pplus_one_succ_l. |
| 226 |
change (dd+0 <= dd + Pos.succ (P_of_succ_nat n))%Z. |
| 227 |
auto with *. |
| 228 |
change (dd <= dn*dd)%Z. |
| 229 |
auto with *. |
| 230 |
Qed. |
| 231 |
|
| 232 |
Lemma Cauchy_IRasCauchy_IR : forall x:Cauchy_IR, CRasCauchy_IR (Cauchy_IRasCR x)[=]x. |
| 233 |
Proof. |
| 234 |
intros [x Hx]. |
| 235 |
eapply Eq_alt_2_2. |
| 236 |
intros e He. |
| 237 |
assert (Z:(0<(1#2)*e)%Q). |
| 238 |
rewrite <- (Qmult_0_r (1#2)). |
| 239 |
eapply mult_resp_less_lft. |
| 240 |
exact He. |
| 241 |
constructor. |
| 242 |
destruct (Hx _ Z) as [n Hn]. |
| 243 |
destruct e as [en ed]. |
| 244 |
destruct en as [|en|en]. inversion He. 2: inversion He. |
| 245 |
exists (Nat.max n (nat_of_P ed)). |
| 246 |
intros m Hm. |
| 247 |
simpl. |
| 248 |
destruct Hx as [n' Hn']. |
| 249 |
apply AbsSmall_minus. |
| 250 |
destruct (le_lt_dec n' m) as [H|H]. |
| 251 |
eapply AbsSmall_trans;[|apply Hn';assumption]. |
| 252 |
change (ed < en*(P_of_succ_nat m))%Z. |
| 253 |
apply Z.lt_le_trans with (P_of_succ_nat m). |
| 254 |
rewrite <- POS_anti_convert. |
| 255 |
rewrite Zpos_eq_Z_of_nat_o_nat_of_P. |
| 256 |
apply inj_lt. |
| 257 |
apply Nat.lt_succ_r. |
| 258 |
apply Nat.le_trans with (Nat.max n (nat_of_P ed));auto with *. |
| 259 |
change (1*P_of_succ_nat m <= en * P_of_succ_nat m)%Z. |
| 260 |
apply Zmult_lt_0_le_compat_r;auto with *. |
| 261 |
stepl ((1#2)*(Z.pos en#ed)+(1#2)*(Z.pos en#ed))%Q; [| simpl; ring]. |
| 262 |
rstepr ((x m[-]x n)[+](x n[-]x n')). |
| 263 |
assert (Y:n <= m). |
| 264 |
apply Nat.le_trans with (Nat.max n (nat_of_P ed));auto with *. |
| 265 |
apply AbsSmall_plus. |
| 266 |
apply Hn. |
| 267 |
assumption. |
| 268 |
apply AbsSmall_minus; auto with *. |
| 269 |
Qed. |
| 270 |
|
| 271 |
(** Equalities are well defined. *) |
| 272 |
Lemma Cauchy_IR_eq_as_CR_eq : forall (x y:Cauchy_IR), |
| 273 |
((Cauchy_IRasCR x) == (Cauchy_IRasCR y))%CR <-> x[=]y. |
| 274 |
Proof. |
| 275 |
intros x y. |
| 276 |
split;[|apply Cauchy_IRasCR_wd]. |
| 277 |
intros H. |
| 278 |
stepl (CRasCauchy_IR (Cauchy_IRasCR x)); [| apply Cauchy_IRasCauchy_IR]. |
| 279 |
stepr (CRasCauchy_IR (Cauchy_IRasCR y)); [| apply Cauchy_IRasCauchy_IR]. |
| 280 |
apply CRasCauchy_IR_wd. |
| 281 |
assumption. |
| 282 |
Qed. |
| 283 |
|
| 284 |
Lemma CR_eq_as_Cauchy_IR_eq : forall (x y:CR), |
| 285 |
(CRasCauchy_IR x [=] CRasCauchy_IR y) <-> (x==y)%CR. |
| 286 |
Proof. |
| 287 |
intros x y. |
| 288 |
set (x':=CRasCauchy_IR x). |
| 289 |
set (y':=CRasCauchy_IR y). |
| 290 |
rewrite <- (CRasCR x). |
| 291 |
rewrite <- (CRasCR y). |
| 292 |
symmetry. |
| 293 |
apply Cauchy_IR_eq_as_CR_eq. |
| 294 |
Qed. |
| 295 |
|
| 296 |
Local Open Scope uc_scope. |
| 297 |
(** |
| 298 |
*** Functions preserved by isomorphism. |
| 299 |
*) |
| 300 |
Lemma reverse_iso_wd_fun : forall |
| 301 |
(f:Cauchy_IR -> Cauchy_IR) |
| 302 |
(g:CR -> CR), |
| 303 |
(forall x y, (x==y -> g x == g y)%CR) -> |
| 304 |
(forall (x:Cauchy_IR), |
| 305 |
(g (Cauchy_IRasCR x) == Cauchy_IRasCR (f x))%CR) -> |
| 306 |
forall (x:CR), |
| 307 |
(f (CRasCauchy_IR x) [=] CRasCauchy_IR (g x)). |
| 308 |
Proof. |
| 309 |
intros f g g_wd H x. |
| 310 |
stepl (CRasCauchy_IR (Cauchy_IRasCR (f (CRasCauchy_IR x)))); [| apply Cauchy_IRasCauchy_IR]. |
| 311 |
apply CRasCauchy_IR_wd. |
| 312 |
symmetry. |
| 313 |
transitivity (g (Cauchy_IRasCR (CRasCauchy_IR x))). |
| 314 |
apply g_wd. |
| 315 |
symmetry. |
| 316 |
apply CRasCR. |
| 317 |
apply H. |
| 318 |
Qed. |
| 319 |
|
| 320 |
Lemma reverse_iso_uc_fun : forall |
| 321 |
(f:Cauchy_IR -> Cauchy_IR) |
| 322 |
(g:CR --> CR), |
| 323 |
(forall (x:Cauchy_IR), |
| 324 |
(g (Cauchy_IRasCR x) == Cauchy_IRasCR (f x))%CR) -> |
| 325 |
forall (x:CR), |
| 326 |
(f (CRasCauchy_IR x) [=] CRasCauchy_IR (g x)). |
| 327 |
Proof. |
| 328 |
intros f g H x. |
| 329 |
apply reverse_iso_wd_fun. |
| 330 |
apply uc_wd. |
| 331 |
assumption. |
| 332 |
Qed. |
| 333 |
|
| 334 |
Lemma reverse_iso_bin_wd_fun : forall |
| 335 |
(f:Cauchy_IR -> Cauchy_IR -> Cauchy_IR) |
| 336 |
(g:CR -> CR -> CR), |
| 337 |
(forall w x, (w == x)%CR -> forall y z, (y == z -> g w y == g x z)%CR) -> |
| 338 |
(forall (x y:Cauchy_IR), |
| 339 |
(g (Cauchy_IRasCR x) (Cauchy_IRasCR y) == Cauchy_IRasCR (f x y))%CR) -> |
| 340 |
forall (x y:CR), |
| 341 |
(f (CRasCauchy_IR x) (CRasCauchy_IR y) [=] CRasCauchy_IR (g x y)). |
| 342 |
Proof. |
| 343 |
intros f g g_wd H x y. |
| 344 |
stepl (CRasCauchy_IR (Cauchy_IRasCR (f (CRasCauchy_IR x) (CRasCauchy_IR y)))); |
| 345 |
[| apply Cauchy_IRasCauchy_IR]. |
| 346 |
apply CRasCauchy_IR_wd. |
| 347 |
symmetry. |
| 348 |
transitivity (g (Cauchy_IRasCR (CRasCauchy_IR x)) (Cauchy_IRasCR (CRasCauchy_IR y))); [|apply H]. |
| 349 |
apply g_wd; symmetry; apply CRasCR. |
| 350 |
Qed. |
| 351 |
|
| 352 |
Lemma reverse_iso_bin_uc_fun : forall |
| 353 |
(f:Cauchy_IR -> Cauchy_IR -> Cauchy_IR) |
| 354 |
(g:CR --> CR --> CR), |
| 355 |
(forall (x y:Cauchy_IR), |
| 356 |
(g (Cauchy_IRasCR x) (Cauchy_IRasCR y) == Cauchy_IRasCR (f x y))%CR) -> |
| 357 |
forall (x y:CR), |
| 358 |
(f (CRasCauchy_IR x) (CRasCauchy_IR y) [=] CRasCauchy_IR (g x y)). |
| 359 |
Proof. |
| 360 |
intros f g H x y. |
| 361 |
apply (reverse_iso_bin_wd_fun f (ucFun2 g)). |
| 362 |
apply ucFun2_wd. |
| 363 |
assumption. |
| 364 |
Qed. |
| 365 |
|
| 366 |
(** injection of rationals is preserved. *) |
| 367 |
Lemma Cauchy_IR_inject_Q_as_CR_inject_Q : forall x:Q, |
| 368 |
(' x == Cauchy_IRasCR (Cauchy_CReals.inject_Q _ x))%CR. |
| 369 |
Proof. |
| 370 |
intros x. |
| 371 |
apply regFunEq_equiv, regFunEq_e. |
| 372 |
intros e. |
| 373 |
simpl. |
| 374 |
destruct (CS_seq_const Q_as_COrdField x (proj1_sig e) (Qpos_ispos e)). |
| 375 |
eapply ball_refl. |
| 376 |
apply (Qpos_nonneg (e + e)). |
| 377 |
Qed. |
| 378 |
|
| 379 |
#[global] |
| 380 |
Hint Rewrite Cauchy_IR_inject_Q_as_CR_inject_Q : CRtoCauchy_IR. |
| 381 |
|
| 382 |
Lemma CR_inject_Q_as_Cauchy_IR_inject_Q : forall x:Q, |
| 383 |
Cauchy_CReals.inject_Q _ x [=] CRasCauchy_IR (' x)%CR. |
| 384 |
Proof. |
| 385 |
intros x. |
| 386 |
eapply Eq_alt_2_2. |
| 387 |
simpl. |
| 388 |
intros e He. |
| 389 |
exists 0. |
| 390 |
intros m Hm. |
| 391 |
unfold cg_minus. |
| 392 |
rstepr ([0]:Q). |
| 393 |
apply zero_AbsSmall. |
| 394 |
apply Qlt_le_weak. |
| 395 |
assumption. |
| 396 |
Qed. |
| 397 |
|
| 398 |
(** plus is preserved. *) |
| 399 |
Lemma Cauchy_IR_plus_as_CR_plus : forall x y:Cauchy_IR, |
| 400 |
(Cauchy_IRasCR x + Cauchy_IRasCR y == Cauchy_IRasCR (x[+]y))%CR. |
| 401 |
Proof. |
| 402 |
intros [x Hx] [y Hy]. |
| 403 |
apply regFunEq_equiv, regFunEq_e. |
| 404 |
intros e. |
| 405 |
simpl. |
| 406 |
unfold Cap_raw. |
| 407 |
simpl. |
| 408 |
destruct (Hx (proj1_sig ((1 # 2) * e)%Qpos)) as [n1 Hn1]. |
| 409 |
destruct (Hy (proj1_sig ((1 # 2) * e)%Qpos)) as [n2 Hn2]. |
| 410 |
destruct (CS_seq_plus) as [n3 Hn3]. |
| 411 |
set (n:= Nat.max n3 (Nat.max n1 n2)). |
| 412 |
change (@ball Q_as_MetricSpace (proj1_sig e+proj1_sig e) (x n1 + y n2) (x n3 + y n3))%Q. |
| 413 |
apply ball_triangle with (x n + y n)%Q. |
| 414 |
assert (QposEq e (((1 # 2) * e +(1 # 2) * e))) by (unfold QposEq; simpl; ring). |
| 415 |
apply (ball_wd _ H _ _ (reflexivity _) _ _ (reflexivity _)). clear H. |
| 416 |
apply ball_triangle with (x n1 + y n)%Q; simpl; unfold Qball. |
| 417 |
unfold QAbsSmall. |
| 418 |
setoid_replace (x n1 + y n2 - (x n1 + y n))%Q with (y n2 - y n)%Q. |
| 419 |
2: ring. |
| 420 |
apply AbsSmall_minus. |
| 421 |
apply Hn2. |
| 422 |
unfold n. |
| 423 |
rewrite Nat.max_assoc. |
| 424 |
auto with *. |
| 425 |
unfold QAbsSmall. |
| 426 |
setoid_replace (x n1 + y n - (x n + y n))%Q with (x n1 - x n)%Q. |
| 427 |
2: ring. |
| 428 |
apply AbsSmall_minus. |
| 429 |
apply Hn1. |
| 430 |
unfold n. |
| 431 |
rewrite (Nat.max_comm n1). |
| 432 |
rewrite Nat.max_assoc. |
| 433 |
auto with *. |
| 434 |
eapply Hn3; unfold n; auto with *. |
| 435 |
Qed. |
| 436 |
|
| 437 |
#[global] |
| 438 |
Hint Rewrite Cauchy_IR_plus_as_CR_plus : CRtoCauchy_IR. |
| 439 |
|
| 440 |
Lemma CR_plus_as_Cauchy_IR_plus : forall x y:CR, |
| 441 |
CRasCauchy_IR x [+] CRasCauchy_IR y [=] CRasCauchy_IR (x+y)%CR. |
| 442 |
Proof. |
| 443 |
apply reverse_iso_bin_uc_fun. |
| 444 |
apply Cauchy_IR_plus_as_CR_plus. |
| 445 |
Qed. |
| 446 |
|
| 447 |
(** opp is preserved. *) |
| 448 |
Lemma Cauchy_IR_opp_as_CR_opp : forall x:Cauchy_IR, |
| 449 |
(-Cauchy_IRasCR x == Cauchy_IRasCR ([--]x))%CR. |
| 450 |
Proof. |
| 451 |
intros [x Hx]. |
| 452 |
apply regFunEq_equiv, regFunEq_e. |
| 453 |
intros e. |
| 454 |
simpl. |
| 455 |
destruct (Hx (proj1_sig e) (Qpos_ispos e)) as [n1 Hn1]. |
| 456 |
destruct (CS_seq_inv Q_as_COrdField x Hx (proj1_sig e) (Qpos_ispos e)) as [n2 Hn2]. |
| 457 |
set (n:=(Nat.max n1 n2)). |
| 458 |
change (@ball Q_as_MetricSpace (proj1_sig e+proj1_sig e) (- x n1) (- x n2))%Q. |
| 459 |
apply (@ball_triangle Q_as_MetricSpace _ _ _ (- x n)%Q). simpl; unfold Qball. |
| 460 |
unfold QAbsSmall. |
| 461 |
setoid_replace (- x n1 - - x n)%Q with (x n - x n1)%Q. |
| 462 |
2: ring. apply (Hn1 n). apply Nat.le_max_l. |
| 463 |
apply Hn2. apply Nat.le_max_r. |
| 464 |
Qed. |
| 465 |
|
| 466 |
#[global] |
| 467 |
Hint Rewrite Cauchy_IR_opp_as_CR_opp : CRtoCauchy_IR. |
| 468 |
|
| 469 |
Lemma CR_opp_as_Cauchy_IR_opp : forall x:CR, |
| 470 |
[--](CRasCauchy_IR x) [=] CRasCauchy_IR (- x)%CR. |
| 471 |
Proof. |
| 472 |
apply reverse_iso_uc_fun. |
| 473 |
apply Cauchy_IR_opp_as_CR_opp. |
| 474 |
Qed. |
| 475 |
|
| 476 |
(** le is preserved. *) |
| 477 |
Lemma Cauchy_IR_le_as_CR_le : forall (x y:Cauchy_IR), |
| 478 |
(Cauchy_IRasCR x <= Cauchy_IRasCR y)%CR <-> x[<=]y. |
| 479 |
Proof. |
| 480 |
intros [x Hx] [y Hy]. |
| 481 |
split. |
| 482 |
intros H1 [n [e He H2]]. |
| 483 |
assert (H1':=H1 ((1#3)*(exist _ _ He))%Qpos). |
| 484 |
clear H1. |
| 485 |
simpl in H1'. |
| 486 |
unfold Cap_raw in H1'; simpl in H1'. |
| 487 |
destruct (Hy (proj1_sig ((1 # 2) * ((1#3)* exist _ _ He))%Qpos)) as [n1 Hn1] in H1'. |
| 488 |
destruct (Hx (proj1_sig ((1 # 2) * ((1#3)* exist _ _ He))%Qpos)) as [n2 Hn2] in H1'. |
| 489 |
simpl in H2. |
| 490 |
set (m:=Nat.max n (Nat.max n1 n2)). |
| 491 |
assert (m1:n<=m);[unfold m; auto with *|]. |
| 492 |
assert (m2:n1<=m);[unfold m; apply Nat.le_trans with (Nat.max n1 n2); auto with *|]. |
| 493 |
assert (m3:n2<=m);[unfold m; apply Nat.le_trans with (Nat.max n1 n2); auto with *|]. |
| 494 |
apply (Qle_not_lt _ _ H1'). |
| 495 |
eapply inv_cancel_less;simpl. |
| 496 |
clear H1'. |
| 497 |
autorewrite with QposElim in *. |
| 498 |
apply Qlt_le_trans with ((2#3)*e)%Q. |
| 499 |
ring_simplify. |
| 500 |
eapply mult_resp_less. |
| 501 |
constructor. |
| 502 |
assumption. |
| 503 |
stepl (e + - ((1#2)*((1#3)*e)) + - ((1#2)*((1#3)*e)))%Q; [| simpl; ring]. |
| 504 |
stepr ((x m - y m) + (y m - y n1) + -(x m - x n2))%Q; [| simpl; ring]. |
| 505 |
eapply plus_resp_leEq_both. |
| 506 |
apply plus_resp_leEq_both. |
| 507 |
apply H2; assumption. |
| 508 |
refine (proj1 (Hn1 m _));assumption. |
| 509 |
apply inv_resp_leEq. |
| 510 |
refine (proj2 (Hn2 m _));assumption. |
| 511 |
(*Other Direction*) |
| 512 |
intros H e. |
| 513 |
simpl. |
| 514 |
unfold Cap_raw; simpl. |
| 515 |
destruct (Hy (proj1_sig ((1 # 2) * e)%Qpos)) as [n1 Hn1]. |
| 516 |
destruct (Hx (proj1_sig ((1 # 2) * e)%Qpos)) as [n2 Hn2]. |
| 517 |
apply Qnot_lt_le. |
| 518 |
intros A. |
| 519 |
apply H; clear H. |
| 520 |
exists (Nat.max n1 n2). |
| 521 |
simpl. |
| 522 |
set (n:=Nat.max n1 n2). |
| 523 |
exists (- proj1_sig e + - (y n1 + - x n2))%Q. |
| 524 |
rewrite <- Qlt_minus_iff. |
| 525 |
assumption. |
| 526 |
intros m Hm. |
| 527 |
unfold cg_minus. |
| 528 |
simpl. |
| 529 |
stepr ((x m - x n2) + -(y m - y n1) + -(y n1 + - x n2))%Q; [| simpl; ring]. |
| 530 |
eapply plus_resp_leEq. |
| 531 |
stepl (-((1 # 2) * proj1_sig e) + - ((1 # 2) * proj1_sig e))%Q; [| simpl; ring]. |
| 532 |
apply plus_resp_leEq_both. |
| 533 |
refine (proj1 (Hn2 _ _)). |
| 534 |
apply Nat.le_trans with n; [unfold n;auto with *|assumption]. |
| 535 |
apply inv_resp_leEq. |
| 536 |
refine (proj2 (Hn1 _ _)). |
| 537 |
apply Nat.le_trans with n; [unfold n;auto with *|assumption]. |
| 538 |
Qed. |
| 539 |
|
| 540 |
#[global] |
| 541 |
Hint Rewrite Cauchy_IR_le_as_CR_le : CRtoCauchy_IR. |
| 542 |
|
| 543 |
Lemma CR_le_as_Cauchy_IR_le : forall (x y:CR), |
| 544 |
CRasCauchy_IR x[<=]CRasCauchy_IR y <-> (x<=y)%CR. |
| 545 |
Proof. |
| 546 |
intros x y. |
| 547 |
rewrite <- Cauchy_IR_le_as_CR_le. |
| 548 |
do 2 rewrite -> CRasCR. |
| 549 |
reflexivity. |
| 550 |
Qed. |
| 551 |
|
| 552 |
(** mult is preserved. *) |
| 553 |
Lemma Cauchy_IR_mult_as_CRmult_bounded : forall x y:Cauchy_IR, |
| 554 |
forall (z:Qpos) (N:nat), (forall i:nat, (N<=i) -> AbsSmall (proj1_sig z) (CS_seq _ y i)) -> |
| 555 |
(ucFun2 (CRmult_bounded z) (Cauchy_IRasCR x) (Cauchy_IRasCR y) == Cauchy_IRasCR (x[*]y))%CR. |
| 556 |
Proof. |
| 557 |
intros [x Hx] y z N Hz. |
| 558 |
destruct y as [y Hy]. |
| 559 |
apply regFunEq_equiv, regFunEq_e. |
| 560 |
intros e. |
| 561 |
simpl. |
| 562 |
destruct CS_seq_mult as [n3 Hn3]. |
| 563 |
unfold Cap_raw. |
| 564 |
simpl in *. |
| 565 |
destruct Hx as [n1 Hn1]. |
| 566 |
apply Qscale_modulus_elim. |
| 567 |
intros Hxn1. |
| 568 |
pose (n:=(Nat.max n3 (Nat.max n1 N))). |
| 569 |
rewrite -> Hxn1. |
| 570 |
assert (Qeq (0 * Qmax (- proj1_sig z) (Qmin (proj1_sig z) |
| 571 |
(Cauchy_IRasCR_raw (Build_CauchySeq Q_as_COrdField y Hy)(QposInf_bind (fun e0 : Qpos => e0) QposInfinity))))%Q (0 * y n)%Q). |
| 572 |
ring. |
| 573 |
rewrite -> H. clear H. |
| 574 |
change (@ball Q_as_MetricSpace (proj1_sig e+proj1_sig e) (0 * y n) (x n3 * y n3))%Q. |
| 575 |
apply ball_triangle with (x n*y n)%Q;[|eapply Hn3; unfold n; auto with *]. |
| 576 |
apply ball_sym. |
| 577 |
simpl. |
| 578 |
setoid_replace (0 * y n)%Q with (x n1 * y n)%Q. |
| 579 |
2: rewrite Hxn1; reflexivity. |
| 580 |
unfold Qball. |
| 581 |
unfold QAbsSmall. |
| 582 |
setoid_replace (x n * y n - x n1 * y n)%Q with ((x n - x n1)*y n)%Q. |
| 583 |
2: ring. |
| 584 |
apply AbsSmall_trans with ((1#2)*proj1_sig e)%Q. |
| 585 |
apply half_3. |
| 586 |
apply Qpos_ispos. |
| 587 |
stepl (((1#2)*proj1_sig e/ proj1_sig z)* proj1_sig z)%Q; |
| 588 |
[| simpl;field;apply Qpos_nonzero]. |
| 589 |
apply mult_AbsSmall;[apply Hn1|apply Hz]; unfold n; apply Nat.le_trans with (Nat.max n1 N); auto with *. |
| 590 |
intros w Hw. |
| 591 |
simpl. |
| 592 |
destruct (Hy (proj1_sig w) (Qpos_ispos w)) as [n2 Hn2]. |
| 593 |
pose (n:=(Nat.max (Nat.max n1 n2) (Nat.max n3 N))). |
| 594 |
assert (n1 <= n);[unfold n; apply Nat.le_trans with (Nat.max n1 n2); auto with *|]. |
| 595 |
assert (n2 <= n);[unfold n; apply Nat.le_trans with (Nat.max n1 n2); auto with *|]. |
| 596 |
assert (n3 <= n);[unfold n; apply Nat.le_trans with (Nat.max n3 N); auto with *|]. |
| 597 |
assert (N <= n);[unfold n; apply Nat.le_trans with (Nat.max n3 N); auto with *|]. |
| 598 |
change (Qball (proj1_sig e+proj1_sig e)) |
| 599 |
with (@ball Q_as_MetricSpace (proj1_sig e + proj1_sig e)). |
| 600 |
apply ball_triangle with (x n * y n)%Q;[|eapply Hn3; assumption]. |
| 601 |
clear Hn3. |
| 602 |
assert (QposEq e ((1#2)*e + (1#2)*e)) by (unfold QposEq; simpl; ring). |
| 603 |
apply (ball_wd _ H3 _ _ (reflexivity _) _ _ (reflexivity _)). clear H3. |
| 604 |
apply ball_triangle with (x n1 * y n)%Q; apply ball_sym; simpl; unfold Qball. |
| 605 |
unfold QAbsSmall. |
| 606 |
setoid_replace (x n1 * y n - x n1 * Qmax (- proj1_sig z) (Qmin (proj1_sig z) (y n2)))%Q |
| 607 |
with (x n1*(y n - Qmax (- proj1_sig z) (Qmin (proj1_sig z) (y n2))))%Q. 2: ring. |
| 608 |
simpl. |
| 609 |
stepl (((1#2)*proj1_sig e/proj1_sig w)*proj1_sig w)%Q; [| simpl;field;apply Qpos_nonzero]. |
| 610 |
apply mult_AbsSmall;[apply Hw|]. |
| 611 |
destruct (Hz n H2) as [X0 X1]. |
| 612 |
destruct (Hn2 _ H0) as [X2 X3]. |
| 613 |
unfold cg_minus in *. |
| 614 |
simpl in *. |
| 615 |
change (Qmax (- proj1_sig z) (Qmin (proj1_sig z) (y n2)))%Q |
| 616 |
with (QboundAbs z (y n2))%Q. |
| 617 |
assert (A0:(- proj1_sig w<=0)%Q). |
| 618 |
rewrite -> Qle_minus_iff. |
| 619 |
ring_simplify. |
| 620 |
apply Qpos_nonneg. |
| 621 |
rewrite -> Qle_minus_iff in *. |
| 622 |
clear - A0 X0 X1 X2 X3 Hn2 H0. |
| 623 |
ring_simplify in A0. |
| 624 |
ring_simplify in X0. |
| 625 |
ring_simplify in X1. |
| 626 |
ring_simplify in X2. |
| 627 |
ring_simplify in X3. |
| 628 |
apply QboundAbs_elim; intros I; try solve [apply Hn2;assumption]; rewrite -> Qle_minus_iff in I. |
| 629 |
apply AbsSmall_minus. |
| 630 |
unfold cg_minus;simpl. |
| 631 |
apply leEq_imp_AbsSmall. |
| 632 |
apply X1. |
| 633 |
rewrite -> Qle_minus_iff. |
| 634 |
stepr ((y n + (-1 # 1) * y n2 + proj1_sig w)+(y n2 + - proj1_sig z))%Q; [| simpl; ring]. |
| 635 |
eapply plus_resp_nonneg; assumption. |
| 636 |
eapply leEq_imp_AbsSmall; simpl; ring_simplify. |
| 637 |
apply X0. |
| 638 |
rewrite -> Qle_minus_iff. |
| 639 |
stepr ((proj1_sig w + (-1 # 1) * y n + y n2)+(- proj1_sig z + - y n2))%Q; [| simpl; ring]. |
| 640 |
eapply plus_resp_nonneg; assumption. |
| 641 |
unfold QAbsSmall. |
| 642 |
setoid_replace (x n * y n - x n1 * y n)%Q with ((x n - x n1)*y n)%Q. 2: ring. |
| 643 |
autorewrite with QposElim. |
| 644 |
stepl (((1#2)*proj1_sig e/proj1_sig z)*proj1_sig z)%Q; [| simpl; field; apply Qpos_nonzero]. |
| 645 |
apply mult_AbsSmall;[apply Hn1;assumption|apply Hz;assumption]. |
| 646 |
Qed. |
| 647 |
|
| 648 |
Lemma AbsSmall_Qabs : forall x y, (Qabs y <= x)%Q <-> AbsSmall x y. |
| 649 |
Proof. |
| 650 |
cut (forall x y, (0 <= y)%Q -> ((Qabs y <= x)%Q <-> AbsSmall (R:=Q_as_COrdField) x y)). |
| 651 |
intros H x y. |
| 652 |
generalize (H x y) (H x (-y)%Q). |
| 653 |
clear H. |
| 654 |
rewrite -> Qabs_opp. |
| 655 |
apply Qabs_case; intros H H1 H2. |
| 656 |
auto. |
| 657 |
assert (X:AbsSmall (R:=Q_as_COrdField) x y <-> AbsSmall (R:=Q_as_COrdField) x (- y)%Q). |
| 658 |
split. |
| 659 |
apply inv_resp_AbsSmall. |
| 660 |
intros X. |
| 661 |
stepr (- - y)%Q; [| simpl; ring]. |
| 662 |
apply inv_resp_AbsSmall. |
| 663 |
assumption. |
| 664 |
rewrite -> X. |
| 665 |
eapply H2. |
| 666 |
rewrite -> Qle_minus_iff in H. |
| 667 |
ring_simplify in H. |
| 668 |
ring_simplify. |
| 669 |
apply H. |
| 670 |
intros x y H. |
| 671 |
rewrite -> Qabs_pos;[|assumption]. |
| 672 |
split. |
| 673 |
intros H0. |
| 674 |
apply leEq_imp_AbsSmall; assumption. |
| 675 |
intros [_ H0]. |
| 676 |
assumption. |
| 677 |
Qed. |
| 678 |
|
| 679 |
Lemma Cauchy_IR_mult_as_CR_mult : forall x y:Cauchy_IR, |
| 680 |
((Cauchy_IRasCR x)*(Cauchy_IRasCR y) == Cauchy_IRasCR (x[*]y))%CR. |
| 681 |
Proof. |
| 682 |
intros x [y Hy]. |
| 683 |
destruct (CS_seq_bounded _ y Hy) as [k Hk [n Hn]]. |
| 684 |
set (y':=Build_CauchySeq Q_as_COrdField y Hy). |
| 685 |
set (k':=(exist _ _ Hk)). |
| 686 |
transitivity ((ucFun2 (CRmult_bounded (CR_b (1 # 1) (Cauchy_IRasCR y')+k')%Qpos) (Cauchy_IRasCR x) |
| 687 |
(Cauchy_IRasCR y'))). |
| 688 |
apply CRmult_bounded_weaken. |
| 689 |
apply CR_b_lowerBound. |
| 690 |
apply CR_b_upperBound. |
| 691 |
simpl. |
| 692 |
rewrite -> Qle_minus_iff. |
| 693 |
ring_simplify. |
| 694 |
auto with *. |
| 695 |
apply Cauchy_IR_mult_as_CRmult_bounded with n. |
| 696 |
intros i Hi. |
| 697 |
eapply AbsSmall_trans;[|apply Hn;assumption]. |
| 698 |
simpl. |
| 699 |
rewrite -> Qlt_minus_iff. |
| 700 |
unfold k'. |
| 701 |
autorewrite with QposElim. |
| 702 |
ring_simplify. |
| 703 |
clear. |
| 704 |
destruct Hy. |
| 705 |
rewrite Qplus_comm. |
| 706 |
apply Q.Qplus_lt_le_0_compat. |
| 707 |
reflexivity. apply Qabs_nonneg. |
| 708 |
Qed. |
| 709 |
|
| 710 |
#[global] |
| 711 |
Hint Rewrite Cauchy_IR_mult_as_CR_mult : CRtoCauchy_IR. |
| 712 |
|
| 713 |
Lemma CR_mult_as_Cauchy_IR_mult : forall x y:CR, |
| 714 |
(CRasCauchy_IR x)[*](CRasCauchy_IR y) [=] CRasCauchy_IR (x*y)%CR. |
| 715 |
Proof. |
| 716 |
apply reverse_iso_bin_wd_fun. |
| 717 |
apply CRmult_wd. |
| 718 |
apply Cauchy_IR_mult_as_CR_mult. |
| 719 |
Qed. |
| 720 |
|
| 721 |
(** lt is preserved. *) |
| 722 |
Lemma Cauchy_IR_lt_as_CR_lt_1 : forall (x y:Cauchy_IR), |
| 723 |
x[<]y -> (Cauchy_IRasCR x < Cauchy_IRasCR y)%CR. |
| 724 |
Proof. |
| 725 |
intros x y [n [e He Hn]]. |
| 726 |
exists (exist _ _ He). |
| 727 |
abstract ( autorewrite with CRtoCauchy_IR; intros [m [d Hd Hm]]; |
| 728 |
refine (Qle_not_lt _ _ (Hn (Nat.max n m) _) _);[auto with *|]; rewrite -> Qlt_minus_iff; |
| 729 |
apply Qlt_le_trans with d;[assumption|]; autorewrite with QposElim in Hm; eapply Hm; auto with * |
| 730 |
). |
| 731 |
Defined. |
| 732 |
|
| 733 |
Lemma CR_lt_as_Cauchy_IR_lt_1 : forall (x y:CR), |
| 734 |
(x < y)%CR -> (CRasCauchy_IR x)[<](CRasCauchy_IR y). |
| 735 |
Proof. |
| 736 |
intros x y [e He]. |
| 737 |
apply shift_zero_less_minus'. |
| 738 |
apply (less_leEq_trans _ [0] (Cauchy_CReals.inject_Q _ (proj1_sig e))). |
| 739 |
eapply ing_lt. |
| 740 |
apply Qpos_ispos. |
| 741 |
unfold cg_minus. |
| 742 |
stepr (CRasCauchy_IR (y-x))%CR. |
| 743 |
stepl (CRasCauchy_IR (' proj1_sig e)%CR). |
| 744 |
rewrite <- Cauchy_IR_le_as_CR_le. |
| 745 |
do 2 rewrite -> CRasCR. |
| 746 |
assumption. |
| 747 |
eapply CR_inject_Q_as_Cauchy_IR_inject_Q. |
| 748 |
stepl (CRasCauchy_IR y[+]CRasCauchy_IR(- x)%CR). |
| 749 |
apply plus_resp_eq. |
| 750 |
eapply CR_opp_as_Cauchy_IR_opp. |
| 751 |
eapply CR_plus_as_Cauchy_IR_plus. |
| 752 |
Qed. |
| 753 |
|
| 754 |
Lemma Cauchy_IR_lt_as_CR_lt_2 : forall (x y:Cauchy_IR), |
| 755 |
((Cauchy_IRasCR x) < (Cauchy_IRasCR y))%CR -> x[<]y. |
| 756 |
Proof. |
| 757 |
intros x y H. |
| 758 |
stepl (CRasCauchy_IR (Cauchy_IRasCR (x))); [| apply Cauchy_IRasCauchy_IR]. |
| 759 |
stepr (CRasCauchy_IR (Cauchy_IRasCR (y))); [| apply Cauchy_IRasCauchy_IR]. |
| 760 |
apply CR_lt_as_Cauchy_IR_lt_1. |
| 761 |
assumption. |
| 762 |
Qed. |
| 763 |
|
| 764 |
Lemma CR_lt_as_Cauchy_IR_lt_2 : forall (x y:CR), |
| 765 |
(CRasCauchy_IR x)[<](CRasCauchy_IR y) -> (x < y)%CR. |
| 766 |
Proof. |
| 767 |
intros x y H. |
| 768 |
eapply CRltT_wd;try apply CRasCR. |
| 769 |
apply Cauchy_IR_lt_as_CR_lt_1. |
| 770 |
assumption. |
| 771 |
Qed. |
| 772 |
|
| 773 |
(** appartness is preserved. *) |
| 774 |
Lemma Cauchy_IR_ap_as_CR_ap_1 : forall (x y:Cauchy_IR), |
| 775 |
x[#]y -> (CRapartT (Cauchy_IRasCR x) (Cauchy_IRasCR y))%CR. |
| 776 |
Proof. |
| 777 |
intros x y [H|H];[left|right];apply Cauchy_IR_lt_as_CR_lt_1; apply H. |
| 778 |
Defined. |
| 779 |
|
| 780 |
Lemma CR_ap_as_Cauchy_IR_ap_1 : forall (x y:CR), |
| 781 |
CRapartT x y -> (CRasCauchy_IR x) [#] (CRasCauchy_IR y). |
| 782 |
Proof. |
| 783 |
intros x y [H|H];[left|right];apply CR_lt_as_Cauchy_IR_lt_1; apply H. |
| 784 |
Defined. |
| 785 |
|
| 786 |
Lemma Cauchy_IR_ap_as_CR_ap_2 : forall (x y:Cauchy_IR), |
| 787 |
(CRapartT (Cauchy_IRasCR x) (Cauchy_IRasCR y))%CR -> x[#]y. |
| 788 |
Proof. |
| 789 |
intros x y [H|H];[left|right];apply Cauchy_IR_lt_as_CR_lt_2; apply H. |
| 790 |
Qed. |
| 791 |
|
| 792 |
Lemma CR_ap_as_Cauchy_IR_ap_2 : forall (x y:CR), |
| 793 |
(CRasCauchy_IR x) [#] (CRasCauchy_IR y) -> CRapartT x y. |
| 794 |
Proof. |
| 795 |
intros x y [H|H];[left|right];apply CR_lt_as_Cauchy_IR_lt_2; apply H. |
| 796 |
Defined. |
| 797 |
|
| 798 |
(** inv is preserved. *) |
| 799 |
Lemma Cauchy_IR_inv_as_CRinv_pos : forall (x:Cauchy_IR) x_, |
| 800 |
forall (z:Qpos) (N:nat), (forall i:nat, (N<=i) -> (proj1_sig z <= (CS_seq _ x i))%Q) -> |
| 801 |
(CRinv_pos z (Cauchy_IRasCR x) == Cauchy_IRasCR (f_rcpcl x (@inr _ _ x_)))%CR. |
| 802 |
Proof. |
| 803 |
intros [x Hx] [a [d d_ x_]] z n Hn. |
| 804 |
apply regFunEq_equiv, regFunEq_e. |
| 805 |
intros e. |
| 806 |
simpl. |
| 807 |
unfold Qinv_modulus. |
| 808 |
destruct (Hx (proj1_sig z * proj1_sig z * proj1_sig e)%Q) as [b Hb]. |
| 809 |
destruct (CS_seq_recip) as [c Hc]. |
| 810 |
set (y := (CS_seq_recip_seq Q_as_COrdField x d d_ a |
| 811 |
(fun (n : nat) (H : le a n) => |
| 812 |
leEq_wdr Q_as_COrdField d |
| 813 |
(@cg_minus Q_as_CGroup (x n) (Qmake Z0 xH)) (x n) (x_ n H) |
| 814 |
(cg_inv_zero Q_as_CGroup (x n))))) in *. |
| 815 |
unfold CS_seq_recip_seq in y. |
| 816 |
simpl in y. |
| 817 |
set (m:=Nat.max (Nat.max a n) (Nat.max b c)). |
| 818 |
assert (Hm1: c<=m). |
| 819 |
unfold m; apply Nat.le_trans with (Nat.max b c); auto with *. |
| 820 |
change (@ball Q_as_MetricSpace (proj1_sig e+proj1_sig e) (/ Qmax (proj1_sig z) (x b))%Q (y c)). |
| 821 |
apply ball_triangle with (y m);[|eapply Hc;assumption]. |
| 822 |
clear Hc. |
| 823 |
unfold y. |
| 824 |
destruct (lt_le_dec m a) as [Z|Z]. |
| 825 |
elim (proj1 (Nat.le_ngt _ _) Z). |
| 826 |
unfold m. |
| 827 |
apply Nat.lt_le_trans with (S (Nat.max a n)); auto with *. |
| 828 |
change (AbsSmall (proj1_sig e) (/ Qmax (proj1_sig z) (x b)-1 * / x m))%Q. |
| 829 |
clear y. |
| 830 |
assert (T:(~ (x m == 0)%Q /\ ~ (Qmax (proj1_sig z) (x b) == 0)%Q)). |
| 831 |
split; apply (ap_symmetric_unfolded Q_as_CSetoid); eapply Qlt_not_eq. |
| 832 |
apply Qlt_le_trans with (proj1_sig z). |
| 833 |
apply Qpos_ispos. |
| 834 |
apply Hn. |
| 835 |
apply Nat.le_trans with (Nat.max a n). |
| 836 |
auto with *. |
| 837 |
unfold m; auto with *. |
| 838 |
apply Qlt_le_trans with (proj1_sig z); auto with *. |
| 839 |
stepr ((/(Qmax (proj1_sig z) (x b))*/(x m))*(x m - (Qmax (proj1_sig z) (x b))))%Q; |
| 840 |
[| simpl; field; assumption]. |
| 841 |
stepl ((/ Qmax (proj1_sig z) (x b) * / x m)*((Qmax (proj1_sig z) (x b))*(x m)* proj1_sig e))%Q; |
| 842 |
[| simpl;field; assumption]. |
| 843 |
apply mult_resp_AbsSmall. |
| 844 |
assert (foo:forall q:Q, (0<=q -> 0<=/q)%Q). |
| 845 |
intros [[|p|p] q] qH; apply qH. |
| 846 |
apply mult_resp_nonneg. |
| 847 |
apply foo. |
| 848 |
apply Qle_trans with (proj1_sig z). |
| 849 |
apply Qpos_nonneg. |
| 850 |
apply Qmax_ub_l. |
| 851 |
apply foo. |
| 852 |
apply Qle_trans with (proj1_sig z). |
| 853 |
apply Qpos_nonneg. |
| 854 |
apply Hn. |
| 855 |
apply Nat.le_trans with (Nat.max a n); unfold m; auto with *. |
| 856 |
simpl in x_. |
| 857 |
apply (AbsSmall_leEq_trans _ (proj1_sig z*proj1_sig z*proj1_sig e)%Q). |
| 858 |
apply mult_resp_leEq_rht;[apply mult_resp_leEq_both|]; try apply Qpos_nonneg. |
| 859 |
apply Qmax_ub_l. |
| 860 |
apply Hn. |
| 861 |
apply Nat.le_trans with (Nat.max a n); unfold m; auto with *. |
| 862 |
assert (W:AbsSmall (R:=Q_as_COrdField) (proj1_sig z * proj1_sig z * proj1_sig e)%Q (x m - x b)%Q). |
| 863 |
apply Hb. |
| 864 |
apply Nat.le_trans with (Nat.max b c); unfold m; auto with *. |
| 865 |
apply Qmax_case;intros C;[|assumption]. |
| 866 |
apply leEq_imp_AbsSmall. |
| 867 |
unfold Qminus. |
| 868 |
rewrite <- Qle_minus_iff. |
| 869 |
apply Hn. |
| 870 |
apply Nat.le_trans with (Nat.max a n); unfold m; auto with *. |
| 871 |
apply Qle_trans with (x m - x b)%Q. |
| 872 |
rewrite -> Qle_minus_iff. |
| 873 |
stepr (proj1_sig z + - x b)%Q; [| simpl; ring]. |
| 874 |
rewrite <- Qle_minus_iff. |
| 875 |
assumption. |
| 876 |
destruct W; assumption. |
| 877 |
Qed. |
| 878 |
|
| 879 |
Lemma Cauchy_IR_nonZero_as_CR_nonZero_1 : forall (x:Cauchy_IR), |
| 880 |
Dom (f_rcpcl' _) x -> (CRapartT (Cauchy_IRasCR x) 0)%CR. |
| 881 |
Proof. |
| 882 |
intros x x_. |
| 883 |
eapply CRapartT_wd. |
| 884 |
reflexivity. |
| 885 |
symmetry. |
| 886 |
apply Cauchy_IR_inject_Q_as_CR_inject_Q. |
| 887 |
apply Cauchy_IR_ap_as_CR_ap_1. |
| 888 |
assumption. |
| 889 |
Defined. |
| 890 |
|
| 891 |
Lemma CR_nonZero_as_Cauchy_IR_nonZero_1 : forall (x:CR), |
| 892 |
(CRapartT x 0)%CR -> Dom (f_rcpcl' _) (CRasCauchy_IR x). |
| 893 |
Proof. |
| 894 |
intros x x_. |
| 895 |
change ((CRasCauchy_IR x)[#][0]). |
| 896 |
stepr (CRasCauchy_IR 0%CR). |
| 897 |
apply CR_ap_as_Cauchy_IR_ap_1. |
| 898 |
assumption. |
| 899 |
eapply CR_inject_Q_as_Cauchy_IR_inject_Q. |
| 900 |
Defined. |
| 901 |
|
| 902 |
Lemma Cauchy_IR_inv_as_CR_inv_short : forall (x:Cauchy_IR) x_, |
| 903 |
(@CRinvT (Cauchy_IRasCR x) (Cauchy_IR_nonZero_as_CR_nonZero_1 _ x_) == Cauchy_IRasCR (f_rcpcl x x_))%CR. |
| 904 |
Proof. |
| 905 |
intros [x Hx] [H|H]. |
| 906 |
set (x':=(Build_CauchySeq Q_as_COrdField x Hx)) in *. |
| 907 |
assert (H':(cm_unit Cauchy_IR)[<][--](x':Cauchy_IR)). |
| 908 |
apply inv_cancel_less. |
| 909 |
rstepl x'. |
| 910 |
assumption. |
| 911 |
set (y:= (Cauchy_IRasCR [--](f_rcpcl (F:=Cauchy_IR) ([--](x':Cauchy_IR)) (@inr _ _ H')))%CR). |
| 912 |
transitivity y. |
| 913 |
destruct H as [n [e He H]]. |
| 914 |
change (-(CRinv_pos (exist _ _ He) (- Cauchy_IRasCR (Build_CauchySeq Q_as_COrdField x Hx)))==y)%CR. |
| 915 |
unfold y. |
| 916 |
rewrite <- Cauchy_IR_opp_as_CR_opp. |
| 917 |
apply CRopp_wd. |
| 918 |
set (X := (Cauchy_IRasCR (f_rcpcl (F:=Cauchy_IR) [--](x':Cauchy_IR) |
| 919 |
(@inr (R_lt Q_as_COrdField [--](x':Cauchy_IR) ([0]:Cauchy_IR)) ([0][<][--](x':Cauchy_IR)) H')))%CR). |
| 920 |
rewrite -> Cauchy_IR_opp_as_CR_opp. |
| 921 |
eapply Cauchy_IR_inv_as_CRinv_pos. |
| 922 |
intros i Hi. |
| 923 |
autorewrite with QposElim. |
| 924 |
simpl. |
| 925 |
stepr (0 - x i)%Q; [| simpl; ring]. |
| 926 |
eapply H. |
| 927 |
apply Hi. |
| 928 |
unfold y. |
| 929 |
apply Cauchy_IRasCR_wd. |
| 930 |
eapply mult_cancel_lft. |
| 931 |
left. |
| 932 |
apply H. |
| 933 |
stepr ([1]:Cauchy_IR). |
| 934 |
eapply eq_transitive. |
| 935 |
apply cring_inv_mult_lft. |
| 936 |
apply eq_symmetric. |
| 937 |
eapply eq_transitive;[|apply cring_inv_mult_rht]. |
| 938 |
apply eq_symmetric. |
| 939 |
apply x_div_x. |
| 940 |
apply eq_symmetric. |
| 941 |
apply x_div_x. |
| 942 |
destruct H as [n [e He H]]. |
| 943 |
eapply Cauchy_IR_inv_as_CRinv_pos. |
| 944 |
intros i Hi. |
| 945 |
autorewrite with QposElim. |
| 946 |
simpl in *. |
| 947 |
stepr (x i- 0)%Q; [| simpl; ring]. |
| 948 |
apply H. |
| 949 |
apply Hi. |
| 950 |
Qed. |
| 951 |
|
| 952 |
#[global] |
| 953 |
Hint Rewrite Cauchy_IR_inv_as_CR_inv_short : CRtoCauchy_IR. |
| 954 |
|
| 955 |
Lemma Cauchy_IR_inv_as_CR_inv : forall (x:Cauchy_IR) x_ H, |
| 956 |
(@CRinvT (Cauchy_IRasCR x) H == Cauchy_IRasCR (f_rcpcl x x_))%CR. |
| 957 |
Proof. |
| 958 |
intros x x_ H. |
| 959 |
rewrite <- Cauchy_IR_inv_as_CR_inv_short. |
| 960 |
apply CRinvT_irrelevant. |
| 961 |
Qed. |
| 962 |
|
| 963 |
Lemma CR_inv_as_Cauchy_IR_inv : forall (x:CR) x_ H, |
| 964 |
f_rcpcl (CRasCauchy_IR x) H [=] CRasCauchy_IR (@CRinvT x x_). |
| 965 |
Proof. |
| 966 |
intros x x_ H. |
| 967 |
stepl (CRasCauchy_IR (Cauchy_IRasCR (f_rcpcl (CRasCauchy_IR x) H))); [| apply Cauchy_IRasCauchy_IR]. |
| 968 |
apply CRasCauchy_IR_wd. |
| 969 |
rewrite <- Cauchy_IR_inv_as_CR_inv_short. |
| 970 |
apply CRinvT_wd. |
| 971 |
apply CRasCR. |
| 972 |
Qed. |
| 973 |
|
| 974 |
Lemma CR_inv_as_Cauchy_IR_inv_short : forall (x:CR) x_, |
| 975 |
f_rcpcl (CRasCauchy_IR x) (CR_nonZero_as_Cauchy_IR_nonZero_1 _ x_) [=] CRasCauchy_IR (@CRinvT x x_). |
| 976 |
Proof. |
| 977 |
intros. |
| 978 |
apply CR_inv_as_Cauchy_IR_inv. |
| 979 |
Qed. |