| 1 |
(* |
| 2 |
Copyright © 2008 Russell O’Connor |
| 3 |
|
| 4 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 5 |
this proof and associated documentation files (the "Proof"), to deal in |
| 6 |
the Proof without restriction, including without limitation the rights to |
| 7 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 8 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 9 |
subject to the following conditions: |
| 10 |
|
| 11 |
The above copyright notice and this permission notice shall be included in all |
| 12 |
copies or substantial portions of the Proof. |
| 13 |
|
| 14 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 16 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 17 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 18 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 19 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 20 |
*) |
| 21 |
|
| 22 |
Require Import CoRN.algebra.RSetoid. |
| 23 |
Require Import CoRN.metric2.Metric. |
| 24 |
Require Import CoRN.metric2.UniformContinuity. |
| 25 |
Require Export CoRN.model.totalorder.QposMinMax. |
| 26 |
Require Export CoRN.reals.fast.CRArith. |
| 27 |
Require Import CoRN.model.metric2.Qmetric. |
| 28 |
From Coq Require Import Qabs. |
| 29 |
Require Import CoRN.model.totalorder.QMinMax. |
| 30 |
Require Import CoRN.logic.Stability. |
| 31 |
|
| 32 |
Local Open Scope Q_scope. |
| 33 |
(** |
| 34 |
** Absolute Value |
| 35 |
*) |
| 36 |
Lemma Qabs_uc_prf : is_UniformlyContinuousFunction |
| 37 |
(Qabs:Q_as_MetricSpace -> Q_as_MetricSpace) Qpos2QposInf. |
| 38 |
Proof. |
| 39 |
intros e a b Hab. |
| 40 |
simpl in *. |
| 41 |
unfold Qball in *. |
| 42 |
rewrite <- AbsSmall_Qabs in *. |
| 43 |
apply Qabs_case. |
| 44 |
intros _. |
| 45 |
eapply Qle_trans;[|apply Hab]. |
| 46 |
apply Qabs_triangle_reverse. |
| 47 |
intros _. |
| 48 |
setoid_replace (- (Qabs a - Qabs b)) |
| 49 |
with (Qabs b - Qabs a) |
| 50 |
by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; ring). |
| 51 |
rewrite Qabs_Qminus in Hab. |
| 52 |
eapply Qle_trans;[|apply Hab]. |
| 53 |
apply Qabs_triangle_reverse. |
| 54 |
Qed. |
| 55 |
|
| 56 |
Local Open Scope uc_scope. |
| 57 |
|
| 58 |
Definition Qabs_uc : Q_as_MetricSpace --> Q_as_MetricSpace := |
| 59 |
Build_UniformlyContinuousFunction Qabs_uc_prf. |
| 60 |
|
| 61 |
Definition CRabs : CR --> CR := Cmap QPrelengthSpace Qabs_uc. |
| 62 |
|
| 63 |
Lemma CRabs_wd : Proper (@msp_eq CR ==> @msp_eq CR) CRabs. |
| 64 |
Proof. |
| 65 |
intros x y xyeq. apply Cmap_wd. |
| 66 |
reflexivity. rewrite xyeq. reflexivity. |
| 67 |
Qed. |
| 68 |
|
| 69 |
Lemma approximate_CRabs (x: CR) (e: Qpos): |
| 70 |
approximate (CRabs x) e = Qabs (approximate x e). |
| 71 |
Proof. reflexivity. Qed. |
| 72 |
|
| 73 |
Lemma inject_Q_CR_abs : forall q : Q, |
| 74 |
(CRabs (inject_Q_CR q) == inject_Q_CR (Qabs q))%CR. |
| 75 |
Proof. |
| 76 |
intros q. |
| 77 |
apply regFunEq_equiv. intros e1 e2. |
| 78 |
apply ball_refl, (Qpos_nonneg (e1+e2)). |
| 79 |
Qed. |
| 80 |
|
| 81 |
Lemma CRabs_AbsSmall : forall a b : CR, (CRabs b <= a)%CR <-> (-a <= b /\ b <= a)%CR. |
| 82 |
Proof. |
| 83 |
split. |
| 84 |
- intros. split. |
| 85 |
+ intro e. simpl. unfold Cap_raw. simpl. |
| 86 |
specialize (H e). simpl in H. |
| 87 |
unfold Cap_raw in H. simpl in H. |
| 88 |
apply (Qle_trans _ _ _ H). |
| 89 |
rewrite Qopp_involutive, Qplus_comm. |
| 90 |
apply Qplus_le_l. |
| 91 |
rewrite <- (Qopp_involutive (approximate b ((1#2)*e)%Qpos)) at 2. |
| 92 |
apply Qopp_le_compat. |
| 93 |
rewrite <- Qabs_opp. apply Qle_Qabs. |
| 94 |
+ intro e. simpl. unfold Cap_raw. simpl. |
| 95 |
specialize (H e). simpl in H. |
| 96 |
unfold Cap_raw in H. simpl in H. |
| 97 |
apply (Qle_trans _ _ _ H). |
| 98 |
apply Qplus_le_r, Qopp_le_compat, Qle_Qabs. |
| 99 |
- intros [H H0]. intro e. simpl. unfold Cap_raw. simpl. |
| 100 |
specialize (H e). simpl in H. |
| 101 |
unfold Cap_raw in H. simpl in H. |
| 102 |
specialize (H0 e). simpl in H0. |
| 103 |
unfold Cap_raw in H0. simpl in H0. |
| 104 |
apply (Qplus_le_l _ _ (Qabs (approximate b ((1 # 2) * e)%Qpos) + proj1_sig e)). |
| 105 |
simpl. ring_simplify. |
| 106 |
apply Qabs_Qle_condition. split. |
| 107 |
+ apply (Qplus_le_l _ _ (- approximate a ((1 # 2) * e)%Qpos)) in H. |
| 108 |
simpl in H. ring_simplify in H. ring_simplify. exact H. |
| 109 |
+ apply (Qplus_le_l _ _ (proj1_sig e + approximate b ((1 # 2) * e)%Qpos)) in H0. |
| 110 |
simpl in H0. ring_simplify in H0. exact H0. |
| 111 |
Qed. |
| 112 |
|
| 113 |
Local Open Scope CR_scope. |
| 114 |
|
| 115 |
Lemma CRabs_pos : forall x:CR, 0 <= x -> CRabs x == x. |
| 116 |
Proof. |
| 117 |
intros x H. apply CRle_antisym. split. |
| 118 |
- apply CRabs_AbsSmall. split. 2: apply CRle_refl. |
| 119 |
apply (@CRle_trans _ 0). 2: exact H. |
| 120 |
rewrite <- CRopp_0. apply CRopp_le_compat, H. |
| 121 |
- intro e. simpl. unfold Cap_raw; simpl. |
| 122 |
apply (Qle_trans _ 0). |
| 123 |
apply (Qopp_le_compat 0), Qpos_nonneg. |
| 124 |
rewrite <- Qle_minus_iff. apply Qle_Qabs. |
| 125 |
Qed. |
| 126 |
|
| 127 |
Lemma CRabs_0: CRabs 0 == 0. |
| 128 |
Proof. apply CRabs_pos, CRle_refl. Qed. |
| 129 |
|
| 130 |
Lemma CRabs_neg: forall x, x <= 0 -> CRabs x == - x. |
| 131 |
Proof. |
| 132 |
intros x H. apply CRle_antisym. split. |
| 133 |
- apply CRabs_AbsSmall. split. |
| 134 |
apply (CRplus_le_l _ _ (-x)). ring_simplify. |
| 135 |
apply CRle_refl. |
| 136 |
apply (@CRle_trans _ 0). exact H. |
| 137 |
rewrite <- CRopp_0. apply CRopp_le_compat, H. |
| 138 |
- intro e. simpl. unfold Cap_raw; simpl. |
| 139 |
apply (Qle_trans _ 0). |
| 140 |
apply (Qopp_le_compat 0), Qpos_nonneg. |
| 141 |
rewrite <- Qle_minus_iff, <- Qabs_opp. |
| 142 |
apply Qle_Qabs. |
| 143 |
Qed. |
| 144 |
|
| 145 |
Lemma CRabs_cases |
| 146 |
(P: CR -> Prop) |
| 147 |
{Pp: Proper (@msp_eq _ ==> iff) P} |
| 148 |
{Ps: forall x, Stable (P x)}: |
| 149 |
forall x, ((0 <= x -> P x) /\ (x <= 0 -> P (- x))) <-> P (CRabs x). |
| 150 |
Proof with auto. |
| 151 |
intros. |
| 152 |
apply from_DN. |
| 153 |
apply (DN_bind (CRle_dec x 0)). |
| 154 |
intro. |
| 155 |
apply DN_return. |
| 156 |
destruct H. |
| 157 |
rewrite (CRabs_neg _ c)... |
| 158 |
intuition. |
| 159 |
revert H. |
| 160 |
rewrite (proj2 (CRle_antisym x 0))... |
| 161 |
rewrite CRopp_0... |
| 162 |
rewrite (CRabs_pos _ c)... |
| 163 |
intuition. |
| 164 |
revert H. |
| 165 |
rewrite (proj2 (CRle_antisym x 0))... |
| 166 |
rewrite CRopp_0... |
| 167 |
Qed. |
| 168 |
|
| 169 |
Lemma CRabs_opp (x: CR): CRabs (-x) == CRabs x. |
| 170 |
Proof with auto. |
| 171 |
intros. |
| 172 |
apply from_DN. |
| 173 |
apply (DN_bind (CRle_dec x 0)). |
| 174 |
intros [A | B]; apply DN_return. |
| 175 |
rewrite (CRabs_neg _ A). |
| 176 |
apply CRabs_pos. |
| 177 |
change (-0 <= -x). |
| 178 |
apply -> CRle_opp... |
| 179 |
rewrite (CRabs_pos _ B). |
| 180 |
rewrite CRabs_neg. |
| 181 |
apply CRopp_opp. |
| 182 |
change (-x <= -0). |
| 183 |
apply -> CRle_opp... |
| 184 |
Qed. |
| 185 |
|
| 186 |
Lemma CRabs_nonneg (x: CR): 0 <= CRabs x. |
| 187 |
Proof. |
| 188 |
intro e. simpl. unfold Cap_raw; simpl. |
| 189 |
rewrite Qplus_0_r. apply (Qle_trans _ 0). |
| 190 |
apply (Qopp_le_compat 0), Qpos_nonneg. |
| 191 |
apply Qabs_nonneg. |
| 192 |
Qed. |
| 193 |
|
| 194 |
Lemma CRle_abs : forall x:CR, (x <= CRabs x)%CR. |
| 195 |
Proof. |
| 196 |
intros x e1. simpl. |
| 197 |
unfold Cap_raw. simpl. |
| 198 |
apply (Qle_trans _ (approximate x ((1 # 2) * e1)%Qpos + - approximate x ((1 # 2) * e1)%Qpos)). |
| 199 |
rewrite Qplus_opp_r. |
| 200 |
apply (Qopp_le_compat 0), Qpos_nonneg. |
| 201 |
apply Qplus_le_l. apply Qabs.Qle_Qabs. |
| 202 |
Qed. |
| 203 |
|
| 204 |
Lemma CRabs_scale (a : Q) (x : CR) : CRabs (scale a x) == scale (Qabs a) (CRabs x). |
| 205 |
Proof. |
| 206 |
apply lift_eq_complete with (f := uc_compose CRabs (scale a)) (g := uc_compose (scale (Qabs a)) CRabs). |
| 207 |
intros q e1 e2. |
| 208 |
rewrite Qplus_0_r. |
| 209 |
change (@ball Q_as_MetricSpace (proj1_sig e1 + proj1_sig e2) (Qabs (a * q)) (Qabs a * Qabs q)%Q). |
| 210 |
apply <- ball_eq_iff. apply Qball_0, Qabs_Qmult. |
| 211 |
apply (Qpos_ispos (e1+e2)). |
| 212 |
Qed. |
| 213 |
|
| 214 |
(* begin hide *) |
| 215 |
(* Another proof *) |
| 216 |
|
| 217 |
Lemma CRabs_scale' (a : Q) (x : CR) : CRabs (scale a x) == scale (Qabs a) (CRabs x). |
| 218 |
Proof. |
| 219 |
unfold CRabs, scale. setoid_rewrite <- fast_MonadLaw2. |
| 220 |
apply map_eq_complete. intro q. apply Qball_0, Qabs_Qmult. |
| 221 |
Qed. |
| 222 |
|
| 223 |
Lemma CRabs_triangle : forall (x y : CR), |
| 224 |
CRabs (x+y) <= CRabs x + CRabs y. |
| 225 |
Proof. |
| 226 |
intros. apply CRabs_AbsSmall. split. |
| 227 |
2: apply CRplus_le_compat; apply CRle_abs. |
| 228 |
rewrite CRopp_plus_distr. |
| 229 |
apply CRplus_le_compat; apply CRopp_le_cancel; |
| 230 |
rewrite CRopp_opp; rewrite <- CRabs_opp; apply CRle_abs. |
| 231 |
Qed. |
| 232 |
|
| 233 |
(* end hide *) |
| 234 |
|
| 235 |
Lemma CRabs_CRmult_Q (a : Q) (x : CR) : CRabs ('a * x) == '(Qabs a) * (CRabs x). |
| 236 |
Proof. rewrite !CRmult_scale. apply CRabs_scale. Qed. |
| 237 |
|
| 238 |
Definition CRdistance (x y: CR): CR := CRabs (x - y). |
| 239 |
|
| 240 |
Lemma CRdistance_CRle (r x y: CR): x - r <= y /\ y <= x + r <-> CRdistance x y <= r. |
| 241 |
Proof. |
| 242 |
intros. unfold CRdistance. |
| 243 |
rewrite CRabs_AbsSmall. |
| 244 |
simpl. |
| 245 |
rewrite (CRplus_le_l (x - r) y (r - y)). |
| 246 |
CRring_replace (r - y + (x - r)) (x - y). |
| 247 |
CRring_replace (r - y + y) r. |
| 248 |
rewrite (CRplus_le_l y (x + r) (-r - y)). |
| 249 |
CRring_replace (-r - y + y) (-r). |
| 250 |
CRring_replace (- r - y + (x + r)) (x - y). |
| 251 |
intuition. |
| 252 |
Qed. |
| 253 |
|
| 254 |
Lemma CRdistance_comm (x y: CR): CRdistance x y == CRdistance y x. |
| 255 |
Proof. |
| 256 |
unfold CRdistance. intros. |
| 257 |
CRring_replace (x - y) (-(y - x)). |
| 258 |
apply CRabs_opp. |
| 259 |
Qed. |
| 260 |
|
| 261 |
Lemma CRdistance_triangle : forall (x y z : CR), |
| 262 |
CRdistance x z <= CRdistance x y + CRdistance y z. |
| 263 |
Proof. |
| 264 |
intros. unfold CRdistance. |
| 265 |
setoid_replace (x-z) with (x-y + (y-z)) |
| 266 |
by (unfold canonical_names.equiv, msp_Equiv; ring). |
| 267 |
apply CRabs_triangle. |
| 268 |
Qed. |
| 269 |
|
| 270 |
Lemma regFunBall_e2 : forall (X: MetricSpace) (x y:Complete X) (e:Q), |
| 271 |
(forall d:Qpos, ball (proj1_sig d + e) |
| 272 |
(approximate x ((1#2)*d)%Qpos) |
| 273 |
(approximate y ((1#2)*d)%Qpos)) |
| 274 |
-> ball e x y. |
| 275 |
Proof. |
| 276 |
intros X x y e H. |
| 277 |
apply ball_closed. |
| 278 |
intros d dpos. |
| 279 |
setoid_replace (e + d)%Q |
| 280 |
with ((1#2)*((1#2)*d) |
| 281 |
+ ((1#2)*((1#2)*d) + e+(1#2)*((1#2)*d)) |
| 282 |
+ (1#2)*((1#2)*d))%Q |
| 283 |
by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring). |
| 284 |
apply (regFunBall_ball |
| 285 |
x y |
| 286 |
((1 # 2) * ((1#2)*d) + e + (1 # 2) * ((1#2)*d))%Q |
| 287 |
((1#2)*((1#2)*exist _ _ dpos))%Qpos |
| 288 |
((1#2)*((1#2)*exist _ _ dpos))%Qpos ). |
| 289 |
setoid_replace ((1 # 2) * ((1 # 2) * d) + e + (1 # 2) * ((1 # 2) * d))%Q |
| 290 |
with ((1 # 2) * d + e)%Q |
| 291 |
by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring). |
| 292 |
apply (H ((1#2)*(exist _ _ dpos))%Qpos). |
| 293 |
Qed. |
| 294 |
|
| 295 |
Lemma CRabs_ball : forall (x y : CR) (e:Q), |
| 296 |
ball e x y <-> (CRabs (x-y) <= 'e)%CR. |
| 297 |
Proof. |
| 298 |
assert (forall (x y:CR) e d, |
| 299 |
ball e x y -> |
| 300 |
(- proj1_sig d <= |
| 301 |
e + approximate x ((1 # 2) * d)%Qpos + - approximate y ((1 # 2) * d)%Qpos)%Q). |
| 302 |
{ intros. |
| 303 |
specialize (H ((1#2)*d)%Qpos ((1#2)*d)%Qpos). |
| 304 |
apply AbsSmall_Qabs in H. |
| 305 |
simpl (proj1_sig ((1 # 2) * d)%Qpos) in H. |
| 306 |
rewrite Qabs_Qminus in H. |
| 307 |
apply (Qle_trans _ _ _ (Qle_Qabs _)) in H. |
| 308 |
apply (Qplus_le_r _ _ (proj1_sig d + approximate y ((1#2)*d)%Qpos)). |
| 309 |
ring_simplify. |
| 310 |
setoid_replace ((1 # 2) * proj1_sig d + e + (1 # 2) * proj1_sig d)%Q |
| 311 |
with (proj1_sig d + e)%Q in H |
| 312 |
by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; ring). |
| 313 |
apply (Qplus_le_l _ _ (approximate x ((1#2)*d)%Qpos)) in H. |
| 314 |
ring_simplify in H. |
| 315 |
rewrite (Qplus_comm (proj1_sig d + e)), Qplus_assoc. |
| 316 |
exact H. } |
| 317 |
split. |
| 318 |
- intro H0. |
| 319 |
rewrite <- (CRdistance_CRle ('e)%CR x y). split. |
| 320 |
+ apply (CRplus_le_r _ _ ('e)%CR). ring_simplify. |
| 321 |
rewrite CRplus_translate. |
| 322 |
intro d. simpl. unfold Cap_raw. simpl. |
| 323 |
apply H, ball_sym, H0. |
| 324 |
+ rewrite CRplus_comm, CRplus_translate. |
| 325 |
intro d. simpl. unfold Cap_raw. simpl. |
| 326 |
apply H, H0. |
| 327 |
- intros H0. apply regFunBall_e2. intro d. |
| 328 |
simpl. |
| 329 |
apply CRdistance_CRle in H0. destruct H0. |
| 330 |
rewrite CRplus_comm, CRplus_translate in H1. |
| 331 |
rewrite (CRplus_le_r _ _ ('e)%CR) in H0. |
| 332 |
ring_simplify in H0. rewrite CRplus_translate in H0. |
| 333 |
apply AbsSmall_Qabs, Qabs_Qle_condition. split. |
| 334 |
+ specialize (H1 d). simpl in H1. |
| 335 |
unfold Cap_raw in H1. simpl in H1. |
| 336 |
apply (Qplus_le_l _ _ (approximate y ((1#2)*d)%Qpos |
| 337 |
+ proj1_sig d + e)). |
| 338 |
simpl. ring_simplify. |
| 339 |
apply (Qplus_le_l _ _ (approximate y ((1 # 2) * d)%Qpos + proj1_sig d)) in H1. |
| 340 |
simpl in H1. ring_simplify in H1. |
| 341 |
exact H1. |
| 342 |
+ specialize (H0 d). simpl in H0. |
| 343 |
unfold Cap_raw in H0. simpl in H0. |
| 344 |
apply (Qplus_le_l _ _ (approximate y ((1#2)*d)%Qpos)). |
| 345 |
simpl. ring_simplify. |
| 346 |
apply (Qplus_le_l _ _ (approximate x ((1 # 2) * d)%Qpos + proj1_sig d)) in H0. |
| 347 |
simpl in H0. ring_simplify in H0. |
| 348 |
rewrite <- Qplus_assoc, Qplus_comm. exact H0. |
| 349 |
Qed. |
| 350 |
|
| 351 |
|
| 352 |
Import MathClasses.interfaces.canonical_names. |
| 353 |
|
| 354 |
#[global] |
| 355 |
Instance CR_abs : Abs CR. |
| 356 |
Proof. |
| 357 |
intro x. exists (CRabs x). |
| 358 |
split; [apply CRabs_pos | apply CRabs_neg]. |
| 359 |
Defined. |
| 360 |
|