Debian Codegraph @

reals/fast/CRArith.v

raw
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