Debian Codegraph @

reals/fast/CRabs.v

raw
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