| 1 |
(* |
| 2 |
Copyright © 2006-2008 Russell O’Connor |
| 3 |
Copyright © 2020 Vincent Semeria |
| 4 |
|
| 5 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 6 |
this proof and associated documentation files (the "Proof"), to deal in |
| 7 |
the Proof without restriction, including without limitation the rights to |
| 8 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 9 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 10 |
subject to the following conditions: |
| 11 |
|
| 12 |
The above copyright notice and this permission notice shall be included in all |
| 13 |
copies or substantial portions of the Proof. |
| 14 |
|
| 15 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 16 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 17 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 18 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 19 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 20 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 21 |
*) |
| 22 |
|
| 23 |
Require Import CoRN.metric2.Metric. |
| 24 |
Require Import CoRN.metric2.UniformContinuity. |
| 25 |
Require Import CoRN.model.totalorder.QMinMax. |
| 26 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 27 |
From Coq Require Import Ring_theory. |
| 28 |
From Coq Require Import Setoid. |
| 29 |
From Coq Require Import QArith. |
| 30 |
From Coq Require Import Qabs. |
| 31 |
From Coq Require Import Qround. |
| 32 |
Require Import CoRN.metric2.Complete. |
| 33 |
Require Import CoRN.metric2.ProductMetric. |
| 34 |
Require Export CoRN.reals.fast.CRFieldOps. |
| 35 |
Require Import CoRN.model.metric2.Qmetric. |
| 36 |
Require Import CoRN.logic.Stability. |
| 37 |
From Coq Require Import ConstructiveEpsilon. |
| 38 |
Require Import CoRN.util.Qdlog. |
| 39 |
Require Import MathClasses.interfaces.abstract_algebra. |
| 40 |
Require Import MathClasses.interfaces.orders. |
| 41 |
|
| 42 |
(* Backwards compatibility for Hint Rewrite locality attributes *) |
| 43 |
Set Warnings "-unsupported-attributes". |
| 44 |
|
| 45 |
Local Open Scope CR_scope. |
| 46 |
|
| 47 |
(** Operations on rational numbers over CR are the same as the operations |
| 48 |
on rational numbers. *) |
| 49 |
Lemma CReq_Qeq : forall (x y:Q), inject_Q_CR x == inject_Q_CR y <-> (x == y)%Q. |
| 50 |
Proof. |
| 51 |
intros x y. |
| 52 |
rewrite <- Qball_0. |
| 53 |
apply Cunit_eq. |
| 54 |
Qed. |
| 55 |
|
| 56 |
Lemma CRlt_Qlt : forall a b, (a < b)%Q -> ((' a%Q) < (' b))%CR. |
| 57 |
Proof. |
| 58 |
intros a b H. |
| 59 |
destruct (Qpos_sub _ _ H) as [c Hc]. |
| 60 |
exists c. |
| 61 |
intros d. |
| 62 |
change (-proj1_sig d <= b + - a + - proj1_sig c)%Q. |
| 63 |
rewrite -> Hc. |
| 64 |
rewrite -> Qle_minus_iff. |
| 65 |
ring_simplify. |
| 66 |
apply Qpos_nonneg. |
| 67 |
Qed. |
| 68 |
|
| 69 |
Lemma CRplus_Qplus : forall (x y:Q), inject_Q_CR x + inject_Q_CR y == inject_Q_CR (x + y)%Q. |
| 70 |
Proof. |
| 71 |
intros x y e1 e2; apply ball_refl. |
| 72 |
rewrite Qplus_0_r. |
| 73 |
apply (Qpos_nonneg (e1+e2)). |
| 74 |
Qed. |
| 75 |
|
| 76 |
#[global] |
| 77 |
Hint Rewrite <- CRplus_Qplus : toCRring. |
| 78 |
|
| 79 |
Lemma CRopp_Qopp : forall (x:Q), - inject_Q_CR x == inject_Q_CR (- x)%Q. |
| 80 |
Proof. |
| 81 |
intros x e1 e2; apply ball_refl. |
| 82 |
rewrite Qplus_0_r. |
| 83 |
apply (Qpos_nonneg (e1+e2)). |
| 84 |
Qed. |
| 85 |
(* begin hide *) |
| 86 |
#[global] |
| 87 |
Hint Rewrite CRopp_Qopp : CRfast_compute. |
| 88 |
#[global] |
| 89 |
Hint Rewrite <- CRopp_Qopp : toCRring. |
| 90 |
(* end hide *) |
| 91 |
Lemma CRminus_Qminus : forall (x y:Q), inject_Q_CR x - inject_Q_CR y == inject_Q_CR (x - y)%Q. |
| 92 |
Proof. |
| 93 |
intros x y e1 e2; apply ball_refl. |
| 94 |
rewrite Qplus_0_r. |
| 95 |
apply (Qpos_nonneg (e1+e2)). |
| 96 |
Qed. |
| 97 |
(* begin hide *) |
| 98 |
#[global] |
| 99 |
Hint Rewrite <- CRminus_Qminus : toCRring. |
| 100 |
(* end hide *) |
| 101 |
Lemma CRmult_Qmult : forall (x y:Q), inject_Q_CR x * inject_Q_CR y == inject_Q_CR (x * y)%Q. |
| 102 |
Proof. |
| 103 |
intros x y. |
| 104 |
rewrite -> CRmult_scale. |
| 105 |
intros e1 e2; apply ball_refl. |
| 106 |
rewrite Qplus_0_r. |
| 107 |
apply (Qpos_nonneg (e1+e2)). |
| 108 |
Qed. |
| 109 |
(* begin hide *) |
| 110 |
#[global] |
| 111 |
Hint Rewrite <- CRmult_Qmult : toCRring. |
| 112 |
(* end hide *) |
| 113 |
Lemma Qap_CRap : forall (x y:Q), (~(x==y))%Q -> (' x)><(' y). |
| 114 |
Proof. |
| 115 |
intros x y Hxy. |
| 116 |
destruct (Q_dec x y) as [[H|H]|H]; try contradiction; |
| 117 |
destruct (Qpos_sub _ _ H) as [c Hc];[left|right]; exists c; abstract (rewrite -> CRminus_Qminus; |
| 118 |
rewrite -> CRle_Qle; rewrite -> Hc; ring_simplify; apply Qle_refl). |
| 119 |
Defined. |
| 120 |
|
| 121 |
Lemma CRinv_Qinv : forall (x:Q) x_, CRinvT (inject_Q_CR x) x_ == inject_Q_CR (/x)%Q. |
| 122 |
Proof. |
| 123 |
intros x [[c x_]|[c x_]]; |
| 124 |
[change (' proj1_sig c <= 0 + - 'x)%CR in x_|change (' proj1_sig c <= ' x + - 0)%CR in x_]; unfold CRinvT; |
| 125 |
rewrite -> CRopp_Qopp, CRplus_Qplus, CRle_Qle in x_; try rewrite -> CRopp_Qopp; |
| 126 |
rewrite -> (@CRinv_pos_Qinv c). |
| 127 |
rewrite -> CRopp_Qopp. |
| 128 |
rewrite -> CReq_Qeq. |
| 129 |
assert (~x==0)%Q. |
| 130 |
intros H. |
| 131 |
rewrite -> H in x_. |
| 132 |
apply (Qle_not_lt _ _ x_). |
| 133 |
apply Qpos_ispos. |
| 134 |
field. |
| 135 |
intros X; apply H. |
| 136 |
assumption. |
| 137 |
rewrite -> Qplus_0_l in x_. |
| 138 |
assumption. |
| 139 |
reflexivity. |
| 140 |
rewrite -> Qplus_0_r in x_. |
| 141 |
assumption. |
| 142 |
Qed. |
| 143 |
|
| 144 |
(* begin hide *) |
| 145 |
#[global] |
| 146 |
Hint Rewrite <- CRinv_Qinv : toCRring. |
| 147 |
(* end hide *) |
| 148 |
(** |
| 149 |
** Ring |
| 150 |
CR forms a ring for the ring tactic. |
| 151 |
*) |
| 152 |
|
| 153 |
Lemma CRplus_0_l (x: CR): (0 + x == x)%CR. |
| 154 |
Proof. |
| 155 |
intros e1 e2. destruct x; simpl. |
| 156 |
unfold Cap_raw; simpl. |
| 157 |
rewrite Qplus_0_r. |
| 158 |
rewrite Qplus_0_l. |
| 159 |
assert ((1#2)*`e1 + `e2 <= `e1 + `e2)%Q. |
| 160 |
{ apply Qplus_le_l. rewrite <- (Qmult_1_l (`e1)) at 2. |
| 161 |
apply Qmult_le_r. apply Qpos_ispos. discriminate. } |
| 162 |
apply (ball_weak_le Q_as_MetricSpace _ _ H), |
| 163 |
(regFun_prf ((1#2)*e1)%Qpos e2). |
| 164 |
Qed. |
| 165 |
|
| 166 |
(* Lifting of Qplus_comm *) |
| 167 |
Lemma CRplus_comm (x y: CR): x + y == y + x. |
| 168 |
Proof. |
| 169 |
rewrite CRplus_uncurry_eq. |
| 170 |
rewrite CRplus_uncurry_eq. |
| 171 |
apply Cmap2_comm. |
| 172 |
intros a b. apply Qball_0, Qplus_comm. |
| 173 |
Qed. |
| 174 |
|
| 175 |
Lemma CRplus_assoc (x y z: CR): x + (y + z) == (x + y) + z. |
| 176 |
Proof. |
| 177 |
intros. |
| 178 |
intros e1 e2. destruct x,y,z; simpl; unfold Cap_raw; simpl. |
| 179 |
unfold Cap_raw; simpl. |
| 180 |
apply AbsSmall_Qabs. |
| 181 |
setoid_replace (approximate ((1 # 2) * e1)%Qpos + |
| 182 |
(approximate0 ((1 # 2) * ((1 # 2) * e1))%Qpos + |
| 183 |
approximate1 ((1 # 2) * ((1 # 2) * e1))%Qpos) - |
| 184 |
(approximate ((1 # 2) * ((1 # 2) * e2))%Qpos + |
| 185 |
approximate0 ((1 # 2) * ((1 # 2) * e2))%Qpos + |
| 186 |
approximate1 ((1 # 2) * e2)%Qpos))%Q |
| 187 |
with ((approximate ((1 # 2) * e1)%Qpos |
| 188 |
- approximate ((1 # 2) * ((1 # 2) * e2))%Qpos) |
| 189 |
+ (approximate0 ((1 # 2) * ((1 # 2) * e1))%Qpos |
| 190 |
- approximate0 ((1 # 2) * ((1 # 2) * e2))%Qpos) |
| 191 |
+ (approximate1 ((1 # 2) * ((1 # 2) * e1))%Qpos |
| 192 |
- approximate1 ((1 # 2) * e2)%Qpos))%Q |
| 193 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 194 |
rewrite Qplus_0_r. |
| 195 |
setoid_replace (` e1 + ` e2)%Q |
| 196 |
with (((1#2)* ` e1 + (1#2)*((1#2) * `e2)) |
| 197 |
+ ((1#2)*((1#2)* `e1) + (1#2)*((1#2)*`e2)) |
| 198 |
+ ((1#2)*((1#2)* `e1) + (1#2)* ` e2))%Q |
| 199 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 200 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 201 |
apply Qplus_le_compat. |
| 202 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 203 |
apply Qplus_le_compat. |
| 204 |
- apply AbsSmall_Qabs. |
| 205 |
apply (regFun_prf ((1#2)*e1)%Qpos ((1#2)*((1#2)*e2))%Qpos). |
| 206 |
- apply AbsSmall_Qabs. |
| 207 |
apply (regFun_prf0 ((1#2)*((1#2)*e1))%Qpos ((1#2)*((1#2)*e2))%Qpos). |
| 208 |
- apply AbsSmall_Qabs. |
| 209 |
apply (regFun_prf1 ((1#2)*((1#2)*e1))%Qpos ((1#2)*e2)%Qpos). |
| 210 |
Qed. |
| 211 |
|
| 212 |
Lemma CRmult_1_l : forall (x: CR), 1 * x == x. |
| 213 |
Proof. |
| 214 |
intro x. rewrite CRmult_scale. |
| 215 |
intros e1 e2. destruct x; simpl. |
| 216 |
rewrite Qplus_0_r. |
| 217 |
rewrite Qmult_1_l. |
| 218 |
rewrite <- (Qmult_1_l (`e1)). |
| 219 |
apply (regFun_prf ((1#1)*e1)%Qpos e2). |
| 220 |
Qed. |
| 221 |
|
| 222 |
(* Lift Qmult_comm. *) |
| 223 |
Lemma CRmult_comm_bounded (x y: CR) (b:Qpos) : |
| 224 |
(' (- ` b)%Q <= x)%CR |
| 225 |
-> (x <= 'proj1_sig b)%CR |
| 226 |
-> (' (- ` b)%Q <= y)%CR |
| 227 |
-> (y <= 'proj1_sig b)%CR |
| 228 |
-> CRmult_bounded b x y == CRmult_bounded b y x. |
| 229 |
Proof. |
| 230 |
intros. rewrite CRmult_uncurry_eq, CRmult_uncurry_eq; try assumption. |
| 231 |
apply Cmap2_comm. |
| 232 |
intros. apply Qball_0, Qmult_comm. |
| 233 |
Qed. |
| 234 |
|
| 235 |
Lemma CRmult_comm (x y: CR): x * y == y * x. |
| 236 |
Proof. |
| 237 |
pose (Qpos_max (CR_b (1#1) x) (CR_b (1#1) y)) as b. |
| 238 |
assert (' (- ` b)%Q <= x) as xlower. |
| 239 |
{ apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) x))%Q)). |
| 240 |
2: apply (CR_b_lowerBound _ _). |
| 241 |
apply CRle_Qle. apply Qopp_le_compat, Qpos_max_ub_l. } |
| 242 |
assert (x <= '(` b)%Q) as xupper. |
| 243 |
{ apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) x))) _ (CR_b_upperBound _ _)). |
| 244 |
apply CRle_Qle. apply Qpos_max_ub_l. } |
| 245 |
assert (' (- ` b)%Q <= y) as ylower. |
| 246 |
{ apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) y))%Q)). |
| 247 |
2: apply (CR_b_lowerBound _ _). |
| 248 |
apply CRle_Qle. apply Qopp_le_compat, Qpos_max_ub_r. } |
| 249 |
assert (y <= '(` b)%Q) as yupper. |
| 250 |
{ apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) y))) _ (CR_b_upperBound _ _)). |
| 251 |
apply CRle_Qle. apply Qpos_max_ub_r. } |
| 252 |
rewrite <- (@CRmult_bounded_mult b x y). |
| 253 |
2: exact ylower. 2: exact yupper. |
| 254 |
rewrite <- (@CRmult_bounded_mult b y x). |
| 255 |
2: exact xlower. 2: exact xupper. |
| 256 |
- apply CRmult_comm_bounded. |
| 257 |
+ exact xlower. |
| 258 |
+ exact xupper. |
| 259 |
+ exact ylower. |
| 260 |
+ exact yupper. |
| 261 |
Qed. |
| 262 |
|
| 263 |
Lemma CRmult_1_r : forall (x: CR), x * 1 == x. |
| 264 |
Proof. |
| 265 |
intro x. rewrite CRmult_comm. apply CRmult_1_l. |
| 266 |
Qed. |
| 267 |
|
| 268 |
Lemma CRmult_assoc (x y z : CR): (x * y) * z == x * (y * z). |
| 269 |
Proof. |
| 270 |
pose ((CR_b (1#1) x + (1#1)) * (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos |
| 271 |
as b. |
| 272 |
assert (' (- ` b)%Q <= z) as zlower. |
| 273 |
{ apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) z))%Q)). |
| 274 |
2: apply CR_b_lowerBound. |
| 275 |
apply CRle_Qle. apply Qopp_le_compat. |
| 276 |
apply (Qle_trans _ (` (CR_b (1#1)%Qpos z) + (1#1))). |
| 277 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 278 |
apply CRmult_assoc_zfactor_le. } |
| 279 |
assert (z <= ' (` b)%Q) as zupper. |
| 280 |
{ apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) z))%Q)). |
| 281 |
apply CR_b_upperBound. |
| 282 |
apply CRle_Qle. |
| 283 |
apply (Qle_trans _ (` (CR_b (1#1)%Qpos z) + (1#1))). |
| 284 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 285 |
apply CRmult_assoc_zfactor_le. } |
| 286 |
rewrite <- (@CRmult_bounded_mult b x y), <- (@CRmult_bounded_mult b). |
| 287 |
2: exact zlower. 2: exact zupper. |
| 288 |
rewrite <- (@CRmult_bounded_mult b), <- (@CRmult_bounded_mult b). |
| 289 |
apply CRmult_assoc_bounded. |
| 290 |
- exact zlower. |
| 291 |
- exact zupper. |
| 292 |
- apply (@CRle_trans _ ('(-proj1_sig ((CR_b (1#1) y) * CR_b (1#1) z)%Qpos)%Q)). |
| 293 |
2: apply CR_b_lowerBound_2. |
| 294 |
apply CRle_Qle, Qopp_le_compat. |
| 295 |
apply (Qle_trans _ ((1#1)*proj1_sig (CR_b (1#1) y + (1#1))%Qpos |
| 296 |
* proj1_sig ((CR_b (1#1) z) + (1#1))%Qpos)). |
| 297 |
rewrite Qmult_1_l. |
| 298 |
apply (Qpos_mult_le_compat (CR_b (1#1) y) (CR_b (1#1) z)). |
| 299 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 300 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 301 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 302 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 303 |
rewrite <- Qplus_0_l at 1. apply Qplus_le_l. apply Qpos_nonneg. |
| 304 |
- apply (CRle_trans (CR_b_upperBound_2 y z)). |
| 305 |
apply CRle_Qle. |
| 306 |
apply (Qle_trans _ ((1#1)*proj1_sig (CR_b (1#1) y + (1#1))%Qpos |
| 307 |
* proj1_sig ((CR_b (1#1) z) + (1#1))%Qpos)). |
| 308 |
rewrite Qmult_1_l. |
| 309 |
apply (Qpos_mult_le_compat (CR_b (1#1) y) (CR_b (1#1) z)). |
| 310 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 311 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 312 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 313 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 314 |
rewrite <- Qplus_0_l at 1. apply Qplus_le_l. apply Qpos_nonneg. |
| 315 |
- apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) y))%Q)). |
| 316 |
2: apply CR_b_lowerBound. |
| 317 |
apply CRle_Qle. apply Qopp_le_compat. |
| 318 |
apply (Qle_trans _ (` (CR_b (1#1)%Qpos y) + (1#1))). |
| 319 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 320 |
apply CRmult_assoc_yfactor_le. |
| 321 |
- apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) y))%Q)). |
| 322 |
apply CR_b_upperBound. |
| 323 |
apply CRle_Qle. |
| 324 |
apply (Qle_trans _ (` (CR_b (1#1)%Qpos y) + (1#1))). |
| 325 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 326 |
apply CRmult_assoc_yfactor_le. |
| 327 |
Qed. |
| 328 |
|
| 329 |
Lemma CRmult_plus_distr_r : ∀ x y z : CR, |
| 330 |
((x + y) * z == x * z + y * z). |
| 331 |
Proof. |
| 332 |
intros x y z. |
| 333 |
pose ((CR_b (1#1) x + CR_b (1#1) y + CR_b (1#1) z))%Qpos as b. |
| 334 |
assert (forall u v, QboundAbs u v <= `u)%Q as qbound_bound. |
| 335 |
{ intros. apply Qmax_lub. |
| 336 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 337 |
apply Qpos_nonneg. apply Qmin_lb_l. } |
| 338 |
assert ( ' (- ` b)%Q <= x)%CR as xlower. |
| 339 |
{ apply (@CRle_trans _ ('(-(proj1_sig (CR_b (1#1) x)))%Q)). |
| 340 |
2: apply CR_b_lowerBound. |
| 341 |
apply CRle_Qle, Qopp_le_compat. |
| 342 |
rewrite <- Qplus_0_r. simpl. |
| 343 |
rewrite <- (Qplus_assoc (Qabs (approximate x (Qpos2QposInf (1#1))) + 1)). |
| 344 |
apply Qplus_le_r. |
| 345 |
apply (Qpos_nonneg (CR_b (1#1) y + CR_b (1#1) z)). } |
| 346 |
assert (x <= ' (` b)%Q)%CR as xupper. |
| 347 |
{ apply (@CRle_trans _ ('((proj1_sig (CR_b (1#1) x)))%Q)). |
| 348 |
apply CR_b_upperBound. |
| 349 |
apply CRle_Qle. |
| 350 |
rewrite <- Qplus_0_r. simpl. |
| 351 |
rewrite <- (Qplus_assoc (Qabs (approximate x (Qpos2QposInf (1#1))) + 1)). |
| 352 |
apply Qplus_le_r. |
| 353 |
apply (Qpos_nonneg (CR_b (1#1) y + CR_b (1#1) z)). } |
| 354 |
|
| 355 |
assert ( ' (- ` b)%Q <= y)%CR as ylower. |
| 356 |
{ apply (@CRle_trans _ ('(-(proj1_sig (CR_b (1#1) y)))%Q)). |
| 357 |
2: apply CR_b_lowerBound. |
| 358 |
apply CRle_Qle, Qopp_le_compat. |
| 359 |
rewrite <- Qplus_0_l. simpl. |
| 360 |
rewrite <- Qplus_assoc. apply Qplus_le_compat. |
| 361 |
apply (Qpos_nonneg ((CR_b (1#1) x))). |
| 362 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. |
| 363 |
apply (Qpos_nonneg ((CR_b (1#1) z))). } |
| 364 |
assert (y <= ' (` b)%Q)%CR as yupper. |
| 365 |
{ apply (@CRle_trans _ ('((proj1_sig (CR_b (1#1) y)))%Q)). |
| 366 |
apply CR_b_upperBound. |
| 367 |
apply CRle_Qle. |
| 368 |
rewrite <- Qplus_0_l. simpl. |
| 369 |
rewrite <- Qplus_assoc. apply Qplus_le_compat. |
| 370 |
apply (Qpos_nonneg ((CR_b (1#1) x))). |
| 371 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. |
| 372 |
apply (Qpos_nonneg ((CR_b (1#1) z))). } |
| 373 |
|
| 374 |
rewrite <- (CRboundAbs_Eq _ (CR_b_lowerBound (1#1) y) (CR_b_upperBound (1#1) y)). |
| 375 |
rewrite <- (CRboundAbs_Eq _ (CR_b_lowerBound (1#1) x) (CR_b_upperBound (1#1) x)). |
| 376 |
assert ( ' (- ` b)%Q <= z)%CR as zlower. |
| 377 |
{ apply (@CRle_trans _ ('(-(proj1_sig (CR_b (1#1) z)))%Q)). |
| 378 |
2: apply CR_b_lowerBound. |
| 379 |
apply CRle_Qle, Qopp_le_compat. |
| 380 |
rewrite <- Qplus_0_l. apply Qplus_le_compat. |
| 381 |
apply Qpos_nonneg. apply Qle_refl. } |
| 382 |
assert (z <= ' (` b)%Q)%CR as zupper. |
| 383 |
{ apply (@CRle_trans _ ('((proj1_sig (CR_b (1#1) z)))%Q)). |
| 384 |
apply CR_b_upperBound. |
| 385 |
apply CRle_Qle. |
| 386 |
rewrite <- Qplus_0_l. apply Qplus_le_compat. |
| 387 |
apply Qpos_nonneg. apply Qle_refl. } |
| 388 |
rewrite <- (@CRmult_bounded_mult b (CRboundAbs _ x) z). |
| 389 |
2: exact zlower. 2: exact zupper. |
| 390 |
rewrite <- (@CRmult_bounded_mult b (CRboundAbs _ y) z). |
| 391 |
2: exact zlower. 2: exact zupper. |
| 392 |
rewrite <- (@CRmult_bounded_mult b). |
| 393 |
2: exact zlower. 2: exact zupper. |
| 394 |
rewrite (@CRmult_uncurry_eq b (CRboundAbs _ x) z). |
| 395 |
2: rewrite (CRboundAbs_Eq _ (CR_b_lowerBound (1#1) x) (CR_b_upperBound (1#1) x)) |
| 396 |
; exact xlower. |
| 397 |
2: rewrite (CRboundAbs_Eq _ (CR_b_lowerBound (1#1) x) (CR_b_upperBound (1#1) x)) |
| 398 |
; exact xupper. |
| 399 |
rewrite (@CRmult_uncurry_eq b (CRboundAbs _ y) z). |
| 400 |
2: rewrite (CRboundAbs_Eq _ (CR_b_lowerBound (1#1) y) (CR_b_upperBound (1#1) y)) |
| 401 |
; exact ylower. |
| 402 |
2: rewrite (CRboundAbs_Eq _ (CR_b_lowerBound (1#1) y) (CR_b_upperBound (1#1) y)) |
| 403 |
; exact yupper. |
| 404 |
rewrite CRmult_uncurry_eq. |
| 405 |
intros e1 e2. |
| 406 |
rewrite Qplus_0_r. |
| 407 |
change (Qball (`e1 + `e2) |
| 408 |
(QboundAbs b |
| 409 |
(approximate (CRboundAbs (CR_b (1#1) x) x) |
| 410 |
((1 # 2) * ((1 # 2) * e1 * Qpos_inv b))%Qpos + |
| 411 |
approximate (CRboundAbs (CR_b (1#1) y) y) |
| 412 |
((1 # 2) * ((1 # 2) * e1 * Qpos_inv b))%Qpos)%Q |
| 413 |
* QboundAbs b (approximate z (Qmult_modulus b ((1 # 2) * e1)))) |
| 414 |
(QboundAbs b (approximate (CRboundAbs (CR_b (1#1) x) x) |
| 415 |
(Qmult_modulus b ((1 # 2) * ((1 # 2) * e2)))) |
| 416 |
* QboundAbs b (approximate z |
| 417 |
(Qmult_modulus b ((1 # 2) * ((1 # 2) * e2)))) |
| 418 |
+ QboundAbs b (approximate (CRboundAbs (CR_b (1#1) y) y) |
| 419 |
(Qmult_modulus b ((1 # 2) * ((1 # 2) * e2)))) |
| 420 |
* QboundAbs b (approximate z |
| 421 |
(Qmult_modulus b ((1 # 2) * ((1 # 2) * e2)))))). |
| 422 |
rewrite <- Qmult_plus_distr_l. |
| 423 |
unfold Qmult_modulus. |
| 424 |
apply AbsSmall_Qabs. |
| 425 |
assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs i * Qabs(j-l) + Qabs(i-k)*Qabs l)%Q |
| 426 |
as multMaj. |
| 427 |
{ intros. |
| 428 |
setoid_replace (i*j-k*l)%Q with (i*(j-l)+ (i-k)*l)%Q |
| 429 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 430 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 431 |
rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. } |
| 432 |
apply (Qle_trans _ ((1#2)*`e1 + (1#2)*`e2 +((1#2)*`e1 +(1#2)*`e2))). |
| 433 |
2: ring_simplify; apply Qle_refl. |
| 434 |
apply (Qle_trans _ _ _ (multMaj _ _ _ _)). clear multMaj. |
| 435 |
apply Qplus_le_compat. |
| 436 |
- apply (Qle_trans _ (`b * Qabs |
| 437 |
(QboundAbs b (approximate z ((1 # 2) * e1 * Qpos_inv b)%Qpos) - |
| 438 |
QboundAbs b |
| 439 |
(approximate z |
| 440 |
((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos)))). |
| 441 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 442 |
rewrite QboundAbs_abs. apply Qmin_lb_r. |
| 443 |
rewrite Qmult_comm. |
| 444 |
apply (Qle_trans _ (Qabs |
| 445 |
(approximate z ((1 # 2) * e1 * Qpos_inv b)%Qpos - |
| 446 |
approximate z |
| 447 |
((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos) * ` b)). |
| 448 |
apply Qmult_le_compat_r. 2: apply Qpos_nonneg. |
| 449 |
apply QboundAbs_contract. |
| 450 |
apply (Qle_trans _ (((1#2)*`e1 / `b + (1#2)*`e2 / `b) * `b)). |
| 451 |
apply Qmult_le_r. apply Qpos_ispos. |
| 452 |
pose proof (regFun_prf z ((1 # 2) * e1 * Qpos_inv b)%Qpos |
| 453 |
((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos) as H4. |
| 454 |
apply AbsSmall_Qabs in H4. |
| 455 |
apply (Qle_trans _ _ _ H4). |
| 456 |
apply Qplus_le_r. simpl. |
| 457 |
rewrite Qmult_assoc. apply Qmult_le_r. |
| 458 |
apply Qinv_lt_0_compat, (Qpos_ispos b). |
| 459 |
apply Qmult_le_r. apply Qpos_ispos. discriminate. |
| 460 |
rewrite Qmult_comm. |
| 461 |
rewrite Qmult_plus_distr_r. |
| 462 |
apply Qplus_le_compat. |
| 463 |
unfold Qdiv. rewrite Qmult_assoc. |
| 464 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 465 |
rewrite Qmult_comm. apply Qle_refl. |
| 466 |
unfold Qdiv. rewrite Qmult_assoc. |
| 467 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 468 |
rewrite Qmult_comm. apply Qle_refl. |
| 469 |
- assert (forall u, Qabs u <= `b -> QboundAbs b u == u)%Q. |
| 470 |
{ intros u H. apply QboundAbs_elim. |
| 471 |
intros. apply Qle_antisym. exact H0. |
| 472 |
apply (Qle_trans _ (Qabs u)). apply Qle_Qabs. exact H. |
| 473 |
intros. apply Qle_antisym. 2: exact H0. |
| 474 |
rewrite <- (Qopp_involutive u). apply Qopp_le_compat. |
| 475 |
rewrite <- Qabs_opp in H. |
| 476 |
exact (Qle_trans _ _ _ (Qle_Qabs _) H). |
| 477 |
intros. reflexivity. } |
| 478 |
rewrite H, H, H; clear H. |
| 479 |
rewrite QboundAbs_abs. |
| 480 |
rewrite Qmult_comm. |
| 481 |
apply (Qle_trans _ (` b * Qabs |
| 482 |
(approximate (CRboundAbs (CR_b (1#1) x) x) |
| 483 |
((1 # 2) * ((1 # 2) * e1 * Qpos_inv b))%Qpos + |
| 484 |
approximate (CRboundAbs (CR_b (1#1) y) y) |
| 485 |
((1 # 2) * ((1 # 2) * e1 * Qpos_inv b))%Qpos - |
| 486 |
(approximate (CRboundAbs (CR_b (1#1) x) x) |
| 487 |
((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos + |
| 488 |
approximate (CRboundAbs (CR_b (1#1) y) y) |
| 489 |
((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos)))). |
| 490 |
+ apply Qmult_le_compat_r. 2: apply Qabs_nonneg. apply Qmin_lb_r. |
| 491 |
+ rewrite Qmult_comm. |
| 492 |
apply (Qle_trans _ (((1#2)*`e1 / `b + (1#2)*`e2 / `b) * `b)). |
| 493 |
apply Qmult_le_r. apply Qpos_ispos. |
| 494 |
assert (forall a b c d, a + b - (c+d) == a - c + (b-d))%Q by (intros; ring). |
| 495 |
rewrite H; clear H. |
| 496 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 497 |
apply (Qle_trans _ (((1#2) * ((1 # 2) * ` e1 / ` b) + (1#2) * ((1 # 2) * ` e2) / ` b) |
| 498 |
+ ((1#2) * ((1 # 2) * ` e1 / ` b) + (1#2) * ((1 # 2) * ` e2) / ` b))). |
| 499 |
apply Qplus_le_compat. |
| 500 |
pose proof (regFun_prf (CRboundAbs (CR_b (1#1) x) x) |
| 501 |
((1 # 2) * ((1 # 2) * e1 * Qpos_inv b))%Qpos |
| 502 |
((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos) as H4. |
| 503 |
apply AbsSmall_Qabs in H4. |
| 504 |
apply (Qle_trans _ _ _ H4). clear H4. apply Qle_refl. |
| 505 |
pose proof (regFun_prf (CRboundAbs (CR_b (1#1) y) y) |
| 506 |
((1 # 2) * ((1 # 2) * e1 * Qpos_inv b))%Qpos |
| 507 |
((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos) as H4. |
| 508 |
apply AbsSmall_Qabs in H4. |
| 509 |
apply (Qle_trans _ _ _ H4). clear H4. apply Qle_refl. |
| 510 |
unfold Qdiv. ring_simplify. |
| 511 |
setoid_replace (8#16)%Q with (1#2)%Q by reflexivity. apply Qle_refl. |
| 512 |
rewrite Qmult_comm, Qmult_plus_distr_r. |
| 513 |
apply Qplus_le_compat. |
| 514 |
unfold Qdiv. rewrite Qmult_assoc. |
| 515 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 516 |
rewrite Qmult_comm. apply Qle_refl. |
| 517 |
unfold Qdiv. rewrite Qmult_assoc. |
| 518 |
apply Qle_shift_div_r. apply Qpos_ispos. |
| 519 |
rewrite Qmult_comm. apply Qle_refl. |
| 520 |
+ change (Qabs (QboundAbs (CR_b (1#1) y) (approximate y ((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos)) |
| 521 |
<= `b)%Q. |
| 522 |
rewrite QboundAbs_abs. |
| 523 |
apply (Qle_trans _ _ _ (Qmin_lb_r _ _)). |
| 524 |
rewrite <- Qplus_0_r. apply Qplus_le_compat. |
| 525 |
2: apply Qpos_nonneg. |
| 526 |
rewrite <- Qplus_0_l. apply Qplus_le_l. |
| 527 |
apply Qpos_nonneg. |
| 528 |
+ change (Qabs (QboundAbs (CR_b (1#1) x) (approximate x ((1 # 2) * ((1 # 2) * e2) * Qpos_inv b)%Qpos)) |
| 529 |
<= `b)%Q. |
| 530 |
rewrite QboundAbs_abs. |
| 531 |
apply (Qle_trans _ _ _ (Qmin_lb_r _ _)). |
| 532 |
rewrite <- Qplus_0_r. apply Qplus_le_compat. |
| 533 |
2: apply Qpos_nonneg. |
| 534 |
rewrite <- Qplus_0_r. apply Qplus_le_r. |
| 535 |
apply Qpos_nonneg. |
| 536 |
+ apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 537 |
setoid_replace (proj1_sig b) with |
| 538 |
(proj1_sig (CR_b (1#1) x) + (proj1_sig (CR_b (1#1) y) + proj1_sig (CR_b (1#1) z)))%Q |
| 539 |
by (simpl; unfold equiv, stdlib_rationals.Q_eq; ring). |
| 540 |
apply Qplus_le_compat. |
| 541 |
change (Qabs (QboundAbs (CR_b (1#1) x) |
| 542 |
(approximate x ((1 # 2) * ((1 # 2) * e1 * Qpos_inv b))%Qpos)) <= proj1_sig (CR_b (1#1) x))%Q. |
| 543 |
rewrite QboundAbs_abs. |
| 544 |
apply Qmin_lb_r. |
| 545 |
change (Qabs (QboundAbs (CR_b (1#1) y) |
| 546 |
(approximate y ((1 # 2) * ((1 # 2) * e1 * Qpos_inv b))%Qpos)) <= proj1_sig (CR_b (1#1) y) + proj1_sig (CR_b (1#1) z))%Q. |
| 547 |
rewrite QboundAbs_abs. |
| 548 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1) y) + 0)). |
| 549 |
rewrite Qplus_0_r. apply Qmin_lb_r. |
| 550 |
apply Qplus_le_r. apply Qpos_nonneg. |
| 551 |
- simpl. intro e. simpl. |
| 552 |
unfold Cap_raw; simpl. |
| 553 |
unfold Cap_raw; simpl. |
| 554 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 555 |
rewrite <- Qle_minus_iff. |
| 556 |
apply (Qle_trans _ (- (Qabs (approximate x (Qpos2QposInf (1#1))) + 1) |
| 557 |
- (Qabs (approximate y (Qpos2QposInf (1#1))) + 1))). |
| 558 |
2: apply Qplus_le_compat; apply Qmax_ub_l. |
| 559 |
setoid_replace (- (Qabs (approximate x (Qpos2QposInf (1#1))) + 1) - |
| 560 |
(Qabs (approximate y (Qpos2QposInf (1#1))) + 1))%Q |
| 561 |
with (- ((Qabs (approximate x (Qpos2QposInf (1#1))) + 1) + |
| 562 |
(Qabs (approximate y (Qpos2QposInf (1#1))) + 1)))%Q |
| 563 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 564 |
apply Qopp_le_compat. |
| 565 |
rewrite <- Qplus_0_r. apply Qplus_le_r. |
| 566 |
apply (Qpos_nonneg (CR_b (1#1) z)). |
| 567 |
- simpl. intro e. simpl. |
| 568 |
unfold Cap_raw; simpl. |
| 569 |
unfold Cap_raw; simpl. |
| 570 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 571 |
rewrite <- Qle_minus_iff. |
| 572 |
apply (Qle_trans _ (Qabs (approximate x (Qpos2QposInf (1#1))) + 1 |
| 573 |
+ (Qabs (approximate y (Qpos2QposInf (1#1))) + 1))). |
| 574 |
apply Qplus_le_compat. |
| 575 |
apply (qbound_bound (CR_b (1#1) x)). |
| 576 |
apply (qbound_bound (CR_b (1#1) y)). |
| 577 |
rewrite <- Qplus_0_r. apply Qplus_le_r. |
| 578 |
apply (Qpos_nonneg (CR_b (1#1) z)). |
| 579 |
Qed. |
| 580 |
|
| 581 |
Lemma CRmult_plus_distr_l : ∀ x y z : CR, |
| 582 |
(z * (x + y) == z * x + z * y)%CR. |
| 583 |
Proof. |
| 584 |
intros. |
| 585 |
rewrite CRmult_comm, CRmult_plus_distr_r. |
| 586 |
rewrite (CRmult_comm z). |
| 587 |
rewrite (CRmult_comm z). |
| 588 |
reflexivity. |
| 589 |
Qed. |
| 590 |
|
| 591 |
Lemma CR_ring_theory : |
| 592 |
@ring_theory CR 0 1 (ucFun2 CRplus_uc) CRmult |
| 593 |
(fun (x y:CR) => (x + - y)) CRopp (@msp_eq CR). |
| 594 |
Proof. |
| 595 |
split. |
| 596 |
- exact CRplus_0_l. |
| 597 |
- exact CRplus_comm. |
| 598 |
- exact CRplus_assoc. |
| 599 |
- exact CRmult_1_l. |
| 600 |
- exact CRmult_comm. |
| 601 |
- intros. symmetry. apply CRmult_assoc. |
| 602 |
- exact CRmult_plus_distr_r. |
| 603 |
- reflexivity. |
| 604 |
- intros x e1 e2. simpl. |
| 605 |
unfold Cap_raw;simpl. rewrite Qplus_0_r. |
| 606 |
rewrite Qplus_opp_r. |
| 607 |
apply Qball_Reflexive. apply (Qpos_nonneg (e1+e2)). |
| 608 |
Qed. |
| 609 |
|
| 610 |
Lemma CR_Q_ring_morphism : |
| 611 |
ring_morph 0%CR 1%CR (ucFun2 CRplus_uc) CRmult |
| 612 |
(fun x y => (x + - y)) CRopp (@msp_eq CR) |
| 613 |
(0%Q) (1%Q) Qplus Qmult Qminus Qopp Qeq_bool (inject_Q_CR). |
| 614 |
Proof. |
| 615 |
split; try reflexivity. |
| 616 |
apply CRplus_Qplus. |
| 617 |
apply CRminus_Qminus. |
| 618 |
intros x y; rewrite -> CRmult_Qmult; reflexivity. |
| 619 |
apply CRopp_Qopp. |
| 620 |
intros x y H. |
| 621 |
rewrite -> CReq_Qeq. |
| 622 |
apply Qeq_bool_eq. |
| 623 |
assumption. |
| 624 |
Qed. |
| 625 |
|
| 626 |
Ltac CRcst t := |
| 627 |
match t with |
| 628 |
| (inject_Q_CR ?z) => Qcst z |
| 629 |
| _ => NotConstant |
| 630 |
end. |
| 631 |
|
| 632 |
Ltac CRring_pre := autorewrite with toCRring. |
| 633 |
|
| 634 |
Lemma CR_ring_eq_ext : ring_eq_ext (ucFun2 CRplus_uc) CRmult CRopp (@msp_eq CR). |
| 635 |
Proof. |
| 636 |
split. |
| 637 |
rapply ucFun2_wd. |
| 638 |
rapply CRmult_wd. |
| 639 |
rapply uc_wd. |
| 640 |
Qed. |
| 641 |
|
| 642 |
Add Ring CR_ring : CR_ring_theory (morphism CR_Q_ring_morphism, setoid (@msp_Setoid CR) CR_ring_eq_ext, constants [CRcst], preprocess [CRring_pre]). |
| 643 |
|
| 644 |
(** Relationship between strict and nonstrict positivity *) |
| 645 |
Lemma CRpos_nonNeg : forall x, CRpos x -> CRnonNeg x. |
| 646 |
Proof. |
| 647 |
intros x [c Hx]. |
| 648 |
cut (0 <= x)%CR. |
| 649 |
unfold CRle. |
| 650 |
intros H. |
| 651 |
assert (x == x - 0)%CR. ring. rewrite -> H0. |
| 652 |
assumption. |
| 653 |
apply CRle_trans with (' proj1_sig c)%CR; auto with *. |
| 654 |
rewrite -> CRle_Qle; auto with *. |
| 655 |
Qed. |
| 656 |
|
| 657 |
Lemma CRneg_nonPos : forall x, CRneg x -> CRnonPos x. |
| 658 |
Proof. |
| 659 |
intros x [c Hx]. |
| 660 |
cut (x <= 0)%CR. |
| 661 |
unfold CRle. |
| 662 |
intros H. |
| 663 |
assert (0 - x == -x)%CR. ring. rewrite -> H0 in H. |
| 664 |
intros e. |
| 665 |
rewrite <- (Qopp_involutive (proj1_sig e)). |
| 666 |
rewrite <- (Qopp_involutive (approximate x e)). |
| 667 |
apply Qopp_le_compat. |
| 668 |
apply H. |
| 669 |
apply CRle_trans with ('(-proj1_sig c)%Q)%CR; auto with *. |
| 670 |
rewrite -> CRle_Qle. |
| 671 |
apply (Qopp_le_compat 0). apply Qpos_nonneg. |
| 672 |
Qed. |
| 673 |
|
| 674 |
(** Now that we have ring-ness, we can easily prove some auxiliary utility lemmas about operations on CR. *) |
| 675 |
|
| 676 |
Ltac CRring_replace x y := |
| 677 |
assert (x == y) as CRring_replace_temp by ring; |
| 678 |
rewrite CRring_replace_temp; |
| 679 |
clear CRring_replace_temp. |
| 680 |
(* setoid_replace picks the st_eq equality which ring doesn't work for... *) |
| 681 |
|
| 682 |
Lemma CRle_opp (x y: CR): x <= y <-> - y <= - x. |
| 683 |
Proof. |
| 684 |
unfold CRle. intros. |
| 685 |
assert (- x - - y == y - x)%CR as E by ring. |
| 686 |
rewrite E. |
| 687 |
intuition. |
| 688 |
Qed. |
| 689 |
|
| 690 |
Lemma CRopp_opp (x: CR): (--x == x)%CR. |
| 691 |
Proof. intros. ring. Qed. |
| 692 |
|
| 693 |
Lemma CRplus_opp (x: CR): (x + - x == 0)%CR. |
| 694 |
Proof. intros. ring. Qed. |
| 695 |
|
| 696 |
Lemma CRopp_0: (-0 == 0)%CR. |
| 697 |
Proof. intros. ring. Qed. |
| 698 |
|
| 699 |
Lemma CRplus_0_r (x: CR): (x + 0 == x)%CR. |
| 700 |
Proof. intros. ring. Qed. |
| 701 |
|
| 702 |
Lemma CRmult_0_r (x: CR): (x * 0 == 0)%CR. |
| 703 |
Proof. intros. ring. Qed. |
| 704 |
|
| 705 |
Lemma CRopp_plus_distr : forall (r1 r2 : CR), |
| 706 |
- (r1 + r2) == - r1 + - r2. |
| 707 |
Proof. intros. ring. Qed. |
| 708 |
|
| 709 |
Lemma CRopp_mult_distr_r : forall (r1 r2 : CR), |
| 710 |
- (r1 * r2) == r1 * (- r2). |
| 711 |
Proof. intros. ring. Qed. |
| 712 |
|
| 713 |
Lemma CRopp_mult_distr_l : forall (r1 r2 : CR), |
| 714 |
- (r1 * r2) == (-r1) * r2. |
| 715 |
Proof. intros. ring. Qed. |
| 716 |
|
| 717 |
|
| 718 |
Lemma approximate_CRplus (x y: CR) (e: Qpos): |
| 719 |
approximate (x + y)%CR e = (approximate x ((1#2) * e)%Qpos + approximate y ((1#2) * e)%Qpos)%Q. |
| 720 |
Proof. reflexivity. Qed. |
| 721 |
|
| 722 |
Lemma CRnonNeg_CRplus (x y: CR): CRnonNeg x -> CRnonNeg y -> CRnonNeg (x + y)%CR. |
| 723 |
Proof. |
| 724 |
unfold CRnonNeg. intros. rewrite approximate_CRplus. |
| 725 |
setoid_replace (- proj1_sig e)%Q |
| 726 |
with (- proj1_sig ((1#2)*e)%Qpos + - proj1_sig ((1#2)*e)%Qpos)%Q |
| 727 |
by (simpl; unfold equiv, stdlib_rationals.Q_eq; ring). |
| 728 |
apply Qplus_le_compat; auto. |
| 729 |
Qed. |
| 730 |
|
| 731 |
Lemma CRplus_eq_l (z x y: CR): x == y <-> x + z == y + z. |
| 732 |
Proof with ring. |
| 733 |
split; intro E. rewrite E... |
| 734 |
rewrite <- (CRplus_0_r x), <- (CRplus_opp z), CRplus_assoc, E... |
| 735 |
Qed. |
| 736 |
|
| 737 |
Lemma CRplus_eq_r (z x y: CR): x == y <-> z + x == z + y. |
| 738 |
Proof. intros. do 2 rewrite (CRplus_comm z). apply CRplus_eq_l. Qed. |
| 739 |
|
| 740 |
Lemma CRplus_le_r (x y z: CR): x <= y <-> x+z <= y+z. |
| 741 |
Proof. |
| 742 |
unfold CRle. intros. |
| 743 |
assert (y + z - (x + z) == y - x)%CR as E by ring. rewrite E. |
| 744 |
intuition. |
| 745 |
Qed. |
| 746 |
|
| 747 |
Lemma CRplus_le_l x: forall y z : CR, x <= y <-> z + x <= z + y. |
| 748 |
Proof. |
| 749 |
intros. rewrite (CRplus_le_r x y z), (CRplus_comm x), (CRplus_comm y). reflexivity. |
| 750 |
Qed. |
| 751 |
|
| 752 |
Lemma CRplus_le_compat (x x' y y': CR): x <= x' -> y <= y' -> x+y <= x'+y'. |
| 753 |
Proof. |
| 754 |
unfold CRle. intros. |
| 755 |
assert (x' + y' - (x + y) == (x' - x) + (y' - y)) as E by ring. rewrite E. |
| 756 |
apply CRnonNeg_CRplus; assumption. |
| 757 |
Qed. |
| 758 |
|
| 759 |
Lemma CRplus_lt_r (x y z: CR): |
| 760 |
prod (x < y -> x+z < y+z) |
| 761 |
(x+z < y+z -> x < y). |
| 762 |
Proof. |
| 763 |
split. |
| 764 |
- intros. destruct H as [q H]. |
| 765 |
exists q. setoid_replace (y+z-(x+z))%CR with (y-x)%CR |
| 766 |
by (unfold equiv, msp_Equiv; ring). |
| 767 |
exact H. |
| 768 |
- intros. destruct H as [q H]. |
| 769 |
exists q. setoid_replace (y-x) with (y+z-(x+z)) |
| 770 |
by (unfold equiv, msp_Equiv; ring). |
| 771 |
exact H. |
| 772 |
Qed. |
| 773 |
|
| 774 |
Lemma CRplus_lt_l (x y z: CR): |
| 775 |
prod (x < y -> z+x < z+y) |
| 776 |
(z+x < z+y -> x < y). |
| 777 |
Proof. |
| 778 |
split. |
| 779 |
- intros. destruct H as [q H]. |
| 780 |
exists q. setoid_replace (z+y-(z+x)) with (y-x) |
| 781 |
by (unfold equiv, msp_Equiv; ring). |
| 782 |
exact H. |
| 783 |
- intros. destruct H as [q H]. |
| 784 |
exists q. setoid_replace (y-x) with (z+y-(z+x)) |
| 785 |
by (unfold equiv, msp_Equiv; ring). |
| 786 |
exact H. |
| 787 |
Qed. |
| 788 |
|
| 789 |
Lemma CRopp_lt_compat : forall x y : CR, |
| 790 |
x < y -> -y < -x. |
| 791 |
Proof. |
| 792 |
intros. apply (CRplus_lt_l _ _ (x+y)). |
| 793 |
assert (x == x+y-y)%CR by ring. |
| 794 |
assert (y == x+y-x)%CR by ring. |
| 795 |
apply (CRltT_wd H0 H1), H. |
| 796 |
Qed. |
| 797 |
|
| 798 |
Lemma CRopp_lt_cancel : forall x y : CR, |
| 799 |
-y < -x -> x < y. |
| 800 |
Proof. |
| 801 |
intros. apply (CRplus_lt_l _ _ (-x-y)). |
| 802 |
assert (-y == -x-y+x)%CR by ring. |
| 803 |
assert (-x == -x-y+y)%CR by ring. |
| 804 |
apply (CRltT_wd H0 H1), H. |
| 805 |
Qed. |
| 806 |
|
| 807 |
Lemma CRopp_le_compat : forall x y : CR, |
| 808 |
x <= y -> -y <= -x. |
| 809 |
Proof. |
| 810 |
intros. apply (CRplus_le_l _ _ (x+y)). |
| 811 |
ring_simplify. exact H. |
| 812 |
Qed. |
| 813 |
|
| 814 |
Lemma CRopp_le_cancel : forall x y : CR, |
| 815 |
-y <= -x -> x <= y. |
| 816 |
Proof. |
| 817 |
intros. apply (CRplus_le_l (-y) (-x) (x+y)) in H. |
| 818 |
ring_simplify in H. exact H. |
| 819 |
Qed. |
| 820 |
|
| 821 |
Lemma CRle_Q : forall (x : CR) (q : Q), |
| 822 |
('q <= x)%CR |
| 823 |
<-> (forall e:Qpos, q <= approximate x e + proj1_sig e)%Q. |
| 824 |
Proof. |
| 825 |
split. |
| 826 |
- intros. |
| 827 |
unfold CRle in H. |
| 828 |
rewrite CRopp_Qopp, CRplus_comm, CRplus_translate in H. |
| 829 |
specialize (H e). |
| 830 |
simpl in H. apply (Qplus_le_l _ _ (`e + q)) in H. |
| 831 |
ring_simplify in H. rewrite Qplus_comm. exact H. |
| 832 |
- intros. unfold CRle. |
| 833 |
rewrite CRopp_Qopp, CRplus_comm, CRplus_translate. |
| 834 |
intro e. |
| 835 |
simpl. apply (Qplus_le_l _ _ (`e + q)). |
| 836 |
ring_simplify. rewrite Qplus_comm. apply H. |
| 837 |
Qed. |
| 838 |
|
| 839 |
Lemma CRlt_irrefl (x: CR): x < x -> False. |
| 840 |
Proof with auto. |
| 841 |
unfold CRltT. |
| 842 |
intro. |
| 843 |
assert (x - x == 0)%CR by ring. |
| 844 |
intros. |
| 845 |
generalize (CRpos_wd H0 H). |
| 846 |
unfold CRpos. |
| 847 |
intros. |
| 848 |
destruct H1. |
| 849 |
destruct x0. |
| 850 |
simpl in c. |
| 851 |
assert (x0 <= 0)%Q. |
| 852 |
rewrite <- CRle_Qle... |
| 853 |
apply Qlt_irrefl with 0%Q. |
| 854 |
apply Qlt_le_trans with x0... |
| 855 |
Qed. |
| 856 |
|
| 857 |
Lemma CRAbsSmall_ball : forall (x y:CR) (e:Q), |
| 858 |
(-'e <= x-y /\ x-y <= 'e)%CR <-> ball e x y. |
| 859 |
Proof. |
| 860 |
intros x y e. |
| 861 |
split. |
| 862 |
- intros [H1 H2]. |
| 863 |
rewrite <- (doubleSpeed_Eq x). |
| 864 |
rewrite <- (doubleSpeed_Eq (doubleSpeed x)). |
| 865 |
rewrite <- (doubleSpeed_Eq y). |
| 866 |
rewrite <- (doubleSpeed_Eq (doubleSpeed y)). |
| 867 |
apply regFunBall_e. |
| 868 |
intros d. |
| 869 |
assert (H1':=H1 d). |
| 870 |
assert (H2':=H2 d). |
| 871 |
clear H1 H2. |
| 872 |
simpl. |
| 873 |
set (x':=approximate x ((1#2)*((1#2)*d))%Qpos). |
| 874 |
set (y':=approximate y ((1#2)*((1#2)*d))%Qpos). |
| 875 |
change (-proj1_sig d <= x' - y' + - - e)%Q in H1'. |
| 876 |
change (-proj1_sig d <= e + - (x' - y'))%Q in H2'. |
| 877 |
rewrite -> Qle_minus_iff in *. |
| 878 |
apply ball_weak. apply Qpos_nonneg. |
| 879 |
split; simpl; rewrite -> Qle_minus_iff. |
| 880 |
rewrite Qopp_involutive. do 2 rewrite Qopp_involutive in H1'. |
| 881 |
rewrite (Qplus_comm (proj1_sig d)). |
| 882 |
rewrite Qplus_assoc. exact H1'. |
| 883 |
rewrite <- Qplus_assoc, Qplus_comm. rewrite Qopp_involutive in H2'. |
| 884 |
exact H2'. |
| 885 |
- intros H. |
| 886 |
rewrite <- (doubleSpeed_Eq x) in H. |
| 887 |
rewrite <- (doubleSpeed_Eq y) in H. |
| 888 |
split; intros d; destruct (H ((1#2)*d)%Qpos ((1#2)*d)%Qpos) as [H1 H2]; clear H; |
| 889 |
set (x':=(approximate (doubleSpeed x) ((1 # 2) * d)%Qpos)) in *; |
| 890 |
set (y':=(approximate (doubleSpeed y) ((1 # 2) * d)%Qpos)) in *. |
| 891 |
autorewrite with QposElim in H1. |
| 892 |
change (- ((1 # 2) * proj1_sig d + e + (1 # 2) * proj1_sig d)<=x' - y')%Q in H1. |
| 893 |
change (-proj1_sig d <= x' - y' + - - e)%Q. |
| 894 |
rewrite -> Qle_minus_iff. |
| 895 |
rewrite -> Qle_minus_iff in H1. |
| 896 |
setoid_replace (x' - y' + - - e + - - ` d)%Q |
| 897 |
with (x' - y' + - - ((1 # 2) * proj1_sig d + e + (1 # 2) * proj1_sig d))%Q |
| 898 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 899 |
assumption. |
| 900 |
autorewrite with QposElim in H2. |
| 901 |
change (x' - y'<=((1 # 2) * proj1_sig d + e + (1 # 2) * proj1_sig d))%Q in H2. |
| 902 |
change (-proj1_sig d <= e + - (x' - y'))%Q. |
| 903 |
rewrite -> Qle_minus_iff. |
| 904 |
rewrite -> Qle_minus_iff in H2. |
| 905 |
setoid_replace (e + - (x' - y') + - - ` d)%Q |
| 906 |
with ((1 # 2) * proj1_sig d + e + (1 # 2) * proj1_sig d + - (x' - y'))%Q |
| 907 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 908 |
assumption. |
| 909 |
Qed. |
| 910 |
|
| 911 |
Lemma in_CRball (r: Q) (x y : CR) |
| 912 |
: x - ' r <= y /\ y <= x + ' r <-> ball r x y. |
| 913 |
(* A characterization of ball in terms of <=, similar to CRAbsSmall. *) |
| 914 |
Proof with intuition. |
| 915 |
intros. |
| 916 |
cut ((-' r <= x - y /\ x-y <= 'r) <-> (x - ' r <= y /\ y <= x + ' r)). |
| 917 |
- pose proof (CRAbsSmall_ball x y r)... |
| 918 |
- simpl. |
| 919 |
setoid_replace (x - y <= ' r) with (x - ' r <= y). |
| 920 |
setoid_replace (- ' r <= x - y) with (y <= x + ' r). |
| 921 |
intuition. |
| 922 |
rewrite (CRplus_le_r (- ' r) (x - y) ('r + y)). |
| 923 |
assert (- ' r + (' r + y) == y) as E by ring. rewrite E. |
| 924 |
assert (x - y + (' r + y) == x + ' r)%CR as F by ring. rewrite F... |
| 925 |
rewrite (CRplus_le_r (x - y) (' r) (y - 'r)). |
| 926 |
assert (x - y + (y - ' r) == x - ' r) as E by ring. rewrite E. |
| 927 |
assert (' r + (y - ' r) == y) as F by ring. rewrite F... |
| 928 |
Qed. |
| 929 |
|
| 930 |
(* And the same for gball: *) |
| 931 |
Lemma in_CRgball (r: Q) (x y: CR): x - ' r <= y /\ y <= x + ' r <-> ball r x y. |
| 932 |
Proof with intuition. |
| 933 |
apply in_CRball. |
| 934 |
Qed. |
| 935 |
|
| 936 |
Lemma CRgball_plus (x x' y y': CR) e1 e2: |
| 937 |
ball e1 x x' -> ball e2 y y' -> ball (e1 + e2) (x + y)%CR (x' + y')%CR. |
| 938 |
Proof with auto. |
| 939 |
do 3 rewrite <- in_CRgball. |
| 940 |
intros [A B] [C D]. |
| 941 |
CRring_replace (x + y - ' (e1 + e2)%Q) (x - ' e1 + (y - ' e2)). |
| 942 |
CRring_replace (x + y + ' (e1 + e2)%Q) (x + ' e1 + (y + ' e2)). |
| 943 |
split; apply CRplus_le_compat... |
| 944 |
Qed. |
| 945 |
|
| 946 |
Lemma Qlt_from_CRlt (a b: Q): (' a < ' b)%CR -> (a < b)%Q. |
| 947 |
Proof with auto. |
| 948 |
unfold CRltT. |
| 949 |
unfold CRpos. |
| 950 |
intros [[e p] H]. |
| 951 |
revert H. |
| 952 |
simpl. |
| 953 |
rewrite CRminus_Qminus. |
| 954 |
rewrite CRle_Qle. |
| 955 |
intros. |
| 956 |
apply Qlt_le_trans with (a + e)%Q. |
| 957 |
rewrite <-(Qplus_0_r a) at 1. |
| 958 |
apply Qplus_lt_r... |
| 959 |
apply Q.Qplus_le_l with (-a)%Q. |
| 960 |
ring_simplify. |
| 961 |
rewrite Qplus_comm... |
| 962 |
Qed. |
| 963 |
|
| 964 |
Lemma CRlt_trans (x y z: CR): x < y -> y < z -> x < z. |
| 965 |
Proof. |
| 966 |
intros [q H] [r H0]. exists (q+r)%Qpos. |
| 967 |
rewrite <- (doubleSpeed_Eq z). |
| 968 |
rewrite <- (doubleSpeed_Eq x). |
| 969 |
intro e. simpl. |
| 970 |
unfold Cap_raw; simpl. |
| 971 |
unfold Cap_raw; simpl. |
| 972 |
specialize (H ((1#2)*e)%Qpos). simpl in H. |
| 973 |
specialize (H0 ((1#2)*e)%Qpos). simpl in H0. |
| 974 |
unfold Cap_raw in H0; simpl in H0. |
| 975 |
unfold Cap_raw in H0; simpl in H0. |
| 976 |
unfold Cap_raw in H; simpl in H. |
| 977 |
unfold Cap_raw in H; simpl in H. |
| 978 |
apply (Qplus_le_compat _ _ _ _ H) in H0. |
| 979 |
setoid_replace (- ((1 # 2) * ` e) + - ((1 # 2) * ` e))%Q |
| 980 |
with (-`e)%Q in H0 by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 981 |
apply (Qle_trans _ _ _ H0). |
| 982 |
ring_simplify. apply Qle_refl. |
| 983 |
Qed. |
| 984 |
|
| 985 |
Lemma CRle_lt_trans (x y z: CR): x <= y -> y < z -> x < z. |
| 986 |
Proof with auto. |
| 987 |
intros ? [e ?]. exists e. |
| 988 |
apply CRle_trans with (z - y)%CR... |
| 989 |
assert (z - x - (z - y) == y - x)%CR as E by ring. |
| 990 |
unfold CRle. |
| 991 |
rewrite E... |
| 992 |
Qed. |
| 993 |
|
| 994 |
Lemma CRlt_le_trans (x y z: CR): x < y -> y <= z -> x < z. |
| 995 |
Proof with auto. |
| 996 |
intros [e ?] ?. exists e. |
| 997 |
apply CRle_trans with (y - x)%CR... |
| 998 |
assert (z - x - (y - x) == z - y)%CR as E by ring. |
| 999 |
unfold CRle. |
| 1000 |
rewrite E... |
| 1001 |
Qed. |
| 1002 |
|
| 1003 |
Lemma CRlt_le_weak (x y: CR): (x < y -> x <= y)%CR. |
| 1004 |
Proof. intros. apply CRpos_nonNeg. assumption. Qed. |
| 1005 |
|
| 1006 |
Lemma lower_CRapproximation (x: CR) (e: Qpos): ' (approximate x e - proj1_sig e)%Q <= x. |
| 1007 |
Proof. |
| 1008 |
intros. rewrite <- CRminus_Qminus. |
| 1009 |
apply CRplus_le_r with ('proj1_sig e)%CR. |
| 1010 |
ring_simplify. rewrite CRplus_comm. |
| 1011 |
apply in_CRball, ball_approx_r. |
| 1012 |
Qed. |
| 1013 |
|
| 1014 |
Lemma upper_CRapproximation (x: CR) (e: Qpos): x <= ' (approximate x e + proj1_sig e)%Q. |
| 1015 |
Proof. |
| 1016 |
intros. rewrite <- CRplus_Qplus. |
| 1017 |
apply CRplus_le_r with (-'proj1_sig e)%CR. |
| 1018 |
assert (' approximate x e + 'proj1_sig e - 'proj1_sig e == ' approximate x e)%CR as E by ring. rewrite E. |
| 1019 |
apply (in_CRball (proj1_sig e) x ('approximate x e)), ball_approx_r. |
| 1020 |
Qed. |
| 1021 |
|
| 1022 |
#[global] |
| 1023 |
Hint Immediate lower_CRapproximation upper_CRapproximation. |
| 1024 |
|
| 1025 |
Lemma reverseRegFun : forall (x : CR) (e1 e2 : Qpos), |
| 1026 |
(-(`e1+`e2) <= Qabs (approximate x e1) - Qabs (approximate x e2))%Q. |
| 1027 |
Proof. |
| 1028 |
intros. |
| 1029 |
setoid_replace (Qabs (approximate x e1) - Qabs (approximate x e2))%Q |
| 1030 |
with (-(Qabs (approximate x e2) - Qabs (approximate x e1)))%Q |
| 1031 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1032 |
apply Qopp_le_compat. |
| 1033 |
apply (Qle_trans _ _ _ (Qabs_triangle_reverse _ _)). |
| 1034 |
pose proof (regFun_prf x e2 e1). |
| 1035 |
apply AbsSmall_Qabs in H. rewrite Qplus_comm. exact H. |
| 1036 |
Qed. |
| 1037 |
|
| 1038 |
Lemma CRinv_0_lt_compat : forall (x : CR) (xnz : (x >< 0)%CR), |
| 1039 |
(0 < x -> 0 < CRinvT x xnz)%CR. |
| 1040 |
Proof. |
| 1041 |
intros. unfold CRinvT. destruct xnz. |
| 1042 |
- exfalso. apply (CRlt_irrefl x). |
| 1043 |
exact (CRlt_trans _ _ _ c H). |
| 1044 |
- destruct c as [q c]. |
| 1045 |
pose (CR_b (1#1) x + (1#1))%Qpos as b. |
| 1046 |
exists (Qpos_inv b). rewrite CRopp_0, CRplus_0_r. |
| 1047 |
rewrite CRopp_0, CRplus_0_r in c. |
| 1048 |
intro e. simpl. unfold Cap_raw. simpl. |
| 1049 |
unfold Qinv_modulus. |
| 1050 |
change (Qabs (approximate x (Qpos2QposInf (1 # 1))) + 1 + 1)%Q |
| 1051 |
with (`b). |
| 1052 |
assert (`q <= `b)%Q as qleb. |
| 1053 |
{ apply CRle_Qle. apply (CRle_trans c). |
| 1054 |
apply (CRle_trans (CR_b_upperBound (1#1)%Qpos x)). |
| 1055 |
simpl. apply CRle_Qle. |
| 1056 |
rewrite <- Qplus_assoc. apply Qplus_le_r. discriminate. } |
| 1057 |
apply Qmax_case. |
| 1058 |
+ intros _. apply (Qle_trans _ 0). |
| 1059 |
apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1060 |
rewrite <- Qle_minus_iff. |
| 1061 |
apply Qle_shift_inv_r. apply Qpos_ispos. |
| 1062 |
rewrite Qmult_comm. apply Qle_shift_div_l. apply Qpos_ispos. |
| 1063 |
rewrite Qmult_1_l. exact qleb. |
| 1064 |
+ intros. |
| 1065 |
apply (Qmult_le_l _ _ (approximate x (q * q * ((1 # 2)%Q ↾ eq_refl * e))%Qpos)). |
| 1066 |
exact (Qlt_le_trans _ (`q) _ (Qpos_ispos q) H0). |
| 1067 |
rewrite Qmult_plus_distr_r, Qmult_inv_r. |
| 1068 |
apply (Qmult_le_l _ _ (`b)). |
| 1069 |
apply Qpos_ispos. |
| 1070 |
rewrite Qmult_plus_distr_r. |
| 1071 |
setoid_replace (` b * |
| 1072 |
((approximate x (q * q * ((1 # 2) * e))%Qpos) * - / ` b))%Q |
| 1073 |
with (-(approximate x (q * q * ((1 # 2)%Q ↾ eq_refl * e))%Qpos))%Q |
| 1074 |
by (unfold equiv, stdlib_rationals.Q_eq; field). |
| 1075 |
2: apply Qpos_nonzero. |
| 1076 |
rewrite Qmult_1_r. |
| 1077 |
apply (Qle_trans _ (-(`q * `q * `e))). |
| 1078 |
setoid_replace (` b * (approximate x (q * q * ((1 # 2)%Q ↾ eq_refl * e))%Qpos * - ` e))%Q |
| 1079 |
with (-(` b * (approximate x (q * q * ((1 # 2)%Q ↾ eq_refl * e))%Qpos *` e)))%Q |
| 1080 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1081 |
apply Qopp_le_compat. |
| 1082 |
rewrite Qmult_assoc. apply Qmult_le_r. apply Qpos_ispos. |
| 1083 |
apply Qpos_mult_le_compat. exact qleb. exact H0. |
| 1084 |
unfold b, CR_b. simpl. |
| 1085 |
rewrite <- (Qabs_pos (approximate x (q * q * ((1 # 2)%Q ↾ eq_refl * e))%Qpos)). |
| 1086 |
apply (Qle_trans _ (-((1#1)+(`q * `q * ((1 # 2) * `e))) + (2#1)))%Q. |
| 1087 |
apply (Qle_trans _ (-(`q * `q * ((1 # 2) * `e)))). |
| 1088 |
apply Qopp_le_compat. apply Qmult_le_l. apply (Qpos_ispos (q*q)). |
| 1089 |
rewrite <- (Qmult_1_l (`e)) at 2. |
| 1090 |
apply Qmult_le_r. apply Qpos_ispos. discriminate. |
| 1091 |
rewrite <- Qplus_0_r. |
| 1092 |
setoid_replace (- ((1#1) + ` q * ` q * ((1 # 2) * ` e)) + (2#1))%Q |
| 1093 |
with (- (` q * ` q * ((1 # 2) * ` e)) + (1#1))%Q |
| 1094 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1095 |
apply Qplus_le_r. discriminate. |
| 1096 |
rewrite <- Qplus_assoc, <- Qplus_assoc, (Qplus_assoc (1#1)). |
| 1097 |
setoid_replace ((1#1)+(1#1))%Q with (2#1)%Q by reflexivity. |
| 1098 |
rewrite (Qplus_comm (2#1)), Qplus_assoc. |
| 1099 |
apply Qplus_le_compat. |
| 1100 |
apply (reverseRegFun x (1#1) (q * q * ((1 # 2) * e))). |
| 1101 |
discriminate. |
| 1102 |
apply (Qle_trans _ (`q)). apply Qpos_nonneg. exact H0. |
| 1103 |
intro abs. rewrite abs in H0. |
| 1104 |
apply (Qle_not_lt _ _ H0), Qpos_ispos. |
| 1105 |
Qed. |
| 1106 |
|
| 1107 |
|
| 1108 |
Lemma CRlt_Qmid (x y: CR): x < y -> sigT (λ q: Q, prod (x < 'q) ('q < y)). |
| 1109 |
Proof with auto. |
| 1110 |
intros [q E]. |
| 1111 |
set (quarter := ((1#4)*q)%Qpos). |
| 1112 |
exists (proj1_sig quarter + (approximate x quarter + proj1_sig quarter))%Q. |
| 1113 |
split. |
| 1114 |
apply CRle_lt_trans with (' (0 + (approximate x quarter + proj1_sig quarter))%Q)%CR... |
| 1115 |
rewrite Qplus_0_l... |
| 1116 |
apply CRlt_Qlt. |
| 1117 |
apply Qplus_lt_l... |
| 1118 |
apply CRlt_le_trans with (x + 'proj1_sig q)%CR. |
| 1119 |
apply CRlt_le_trans with (' (approximate x quarter - proj1_sig quarter + proj1_sig q)%Q)%CR. |
| 1120 |
apply CRlt_Qlt. |
| 1121 |
setoid_replace (proj1_sig q) |
| 1122 |
with (proj1_sig quarter + proj1_sig quarter + proj1_sig quarter + proj1_sig quarter)%Q. |
| 1123 |
ring_simplify. |
| 1124 |
apply Qplus_lt_l. |
| 1125 |
apply Qmult_lt_compat_r... |
| 1126 |
reflexivity. |
| 1127 |
simpl. unfold equiv, stdlib_rationals.Q_eq; ring. |
| 1128 |
rewrite <- CRplus_Qplus. |
| 1129 |
apply CRplus_le_compat... |
| 1130 |
apply CRle_refl. |
| 1131 |
apply CRplus_le_r with (-x)%CR. |
| 1132 |
CRring_replace (x + 'proj1_sig q - x) ('proj1_sig q)... |
| 1133 |
Qed. |
| 1134 |
|
| 1135 |
Lemma CRlt_linear : forall x y z : CR, |
| 1136 |
x < z -> (sum (x < y) (y < z)). |
| 1137 |
Proof. |
| 1138 |
intros. |
| 1139 |
destruct (CRlt_Qmid _ _ H) as [q [H0 H1]]. (* Destructing x < z and dividing the |
| 1140 |
witness by 2 would be faster. *) |
| 1141 |
destruct (CRlt_Qmid _ _ H1) as [r [H2 H3]]. |
| 1142 |
assert (Qlt 0 ((1#2)*(r-q))) as qltr. |
| 1143 |
{ rewrite <- (Qmult_0_r (1#2)). apply Qmult_lt_l. |
| 1144 |
reflexivity. |
| 1145 |
unfold Qminus. rewrite <- Qlt_minus_iff. |
| 1146 |
apply Qlt_from_CRlt, H2. } |
| 1147 |
destruct (Qlt_le_dec (approximate y (Qpos2QposInf (exist (Qlt 0) _ qltr))) |
| 1148 |
((1#2)*(q+r))). |
| 1149 |
- right. refine (CRle_lt_trans _ ('r) _ _ H3). |
| 1150 |
pose proof (upper_CRapproximation y (exist (Qlt 0) _ qltr)). |
| 1151 |
apply (@CRle_trans _ _ _ H4). |
| 1152 |
apply CRle_Qle. |
| 1153 |
apply (Qle_trans _ ((1 # 2) * (q + r) + (1 # 2) * (r - q))). |
| 1154 |
apply Qplus_le_l, Qlt_le_weak, q0. |
| 1155 |
ring_simplify. apply Qle_refl. |
| 1156 |
- left. apply (CRlt_le_trans _ ('q) _ H0). |
| 1157 |
pose proof (lower_CRapproximation y (exist (Qlt 0) _ qltr)). |
| 1158 |
refine (@CRle_trans _ _ _ _ H4). apply CRle_Qle. |
| 1159 |
apply (Qle_trans _ ((1 # 2) * (q + r) - (1 # 2) * (r - q))). |
| 1160 |
ring_simplify. apply Qle_refl. |
| 1161 |
apply Qplus_le_l, q0. |
| 1162 |
Qed. |
| 1163 |
|
| 1164 |
Lemma CRle_not_lt (x y: CR): (x <= y)%CR <-> (y < x -> False)%CR. |
| 1165 |
Proof. |
| 1166 |
split. |
| 1167 |
- intros H [q H0]. |
| 1168 |
apply (CRplus_le_compat _ _ _ _ H) in H0. |
| 1169 |
setoid_replace (y + (x-y))%CR with (x+0) in H0 |
| 1170 |
by (unfold equiv, msp_Equiv; ring). |
| 1171 |
apply CRplus_le_l in H0. |
| 1172 |
apply CRle_Qle in H0. |
| 1173 |
apply (Qle_not_lt _ _ H0 (Qpos_ispos q)). |
| 1174 |
- intros. |
| 1175 |
assert (forall z:CR, (0 < z -> False) -> z <= 0) as zero_irrefl. |
| 1176 |
{ clear H x y. intros z H0. unfold CRltT in H0. |
| 1177 |
unfold CRle. |
| 1178 |
apply (@CRnonNeg_wd (-z)). ring. |
| 1179 |
intro q. |
| 1180 |
apply Qnot_lt_le. intro abs. apply H0. clear H0. |
| 1181 |
apply (@CRpos_wd z). ring. simpl in abs. |
| 1182 |
apply Qlt_minus_iff in abs. |
| 1183 |
rewrite Qopp_involutive, Qplus_comm in abs. |
| 1184 |
exists (exist (Qlt 0) _ abs). intro r. |
| 1185 |
simpl. unfold Cap_raw; simpl. |
| 1186 |
pose proof (regFun_prf z q ((1#2)*r)%Qpos). |
| 1187 |
apply AbsSmall_Qabs in H. |
| 1188 |
apply (Qle_trans _ _ _ (Qle_Qabs _)) in H. |
| 1189 |
apply (Qplus_le_l _ _ (approximate z q + `r)). |
| 1190 |
simpl. ring_simplify. |
| 1191 |
apply (Qplus_le_l _ _ (approximate z ((1#2)*r)%Qpos)) in H. |
| 1192 |
ring_simplify in H. rewrite (Qplus_comm (`r)). |
| 1193 |
apply (Qle_trans _ _ _ H). |
| 1194 |
rewrite <- Qplus_assoc, <- Qplus_assoc. |
| 1195 |
apply Qplus_le_r. rewrite Qplus_comm. |
| 1196 |
apply Qplus_le_l. simpl. |
| 1197 |
rewrite <- (Qmult_1_l (`r)) at 2. |
| 1198 |
apply Qmult_le_r. apply Qpos_ispos. discriminate. } |
| 1199 |
assert (0<x-y -> False)%CR. |
| 1200 |
{ intros [q H0]. apply H. clear H zero_irrefl. |
| 1201 |
exists q. unfold CRle. unfold CRle in H0. |
| 1202 |
setoid_replace (x - y - ' 0%Q - ' ` q)%CR |
| 1203 |
with (x - y - ' ` q) in H0 |
| 1204 |
by (unfold equiv, msp_Equiv; ring). |
| 1205 |
exact H0. } |
| 1206 |
apply (CRplus_le_r _ _ (-y)). |
| 1207 |
rewrite CRplus_opp. |
| 1208 |
apply zero_irrefl, H0. |
| 1209 |
Qed. |
| 1210 |
|
| 1211 |
Lemma CRle_alt : forall (x y : CR), |
| 1212 |
x <= y <-> forall e:Qpos, (-(2#1)*proj1_sig e <= approximate y e - approximate x e)%Q. |
| 1213 |
Proof. |
| 1214 |
split. |
| 1215 |
- intros. |
| 1216 |
apply Qnot_lt_le. intro abs. |
| 1217 |
pose proof (lower_CRapproximation x e). |
| 1218 |
pose proof (upper_CRapproximation y e). |
| 1219 |
apply (Qplus_lt_l _ _ (`e + approximate x e)) in abs. |
| 1220 |
ring_simplify in abs. |
| 1221 |
setoid_replace (approximate x e + -(1#1) * `e)%Q |
| 1222 |
with (approximate x e - `e)%Q in abs |
| 1223 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1224 |
apply CRlt_Qlt in abs. |
| 1225 |
apply (CRle_lt_trans _ _ _ H1) in abs. clear H1. |
| 1226 |
apply (CRlt_le_trans _ _ _ abs) in H0. |
| 1227 |
apply CRle_not_lt in H. contradiction. exact H0. |
| 1228 |
- intros. intro e. |
| 1229 |
specialize (H ((1#2)*e)%Qpos). simpl in H. |
| 1230 |
setoid_replace (- (2#1) * ((1 # 2) * ` e))%Q with (-`e)%Q |
| 1231 |
in H by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1232 |
apply H. |
| 1233 |
Qed. |
| 1234 |
|
| 1235 |
Lemma CRnonNeg_le_0 x: CRnonNeg x <-> 0 <= x. |
| 1236 |
Proof. |
| 1237 |
unfold CRle. |
| 1238 |
assert (x - 0 == x)%CR as E by ring. |
| 1239 |
rewrite E. |
| 1240 |
intuition. |
| 1241 |
Qed. |
| 1242 |
|
| 1243 |
Lemma CRnonNeg_0: CRnonNeg (0)%CR. |
| 1244 |
Proof. |
| 1245 |
unfold CRnonNeg. simpl. intros. |
| 1246 |
apply (Qopp_le_compat 0). apply Qpos_nonneg. |
| 1247 |
Qed. |
| 1248 |
|
| 1249 |
#[global] |
| 1250 |
Hint Immediate CRnonNeg_0. |
| 1251 |
|
| 1252 |
Definition CRle_lt_dec: forall x y, DN ((x <= y)%CR + (y < x)%CR). |
| 1253 |
Proof with auto. |
| 1254 |
intros. |
| 1255 |
apply (DN_fmap (@DN_decisionT (y < x)%CR)). |
| 1256 |
intros [A | B]... |
| 1257 |
left. |
| 1258 |
apply CRle_not_lt in B. exact B. |
| 1259 |
Qed. |
| 1260 |
|
| 1261 |
Definition CRle_dec: forall (x y: CR), DN ((x<=y)%CR + (y<=x)%CR). |
| 1262 |
Proof with auto. |
| 1263 |
intros. apply (DN_fmap (CRle_lt_dec x y)). |
| 1264 |
intros [A | B]... |
| 1265 |
right. |
| 1266 |
apply CRlt_le_weak... |
| 1267 |
Qed. |
| 1268 |
|
| 1269 |
Lemma approximate_CRminus (x y: CR) (e: QposInf): |
| 1270 |
approximate (x - y)%CR e = |
| 1271 |
(approximate x (Qpos2QposInf (1 # 2) * e)%QposInf - approximate y (Qpos2QposInf (1 # 2) * e)%QposInf)%Q. |
| 1272 |
Proof. destruct e; reflexivity. Qed. |
| 1273 |
|
| 1274 |
|
| 1275 |
Lemma CRnonNeg_criterion (x: CR): (forall q, (x <= ' q)%CR -> 0 <= q)%Q -> CRnonNeg x. |
| 1276 |
Proof with auto with qarith. |
| 1277 |
unfold CRle. |
| 1278 |
unfold CRnonNeg. |
| 1279 |
intros. |
| 1280 |
apply Q.Qplus_le_l with (proj1_sig e). |
| 1281 |
ring_simplify. |
| 1282 |
apply H. |
| 1283 |
intros. |
| 1284 |
rewrite approximate_CRminus. |
| 1285 |
simpl. |
| 1286 |
cut (approximate x ((1 # 2) * e0)%Qpos - approximate x e <= proj1_sig e0 + proj1_sig e)%Q. |
| 1287 |
- intros. |
| 1288 |
apply Q.Qplus_le_l with (proj1_sig e0 + approximate x ((1#2)*e0)%Qpos - approximate x e)%Q. |
| 1289 |
simpl. ring_simplify... |
| 1290 |
- apply Qle_trans with (Qabs (approximate x ((1 # 2) * e0)%Qpos - approximate x e))%Q. |
| 1291 |
apply Qle_Qabs. |
| 1292 |
apply Qle_trans with (proj1_sig ((1#2)*e0)%Qpos + proj1_sig e)%Q... |
| 1293 |
pose proof (regFun_prf x ((1#2)*e0)%Qpos e). |
| 1294 |
apply Qball_Qabs in H0... |
| 1295 |
apply Qplus_le_compat. |
| 1296 |
simpl. |
| 1297 |
rewrite <- (Qmult_1_r (proj1_sig e0)) at 2. |
| 1298 |
rewrite (Qmult_comm (proj1_sig e0)). |
| 1299 |
apply Qmult_le_compat_r... |
| 1300 |
apply Qle_refl. |
| 1301 |
Qed. |
| 1302 |
|
| 1303 |
(* Similarly, we can derive non-strict inequalities between reals from |
| 1304 |
non-strict inequalities which approximate it by a rational on one or both sides. *) |
| 1305 |
|
| 1306 |
Lemma Qle_CRle_r (x y: CR): (forall y', y <= ' y' -> x <= ' y') <-> x <= y. |
| 1307 |
Proof with auto. |
| 1308 |
split; intros. 2: apply CRle_trans with y... |
| 1309 |
apply from_DN. |
| 1310 |
apply (DN_bind (CRle_lt_dec x y)). |
| 1311 |
intros [?|W]. apply DN_return... |
| 1312 |
exfalso. |
| 1313 |
destruct (CRlt_Qmid _ _ W) as [w [A B]]. |
| 1314 |
pose proof (H w (CRlt_le_weak _ _ A)). |
| 1315 |
apply (CRle_not_lt x ('w)%CR)... |
| 1316 |
Qed. |
| 1317 |
|
| 1318 |
Lemma Qle_CRle_l (x y: CR): (forall x', ' x' <= x -> ' x' <= y) <-> x <= y. |
| 1319 |
Proof with auto. |
| 1320 |
intros. |
| 1321 |
rewrite CRle_opp. |
| 1322 |
rewrite <- Qle_CRle_r. |
| 1323 |
split; intros. |
| 1324 |
rewrite CRle_opp, CRopp_opp, CRopp_Qopp. |
| 1325 |
apply H. |
| 1326 |
rewrite CRle_opp, CRopp_Qopp, Qopp_opp... |
| 1327 |
rewrite CRle_opp, CRopp_Qopp. |
| 1328 |
apply H. |
| 1329 |
rewrite CRle_opp, CRopp_Qopp, CRopp_opp, Qopp_opp... |
| 1330 |
Qed. |
| 1331 |
|
| 1332 |
Lemma Qle_CRle (x y: CR): (forall x' y', ' x' <= x -> y <= ' y' -> (x' <= y')%Q) <-> x <= y. |
| 1333 |
Proof with auto. |
| 1334 |
split; intros. |
| 1335 |
apply (proj1 (Qle_CRle_l _ _)). intros. |
| 1336 |
apply (proj1 (Qle_CRle_r _ _)). intros. |
| 1337 |
apply CRle_Qle... |
| 1338 |
apply CRle_Qle. |
| 1339 |
apply CRle_trans with x... |
| 1340 |
apply CRle_trans with y... |
| 1341 |
Qed. |
| 1342 |
|
| 1343 |
Lemma CRnonNegQpos : forall e : Qpos, CRnonNeg (' ` e). |
| 1344 |
Proof. |
| 1345 |
intros [e e_pos]; apply CRnonNeg_criterion; simpl. |
| 1346 |
intros q A; apply Qlt_le_weak, Qlt_le_trans with (y := e); trivial. |
| 1347 |
now apply CRle_Qle. |
| 1348 |
Qed. |
| 1349 |
|
| 1350 |
Lemma scale_0 x: scale 0 x == 0. |
| 1351 |
Proof. rewrite <- CRmult_scale. ring. Qed. |
| 1352 |
|
| 1353 |
Lemma scale_CRplus (q: Q) (x y: CR): scale q (x + y) == scale q x + scale q y. |
| 1354 |
Proof. intros. do 3 rewrite <- CRmult_scale. ring. Qed. |
| 1355 |
|
| 1356 |
Lemma scale_CRopp (q: Q) (x: CR): scale q (-x) == - scale q x. |
| 1357 |
Proof. intros. do 2 rewrite <- CRmult_scale. ring. Qed. |
| 1358 |
|
| 1359 |
(** This returs GT if x is clearly greater than e, returns LT if x |
| 1360 |
is clearly less than (-e), and returns Eq otherwise. *) |
| 1361 |
Definition CR_epsilon_sign_dec (e:Qpos) (x:CR) : comparison := |
| 1362 |
let z := approximate x e in |
| 1363 |
match Q.Qle_dec ((2#1) * proj1_sig e) z with |
| 1364 |
| left p => Gt |
| 1365 |
| right _ => |
| 1366 |
match Q.Qle_dec z (-(2#1) * proj1_sig e)%Q with |
| 1367 |
| left p => Datatypes.Lt |
| 1368 |
| right _ => Eq |
| 1369 |
end |
| 1370 |
end. |
| 1371 |
|
| 1372 |
(** This helper lemma reduces a CRpos problem to a sigma type with |
| 1373 |
a simple equality proposition. *) |
| 1374 |
Lemma CR_epsilon_sign_dec_pos : forall x, |
| 1375 |
{e:Qpos | CR_epsilon_sign_dec e x ≡ Gt} -> CRpos x. |
| 1376 |
Proof. |
| 1377 |
intros x [e H]. |
| 1378 |
apply (@CRpos_char e). |
| 1379 |
abstract (unfold CR_epsilon_sign_dec in H; destruct (Q.Qle_dec ((2#1) * proj1_sig e) (approximate x e)) as [A|A]; |
| 1380 |
[assumption | destruct (Q.Qle_dec (approximate x e) (- (2#1) * proj1_sig e)) as [B|B]; discriminate H]). |
| 1381 |
Defined. |
| 1382 |
|
| 1383 |
Lemma CR_epsilon_sign_dec_Gt (e:Qpos) (x:CR) : |
| 1384 |
((2#1) * proj1_sig e <= approximate x e)%Q -> CR_epsilon_sign_dec e x ≡ Gt. |
| 1385 |
Proof. |
| 1386 |
intros. |
| 1387 |
unfold CR_epsilon_sign_dec. |
| 1388 |
destruct Q.Qle_dec; intuition. |
| 1389 |
Qed. |
| 1390 |
|
| 1391 |
(* nasty because approximate is not Proper *) |
| 1392 |
Lemma CR_epsilon_sign_dec_pos_rev (x : CR) (e : Qpos) : |
| 1393 |
('proj1_sig e <= x)%CR -> CR_epsilon_sign_dec ((1#4) * e) x ≡ Gt. |
| 1394 |
Proof. |
| 1395 |
intros E. |
| 1396 |
apply CR_epsilon_sign_dec_Gt. |
| 1397 |
apply Qplus_le_l with (-proj1_sig e)%Q. |
| 1398 |
simpl ((2#1) * ` ((1 # 4)%Q ↾ eq_refl * e)%Qpos + - ` e)%Q. |
| 1399 |
setoid_replace ((2#1) * ((1 # 4) * proj1_sig e) + - proj1_sig e)%Q |
| 1400 |
with (-((1#2) * proj1_sig e))%Q |
| 1401 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1402 |
replace ((1#4) * e)%Qpos with ((1#2) * ((1#2) * e))%Qpos. |
| 1403 |
now apply (E ((1#2) * e))%Qpos. |
| 1404 |
apply Qpos_hprop. |
| 1405 |
now destruct e as [[[ | | ] ?] ?]. |
| 1406 |
Qed. |
| 1407 |
|
| 1408 |
Lemma CRbound_distance_from_below |
| 1409 |
: forall (x : CR) (q : Q) (a b : Qpos), |
| 1410 |
(approximate x a <= q)%Q -> ('q <= x)%CR |
| 1411 |
-> (Qabs (approximate x b - q) <= `a + `b)%Q. |
| 1412 |
Proof. |
| 1413 |
intros. |
| 1414 |
assert (x <= 'q + '`a)%CR. |
| 1415 |
{ apply (CRle_trans (upper_CRapproximation x a)). |
| 1416 |
rewrite CRplus_Qplus. apply CRle_Qle. |
| 1417 |
apply Qplus_le_l. exact H. } |
| 1418 |
apply Qabs_case. |
| 1419 |
- intros. |
| 1420 |
pose proof (lower_CRapproximation x b). |
| 1421 |
apply (Qplus_le_l _ _ (q-`b)). |
| 1422 |
ring_simplify. |
| 1423 |
setoid_replace (-(1#1)*`b)%Q with (- ` b)%Q |
| 1424 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1425 |
apply CRle_Qle. apply (CRle_trans H3). |
| 1426 |
rewrite <- CRplus_Qplus. exact H1. |
| 1427 |
- intros. |
| 1428 |
pose proof (upper_CRapproximation x b). |
| 1429 |
apply (Qplus_le_r _ _ (approximate x b)). |
| 1430 |
ring_simplify. |
| 1431 |
rewrite (Qplus_comm (approximate x b)), <- Qplus_assoc. |
| 1432 |
apply (Qle_trans _ (0 + (approximate x b + `b))). |
| 1433 |
rewrite Qplus_0_l. |
| 1434 |
apply CRle_Qle. apply (CRle_trans H0), H3. |
| 1435 |
apply Qplus_le_l. apply Qpos_nonneg. |
| 1436 |
Qed. |
| 1437 |
|
| 1438 |
Lemma CRmult_inv_r_bounded |
| 1439 |
: forall (x : CR) (q b : Qpos), |
| 1440 |
(' ` q <= x)%CR |
| 1441 |
-> (`q < `b)%Q |
| 1442 |
-> (/ `q <= `b)%Q |
| 1443 |
-> (forall e:Qpos, approximate x e <= `b)%Q |
| 1444 |
-> (forall e:Qpos, - `b <= approximate x e)%Q |
| 1445 |
-> CRmult_bounded b x (CRinv_pos q x) == 1. |
| 1446 |
Proof. |
| 1447 |
intros x q b pos qltb invqleb xbelow xabove. |
| 1448 |
rewrite CRmult_uncurry_eq. |
| 1449 |
intros e1 e2. |
| 1450 |
simpl. |
| 1451 |
apply AbsSmall_Qabs. |
| 1452 |
assert (forall a c : Q, |
| 1453 |
0 < c -> Qabs (a*/c-(1#1)) == Qabs (/c) * Qabs (a-c))%Q as absShift. |
| 1454 |
{ intros. rewrite <- (Qmult_inv_r c). |
| 1455 |
setoid_replace (a * / c - c * / c)%Q |
| 1456 |
with ((a-c)*/c)%Q |
| 1457 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1458 |
rewrite Qabs_Qmult. apply Qmult_comm. intro abs. rewrite abs in H. |
| 1459 |
exact (Qlt_irrefl 0 H). } |
| 1460 |
assert (forall i j : Q, i<=j -> Qmax i j == j)%Q as elim_max. |
| 1461 |
{ intros. apply (Qle_max_r i j), H. } |
| 1462 |
assert (forall i j : Q, j<=i -> Qmin i j == j)%Q as elim_min. |
| 1463 |
{ intros. apply (Qle_min_r i j), H. } |
| 1464 |
assert (QboundAbs b (/ Qmax (` q) (approximate x (Qinv_modulus q ((1 # 2) ↾ eq_refl * e1 * Qpos_inv b)))) |
| 1465 |
== / Qmax (` q) (approximate x (Qinv_modulus q ((1 # 2) ↾ eq_refl * e1 * Qpos_inv b))))%Q. |
| 1466 |
{ simpl. |
| 1467 |
rewrite elim_max. |
| 1468 |
apply Qle_min_r. apply (Qle_trans _ (/`q)). |
| 1469 |
2: exact invqleb. apply Qle_shift_inv_l. |
| 1470 |
apply Qpos_ispos. rewrite Qmult_comm. |
| 1471 |
apply Qle_shift_div_r. |
| 1472 |
apply (Qlt_le_trans _ (`q)). apply Qpos_ispos. |
| 1473 |
apply Qmax_ub_l. rewrite Qmult_1_l. apply Qmax_ub_l. |
| 1474 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1475 |
apply Qmin_glb. apply Qpos_nonneg. |
| 1476 |
apply Qlt_le_weak, Qinv_lt_0_compat. |
| 1477 |
apply (Qlt_le_trans _ (`q)). apply Qpos_ispos. |
| 1478 |
apply Qmax_ub_l. } |
| 1479 |
simpl in H. rewrite H, absShift. clear absShift H. |
| 1480 |
rewrite Qabs_pos. |
| 1481 |
rewrite Qmult_comm. apply Qle_shift_div_r. |
| 1482 |
apply (Qlt_le_trans _ (`q)). apply Qpos_ispos. |
| 1483 |
apply Qmax_ub_l. |
| 1484 |
apply (Qle_trans _ ((1#2)*`e1 * `q + (1#2)*`e1 * `q)). |
| 1485 |
assert (((1 # 2) * ` e1 * / ` b + ` q * ` q * ((1 # 2) * ` e1 * / ` b) <= |
| 1486 |
(1 # 2) * ` e1 * ` q + (1 # 2) * ` e1 * ` q))%Q as dist_ok. |
| 1487 |
{ apply Qplus_le_compat. |
| 1488 |
- apply Qmult_le_l. apply (Qpos_ispos ((1#2)*e1)). |
| 1489 |
apply Qle_shift_inv_r. apply Qpos_ispos. |
| 1490 |
rewrite <- (Qmult_inv_r (`q)). |
| 1491 |
apply Qmult_le_l. apply Qpos_ispos. exact invqleb. |
| 1492 |
apply Qpos_nonzero. |
| 1493 |
- rewrite <- Qmult_assoc, (Qmult_comm (`q)). |
| 1494 |
apply Qmult_le_r. apply Qpos_ispos. |
| 1495 |
rewrite Qmult_assoc. |
| 1496 |
apply (Qle_shift_div_r _ (`b)). apply Qpos_ispos. |
| 1497 |
rewrite Qmult_comm. apply Qmult_le_l. |
| 1498 |
apply (Qpos_ispos ((1#2)*e1)). apply Qlt_le_weak, qltb. } |
| 1499 |
apply (Qmax_case (`q)). |
| 1500 |
- unfold Qinv_modulus. intros. |
| 1501 |
unfold Qmult_modulus. |
| 1502 |
assert (QboundAbs b (` q) == `q)%Q as H1. |
| 1503 |
{ simpl. transitivity (Qmin (`b) (`q)). apply Qle_max_r. |
| 1504 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1505 |
apply Qmin_glb. apply Qpos_nonneg. |
| 1506 |
apply Qpos_nonneg. |
| 1507 |
apply Qle_min_r. apply Qlt_le_weak, qltb. } |
| 1508 |
rewrite <- H1 at 1. clear H1. |
| 1509 |
apply (Qle_trans _ (Qabs |
| 1510 |
(approximate x ((1 # 2)%Q ↾ eq_refl * e1 * Qpos_inv b)%Qpos - (` q)))). |
| 1511 |
apply QboundAbs_contract. |
| 1512 |
apply (Qle_trans _ ((`q * `q * ((1 # 2) * `e1 * / `b)) |
| 1513 |
+ (1 # 2) * `e1 * / `b )). |
| 1514 |
apply (CRbound_distance_from_below |
| 1515 |
x (`q) |
| 1516 |
(q * q * ((1 # 2)%Q ↾ eq_refl * e1 * Qpos_inv b))%Qpos |
| 1517 |
((1 # 2) * e1 * Qpos_inv b)%Qpos). |
| 1518 |
2: exact pos. |
| 1519 |
exact H. rewrite Qplus_comm. exact dist_ok. |
| 1520 |
- unfold Qinv_modulus. intros. |
| 1521 |
unfold Qmult_modulus. |
| 1522 |
rewrite elim_min. |
| 1523 |
rewrite elim_max. |
| 1524 |
pose proof (regFun_prf x ((1 # 2)%Q ↾ eq_refl * e1 * Qpos_inv b)%Qpos |
| 1525 |
(q * q * ((1 # 2)%Q ↾ eq_refl * e1 * Qpos_inv b))%Qpos) |
| 1526 |
as H1. |
| 1527 |
apply AbsSmall_Qabs in H1. |
| 1528 |
apply (Qle_trans _ _ _ H1). clear H1. exact dist_ok. |
| 1529 |
apply xabove. apply xbelow. |
| 1530 |
- rewrite <- Qmult_plus_distr_l. |
| 1531 |
rewrite <- Qmult_plus_distr_l. |
| 1532 |
setoid_replace ((1 # 2) + (1 # 2))%Q with (1#1)%Q by reflexivity. |
| 1533 |
rewrite Qmult_1_l. |
| 1534 |
apply (Qle_trans _ ((`e1+`e2)*`q)). |
| 1535 |
rewrite <- Qplus_0_r, Qmult_plus_distr_l. |
| 1536 |
apply Qplus_le_r. apply (Qpos_nonneg (e2*q)). |
| 1537 |
rewrite Qplus_0_r. |
| 1538 |
apply Qmult_le_l. apply (Qpos_ispos (e1+e2)). |
| 1539 |
apply Qmax_ub_l. |
| 1540 |
- apply Qlt_le_weak, Qinv_lt_0_compat. |
| 1541 |
apply (Qlt_le_trans _ (`q)). apply Qpos_ispos. |
| 1542 |
apply Qmax_ub_l. |
| 1543 |
- apply (Qlt_le_trans _ (`q)). apply Qpos_ispos. |
| 1544 |
apply Qmax_ub_l. |
| 1545 |
- intro e. simpl. unfold Cap_raw. simpl. |
| 1546 |
apply (Qle_trans _ 0). |
| 1547 |
apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1548 |
rewrite <- Qle_minus_iff. apply xabove. |
| 1549 |
- intro e. simpl. unfold Cap_raw. simpl. |
| 1550 |
apply (Qle_trans _ 0). |
| 1551 |
apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1552 |
rewrite <- Qle_minus_iff. apply xbelow. |
| 1553 |
Qed. |
| 1554 |
|
| 1555 |
Lemma CRmult_inv_r_pos : forall (x : CR) (xnz : (x >< 0)%CR), |
| 1556 |
(0 < x)%CR -> (x * CRinvT x xnz == 1). |
| 1557 |
Proof. |
| 1558 |
intros. destruct xnz. |
| 1559 |
exfalso. exact (CRlt_irrefl x (CRlt_trans _ _ _ c H)). |
| 1560 |
destruct c as [q pos]. unfold CRinvT. |
| 1561 |
rewrite CRopp_0, CRplus_0_r in pos. |
| 1562 |
pose (Qpos_max (Qpos_inv q) (CR_b (1#1) x + (1#1))) as b. |
| 1563 |
assert (' (- ` b)%Q <= x) as xlower. |
| 1564 |
{ apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) x))%Q)). |
| 1565 |
2: apply (CR_b_lowerBound _ _). |
| 1566 |
apply CRle_Qle. apply Qopp_le_compat. |
| 1567 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1)%Qpos x) + (1#1))). |
| 1568 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1569 |
apply (Qpos_max_ub_r (Qpos_inv q) (CR_b (1#1) x + (1#1))). } |
| 1570 |
assert (x <= '(` b)%Q) as xupper. |
| 1571 |
{ apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) x))) _ (CR_b_upperBound _ _)). |
| 1572 |
apply CRle_Qle. |
| 1573 |
apply (Qle_trans _ (proj1_sig (CR_b (1#1)%Qpos x) + (1#1))). |
| 1574 |
rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate. |
| 1575 |
apply (Qpos_max_ub_r (Qpos_inv q) (CR_b (1#1) x + (1#1))). } |
| 1576 |
rewrite <- (CRboundAbs_Eq _ xlower xupper). |
| 1577 |
assert (`q < `b)%Q as qltb. |
| 1578 |
{ apply Qlt_from_CRlt. apply (CRle_lt_trans _ _ _ pos). |
| 1579 |
apply (CRle_lt_trans _ _ _ (CR_b_upperBound (1#1) x)). |
| 1580 |
apply CRlt_Qlt. unfold b. |
| 1581 |
apply (Qlt_le_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos)). |
| 1582 |
rewrite <- Qplus_0_r. apply Qplus_lt_r. reflexivity. |
| 1583 |
apply Qpos_max_ub_r. } |
| 1584 |
assert (/`q <= `b)%Q as invqleb. |
| 1585 |
{ apply (Qpos_max_ub_l (Qpos_inv q) (CR_b (1#1) x + (1#1))). } |
| 1586 |
rewrite <- (CRmult_bounded_mult b). |
| 1587 |
apply (CRmult_inv_r_bounded (CRboundAbs b x) q b). |
| 1588 |
- rewrite (CRboundAbs_Eq _ xlower xupper). exact pos. |
| 1589 |
- exact qltb. |
| 1590 |
- exact invqleb. |
| 1591 |
- intros. simpl. apply Qmax_lub. |
| 1592 |
apply (Qle_trans _ 0). |
| 1593 |
apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1594 |
apply Qpos_nonneg. apply Qmin_lb_l. |
| 1595 |
- intros. simpl. apply Qmax_ub_l. |
| 1596 |
- rewrite (CRboundAbs_Eq _ xlower xupper). |
| 1597 |
intro e. simpl. unfold Cap_raw. simpl. |
| 1598 |
rewrite Qopp_involutive. |
| 1599 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1600 |
apply (Qle_trans _ (/ Qmax (` q) (approximate x (Qinv_modulus q ((1 # 2) ↾ eq_refl * e))) + 0)). |
| 1601 |
rewrite Qplus_0_r. |
| 1602 |
apply Qlt_le_weak, Qinv_lt_0_compat. |
| 1603 |
apply (Qlt_le_trans _ (`q)). apply Qpos_ispos. |
| 1604 |
apply Qmax_ub_l. apply Qplus_le_r. apply Qpos_nonneg. |
| 1605 |
- rewrite (CRboundAbs_Eq _ xlower xupper). |
| 1606 |
intro e. simpl. unfold Cap_raw. simpl. |
| 1607 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1608 |
rewrite <- Qle_minus_iff. |
| 1609 |
apply (Qle_trans _ (/ `q)). |
| 1610 |
2: apply (Qpos_max_ub_l (Qpos_inv q) (CR_b (1#1) x + (1#1))). |
| 1611 |
apply Qle_shift_inv_r. |
| 1612 |
apply (Qlt_le_trans _ (`q)). apply Qpos_ispos. |
| 1613 |
apply Qmax_ub_l. |
| 1614 |
rewrite Qmult_comm. apply Qle_shift_div_l. |
| 1615 |
apply Qpos_ispos. rewrite Qmult_1_l. |
| 1616 |
apply Qmax_ub_l. |
| 1617 |
Qed. |
| 1618 |
|
| 1619 |
Lemma CRmult_inv_r : forall (x : CR) (xnz : (x >< 0)%CR), |
| 1620 |
x * CRinvT x xnz == 1. |
| 1621 |
Proof. |
| 1622 |
intros. destruct xnz as [neg|pos]. |
| 1623 |
- pose proof neg as otherNeg. |
| 1624 |
destruct neg as [q neg]. unfold CRinvT. |
| 1625 |
setoid_replace (x * - CRinv_pos q (- x))%CR |
| 1626 |
with (-x * CRinv_pos q (- x))%CR |
| 1627 |
by (unfold equiv, msp_Equiv; ring). |
| 1628 |
apply CRopp_lt_compat in otherNeg. |
| 1629 |
apply (CRltT_wd CRopp_0 (reflexivity _)) in otherNeg. |
| 1630 |
pose proof (CRmult_inv_r_pos (-x)%CR (inr otherNeg) otherNeg). |
| 1631 |
pose proof (CRinvT_pos_inv q (inr otherNeg)). |
| 1632 |
destruct otherNeg as [r H1]. unfold CRinvT in H. |
| 1633 |
unfold CRinvT in H0. |
| 1634 |
rewrite H0. exact H. rewrite CRplus_0_l in neg. exact neg. |
| 1635 |
- apply CRmult_inv_r_pos, pos. |
| 1636 |
Qed. |
| 1637 |
|
| 1638 |
(* Type class versions of a lot of the above *) |
| 1639 |
Close Scope CR_scope. |
| 1640 |
Local Opaque CR. |
| 1641 |
|
| 1642 |
#[global] |
| 1643 |
Instance: Ring CR. |
| 1644 |
Proof. apply (rings.from_stdlib_ring_theory CR_ring_theory). Qed. |
| 1645 |
|
| 1646 |
(* We need the (1#4) because CR_epsilon_sign_dec_pos_rev is nasty *) |
| 1647 |
#[global] |
| 1648 |
Instance CRlt: Lt CR := λ x y, |
| 1649 |
∃ n : nat, CR_epsilon_sign_dec ((1#4) * Qpos_power (2#1) (-cast nat Z n)) (y - x) ≡ Gt. |
| 1650 |
|
| 1651 |
Lemma CR_lt_ltT x y : prod (x < y -> CRltT x y) |
| 1652 |
(CRltT x y -> x < y). |
| 1653 |
Proof. |
| 1654 |
split. |
| 1655 |
intros E. |
| 1656 |
apply CR_epsilon_sign_dec_pos. |
| 1657 |
apply constructive_indefinite_description_nat in E. |
| 1658 |
destruct E as [n En]. |
| 1659 |
now exists ((1#4) * Qpos_power (2#1) (-cast nat Z n))%Qpos. |
| 1660 |
intros. now apply comparison_eq_dec. |
| 1661 |
intros [ε Eε]. |
| 1662 |
exists (Z.nat_of_Z (-Qdlog2 ('ε))). |
| 1663 |
apply CR_epsilon_sign_dec_pos_rev. |
| 1664 |
apply CRle_trans with ('proj1_sig ε); auto. |
| 1665 |
apply CRle_Qle. simpl. |
| 1666 |
destruct (decide (proj1_sig ε ≤ 1)). |
| 1667 |
rewrite Z.nat_of_Z_nonneg. |
| 1668 |
rewrite Z.opp_involutive. |
| 1669 |
apply Qdlog2_spec. |
| 1670 |
now destruct ε. |
| 1671 |
apply Z.opp_nonneg_nonpos. |
| 1672 |
now apply Qdlog2_nonpos. |
| 1673 |
rewrite Z.nat_of_Z_nonpos. |
| 1674 |
now apply Qlt_le_weak, Qnot_le_lt. |
| 1675 |
apply Z.opp_nonpos_nonneg. |
| 1676 |
apply Qdlog2_nonneg. |
| 1677 |
now apply Qlt_le_weak, Qnot_le_lt. |
| 1678 |
Qed. |
| 1679 |
|
| 1680 |
#[global] |
| 1681 |
Instance CRapart: Apart CR := λ x y, x < y ∨ y < x. |
| 1682 |
|
| 1683 |
Lemma CR_apart_apartT x y : prod (x ≶ y -> CRapartT x y) |
| 1684 |
(CRapartT x y -> x ≶ y). |
| 1685 |
Proof. |
| 1686 |
split. |
| 1687 |
intros E. |
| 1688 |
set (f (n : nat) := CR_epsilon_sign_dec ((1#4) * Qpos_power (2#1) (-cast nat Z n))). |
| 1689 |
assert (∃ n, f n (y - x) ≡ Gt ∨ f n (x - y) ≡ Gt) as E2. |
| 1690 |
now destruct E as [[n En] | [n En]]; exists n; [left | right]. |
| 1691 |
apply constructive_indefinite_description_nat in E2. |
| 1692 |
destruct E2 as [n E2]. |
| 1693 |
destruct (comparison_eq_dec (f n (y - x)) Gt) as [En|En]. |
| 1694 |
left. apply CR_epsilon_sign_dec_pos. |
| 1695 |
now exists ((1#4) * Qpos_power (2#1) (-cast nat Z n))%Qpos. |
| 1696 |
right. apply CR_epsilon_sign_dec_pos. |
| 1697 |
exists ((1#4) * Qpos_power (2#1) (-cast nat Z n))%Qpos. |
| 1698 |
destruct E2; tauto. |
| 1699 |
intros n. |
| 1700 |
destruct (comparison_eq_dec (f n (y - x)) Gt); auto. |
| 1701 |
destruct (comparison_eq_dec (f n (x - y)) Gt); tauto. |
| 1702 |
intros [E|E]. |
| 1703 |
left. now apply CR_lt_ltT. |
| 1704 |
right. now apply CR_lt_ltT. |
| 1705 |
Qed. |
| 1706 |
|
| 1707 |
Lemma CReq_not_apart : forall x y : CR, |
| 1708 |
(x == y)%CR <-> (CRapartT x y -> False). |
| 1709 |
Proof. |
| 1710 |
split. |
| 1711 |
- intros. destruct H0. |
| 1712 |
revert c. apply CRle_not_lt. |
| 1713 |
rewrite H. apply CRle_refl. |
| 1714 |
revert c. apply CRle_not_lt. |
| 1715 |
rewrite H. apply CRle_refl. |
| 1716 |
- intros. apply CRle_antisym. split. |
| 1717 |
apply CRle_not_lt. intro abs. |
| 1718 |
contradict H. right. exact abs. |
| 1719 |
apply CRle_not_lt. intro abs. |
| 1720 |
contradict H. left. exact abs. |
| 1721 |
Qed. |
| 1722 |
|
| 1723 |
#[global] |
| 1724 |
Instance: StrongSetoid CR. |
| 1725 |
Proof. |
| 1726 |
split. |
| 1727 |
- intros x E. |
| 1728 |
destruct E; apply CR_lt_ltT in H; exact (CRlt_irrefl x H). |
| 1729 |
- intros x y E. |
| 1730 |
destruct E. right. exact H. left. exact H. |
| 1731 |
- intros x y E z. destruct E. apply CR_lt_ltT in H. |
| 1732 |
apply (@CRlt_linear x z y) in H. destruct H. |
| 1733 |
left. left. apply CR_lt_ltT. exact c. right. left. |
| 1734 |
apply CR_lt_ltT. exact c. apply CR_lt_ltT in H. |
| 1735 |
apply (@CRlt_linear _ z) in H. destruct H. |
| 1736 |
right. right. apply CR_lt_ltT. |
| 1737 |
exact c. left. right. apply CR_lt_ltT. exact c. |
| 1738 |
- split. |
| 1739 |
+ intros. apply CRle_antisym. split. |
| 1740 |
apply CRle_not_lt. intro abs. apply H. right. |
| 1741 |
apply CR_lt_ltT. exact abs. |
| 1742 |
apply CRle_not_lt. intro abs. apply H. left. |
| 1743 |
apply CR_lt_ltT. exact abs. |
| 1744 |
+ intros H abs. destruct abs. |
| 1745 |
apply CR_lt_ltT in H0. |
| 1746 |
pose proof (@CRltT_wd _ _ H y y (reflexivity _) H0). |
| 1747 |
exact (CRlt_irrefl y H1). |
| 1748 |
apply CR_lt_ltT in H0. symmetry in H. |
| 1749 |
pose proof (@CRltT_wd _ _ H x x (reflexivity _) H0). |
| 1750 |
exact (CRlt_irrefl x H1). |
| 1751 |
Qed. |
| 1752 |
|
| 1753 |
Lemma CRle_scale : forall (a b : CR) (q : Qpos), |
| 1754 |
(a <= b)%CR <-> (scale (`q) a <= scale (`q) b)%CR. |
| 1755 |
Proof. |
| 1756 |
assert (forall (a b:CR) (q:Qpos), (a <= b)%CR -> (scale (`q) a <= scale (`q) b)%CR). |
| 1757 |
{ intros. intro e. simpl. |
| 1758 |
unfold Cap_raw; simpl. |
| 1759 |
unfold Qscale_modulus. destruct q, x, Qnum. simpl. |
| 1760 |
- exfalso; inversion q. |
| 1761 |
- simpl. |
| 1762 |
rewrite CRle_alt in H. |
| 1763 |
specialize (H ((Qden # p) * ((1#2)*e))%Qpos). |
| 1764 |
simpl in H. |
| 1765 |
setoid_replace (- (2#1) * ((Zpos Qden # p) * ((1 # 2) * ` e)))%Q |
| 1766 |
with (-`e * (Zpos Qden#p))%Q in H |
| 1767 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1768 |
apply Qle_shift_div_l in H. 2: reflexivity. |
| 1769 |
apply (Qle_trans _ _ _ H). clear H. |
| 1770 |
unfold Qdiv. |
| 1771 |
setoid_replace (/ (Zpos Qden # p)) with (Zpos p # Qden) by reflexivity. |
| 1772 |
rewrite Qmult_comm. unfold Qminus. |
| 1773 |
rewrite Qmult_plus_distr_r. apply Qplus_le_r. |
| 1774 |
ring_simplify. apply Qle_refl. |
| 1775 |
- exfalso. inversion q. } |
| 1776 |
split. intros. apply H, H0. |
| 1777 |
intros. apply (H _ _ (Qpos_inv q)) in H0. |
| 1778 |
setoid_replace (scale (` (Qpos_inv q)) (scale (` q) a)) with a in H0. |
| 1779 |
setoid_replace (scale (` (Qpos_inv q)) (scale (` q) b)) with b in H0. |
| 1780 |
exact H0. |
| 1781 |
- rewrite <- CRmult_scale, <- CRmult_scale. |
| 1782 |
rewrite <- CRmult_assoc. rewrite CRmult_Qmult. |
| 1783 |
setoid_replace (` (Qpos_inv q) * ` q)%Q with 1%Q. |
| 1784 |
apply CRmult_1_l. simpl. |
| 1785 |
rewrite Qmult_comm, Qmult_inv_r. reflexivity. apply Qpos_nonzero. |
| 1786 |
- rewrite <- CRmult_scale, <- CRmult_scale. |
| 1787 |
rewrite <- CRmult_assoc. rewrite CRmult_Qmult. |
| 1788 |
setoid_replace (` (Qpos_inv q) * ` q)%Q with 1%Q. |
| 1789 |
apply CRmult_1_l. simpl. |
| 1790 |
rewrite Qmult_comm, Qmult_inv_r. reflexivity. apply Qpos_nonzero. |
| 1791 |
Qed. |
| 1792 |
|
| 1793 |
Lemma QboundAbs_mult : forall (a b : Q) (c : Qpos), |
| 1794 |
-(`c*`c) <= QboundAbs c a * QboundAbs c b. |
| 1795 |
Proof. |
| 1796 |
intros. destruct (Qlt_le_dec 0 a). |
| 1797 |
- assert (-`c <= QboundAbs c b) by apply Qmax_ub_l. |
| 1798 |
apply (Qmult_le_compat_r _ _ (QboundAbs c a)) in H. |
| 1799 |
rewrite (Qmult_comm (QboundAbs c b)) in H. |
| 1800 |
refine (Qle_trans _ _ _ _ H). |
| 1801 |
setoid_replace (- ` c * QboundAbs c a)%Q |
| 1802 |
with (-(` c * QboundAbs c a))%Q |
| 1803 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1804 |
apply Qopp_le_compat. apply Qmult_le_l. apply Qpos_ispos. |
| 1805 |
apply Qmax_lub. apply (Qle_trans _ 0). |
| 1806 |
apply (Qopp_le_compat 0), Qpos_nonneg. apply Qpos_nonneg. |
| 1807 |
apply Qmin_lb_l. |
| 1808 |
apply (Qle_trans _ (Qmin (`c) a)). |
| 1809 |
apply Qmin_glb. apply Qpos_nonneg. apply Qlt_le_weak, q. |
| 1810 |
apply Qmax_ub_r. |
| 1811 |
- rewrite <- (Qopp_involutive (QboundAbs c a * QboundAbs c b)). |
| 1812 |
apply Qopp_le_compat. |
| 1813 |
assert (QboundAbs c b <= `c)%Q. |
| 1814 |
{ apply Qmax_lub. apply (Qle_trans _ 0). |
| 1815 |
apply (Qopp_le_compat 0), Qpos_nonneg. apply Qpos_nonneg. |
| 1816 |
apply Qmin_lb_l. } |
| 1817 |
apply (Qmult_le_compat_r _ _ (-QboundAbs c a)) in H. |
| 1818 |
rewrite Qmult_comm in H. |
| 1819 |
setoid_replace (-(QboundAbs c a * QboundAbs c b))%Q |
| 1820 |
with (- QboundAbs c a * QboundAbs c b)%Q |
| 1821 |
by (unfold equiv, stdlib_rationals.Q_eq; ring). |
| 1822 |
apply (Qle_trans _ _ _ H). |
| 1823 |
apply Qmult_le_l. apply Qpos_ispos. |
| 1824 |
rewrite <- (Qopp_involutive (`c)). |
| 1825 |
apply Qopp_le_compat. apply Qmax_ub_l. |
| 1826 |
apply (Qopp_le_compat _ 0). |
| 1827 |
apply Qmax_lub. apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1828 |
apply (Qle_trans _ a). apply Qmin_lb_r. exact q. |
| 1829 |
Qed. |
| 1830 |
|
| 1831 |
Lemma CRmult_le_0_compat_bounded |
| 1832 |
: forall (a b : CR) (c : Qpos), |
| 1833 |
CRnonNeg b |
| 1834 |
-> CRnonNeg a |
| 1835 |
-> (forall e:Qpos, -`c <= approximate a e) |
| 1836 |
-> (forall e:Qpos, approximate a e <= `c) |
| 1837 |
-> (forall e:Qpos, -`c <= approximate b e) |
| 1838 |
-> (forall e:Qpos, approximate b e <= `c) |
| 1839 |
-> (0 <= CRmult_bounded c a b)%CR. |
| 1840 |
Proof. |
| 1841 |
intros a b c H0 H alower aupper blower bupper. |
| 1842 |
rewrite CRmult_uncurry_eq. |
| 1843 |
intro e. |
| 1844 |
simpl. unfold Cap_raw;simpl. |
| 1845 |
rewrite Qplus_0_r. unfold Qmult_modulus. |
| 1846 |
destruct (Qlt_le_dec (`c*`c) (`e)). |
| 1847 |
apply (Qle_trans _ (-(`c*`c))). |
| 1848 |
apply Qopp_le_compat, Qlt_le_weak, q. |
| 1849 |
apply QboundAbs_mult. |
| 1850 |
specialize (H ((1 # 2) * ((1 # 2) * e) * Qpos_inv c)%Qpos). |
| 1851 |
specialize (H0 ((1 # 2) * ((1 # 2) * e) * Qpos_inv c)%Qpos). |
| 1852 |
apply Qle_minus_iff in H. rewrite Qopp_involutive in H. |
| 1853 |
apply Qle_minus_iff in H0. rewrite Qopp_involutive in H0. |
| 1854 |
apply (Qmult_le_0_compat _ _ H) in H0. clear H. |
| 1855 |
rewrite Qmult_plus_distr_r in H0. |
| 1856 |
rewrite Qmult_plus_distr_l, Qmult_plus_distr_l in H0. |
| 1857 |
assert (forall i j k l:Q, 0 <= i + j + (k + l) -> -(j+k+l) <= i). |
| 1858 |
{ intros. apply (Qplus_le_r _ _ (j+k+l)). |
| 1859 |
ring_simplify. |
| 1860 |
rewrite <- Qplus_assoc, (Qplus_comm i) in H. |
| 1861 |
rewrite Qplus_assoc in H. exact H. } |
| 1862 |
apply H in H0. clear H. |
| 1863 |
simpl in H0. |
| 1864 |
assert (forall i j : Q, i<=j -> Qmax i j == j)%Q as elim_max. |
| 1865 |
{ intros. apply (Qle_max_r i j), H. } |
| 1866 |
assert (forall i j : Q, j<=i -> Qmin i j == j)%Q as elim_min. |
| 1867 |
{ intros. apply (Qle_min_r i j), H. } |
| 1868 |
rewrite elim_min, elim_min, elim_max, elim_max. |
| 1869 |
refine (Qle_trans _ _ _ _ H0). |
| 1870 |
apply Qopp_le_compat. |
| 1871 |
apply (Qle_trans _ ((1#3)*`e + (1#3)*`e + (1#3)*`e)). |
| 1872 |
2: ring_simplify; apply Qle_refl. |
| 1873 |
apply Qplus_le_compat. apply Qplus_le_compat. |
| 1874 |
- apply (Qle_trans _ _ _ (Qle_Qabs _)). |
| 1875 |
rewrite Qabs_Qmult. |
| 1876 |
rewrite Qmult_comm. |
| 1877 |
apply (Qle_trans _ (`c * Qabs ((1 # 2) * ((1 # 2) * ` e) * / ` c))). |
| 1878 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1879 |
pose proof (QboundAbs_abs c (approximate b |
| 1880 |
((1 # 2) * ((1 # 2) * e) * Qpos_inv c)%Qpos)) as H. |
| 1881 |
simpl in H. rewrite elim_min, elim_max in H. rewrite H. clear H. |
| 1882 |
apply Qmin_lb_r. |
| 1883 |
apply blower. apply bupper. |
| 1884 |
rewrite Qmult_comm, Qabs_pos, <- Qmult_assoc. |
| 1885 |
rewrite (Qmult_comm (/`c)), Qmult_inv_r, Qmult_1_r. |
| 1886 |
2: apply Qpos_nonzero. rewrite Qmult_assoc. |
| 1887 |
apply Qmult_le_r. apply Qpos_ispos. discriminate. |
| 1888 |
apply Qmult_le_0_compat. |
| 1889 |
apply Qmult_le_0_compat. discriminate. |
| 1890 |
apply Qmult_le_0_compat. discriminate. |
| 1891 |
apply Qpos_nonneg. apply Qlt_le_weak, Qinv_lt_0_compat, Qpos_ispos. |
| 1892 |
- apply (Qle_trans _ _ _ (Qle_Qabs _)). |
| 1893 |
rewrite Qabs_Qmult. |
| 1894 |
apply (Qle_trans _ (`c * Qabs ((1 # 2) * ((1 # 2) * ` e) * / ` c))). |
| 1895 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 1896 |
pose proof (QboundAbs_abs c (approximate a |
| 1897 |
((1 # 2) * ((1 # 2) * e) * Qpos_inv c)%Qpos)). |
| 1898 |
simpl in H. rewrite elim_min, elim_max in H. |
| 1899 |
rewrite H. clear H. |
| 1900 |
apply Qmin_lb_r. apply alower. apply aupper. |
| 1901 |
rewrite Qmult_comm, Qabs_pos, <- Qmult_assoc. |
| 1902 |
rewrite (Qmult_comm (/`c)), Qmult_inv_r, Qmult_1_r. |
| 1903 |
2: apply Qpos_nonzero. rewrite Qmult_assoc. |
| 1904 |
apply Qmult_le_r. apply Qpos_ispos. discriminate. |
| 1905 |
apply Qmult_le_0_compat. |
| 1906 |
apply Qmult_le_0_compat. discriminate. |
| 1907 |
apply Qmult_le_0_compat. discriminate. |
| 1908 |
apply Qpos_nonneg. apply Qlt_le_weak, Qinv_lt_0_compat, Qpos_ispos. |
| 1909 |
- apply (Qle_trans _ ((1#16)*(`e*/`c*/`c)*`e)). |
| 1910 |
ring_simplify. apply Qle_refl. apply Qmult_le_r. |
| 1911 |
apply Qpos_ispos. apply (Qle_trans _ ((1#16)*(1#1))). |
| 1912 |
2: discriminate. |
| 1913 |
apply Qmult_le_l. reflexivity. apply Qle_shift_div_r. |
| 1914 |
apply Qpos_ispos. apply Qle_shift_div_r. apply Qpos_ispos. |
| 1915 |
rewrite Qmult_1_l. exact q. |
| 1916 |
- apply blower. |
| 1917 |
- apply alower. |
| 1918 |
- apply bupper. |
| 1919 |
- apply aupper. |
| 1920 |
- intro e. simpl. unfold Cap_raw. simpl. |
| 1921 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1922 |
rewrite <- Qle_minus_iff. apply alower. |
| 1923 |
- intro e. simpl. unfold Cap_raw. simpl. |
| 1924 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1925 |
rewrite <- Qle_minus_iff. apply aupper. |
| 1926 |
Qed. |
| 1927 |
|
| 1928 |
Lemma CRmult_le_0_compat : forall a b : CR, |
| 1929 |
(0 <= a)%CR -> (0 <= b)%CR -> (0 <= a*b)%CR. |
| 1930 |
Proof. |
| 1931 |
intros. |
| 1932 |
pose (Qpos_max (CR_b (1#1) a) (CR_b (1#1) b)) as c. |
| 1933 |
assert (' (- ` c)%Q <= a)%CR as alower. |
| 1934 |
{ apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) a))%Q)). |
| 1935 |
2: apply (CR_b_lowerBound _ _). |
| 1936 |
apply CRle_Qle. apply Qopp_le_compat, Qpos_max_ub_l. } |
| 1937 |
assert (a <= '(` c)%Q)%CR as aupper. |
| 1938 |
{ apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) a))) _ (CR_b_upperBound _ _)). |
| 1939 |
apply CRle_Qle. apply Qpos_max_ub_l. } |
| 1940 |
assert (' (- ` c)%Q <= b)%CR as blower. |
| 1941 |
{ apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) b))%Q)). |
| 1942 |
2: apply (CR_b_lowerBound _ _). |
| 1943 |
apply CRle_Qle. apply Qopp_le_compat, Qpos_max_ub_r. } |
| 1944 |
assert (b <= '(` c)%Q)%CR as bupper. |
| 1945 |
{ apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) b))) _ (CR_b_upperBound _ _)). |
| 1946 |
apply CRle_Qle. apply Qpos_max_ub_r. } |
| 1947 |
unfold CRle in H0. |
| 1948 |
rewrite CRopp_0, CRplus_0_r in H0. |
| 1949 |
unfold CRle in H. |
| 1950 |
rewrite CRopp_0, CRplus_0_r in H. |
| 1951 |
rewrite <- (@CRboundAbs_Eq c a) in H. |
| 1952 |
2: exact alower. 2: exact aupper. |
| 1953 |
rewrite <- (@CRboundAbs_Eq c b) in H0. |
| 1954 |
2: exact blower. 2: exact bupper. |
| 1955 |
rewrite <- (CRmult_bounded_mult c). |
| 1956 |
2: exact blower. 2: exact bupper. |
| 1957 |
change (0 <= ucFun2 (CRmult_bounded c) a b)%CR. |
| 1958 |
rewrite <- (@CRboundAbs_Eq c a). |
| 1959 |
rewrite <- (@CRboundAbs_Eq c b). |
| 1960 |
apply (CRmult_le_0_compat_bounded |
| 1961 |
(CRboundAbs c a) (CRboundAbs c b) c). |
| 1962 |
- exact H0. |
| 1963 |
- exact H. |
| 1964 |
- intros. apply Qmax_ub_l. |
| 1965 |
- intros. simpl. apply Qmax_lub. |
| 1966 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1967 |
apply Qpos_nonneg. apply Qmin_lb_l. |
| 1968 |
- intros. apply Qmax_ub_l. |
| 1969 |
- intros. simpl. apply Qmax_lub. |
| 1970 |
apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg. |
| 1971 |
apply Qpos_nonneg. apply Qmin_lb_l. |
| 1972 |
- exact blower. |
| 1973 |
- exact bupper. |
| 1974 |
- exact alower. |
| 1975 |
- exact aupper. |
| 1976 |
Qed. |
| 1977 |
|
| 1978 |
Lemma CRmult_lt_0_compat : forall a b : CR, |
| 1979 |
(0 < a)%CR -> (0 < b)%CR -> (0 < a*b)%CR. |
| 1980 |
Proof. |
| 1981 |
intros a b [q H] [r H0]. exists (q*r). |
| 1982 |
rewrite CRopp_0, CRplus_0_r. |
| 1983 |
rewrite CRopp_0, CRplus_0_r in H. |
| 1984 |
rewrite CRopp_0, CRplus_0_r in H0. |
| 1985 |
pose proof (CRle_scale ('`r) b q) as [H1 _]. |
| 1986 |
specialize (H1 H0). |
| 1987 |
rewrite <- CRmult_scale in H1. |
| 1988 |
rewrite CRmult_Qmult in H1. |
| 1989 |
apply (CRle_trans H1). |
| 1990 |
apply (CRplus_le_r _ _ (-scale (`q) b)%CR). |
| 1991 |
rewrite CRplus_opp. |
| 1992 |
rewrite <- CRmult_scale. |
| 1993 |
setoid_replace (a * b - ' ` q * b)%CR with ((a-'`q)*b)%CR |
| 1994 |
by (unfold equiv, msp_Equiv; ring). |
| 1995 |
apply CRmult_le_0_compat. |
| 1996 |
apply (CRplus_le_l _ _ ('`q)%CR). ring_simplify. exact H. |
| 1997 |
apply (@CRle_trans _ ('`r)%CR). |
| 1998 |
apply CRle_Qle. apply Qpos_nonneg. exact H0. |
| 1999 |
Qed. |
| 2000 |
|
| 2001 |
Lemma CRmult_lt_r : forall (x y z: CR), |
| 2002 |
(0 < z)%CR -> prod (x < y -> x*z < y*z)%CR |
| 2003 |
(x*z < y*z -> x < y)%CR. |
| 2004 |
Proof. |
| 2005 |
assert (forall (x y z: CR), (0 < z)%CR -> (x < y -> x*z < y*z)%CR). |
| 2006 |
{ intros. |
| 2007 |
pose proof (@CRplus_lt_r x y (-x)%CR) as [H1 _]. |
| 2008 |
apply H1 in H0. clear H1. |
| 2009 |
apply (CRltT_wd (CRplus_opp x) (reflexivity (y-x)%CR)) in H0. |
| 2010 |
apply (CRmult_lt_0_compat _ _ H) in H0. |
| 2011 |
pose proof (@CRplus_lt_r 0%CR (z*(y-x))%CR (x*z)%CR) as [H1 _]. |
| 2012 |
apply H1 in H0. clear H1. |
| 2013 |
assert (z*(y-x)+x*z == y*z)%CR by ring. |
| 2014 |
pose proof (CRltT_wd (CRplus_0_l (x*z)%CR) H1). |
| 2015 |
apply H2 in H0. exact H0. } |
| 2016 |
split. apply X, H. |
| 2017 |
intros. (* Divide by z in H0. *) |
| 2018 |
pose proof (CRinv_0_lt_compat _ (inr H) H). |
| 2019 |
specialize (X (x*z)%CR (y*z)%CR _ H1 H0). |
| 2020 |
assert (x * z * CRinvT z (inr H) == x)%CR. |
| 2021 |
{ rewrite CRmult_assoc, CRmult_inv_r. apply CRmult_1_r. } |
| 2022 |
assert (y * z * CRinvT z (inr H) == y)%CR. |
| 2023 |
{ rewrite CRmult_assoc, CRmult_inv_r. apply CRmult_1_r. } |
| 2024 |
apply (CRltT_wd H2 H3) in X. exact X. |
| 2025 |
Qed. |
| 2026 |
|
| 2027 |
Lemma CRmult_lt_l (x y z: CR): |
| 2028 |
(0 < z)%CR -> prod (x < y -> z*x < z*y)%CR |
| 2029 |
(z*x < z*y -> x < y)%CR. |
| 2030 |
Proof. |
| 2031 |
split. |
| 2032 |
- intros. |
| 2033 |
apply (CRltT_wd (CRmult_comm x z) (CRmult_comm y z)). |
| 2034 |
pose proof (CRmult_lt_r x y z H) as [H1 _]. |
| 2035 |
apply H1, H0. |
| 2036 |
- intros. |
| 2037 |
pose proof (CRmult_lt_r x y z H) as [_ H1]. |
| 2038 |
apply H1. clear H1. |
| 2039 |
apply (CRltT_wd (CRmult_comm z x) (CRmult_comm z y)). |
| 2040 |
apply H0. |
| 2041 |
Qed. |
| 2042 |
|
| 2043 |
Lemma CRmult_le_compat_l : forall (x y z: CR), |
| 2044 |
(0 <= z -> x <= y -> z*x <= z*y)%CR. |
| 2045 |
Proof. |
| 2046 |
intros. pose proof (@CRplus_le_r x y (-x)%CR) as [H1 _]. |
| 2047 |
specialize (H1 H0). rewrite CRplus_opp in H1. |
| 2048 |
apply (CRmult_le_0_compat _ _ H) in H1. |
| 2049 |
pose proof (@CRplus_le_l 0%CR (z*(y-x))%CR (x*z)%CR) as [H2 _]. |
| 2050 |
specialize (H2 H1). ring_simplify in H2. |
| 2051 |
rewrite CRmult_comm in H2. exact H2. |
| 2052 |
Qed. |
| 2053 |
|
| 2054 |
Lemma CRmult_lt_0_weaken |
| 2055 |
: forall (x y : CR), |
| 2056 |
(0 < x * y -> 0 <= y -> 0 < x)%CR. |
| 2057 |
Proof. |
| 2058 |
intros. |
| 2059 |
pose proof (CRlt_Qlt 0 1 eq_refl) as zeroLtOne. |
| 2060 |
destruct (CRlt_linear 0%CR x 1%CR zeroLtOne) as [H3|H3]. |
| 2061 |
- exact H3. |
| 2062 |
- clear zeroLtOne. |
| 2063 |
(* Prove that x*y <= y, then 0 < y and then 0 < x. *) |
| 2064 |
apply CRlt_le_weak in H3. |
| 2065 |
pose proof (CRmult_le_compat_l x 1%CR y H0 H3) as H1. |
| 2066 |
rewrite CRmult_1_r in H1. |
| 2067 |
rewrite CRmult_comm in H1. |
| 2068 |
apply (@CRlt_le_trans 0%CR (x*y) y H) in H1. |
| 2069 |
assert (0 == 0*y)%CR by ring. |
| 2070 |
apply (CRltT_wd H2 (reflexivity _)) in H. clear H2. |
| 2071 |
apply (CRmult_lt_r 0%CR x y). exact H1. exact H. |
| 2072 |
Qed. |
| 2073 |
|
| 2074 |
Lemma CRmult_lt_0_cancel_l : forall a b : CR, |
| 2075 |
(0 < a*b)%CR -> prod (a≶0) (b≶0). |
| 2076 |
Proof. |
| 2077 |
pose proof (CRlt_Qlt 0 1 eq_refl). |
| 2078 |
intros. |
| 2079 |
destruct (CRlt_linear _ a _ H) as [H1|H1]. |
| 2080 |
- split. right. apply CR_lt_ltT, H1. |
| 2081 |
(* Divide by a *) |
| 2082 |
right. |
| 2083 |
pose proof (CRinv_0_lt_compat _ (inr H1) H1). |
| 2084 |
pose proof (CRmult_lt_l 0%CR (a*b)%CR _ H2) as [H3 _]. |
| 2085 |
apply H3 in H0. clear H3 H2. |
| 2086 |
assert (CRinvT a (inr H1) * (a * b) == b)%CR. |
| 2087 |
rewrite <- CRmult_assoc. rewrite <- (CRmult_comm a), CRmult_inv_r. |
| 2088 |
apply CRmult_1_l. |
| 2089 |
assert (CRinvT a (inr H1) * 0 == 0)%CR by ring. |
| 2090 |
apply (CRltT_wd H3 H2) in H0. apply CR_lt_ltT, H0. |
| 2091 |
- destruct (CRlt_linear _ b _ H0) as [H2|H2]. |
| 2092 |
+ split. 2: right; apply CR_lt_ltT, H2. right. |
| 2093 |
pose proof (CRmult_lt_r 0%CR a b H2) as [_ H3]. |
| 2094 |
apply CR_lt_ltT, H3. |
| 2095 |
assert (0 == 0 * b)%CR by ring. |
| 2096 |
apply (CRltT_wd H4 (reflexivity _)), H0. |
| 2097 |
+ (* Both a and b are negative *) |
| 2098 |
assert (a*b == (-a)*(-b))%CR by ring. |
| 2099 |
apply (CRltT_wd (reflexivity 0%CR) H3) in H0. clear H3. |
| 2100 |
assert (0 <= -b)%CR. |
| 2101 |
{ apply (CRplus_le_l _ _ b). rewrite CRplus_opp, CRplus_0_r. |
| 2102 |
apply CRle_not_lt. intro abs. |
| 2103 |
pose proof (CRmult_lt_r 1 a b abs)%CR as [_ H3]. |
| 2104 |
apply (CRlt_irrefl a). |
| 2105 |
apply (CRlt_trans _ _ _ H1), H3. |
| 2106 |
assert (b == 1 * b)%CR by ring. |
| 2107 |
apply (CRltT_wd H4 (reflexivity _)), H2. } |
| 2108 |
pose proof (CRmult_lt_0_weaken _ _ H0 H3). |
| 2109 |
split; left. |
| 2110 |
apply CR_lt_ltT, (CRopp_lt_cancel a 0%CR). |
| 2111 |
pose proof CRopp_0. symmetry in H5. |
| 2112 |
apply (CRltT_wd H5 (reflexivity _)), H4. |
| 2113 |
pose proof (@CRplus_lt_r b 0%CR (-b)%CR) as [_ H5]. |
| 2114 |
apply CR_lt_ltT, H5. clear H5. |
| 2115 |
assert (-b == 0-b)%CR by ring. |
| 2116 |
pose proof (CRplus_opp b). symmetry in H6. |
| 2117 |
apply (CRltT_wd H6 H5). clear H6 H5. |
| 2118 |
pose proof (CRmult_lt_l 0 (-b) (-a) H4)%CR as [_ H5]. |
| 2119 |
apply H5. clear H5. |
| 2120 |
assert (0 == (-a) * 0)%CR by ring. |
| 2121 |
apply (CRltT_wd H5 (reflexivity _)), H0. |
| 2122 |
Qed. |
| 2123 |
|
| 2124 |
Lemma CRmult_lt_cancel_l : forall a b c : CR, |
| 2125 |
(a*b < a*c)%CR -> (prod (a≶0) (b≶c)). |
| 2126 |
Proof. |
| 2127 |
intros. |
| 2128 |
pose proof (CRplus_lt_l (a*b) (a*c) (-a*b))%CR as [H0 _]. |
| 2129 |
specialize (H0 H). |
| 2130 |
assert (- a * b + a * b == 0)%CR by ring. |
| 2131 |
assert (- a * b + a * c == a*(c-b))%CR by ring. |
| 2132 |
apply (CRltT_wd H1 H2) in H0. clear H1 H2. |
| 2133 |
apply CRmult_lt_0_cancel_l in H0. destruct H0. |
| 2134 |
split. exact a0. destruct a1. |
| 2135 |
- right. apply CR_lt_ltT in H0. |
| 2136 |
pose proof (CRplus_lt_l (c-b) (0) b)%CR as [H1 _]. |
| 2137 |
specialize (H1 H0). |
| 2138 |
assert (b + (c - b) == c)%CR by ring. |
| 2139 |
assert (b + 0 == b)%CR by ring. |
| 2140 |
apply (CRltT_wd H2 H3) in H1. apply CR_lt_ltT, H1. |
| 2141 |
- left. apply CR_lt_ltT in H0. |
| 2142 |
pose proof (CRplus_lt_l 0 (c-b) b)%CR as [H1 _]. |
| 2143 |
specialize (H1 H0). |
| 2144 |
assert (b + (c - b) == c)%CR by ring. |
| 2145 |
assert (b + 0 == b)%CR by ring. |
| 2146 |
apply (CRltT_wd H3 H2) in H1. apply CR_lt_ltT, H1. |
| 2147 |
Qed. |
| 2148 |
|
| 2149 |
Lemma CRmult_le_0_reg_l : forall a b : CR, |
| 2150 |
~((0 < a)%CR -> False) -> (0 <= a * b)%CR -> (0 <= b)%CR. |
| 2151 |
Proof. |
| 2152 |
intros. |
| 2153 |
apply CRle_not_lt. intro abs. |
| 2154 |
contradict H; intro H. |
| 2155 |
rewrite <- CRopp_0 in H0. |
| 2156 |
setoid_replace (a*b)%CR with (-(a*-b))%CR in H0 |
| 2157 |
by (unfold equiv, msp_Equiv; ring). |
| 2158 |
apply CRopp_le_cancel in H0. |
| 2159 |
pose proof (CRle_not_lt (a*-b)%CR 0%CR) as [H1 _]. |
| 2160 |
specialize (H1 H0). contradict H1. clear H0. |
| 2161 |
apply CRmult_lt_0_compat. |
| 2162 |
exact H. |
| 2163 |
apply (CRltT_wd CRopp_0 (reflexivity _)). |
| 2164 |
apply CRopp_lt_compat, abs. |
| 2165 |
Qed. |
| 2166 |
|
| 2167 |
Lemma CRmult_eq_0_reg_l : forall x y : CR, |
| 2168 |
(~(y == 0)%CR) |
| 2169 |
-> (x*y == 0)%CR |
| 2170 |
-> (x == 0)%CR. |
| 2171 |
Proof. |
| 2172 |
intros. apply ball_stable. |
| 2173 |
change (~~(x==0)%CR). |
| 2174 |
intros abs. |
| 2175 |
rewrite CReq_not_apart in abs. |
| 2176 |
contradict abs; intro xap0. |
| 2177 |
rewrite CReq_not_apart in H. |
| 2178 |
contradict H; intro yap0. |
| 2179 |
pose proof CRopp_0 as opp0. |
| 2180 |
symmetry in opp0. |
| 2181 |
destruct xap0. |
| 2182 |
- pose proof (CRopp_opp x). |
| 2183 |
symmetry in H. |
| 2184 |
apply (CRltT_wd H opp0) in c. clear H. |
| 2185 |
apply CRopp_lt_cancel in c. |
| 2186 |
destruct yap0. |
| 2187 |
+ pose proof (CRopp_opp y). |
| 2188 |
symmetry in H. |
| 2189 |
apply (CRltT_wd H opp0) in c0. clear H. |
| 2190 |
apply CRopp_lt_cancel in c0. |
| 2191 |
pose proof (CRmult_lt_0_compat _ _ c c0) as H. |
| 2192 |
revert H. |
| 2193 |
apply CRle_not_lt. |
| 2194 |
setoid_replace (-x*-y)%CR with (x*y)%CR |
| 2195 |
by (unfold equiv, msp_Equiv; ring). |
| 2196 |
rewrite H0. apply CRle_refl. |
| 2197 |
+ pose proof (CRmult_lt_0_compat _ _ c c0) as H. |
| 2198 |
revert H. |
| 2199 |
apply CRle_not_lt. |
| 2200 |
rewrite opp0. |
| 2201 |
setoid_replace (-x*y)%CR with (-(x*y))%CR |
| 2202 |
by (unfold equiv, msp_Equiv; ring). |
| 2203 |
apply CRopp_le_compat. |
| 2204 |
rewrite H0. apply CRle_refl. |
| 2205 |
- destruct yap0. |
| 2206 |
+ pose proof (CRopp_opp y). |
| 2207 |
symmetry in H. |
| 2208 |
apply (CRltT_wd H opp0) in c0. clear H. |
| 2209 |
apply CRopp_lt_cancel in c0. |
| 2210 |
pose proof (CRmult_lt_0_compat _ _ c c0) as H. |
| 2211 |
revert H. |
| 2212 |
apply CRle_not_lt. |
| 2213 |
setoid_replace (x*-y)%CR with (-(x*y))%CR |
| 2214 |
by (unfold equiv, msp_Equiv; ring). |
| 2215 |
rewrite H0, <- opp0. apply CRle_refl. |
| 2216 |
+ pose proof (CRmult_lt_0_compat _ _ c c0) as H. |
| 2217 |
revert H. |
| 2218 |
apply CRle_not_lt. |
| 2219 |
rewrite H0. apply CRle_refl. |
| 2220 |
Qed. |
| 2221 |
|
| 2222 |
Lemma CRsquare_pos : forall x : CR, (0 <= x*x)%CR. |
| 2223 |
Proof. |
| 2224 |
(* Goal is a negation, use excluded middle x is positive or not. *) |
| 2225 |
intros x. |
| 2226 |
apply CRle_not_lt. intro abs. |
| 2227 |
assert (~(0 <= x)%CR) as H. |
| 2228 |
{ intro J. revert abs. |
| 2229 |
apply CRle_not_lt. |
| 2230 |
exact (CRmult_le_0_compat x x J J). } |
| 2231 |
contradict H. apply CRle_not_lt. |
| 2232 |
intro H. |
| 2233 |
revert abs. |
| 2234 |
apply CRle_not_lt. |
| 2235 |
apply CRlt_le_weak in H. |
| 2236 |
setoid_replace (x*x)%CR with (-x*-x)%CR |
| 2237 |
by (unfold equiv, msp_Equiv; ring). |
| 2238 |
apply CRmult_le_0_compat. |
| 2239 |
rewrite <- CRopp_0. |
| 2240 |
apply CRopp_le_compat, H. |
| 2241 |
rewrite <- CRopp_0. |
| 2242 |
apply CRopp_le_compat, H. |
| 2243 |
Qed. |
| 2244 |
|
| 2245 |
|
| 2246 |
#[global] |
| 2247 |
Instance: StrongSetoid_BinaryMorphism CRmult. |
| 2248 |
Proof. |
| 2249 |
split; try apply _. |
| 2250 |
assert (forall a b c d : CR, (a*b < c*d)%CR -> (sum (a≶c) (b≶d))). |
| 2251 |
{ intros. |
| 2252 |
pose proof (@CRlt_linear _ (a*d)%CR _ H) as [H0|H0]. |
| 2253 |
right. apply CRmult_lt_cancel_l in H0. apply H0. |
| 2254 |
left. apply (@CRltT_wd (a*d) (d*a) (CRmult_comm _ _) |
| 2255 |
(c*d) (d*c) (CRmult_comm _ _)) in H0. |
| 2256 |
apply CRmult_lt_cancel_l in H0. apply H0. } |
| 2257 |
intros x₁ y₁ x₂ y₂ E. |
| 2258 |
destruct E. apply CR_lt_ltT in H. apply X in H. |
| 2259 |
destruct H. left. exact a. right. exact a. |
| 2260 |
apply CR_lt_ltT, X in H. |
| 2261 |
destruct H. left. |
| 2262 |
destruct a. right. exact H. left. exact H. |
| 2263 |
right. destruct a. right. exact H. left. exact H. |
| 2264 |
Qed. |
| 2265 |
|
| 2266 |
#[global] |
| 2267 |
Instance: FullPseudoOrder CRle CRlt. |
| 2268 |
Proof. |
| 2269 |
split. |
| 2270 |
split; try apply _. |
| 2271 |
- intros x y [E1 E2]. |
| 2272 |
apply CR_lt_ltT in E1. apply CR_lt_ltT in E2. |
| 2273 |
exact (@CRlt_irrefl x (@CRlt_trans x y x E1 E2)). |
| 2274 |
- intros x y E z. |
| 2275 |
apply CR_lt_ltT in E. |
| 2276 |
pose proof (CRlt_linear _ z _ E). destruct H. |
| 2277 |
left. apply CR_lt_ltT. exact c. |
| 2278 |
right. apply CR_lt_ltT. exact c. |
| 2279 |
- intros x y; split. |
| 2280 |
intro E. exact E. intro E. exact E. |
| 2281 |
- split. intros. |
| 2282 |
pose proof (CRle_not_lt x y) as [H0 _]. specialize (H0 H). |
| 2283 |
intro abs. apply CR_lt_ltT in abs. apply H0, abs. |
| 2284 |
intros. apply CRle_not_lt. intro abs. |
| 2285 |
apply H. apply CR_lt_ltT. exact abs. |
| 2286 |
Qed. |
| 2287 |
|
| 2288 |
#[global] |
| 2289 |
Instance: FullPseudoSemiRingOrder CRle CRlt. |
| 2290 |
Proof. |
| 2291 |
apply rings.from_full_pseudo_ring_order. |
| 2292 |
- repeat (split; try apply _). |
| 2293 |
intros. apply CR_lt_ltT. apply CRplus_lt_l. |
| 2294 |
apply CR_lt_ltT. exact H. |
| 2295 |
- split; try apply _. |
| 2296 |
intros. apply (strong_binary_extensionality CRmult), H. |
| 2297 |
- intros. apply CR_lt_ltT. apply CRmult_lt_0_compat. |
| 2298 |
apply CR_lt_ltT, H. |
| 2299 |
apply CR_lt_ltT, H0. |
| 2300 |
Qed. |
| 2301 |
|
| 2302 |
#[global] |
| 2303 |
Program Instance CRinv: Recip CR := λ x, CRinvT x _. |
| 2304 |
Next Obligation. apply CR_apart_apartT. now destruct x. Qed. |
| 2305 |
|
| 2306 |
#[global] |
| 2307 |
Instance: Field CR. |
| 2308 |
Proof. |
| 2309 |
split; try apply _. |
| 2310 |
- apply CR_apart_apartT. right. |
| 2311 |
exists (1#1)%Qpos. simpl. rewrite CRopp_0, CRplus_0_r. |
| 2312 |
apply CRle_refl. |
| 2313 |
- split; try apply _. |
| 2314 |
intros [x Px] [y Py] E. |
| 2315 |
unfold recip, CRinv. simpl. |
| 2316 |
apply (CRinvT_wd (CRinv_obligation_1 (x ↾ Px)) |
| 2317 |
(CRinv_obligation_1 (y ↾ Py))). |
| 2318 |
apply E. |
| 2319 |
- intros x. |
| 2320 |
unfold recip. simpl. |
| 2321 |
destruct x as [x xnz]. apply CRmult_inv_r. |
| 2322 |
Qed. |
| 2323 |
|
| 2324 |
#[global] |
| 2325 |
Instance: StrongSetoid_Morphism inject_Q_CR. |
| 2326 |
Proof. |
| 2327 |
apply strong_setoids.dec_strong_morphism. |
| 2328 |
split; try apply _. |
| 2329 |
Qed. |
| 2330 |
|
| 2331 |
#[global] |
| 2332 |
Instance: StrongSemiRing_Morphism inject_Q_CR. |
| 2333 |
Proof. |
| 2334 |
repeat (split; try apply _); intros; try reflexivity; symmetry. |
| 2335 |
now apply CRplus_Qplus. |
| 2336 |
now apply CRmult_Qmult. |
| 2337 |
Qed. |
| 2338 |
|
| 2339 |
#[global] |
| 2340 |
Instance: StrongInjective inject_Q_CR. |
| 2341 |
Proof. |
| 2342 |
repeat (split; try apply _); intros. |
| 2343 |
apply CR_apart_apartT. |
| 2344 |
now apply Qap_CRap. |
| 2345 |
Qed. |
| 2346 |
|
| 2347 |
#[global] |
| 2348 |
Instance: OrderEmbedding inject_Q_CR. |
| 2349 |
Proof. repeat (split; try apply _); now apply CRle_Qle. Qed. |
| 2350 |
|
| 2351 |
#[global] |
| 2352 |
Instance: StrictOrderEmbedding inject_Q_CR. |
| 2353 |
Proof. split; apply _. Qed. |
| 2354 |
|