Debian Codegraph @

reals/fast/CRGroupOps.v

raw
1 (*
2 Copyright © 2006-2008 Russell O’Connor
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this proof and associated documentation files (the "Proof"), to deal in
6 the Proof without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 the Proof, and to permit persons to whom the Proof is furnished to do so,
9 subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Proof.
13
14 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
20 *)
21
22 Require Import QArith Qabs.
23 Require Import CoRN.metric2.Metric.
24 Require Import CoRN.metric2.UniformContinuity.
25 Require Import CoRN.model.totalorder.QposMinMax.
26 Require Export CoRN.model.metric2.CRmetric.
27 Require Import CoRN.model.totalorder.QMinMax.
28 Require Import CoRN.model.metric2.Qmetric.
29 Require Import CoRN.metric2.ProductMetric.
30 Require Import CoRN.stdlib_omissions.Pair.
31 Require Import MathClasses.interfaces.canonical_names.
32
33 (* Backwards compatibility for Hint Rewrite locality attributes *)
34 Set Warnings "-unsupported-attributes".
35
36 Set Implicit Arguments.
37
38 Opaque CR Qmin Qmax.
39
40 Local Open Scope Q_scope.
41 Local Open Scope uc_scope.
42
43 #[global]
44 Instance CR0: Zero CR := cast Q CR 0.
45 Notation "0" := (inject_Q_CR 0) : CR_scope.
46
47 #[global]
48 Instance CR1: One CR := cast Q CR 1.
49 Notation "1" := (inject_Q_CR 1) : CR_scope.
50
51 (**
52 ** Addition
53 Lifting addition over [Q] by one parameter yields a rational translation
54 function. *)
55 Lemma Qtranslate_uc_prf (a:Q)
56 : is_UniformlyContinuousFunction (fun b:Q => (a+b):Q) Qpos2QposInf.
57 Proof.
58 intros e b0 b1 H.
59 simpl in *.
60 unfold Qball in *.
61 unfold QAbsSmall.
62 setoid_replace (a + b0 - (a + b1)) with (b0 - b1)%Q.
63 apply H. ring_simplify. reflexivity.
64 Qed.
65
66 Definition Qtranslate_uc (a:Q_as_MetricSpace) : Q_as_MetricSpace --> Q_as_MetricSpace :=
67 Build_UniformlyContinuousFunction (Qtranslate_uc_prf a).
68 Transparent CR.
69 Definition translate (a:Q) : CR --> CR := Cmap QPrelengthSpace (Qtranslate_uc a).
70
71 Lemma translate_ident : forall x:CR, (translate 0 x==x)%CR.
72 Proof.
73 intros x.
74 unfold translate.
75 assert (H:msp_eq (Qtranslate_uc 0) (uc_id _)).
76 apply ucEq_equiv.
77 intros a.
78 simpl.
79 rewrite Qplus_0_l.
80 reflexivity.
81 simpl.
82 intros e1 e2. destruct x; simpl.
83 rewrite Qplus_0_r.
84 rewrite Qplus_0_l. apply regFun_prf.
85 Qed.
86
87 (** Lifting translate yields binary addition over CR. *)
88 Lemma Qplus_uc_prf : is_UniformlyContinuousFunction Qtranslate_uc Qpos2QposInf.
89 Proof.
90 intros e a0 a1 H. split. apply Qpos_nonneg. intro b.
91 simpl in *.
92 do 2 rewrite -> (fun x => Qplus_comm x b).
93 apply Qtranslate_uc_prf.
94 assumption.
95 Qed.
96
97 Definition Qplus_uc : Q_as_MetricSpace --> Q_as_MetricSpace --> Q_as_MetricSpace :=
98 Build_UniformlyContinuousFunction Qplus_uc_prf.
99
100
101 (** Finally, CRplus: *)
102
103 Definition CRplus_uc : CR --> CR --> CR := Cmap2 QPrelengthSpace QPrelengthSpace Qplus_uc.
104 #[global]
105 Instance CRplus: Plus CR := ucFun2 CRplus_uc.
106 Notation "x + y" := (ucFun2 CRplus_uc x y) : CR_scope.
107
108 Lemma CRplus_translate : forall (a:Q) (y:CR), (' a + y == translate a y)%CR.
109 Proof.
110 intros a y.
111 unfold ucFun2, CRplus.
112 unfold Cmap2.
113 unfold inject_Q_CR.
114 simpl. intros e1 e2. simpl.
115 unfold Cap_raw. simpl. destruct y; simpl.
116 simpl. split.
117 - ring_simplify.
118 destruct (regFun_prf ((1#2)*e1)%Qpos e2) as [H _].
119 simpl in H.
120 refine (Qle_trans _ _ _ _ H).
121 ring_simplify. apply Qplus_le_l.
122 apply Qmult_le_r. apply Qpos_ispos. discriminate.
123 - ring_simplify.
124 destruct (regFun_prf ((1#2)*e1)%Qpos e2) as [_ H].
125 apply (Qle_trans _ _ _ H).
126 apply Qplus_le_l. simpl. rewrite <- (Qmult_1_l (` e1)) at 2.
127 apply Qmult_le_r. apply Qpos_ispos. discriminate.
128 Qed.
129
130 #[global]
131 Hint Rewrite CRplus_translate : CRfast_compute.
132
133 Lemma translate_Qplus : forall a b:Q, (translate a ('b)=='(a+b)%Q)%CR.
134 Proof.
135 intros a b.
136 unfold translate, Cmap.
137 setoid_rewrite -> Cmap_fun_correct.
138 apply MonadLaw3.
139 Qed.
140
141 #[global]
142 Hint Rewrite translate_Qplus : CRfast_compute.
143 (**
144 ** Negation
145 Lifting negation on [Q] yields negation on CR.
146 *)
147 Lemma Qopp_uc_prf : @is_UniformlyContinuousFunction
148 Q_as_MetricSpace Q_as_MetricSpace Qopp Qpos2QposInf.
149 Proof.
150 intros e a b H.
151 simpl in *.
152 unfold Qball in *.
153 apply QAbsSmall_opp in H.
154 unfold QAbsSmall.
155 setoid_replace (-a - - b) with (-(a-b)).
156 apply H. ring_simplify. reflexivity.
157 Qed.
158
159 Definition Qopp_uc : Q_as_MetricSpace --> Q_as_MetricSpace :=
160 Build_UniformlyContinuousFunction Qopp_uc_prf.
161
162 #[global]
163 Instance CRopp: Negate CR := Cmap QPrelengthSpace Qopp_uc.
164
165 Notation "- x" := (CRopp x) : CR_scope.
166
167 (**
168 ** Subtraction
169 There is no subtraction on CR. It is simply notation for adding a
170 negated quantity. This way all lemmas about addition automatically
171 apply to subtraction.
172 *)
173 Notation "x - y" := (x + (- y))%CR : CR_scope.
174 (* begin hide *)
175 Add Morphism CRopp with signature (@msp_eq _) ==> (@msp_eq _) as CRopp_wd.
176 Proof.
177 apply uc_wd.
178 Qed.
179 (* end hide *)
180 (**
181 ** Inequality
182 First a predicate for nonnegative numbers is defined. *)
183 Definition CRnonNeg (x:CR) := forall e:Qpos, (-proj1_sig e) <= (approximate x e).
184 (* begin hide *)
185 Add Morphism CRnonNeg with signature (@msp_eq _) ==> iff as CRnonNeg_wd.
186 Proof.
187 assert (forall x1 x2 : RegularFunction Qball,
188 regFunEq x1 x2 -> CRnonNeg x1 -> CRnonNeg x2).
189 intros x y Hxy Hx e.
190 apply Qnot_lt_le.
191 intros He.
192 rewrite -> Qlt_minus_iff in He.
193 pose (e' := exist _ _ He).
194 pose (H1:=(Hx ((1#3)*e')%Qpos)).
195 pose (H2:=(Hxy ((1#3)*e')%Qpos e)).
196 destruct H2 as [_ H2].
197 change (approximate x ((1 # 3) * e')%Qpos - approximate y e
198 <= proj1_sig ((1 # 3) * e' + e)%Qpos) in H2.
199 rewrite -> Qle_minus_iff in H1.
200 rewrite -> Qle_minus_iff in H2.
201 autorewrite with QposElim in *.
202 ring_simplify in H1.
203 ring_simplify in H2.
204 assert (0+0<=(approximate x ((1 # 3) * e')%Qpos + (1 # 3) * proj1_sig e')
205 + ((1 # 3) * proj1_sig e' + proj1_sig e + (-1 # 1) * approximate x ((1 # 3) * e')%Qpos + approximate y e)) as H3.
206 apply Qplus_le_compat; assumption.
207 ring_simplify in H3.
208 setoid_replace ((6 # 9) * proj1_sig e' + proj1_sig e + approximate y e)
209 with ((6#9)* proj1_sig e' - proj1_sig e') in H3.
210 ring_simplify in H3.
211 apply (Qle_not_lt _ _ H3).
212 rewrite -> Qlt_minus_iff.
213 ring_simplify.
214 apply (Qpos_ispos ((3#9)*e')).
215 unfold e'. simpl. ring_simplify. reflexivity.
216 intros.
217 split.
218 apply H, regFunEq_equiv; assumption.
219 apply H.
220 apply regFunEq_equiv.
221 symmetry.
222 assumption.
223 Qed.
224 (* end hide *)
225 (** And similarly for nonpositive. *)
226 Definition CRnonPos (x:CR) := forall e:Qpos, (approximate x e) <= proj1_sig e.
227 (* begin hide *)
228 Add Morphism CRnonPos with signature (@msp_eq _) ==> iff as CRnonPos_wd.
229 Proof.
230 assert (forall x1 x2 : RegularFunction Qball,
231 regFunEq x1 x2 -> CRnonPos x1 -> CRnonPos x2).
232 intros x y Hxy Hx e.
233 apply Qnot_lt_le.
234 intros He.
235 rewrite -> Qlt_minus_iff in He.
236 pose (e' := exist _ _ He).
237 pose (H1:=(Hx ((1#3)*e')%Qpos)).
238 pose (H2:=(Hxy ((1#3)*e')%Qpos e)).
239 destruct H2 as [H2 _].
240 change (-proj1_sig ((1 # 3) * e' + e)%Qpos
241 <= approximate x ((1 # 3) * e')%Qpos - approximate y e) in H2.
242 rewrite -> Qle_minus_iff in H1.
243 rewrite -> Qle_minus_iff in H2.
244 simpl in *.
245 ring_simplify in H1.
246 ring_simplify in H2.
247 assert (H3: 0+0<=((1 # 3) * proj1_sig e' + (-1 # 1) * approximate x ((1 # 3) * e')%Qpos)
248 +(approximate x ((1 # 3) * e')%Qpos + (-1 # 1) * approximate y e + (1 # 3) * proj1_sig e' + proj1_sig e)).
249 apply Qplus_le_compat. simpl. ring_simplify. assumption.
250 simpl. ring_simplify. assumption.
251 ring_simplify in H3.
252 setoid_replace ((6 # 9) * proj1_sig e' + (-1 # 1) * approximate y e + proj1_sig e)
253 with ((6#9)*proj1_sig e'-proj1_sig e') in H3.
254 ring_simplify in H3.
255 apply (Qle_not_lt _ _ H3).
256 rewrite -> Qlt_minus_iff.
257 ring_simplify.
258 apply (Qpos_ispos ((3#9)*e')).
259 unfold e'. simpl. ring_simplify. reflexivity.
260 intros.
261 split.
262 apply H, regFunEq_equiv; assumption.
263 apply H.
264 apply regFunEq_equiv.
265 symmetry.
266 assumption.
267 Qed.
268 (* end hide *)
269 (** Inequality is defined in terms of nonnegativity. *)
270 #[global]
271 Instance CRle: Le CR := λ x y, (CRnonNeg (y - x))%CR.
272 Infix "<=" := CRle : CR_scope.
273
274 (* begin hide *)
275 Add Morphism CRle with signature (@msp_eq _) ==> (@msp_eq _) ==> iff as CRle_wd.
276 Proof.
277 intros x1 x2 Hx y1 y2 Hy.
278 change (x1==x2)%CR in Hx.
279 change (y1==y2)%CR in Hy.
280 unfold CRle.
281 apply CRnonNeg_wd.
282 apply ucFun2_wd.
283 assumption.
284 apply CRopp_wd.
285 assumption.
286 Qed.
287 (* end hide *)
288 (** Basic properties of inequality *)
289 Lemma CRle_refl : forall x, (x <= x)%CR.
290 Proof.
291 intros x e.
292 simpl.
293 unfold Cap_raw.
294 simpl.
295 rewrite -> Qle_minus_iff.
296 ring_simplify.
297 apply Qlt_le_weak. destruct e; exact q.
298 Qed.
299
300 Lemma CRle_antisym : forall x y, (x==y <-> (x <= y /\ y <= x))%CR.
301 Proof.
302 intros x y.
303 split;[intros H;rewrite -> H;split; apply CRle_refl|].
304 intros [H1 H2].
305 rewrite <- (doubleSpeed_Eq x).
306 rewrite <- (doubleSpeed_Eq y).
307 apply regFunEq_equiv, regFunEq_e.
308 intros e.
309 apply ball_weak. apply Qpos_nonneg.
310 split;[apply H2|].
311 specialize (H1 e).
312 apply Qopp_le_compat in H1. rewrite Qopp_involutive in H1.
313 refine (Qle_trans _ _ _ _ H1).
314 simpl. unfold Cap_raw. simpl.
315 ring_simplify. apply Qle_refl.
316 Qed.
317
318 Lemma CRle_trans : forall x y z, (x <= y -> y <= z -> x <= z)%CR.
319 Proof.
320 intros x y z H1 H2.
321 unfold CRle.
322 rewrite <- (doubleSpeed_Eq (z-x)%CR).
323 intros e.
324 assert (H1':=H1 ((1#2)*e)%Qpos).
325 assert (H2':=H2 ((1#2)*e)%Qpos).
326 clear H1 H2.
327 simpl in *.
328 unfold Cap_raw in *.
329 simpl in *.
330 apply (Qle_trans _ ((approximate z ((1 # 2) * ((1 # 2) * e))%Qpos
331 - approximate y ((1 # 2) * ((1 # 2) * e))%Qpos + (approximate y ((1 # 2) * ((1 # 2) * e))%Qpos
332 - approximate x ((1 # 2) * ((1 # 2) * e))%Qpos)))).
333 2: ring_simplify; apply Qle_refl.
334 apply (Qle_trans _ (-(1#2)*proj1_sig e + - (1#2)* proj1_sig e)).
335 ring_simplify. apply Qmult_le_r. apply Qpos_ispos. discriminate.
336 apply Qplus_le_compat; apply (Qle_trans _ (- ((1 # 2) * ` e))).
337 destruct e. simpl. ring_simplify. apply Qle_refl. assumption.
338 destruct e. simpl. ring_simplify. apply Qle_refl. assumption.
339 Qed.
340
341 (**
342 ** Maximum
343 [QboundBelow] ensures that a real number is at least some fixed
344 rational number. It is the lifting of the first parameter of [Qmax].
345 *)
346 Lemma QboundBelow_uc_prf (a:Q)
347 : is_UniformlyContinuousFunction (fun b:Q => (Qmax a b):Q) Qpos2QposInf.
348 Proof.
349 intros e b0 b1 H.
350 simpl in *.
351 assert (X:forall a b0 b1, Qball (proj1_sig e) b0 b1
352 -> b0 <= a <= b1 -> Qball (proj1_sig e) a b1).
353 clear a b0 b1 H.
354 intros a b0 b1 H [H1 H2].
355 unfold Qball in *.
356 unfold QAbsSmall in *.
357 split.
358 apply Qle_trans with (b0-b1).
359 apply H.
360 apply Qplus_le_l.
361 assumption.
362 apply Qle_trans with 0.
363 apply (Qplus_le_l _ _ b1).
364 ring_simplify. assumption.
365 apply Qpos_nonneg.
366 do 2 apply Qmax_case; intros H1 H2.
367 apply ball_refl. apply Qpos_nonneg.
368 eapply X.
369 apply H.
370 tauto.
371 apply ball_sym.
372 apply X with b1.
373 apply ball_sym.
374 apply H.
375 tauto.
376 assumption.
377 Qed.
378
379 Definition QboundBelow_uc (a:Q_as_MetricSpace) : Q_as_MetricSpace --> Q_as_MetricSpace :=
380 Build_UniformlyContinuousFunction (QboundBelow_uc_prf a).
381
382 Definition boundBelow (a:Q) : CR --> CR := Cmap QPrelengthSpace (QboundBelow_uc a).
383
384 (** CRmax is the lifting of [QboundBelow]. *)
385 Lemma Qmax_uc_prf : is_UniformlyContinuousFunction QboundBelow_uc Qpos2QposInf.
386 Proof.
387 intros e a0 a1 H. split. apply Qpos_nonneg. intro b.
388 simpl in *.
389 do 2 rewrite -> (fun x => Qmax_comm x b).
390 apply QboundBelow_uc_prf.
391 assumption.
392 Qed.
393
394 Definition Qmax_uc : Q_as_MetricSpace --> Q_as_MetricSpace --> Q_as_MetricSpace :=
395 Build_UniformlyContinuousFunction Qmax_uc_prf.
396
397 Definition CRmax : CR --> CR --> CR := Cmap2 QPrelengthSpace QPrelengthSpace Qmax_uc.
398
399 Lemma Qmax_contract : forall (a b c : Q),
400 Qabs (Qmax a b - Qmax a c) <= Qabs (b - c).
401 Proof.
402 intros. apply Qabs_Qle_condition. split.
403 - apply Qmax_case.
404 + intros. apply Qmax_case. intros.
405 unfold Qminus. rewrite Qplus_opp_r. apply (Qopp_le_compat 0).
406 apply Qabs_nonneg. intros. rewrite Qabs_neg, Qopp_involutive.
407 apply Qplus_le_l, H. apply (Qplus_le_l _ _ c).
408 ring_simplify. exact (Qle_trans _ _ _ H H0).
409 + intros. apply Qmax_case. intros.
410 apply (Qle_trans _ 0). apply (Qopp_le_compat 0).
411 apply Qabs_nonneg.
412 unfold Qminus. rewrite <- Qle_minus_iff. exact H.
413 intros. setoid_replace (b-c)%Q with (-(c-b)).
414 apply Qopp_le_compat. rewrite Qabs_opp. apply Qle_Qabs.
415 unfold equiv, stdlib_rationals.Q_eq. ring.
416 - apply Qmax_case.
417 + intros. apply Qmax_case. intros.
418 unfold Qminus. rewrite Qplus_opp_r.
419 apply Qabs_nonneg. intros.
420 apply (Qle_trans _ 0).
421 apply (Qplus_le_l _ _ c). ring_simplify. exact H0.
422 apply Qabs_nonneg.
423 + intros. apply Qmax_case. intros.
424 rewrite Qabs_pos. apply Qplus_le_r, Qopp_le_compat, H0.
425 unfold Qminus. rewrite <- Qle_minus_iff.
426 exact (Qle_trans _ _ _ H0 H).
427 intros. apply Qle_Qabs.
428 Qed.
429
430 Lemma CRmax_boundBelow : forall (a:Q) (y:CR), (CRmax (' a) y == boundBelow a y)%CR.
431 Proof.
432 intros a y.
433 unfold ucFun2, CRmax.
434 unfold Cmap2.
435 unfold inject_Q_CR.
436 intros e1 e2.
437 destruct y; simpl; unfold Cmap_fun, Cap_fun, Cap_raw; simpl.
438 specialize (regFun_prf ((1 # 2) * e1)%Qpos e2).
439 apply AbsSmall_Qabs.
440 apply (Qle_trans _ _ _ (Qmax_contract _ _ _)).
441 apply AbsSmall_Qabs in regFun_prf.
442 apply (Qle_trans _ _ _ regFun_prf).
443 apply Qplus_le_l. simpl.
444 rewrite <- (Qmult_1_l (proj1_sig e1)) at 2.
445 rewrite Qplus_0_r.
446 apply Qmult_le_r. apply Qpos_ispos. discriminate.
447 Qed.
448
449 (** Basic properties of CRmax. *)
450 Lemma CRmax_ub_l : forall x y, (x <= CRmax x y)%CR.
451 Proof.
452 intros x y e.
453 simpl.
454 unfold Cap_raw.
455 simpl.
456 unfold Cap_raw.
457 simpl.
458 rewrite -> Qmax_plus_distr_l.
459 eapply Qle_trans;[|apply Qmax_ub_l].
460 cut (QAbsSmall (proj1_sig e) (approximate x ((1 # 2) * ((1 # 2) * e))%Qpos +
461 - approximate x ((1 # 2) * e)%Qpos));[unfold QAbsSmall;tauto|].
462 change (ball (proj1_sig e) (approximate x ((1 # 2) * ((1 # 2) * e))%Qpos) (approximate x ((1 # 2) * e)%Qpos)).
463 eapply ball_weak_le;[|apply regFun_prf].
464 simpl.
465 rewrite -> Qle_minus_iff.
466 ring_simplify.
467 apply (Qpos_nonneg ((2#8)*e)).
468 Qed.
469
470 Lemma CRmax_ub_r : forall x y, (y <= CRmax x y)%CR.
471 Proof.
472 intros y x e.
473 simpl.
474 unfold Cap_raw.
475 simpl.
476 unfold Cap_raw.
477 simpl.
478 rewrite -> Qmax_plus_distr_l.
479 eapply Qle_trans;[|apply Qmax_ub_r].
480 cut (QAbsSmall (proj1_sig e) (approximate x ((1 # 2) * ((1 # 2) * e))%Qpos +
481 - approximate x ((1 # 2) * e)%Qpos));[unfold QAbsSmall;tauto|].
482 change (ball (proj1_sig e) (approximate x ((1 # 2) * ((1 # 2) * e))%Qpos) (approximate x ((1 # 2) * e)%Qpos)).
483 eapply ball_weak_le;[|apply regFun_prf].
484 simpl.
485 rewrite -> Qle_minus_iff.
486 ring_simplify.
487 apply (Qpos_nonneg ((2#8)*e)).
488 Qed.
489
490 Lemma CRmax_lub: forall x y z : CR, (x <= z -> y <= z -> CRmax x y <= z)%CR.
491 Proof.
492 intros x y z Hx Hy.
493 rewrite <- (doubleSpeed_Eq z) in * |- *.
494 intros e.
495 assert (Hx':=Hx ((1#2)*e)%Qpos).
496 assert (Hy':=Hy ((1#2)*e)%Qpos).
497 clear Hx Hy.
498 simpl in *.
499 unfold Cap_raw in *.
500 simpl in *.
501 unfold Cap_raw.
502 simpl.
503 apply (Qle_trans _ ((-(1#2)*proj1_sig e) + (- (1#2)*proj1_sig e))).
504 ring_simplify. apply Qmult_le_r. apply Qpos_ispos. discriminate.
505 apply (Qle_trans _ ((approximate z ((1#2)*((1 # 2) * e))%Qpos +
506 - approximate z ((1#2)*((1 # 2) * ((1 # 2) * e)))%Qpos) +
507 (approximate z ((1#2)*((1 # 2) * ((1 # 2) * e)))%Qpos
508 - Qmax (approximate x ((1 # 2) * ((1 # 2) * e))%Qpos)
509 (approximate y ((1 # 2) * ((1 # 2) * e))%Qpos)))).
510 2: ring_simplify; apply Qle_refl.
511 apply Qplus_le_compat.
512 - apply (Qle_trans _ (- ((1 # 2) * ` e))).
513 destruct e; simpl; ring_simplify; apply Qle_refl.
514 cut (ball ((1#2)*proj1_sig e) (approximate z ((1#2)*((1 # 2) * e))%Qpos)
515 (approximate z ((1#2)*((1 # 2) * ((1 # 2) * e)))%Qpos)).
516 intros [A B]. assumption.
517 refine (ball_weak_le _ _ _ _ _). 2:apply regFun_prf.
518 rewrite -> Qle_minus_iff.
519 simpl. ring_simplify.
520 apply (Qpos_nonneg ((8#64)*e)).
521 - apply (Qle_trans _ (- ((1 # 2) * ` e))).
522 destruct e; simpl; ring_simplify; apply Qle_refl.
523 apply Qmax_case; intros; assumption.
524 Qed.
525 (**
526 ** Minimum
527 [QboundAbove] ensures that a real number is at most some fixed
528 rational number. It is the lifting of the first parameter of [Qmin].
529 *)
530 Lemma QboundAbove_uc_prf (a:Q)
531 : is_UniformlyContinuousFunction (fun b:Q => (Qmin a b):Q) Qpos2QposInf.
532 Proof.
533 intros e b0 b1 H.
534 simpl in *.
535 unfold Qball.
536 unfold QAbsSmall.
537 setoid_replace (Qmin a b0 - Qmin a b1)
538 with ((Qmax (- a) (-b1)) - (Qmax (-a) (-b0))).
539 apply QboundBelow_uc_prf.
540 apply Qopp_uc_prf.
541 apply ball_sym.
542 assumption.
543 unfold Qminus.
544 simpl.
545 rewrite -> Qmin_max_de_morgan.
546 rewrite -> Qmax_min_de_morgan.
547 repeat rewrite -> Qopp_involutive.
548 ring_simplify. reflexivity.
549 Qed.
550
551 Definition QboundAbove_uc (a:Q_as_MetricSpace) : Q_as_MetricSpace --> Q_as_MetricSpace :=
552 Build_UniformlyContinuousFunction (QboundAbove_uc_prf a).
553
554 Definition boundAbove (a:Q) : CR --> CR := Cmap QPrelengthSpace (QboundAbove_uc a).
555
556 (** CRmin is the lifting of [QboundAbove]. *)
557 Lemma Qmin_uc_prf : is_UniformlyContinuousFunction QboundAbove_uc Qpos2QposInf.
558 Proof.
559 intros e a0 a1 H. split. apply Qpos_nonneg. intro b.
560 simpl in *.
561 do 2 rewrite -> (fun x => Qmin_comm x b).
562 apply QboundAbove_uc_prf.
563 assumption.
564 Qed.
565
566 Definition Qmin_uc : Q_as_MetricSpace --> Q_as_MetricSpace --> Q_as_MetricSpace :=
567 Build_UniformlyContinuousFunction Qmin_uc_prf.
568
569 Definition CRmin : CR --> CR --> CR := Cmap2 QPrelengthSpace QPrelengthSpace Qmin_uc.
570
571 Lemma CRmin_boundAbove : forall (a:Q) (y:CR), (CRmin (' a) y == boundAbove a y)%CR.
572 Proof.
573 intros a y.
574 unfold ucFun2, CRmin.
575 unfold Cmap2.
576 unfold inject_Q_CR.
577 intros e1 e2.
578 destruct y; simpl; unfold Cmap_fun, Cap_fun, Cap_raw; simpl.
579 specialize (regFun_prf ((1 # 2) * e1)%Qpos e2).
580 rewrite Qplus_0_r. split.
581 - apply Qmin_case. intros. apply Qmin_case. intros.
582 unfold Qminus. rewrite Qplus_opp_r. apply (Qopp_le_compat 0).
583 apply (Qpos_nonneg (e1+e2)). intros.
584 intros. apply (Qle_trans _ 0). apply (Qopp_le_compat 0), (Qpos_nonneg (e1+e2)).
585 unfold Qminus. rewrite <- Qle_minus_iff. exact H0. intros.
586 apply (Qle_trans _ (approximate ((1 # 2)%Q ↾ eq_refl * e1)%Qpos - approximate e2)).
587 destruct regFun_prf as [H1 _].
588 refine (Qle_trans _ _ _ _ H1). simpl. ring_simplify.
589 apply Qplus_le_l. apply Qmult_le_r. apply Qpos_ispos. discriminate.
590 apply Qplus_le_r. apply Qopp_le_compat.
591 apply Qmin_case. intros. exact H0. intros. apply Qle_refl.
592 - apply Qmin_case. apply Qmin_case. intros.
593 unfold Qminus. rewrite Qplus_opp_r. apply (Qpos_nonneg (e1+e2)).
594 intros. apply (Qle_trans _ (approximate ((1 # 2) * e1)%Qpos - approximate e2)).
595 apply Qplus_le_l, H0. destruct regFun_prf as [_ H1].
596 apply (Qle_trans _ _ _ H1). apply Qplus_le_l. simpl.
597 rewrite <- (Qmult_1_l (proj1_sig e1)) at 2.
598 apply Qmult_le_r. apply Qpos_ispos. discriminate.
599 intros. apply Qmin_case.
600 intros. apply (Qle_trans _ 0).
601 apply (Qplus_le_l _ _ a). ring_simplify. exact H.
602 apply (Qpos_nonneg (e1+e2)). intros.
603 destruct regFun_prf as [_ H1].
604 apply (Qle_trans _ _ _ H1). apply Qplus_le_l. simpl.
605 rewrite <- (Qmult_1_l (proj1_sig e1)) at 2.
606 apply Qmult_le_r. apply Qpos_ispos. discriminate.
607 Qed.
608
609 (** Basic properties of CRmin. *)
610 Lemma CRmin_lb_l : forall x y, (CRmin x y <= x)%CR.
611 Proof.
612 intros x y e.
613 simpl.
614 unfold Cap_raw.
615 simpl.
616 unfold Cap_raw.
617 simpl.
618 rewrite -> Qmin_max_de_morgan.
619 rewrite -> Qmax_plus_distr_r.
620 eapply Qle_trans;[|apply Qmax_ub_l].
621 cut (QAbsSmall (proj1_sig e) (approximate x ((1 # 2) * e)%Qpos +
622 - approximate x ((1 # 2) * ((1 # 2) * e))%Qpos));[unfold QAbsSmall;tauto|].
623 change (ball (proj1_sig e) (approximate x ((1 # 2) * e)%Qpos) (approximate x ((1 # 2) * ((1 # 2) * e))%Qpos)).
624 eapply ball_weak_le;[|apply regFun_prf].
625 simpl.
626 rewrite -> Qle_minus_iff.
627 ring_simplify.
628 apply (Qpos_nonneg ((2#8)*e)).
629 Qed.
630
631 Lemma CRmin_lb_r : forall x y, (CRmin x y <= y)%CR.
632 Proof.
633 intros y x e.
634 simpl.
635 unfold Cap_raw.
636 simpl.
637 unfold Cap_raw.
638 simpl.
639 rewrite -> Qmin_max_de_morgan.
640 rewrite -> Qmax_plus_distr_r.
641 eapply Qle_trans;[|apply Qmax_ub_r].
642 cut (QAbsSmall (proj1_sig e) (approximate x ((1 # 2) * e)%Qpos +
643 - approximate x ((1 # 2) * ((1 # 2) * e))%Qpos));[unfold QAbsSmall;tauto|].
644 change (ball (proj1_sig e) (approximate x ((1 # 2) * e)%Qpos) (approximate x ((1 # 2) * ((1 # 2) * e))%Qpos)).
645 eapply ball_weak_le;[|apply regFun_prf].
646 simpl.
647 rewrite -> Qle_minus_iff.
648 ring_simplify.
649 apply (Qpos_nonneg ((2#8)*e)).
650 Qed.
651
652 Lemma CRmin_glb: forall x y z : CR, (z <= x -> z <= y -> z <= CRmin x y)%CR.
653 Proof.
654 intros x y z Hx Hy.
655 rewrite <- (doubleSpeed_Eq z) in * |- *.
656 intros e.
657 assert (Hx':=Hx ((1#2)*e)%Qpos).
658 assert (Hy':=Hy ((1#2)*e)%Qpos).
659 clear Hx Hy.
660 simpl in *.
661 unfold Cap_raw in *.
662 simpl in *.
663 unfold Cap_raw.
664 simpl.
665 apply (Qle_trans _ ((-(1#2)*proj1_sig e) + (- (1#2)*proj1_sig e))).
666 ring_simplify. apply Qmult_le_r. apply Qpos_ispos. discriminate.
667 apply (Qle_trans _ ((approximate z ((1#2)*((1 # 2) * ((1 # 2) * e)))%Qpos +
668 - approximate z ((1#2)*((1 # 2) * e))%Qpos) + (Qmin (approximate x ((1 # 2) * ((1 # 2) * e))%Qpos)
669 (approximate y ((1 # 2) * ((1 # 2) * e))%Qpos) +
670 - approximate z ((1#2)*((1 # 2) * ((1 # 2) * e)))%Qpos))).
671 2: ring_simplify; rewrite Qplus_comm; apply Qle_refl.
672 apply Qplus_le_compat.
673 - apply (Qle_trans _ (- ((1 # 2) * ` e))).
674 destruct e; simpl; ring_simplify; apply Qle_refl.
675 cut (ball ((1#2)*proj1_sig e) (approximate z ((1#2)*((1 # 2) * ((1 # 2) * e)))%Qpos)
676 (approximate z ((1#2)*((1 # 2) * e))%Qpos)) ;[intros [A B]; assumption|].
677 refine (ball_weak_le _ _ _ _ _). 2:apply regFun_prf.
678 rewrite -> Qle_minus_iff.
679 simpl.
680 ring_simplify.
681 apply (Qpos_nonneg ((8#64)*e)).
682 - apply (Qle_trans _ (- ((1 # 2) * ` e))).
683 destruct e; simpl; ring_simplify; apply Qle_refl.
684 apply Qmin_case;intro;assumption.
685 Qed.
686
687 (* Non-curried equivalent version of addition. *)
688
689 Lemma Qplus_uc_uncurry : is_UniformlyContinuousFunction
690 (fun ab : ProductMS Q_as_MetricSpace
691 Q_as_MetricSpace
692 => fst ab + snd ab)
693 (fun e => (1#2)*e)%Qpos.
694 Proof.
695 intros e1 [a b] [c d] [H H0]. simpl.
696 simpl in H, H0. apply AbsSmall_Qabs.
697 setoid_replace (a + b - (c + d))%Q
698 with (a - c + (b - d))
699 by (unfold equiv, stdlib_rationals.Q_eq; ring).
700 apply (Qle_trans _ _ _ (Qabs_triangle _ _)).
701 apply (Qle_trans _ ((1#2)*`e1 + (1#2)*`e1)).
702 apply Qplus_le_compat.
703 - apply AbsSmall_Qabs in H. apply H.
704 - apply AbsSmall_Qabs in H0. apply H0.
705 - ring_simplify. apply Qle_refl.
706 Qed.
707
708 Definition Qplus_uncurry
709 : ProductMS Q_as_MetricSpace Q_as_MetricSpace --> Q_as_MetricSpace
710 := Build_UniformlyContinuousFunction Qplus_uc_uncurry.
711
712 Lemma CRplus_uncurry_eq : forall x y : CR,
713 msp_eq (CRplus x y)
714 (Cmap (ProductMS_prelength QPrelengthSpace QPrelengthSpace)
715 Qplus_uncurry (undistrib_Complete (x,y))).
716 Proof.
717 intros x y. unfold CRplus, ucFun2, CRplus_uc.
718 transitivity (Cmap2 QPrelengthSpace QPrelengthSpace (uc_curry Qplus_uncurry) x y).
719 2: apply Cmap2_curry.
720 apply Cap_wd. 2: reflexivity.
721 apply Cmap_wd. 2: reflexivity.
722 apply ucEq_equiv.
723 split. apply Qle_refl.
724 intros a. reflexivity.
725 Qed.