Debian Codegraph @

reals/faster/ARArith.v

raw
1 Require Import CoRN.algebra.RSetoid.
2 Require Import CoRN.metric2.Metric.
3 Require Import CoRN.metric2.UniformContinuity.
4 From Coq Require Import Program Ring Qabs.
5 Require Import CoRN.stdlib_omissions.Q MathClasses.misc.workaround_tactics
6 CoRN.model.totalorder.QMinMax CoRN.model.totalorder.QposMinMax CoRN.util.Qdlog
7 CoRN.metric2.Complete CoRN.metric2.Prelength CoRN.model.metric2.Qmetric CoRN.metric2.MetricMorphisms
8 CoRN.reals.fast.CRArith CoRN.reals.fast.CRpower
9 MathClasses.implementations.stdlib_binary_naturals MathClasses.orders.minmax MathClasses.implementations.positive_semiring_elements.
10 Require Export
11 CoRN.reals.faster.ApproximateRationals
12 CoRN.reals.faster.AQmetric.
13
14 Section ARarith.
15 Context `{AppRationals AQ}.
16
17 Add Ring AQ : (rings.stdlib_ring_theory AQ).
18 Add Ring Z : (rings.stdlib_ring_theory Z).
19
20 Local Open Scope uc_scope.
21 Local Opaque regFunEq.
22
23 Hint Rewrite (rings.preserves_0 (f:=cast AQ Q)) : aq_preservation.
24 Hint Rewrite (rings.preserves_1 (f:=cast AQ Q)) : aq_preservation.
25 Hint Rewrite (rings.preserves_plus (f:=cast AQ Q)) : aq_preservation.
26 Hint Rewrite (rings.preserves_mult (f:=cast AQ Q)) : aq_preservation.
27 Hint Rewrite (rings.preserves_negate (f:=cast AQ Q)) : aq_preservation.
28 Hint Rewrite aq_preserves_max : aq_preservation.
29 Hint Rewrite aq_preserves_min : aq_preservation.
30 Hint Rewrite (abs.preserves_abs (f:=cast AQ Q)): aq_preservation.
31 Ltac aq_preservation := autorewrite with aq_preservation; try reflexivity.
32 Local Obligation Tactic := program_simpl; aq_preservation.
33
34 (* Compress *)
35 Lemma aq_approx_regular_prf (x : AQ) :
36 is_RegularFunction_noInf _ (λ ε : Qpos, app_approx x (Qdlog2 (proj1_sig ε))
37 : AQ_as_MetricSpace).
38 Proof.
39 intros ε1 ε2. simpl.
40 eapply ball_triangle.
41 apply aq_approx_dlog2.
42 apply ball_sym, aq_approx_dlog2.
43 Qed.
44
45 Definition AQcompress (x : AQ_as_MetricSpace) : AR :=
46 mkRegularFunction (0 : AQ_as_MetricSpace) (aq_approx_regular_prf x).
47
48 Lemma AQcompress_uc_prf : is_UniformlyContinuousFunction AQcompress Qpos2QposInf.
49 Proof.
50 intros ε x y E δ1 δ2. simpl in *.
51 eapply ball_triangle.
52 2: apply ball_sym, aq_approx_dlog2.
53 eapply ball_triangle; eauto.
54 apply aq_approx_dlog2.
55 Qed.
56
57 Definition AQcompress_uc := Build_UniformlyContinuousFunction AQcompress_uc_prf.
58
59 Definition ARcompress : AR --> AR := Cbind AQPrelengthSpace AQcompress_uc.
60
61 Lemma ARcompress_correct (x : AR) : ARcompress x = x.
62 Proof.
63 apply regFunEq_equiv, regFunEq_e. intros ε.
64 assert (QposEq (ε + ε) ((1#2) * ε + ((1#2) * ε + ε)))
65 by (unfold QposEq; simpl; ring).
66 apply (ball_wd _ H5 _ _ (reflexivity _) _ _ (reflexivity _)). clear H5.
67 eapply ball_triangle.
68 apply_simplified (aq_approx_dlog2 (approximate x ((1 # 2) * ε)%Qpos) ((1#2) * ε)%Qpos).
69 apply regFun_prf.
70 Qed.
71
72 (* Constants *)
73 Global Instance inject_PosAQ_AR: Cast (AQ₊) AR := (cast AQ AR ∘ cast (AQ₊) AQ)%prg.
74 Global Instance inject_Z_AR: Cast Z AR := (cast AQ AR ∘ cast Z AQ)%prg.
75
76 Lemma ARtoCR_inject (x : AQ) : cast AR CR (cast AQ AR x) = cast Q CR (cast AQ Q x).
77 Proof.
78 apply regFunEq_equiv, regFunEq_e. intros ε. apply ball_refl.
79 apply (Qpos_nonneg (ε + ε)).
80 Qed.
81
82 Global Instance AR0: Zero AR := cast AQ AR 0.
83 Lemma ARtoCR_preserves_0 : cast AR CR 0 = 0.
84 Proof. unfold "0", AR0. rewrite ARtoCR_inject. aq_preservation. Qed.
85 Hint Rewrite ARtoCR_preserves_0 : ARtoCR.
86
87 Global Instance AR1: One AR := cast AQ AR 1.
88 Lemma ARtoCR_preserves_1 : cast AR CR 1 = 1.
89 Proof. unfold "1", AR1. rewrite ARtoCR_inject. aq_preservation. Qed.
90 Hint Rewrite ARtoCR_preserves_1 : ARtoCR.
91
92 (* Plus *)
93 Program Definition AQtranslate_uc (x : AQ_as_MetricSpace) := unary_uc
94 (cast AQ Q_as_MetricSpace)
95 ((x +) : AQ_as_MetricSpace → AQ_as_MetricSpace) (Qtranslate_uc ('x)) _.
96 Next Obligation. apply Qball_0. apply preserves_sg_op. Qed.
97
98 Definition ARtranslate (x : AQ_as_MetricSpace) : AR --> AR := Cmap AQPrelengthSpace (AQtranslate_uc x).
99
100 Lemma ARtoCR_preserves_translate x y : 'ARtranslate x y = translate ('x) ('y).
101 Proof. apply preserves_unary_fun. Qed.
102 Hint Rewrite ARtoCR_preserves_translate : ARtoCR.
103
104 Program Definition AQplus_uc := binary_uc
105 (cast AQ Q_as_MetricSpace)
106 ((+) : AQ_as_MetricSpace → AQ_as_MetricSpace → AQ_as_MetricSpace) Qplus_uc _.
107 Next Obligation. apply Qball_0. apply preserves_sg_op. Qed.
108
109 Definition ARplus_uc : AR --> AR --> AR := Cmap2 AQPrelengthSpace AQPrelengthSpace AQplus_uc.
110 Global Instance ARplus: Plus AR := ucFun2 ARplus_uc.
111
112 Lemma ARtoCR_preserves_plus x y : cast AR CR (x + y) = 'x + 'y.
113 Proof. apply preserves_binary_fun. Qed.
114 Hint Rewrite ARtoCR_preserves_plus : ARtoCR.
115
116 (* Inverse *)
117 Program Definition AQopp_uc := unary_uc (cast AQ Q_as_MetricSpace) ((-) : AQ → AQ) Qopp_uc _.
118 Next Obligation. apply Qball_0. aq_preservation. Qed.
119
120 Definition ARopp_uc : AR --> AR := Cmap AQPrelengthSpace AQopp_uc.
121 Global Instance ARopp: Negate AR := ARopp_uc.
122
123 Lemma ARtoCR_preserves_opp x : cast AR CR (-x) = -'x.
124 Proof. apply preserves_unary_fun. Qed.
125 Hint Rewrite ARtoCR_preserves_opp : ARtoCR.
126
127 (* Mult *)
128 Program Definition AQboundBelow_uc (x : AQ_as_MetricSpace) :
129 AQ_as_MetricSpace --> AQ_as_MetricSpace :=
130 unary_uc (cast AQ Q_as_MetricSpace)
131 ((x ⊔) : AQ_as_MetricSpace → AQ_as_MetricSpace) (QboundBelow_uc ('x)) _.
132 Next Obligation. apply Qball_0. aq_preservation. Qed.
133
134 Definition ARboundBelow (x : AQ_as_MetricSpace) : AR --> AR := Cmap AQPrelengthSpace (AQboundBelow_uc x).
135
136 Lemma ARtoCR_preserves_boundBelow x y : 'ARboundBelow x y = boundBelow ('x) ('y).
137 Proof. apply preserves_unary_fun. Qed.
138 Hint Rewrite ARtoCR_preserves_boundBelow : ARtoCR.
139
140 Program Definition AQboundAbove_uc (x : AQ_as_MetricSpace) :
141 AQ_as_MetricSpace --> AQ_as_MetricSpace := unary_uc
142 (cast AQ Q_as_MetricSpace)
143 ((x ⊓) : AQ_as_MetricSpace → AQ_as_MetricSpace) (QboundAbove_uc ('x)) _.
144 Next Obligation. apply Qball_0. aq_preservation. Qed.
145
146 Definition ARboundAbove (x : AQ_as_MetricSpace) : AR --> AR := Cmap AQPrelengthSpace (AQboundAbove_uc x).
147
148 Lemma ARtoCR_preserves_boundAbove x y : 'ARboundAbove x y = boundAbove ('x) ('y).
149 Proof. apply preserves_unary_fun. Qed.
150 Hint Rewrite ARtoCR_preserves_boundAbove : ARtoCR.
151
152 Program Definition AQboundAbs_uc (c : AQ₊) :
153 AQ_as_MetricSpace --> AQ_as_MetricSpace := unary_uc
154 (cast AQ Q_as_MetricSpace)
155 (λ x : AQ_as_MetricSpace, (-'c) ⊔ (('c) ⊓ x) : AQ_as_MetricSpace) (QboundAbs ('c)) _.
156 Next Obligation. apply Qball_0. aq_preservation. Qed.
157
158 Definition ARboundAbs (c : AQ₊) : AR --> AR := Cmap AQPrelengthSpace (AQboundAbs_uc c).
159
160 Lemma ARtoCR_preserves_bound_abs c x : 'ARboundAbs c x = CRboundAbs ('c) ('x).
161 Proof. apply preserves_unary_fun. Qed.
162 Hint Rewrite ARtoCR_preserves_bound_abs : ARtoCR.
163
164 Program Definition AQscale_uc (x : AQ_as_MetricSpace) :
165 AQ_as_MetricSpace --> AQ_as_MetricSpace := unary_uc
166 (cast AQ Q_as_MetricSpace)
167 ((x *.) : AQ_as_MetricSpace → AQ_as_MetricSpace) (Qscale_uc ('x)) _.
168 Next Obligation. apply Qball_0. aq_preservation. Qed.
169
170 Definition ARscale (x : AQ_as_MetricSpace) : AR --> AR := Cmap AQPrelengthSpace (AQscale_uc x).
171
172 Lemma ARtoCR_preserves_scale x y : 'ARscale x y = scale ('x) ('y).
173 Proof. apply preserves_unary_fun. Qed.
174 Hint Rewrite ARtoCR_preserves_scale : ARtoCR.
175
176 Program Definition AQmult_uc (c : AQ₊) :
177 AQ_as_MetricSpace --> AQ_as_MetricSpace --> AQ_as_MetricSpace := binary_uc
178 (cast AQ Q_as_MetricSpace)
179 (λ x y : AQ_as_MetricSpace, x * AQboundAbs_uc c y : AQ_as_MetricSpace) (Qmult_uc ('c)) _.
180 Next Obligation. apply Qball_0. aq_preservation. Qed.
181
182 Definition ARmult_bounded (c : AQ₊) : AR --> AR --> AR
183 := Cmap2 AQPrelengthSpace AQPrelengthSpace (AQmult_uc c).
184
185 Lemma ARtoCR_preserves_mult_bounded x y c :
186 'ARmult_bounded c x y = CRmult_bounded ('c) ('x) ('y).
187 Proof. apply @preserves_binary_fun. Qed.
188 Hint Rewrite ARtoCR_preserves_mult_bounded : ARtoCR.
189
190 Lemma ARtoCR_approximate (x : AR) (ε : Qpos) : '(approximate x ε) = approximate ('x) ε.
191 Proof. reflexivity. Qed.
192
193 Lemma AR_b_correct (x : AR) :
194 cast AQ Q (abs (approximate x (Qpos2QposInf (1#1))) + 1) = Qabs (approximate (cast AR CR x) (Qpos2QposInf (1#1))) + (1#1).
195 Proof. aq_preservation. Qed.
196
197 Program Definition AR_b (x : AR) : AQ₊
198 := exist _ (abs (approximate x (Qpos2QposInf (1#1))) + 1) _.
199 Next Obligation.
200 apply (strictly_order_reflecting (cast AQ Q)).
201 rewrite AR_b_correct. aq_preservation.
202 apply CR_b_pos.
203 Qed.
204
205 Global Instance ARmult: Mult AR := λ x y, ARmult_bounded (AR_b y) x y.
206
207 Lemma ARtoCR_preserves_mult x y : cast AR CR (x * y) = 'x * 'y.
208 Proof.
209 unfold "*", ARmult at 1. rewrite ARtoCR_preserves_mult_bounded.
210 assert (QposEq ('AR_b y : Qpos) (CR_b (1 # 1) ('y))).
211 { unfold QposEq. simpl.
212 now rewrite ARtoCR_approximate, <-AR_b_correct. }
213 apply (CRmult_bounded_wd H5).
214 Qed.
215
216 Lemma ARmult_scale (x : AQ) (y : AR) :
217 'x * y = ARscale x y.
218 Proof.
219 apply (injective (cast AR CR)).
220 rewrite ARtoCR_preserves_mult, ARtoCR_preserves_scale, ARtoCR_inject.
221 now apply CRmult_scale.
222 Qed.
223
224 Hint Rewrite ARtoCR_preserves_mult : ARtoCR.
225
226 (* The approximate reals form a ring *)
227 Instance ARring: Ring AR.
228 Proof.
229 apply (rings.projected_ring (cast AR CR)).
230 exact ARtoCR_preserves_plus.
231 exact ARtoCR_preserves_0.
232 exact ARtoCR_preserves_mult.
233 exact ARtoCR_preserves_1.
234 exact ARtoCR_preserves_opp.
235 Qed.
236
237 Instance: SemiRing_Morphism (cast AR CR).
238 Proof.
239 split. apply _. apply _.
240 split. apply _. apply _.
241 split. apply _. apply _.
242 split. apply _. apply _.
243 apply _.
244 exact ARtoCR_preserves_plus.
245 exact ARtoCR_preserves_0.
246 split. apply _. apply _.
247 split. apply _. apply _.
248 split. apply _. apply _.
249 apply _.
250 exact ARtoCR_preserves_mult.
251 exact ARtoCR_preserves_1.
252 Qed.
253
254 Instance: SemiRing_Morphism (cast CR AR).
255 Proof. change (SemiRing_Morphism (inverse (cast AR CR))). split; apply _. Qed.
256
257 Instance: SemiRing_Morphism (cast AQ AR).
258 Proof.
259 split. apply _. apply _.
260 split. apply _. apply _.
261 split. apply _. apply _.
262 split. apply _. apply _.
263 apply _.
264 intros. apply regFunEq_equiv, regFunEq_e. intros ε. apply ball_refl.
265 apply (Qpos_nonneg (ε + ε)).
266 apply regFunEq_equiv, regFunEq_e. intros ε.
267 apply ball_refl.
268 apply (Qpos_nonneg (ε + ε)).
269
270 split. apply _. apply _.
271 split. apply _. apply _.
272 split. apply _. apply _.
273 apply _.
274 intros. rewrite ARmult_scale. apply regFunEq_equiv, regFunEq_e. intros ε.
275 apply ball_refl.
276 apply (Qpos_nonneg (ε + ε)).
277 apply regFunEq_equiv, regFunEq_e. intros ε.
278 apply ball_refl.
279 apply (Qpos_nonneg (ε + ε)).
280 Qed.
281
282 Add Ring CR : (rings.stdlib_ring_theory CR).
283 Add Ring AR : (rings.stdlib_ring_theory AR).
284
285 Lemma ARplus_comm : forall x y : AR, x + y = y + x.
286 Proof.
287 intros. ring.
288 Qed.
289
290 Lemma ARplus_assoc : forall u v w : AR,
291 (u + v) + w = u + (v + w).
292 Proof.
293 intros. ring.
294 Qed.
295
296 Lemma ARplus_opp_r :
297 forall x : AR, x - x = 0.
298 Proof.
299 intros. ring.
300 Qed.
301
302 Lemma ARmult_comm : forall x y : AR, x * y = y * x.
303 Proof.
304 intros. ring.
305 Qed.
306
307 Lemma ARmult_assoc : forall u v w : AR,
308 (u * v) * w = u * (v * w).
309 Proof.
310 intros. ring.
311 Qed.
312
313 Lemma ARmult_1_l : forall x : AR, 1 * x = x.
314 Proof.
315 intros. ring.
316 Qed.
317
318 Lemma ARmult_1_r : forall x : AR, x * 1 = x.
319 Proof.
320 intros. ring.
321 Qed.
322
323 Lemma ARopp_mult_distr_r : forall (r1 r2 : AR),
324 - (r1 * r2) = r1 * (- r2).
325 Proof.
326 intros. ring.
327 Qed.
328
329 Lemma ARopp_involutive : forall (r1 : AR), - - r1 = r1.
330 Proof.
331 intros. ring.
332 Qed.
333
334 Lemma ARplus_0_r : forall x : AR, x + 0 = x.
335 Proof.
336 intros. ring.
337 Qed.
338
339 (* Non strict order *)
340 Definition ARnonNeg (x : AR) : Prop := ∀ ε : Qpos, -cast Qpos Q ε ≤ cast AQ Q (approximate x ε).
341
342 Lemma ARtoCR_preserves_nonNeg x : ARnonNeg x ↔ CRnonNeg ('x).
343 Proof. reflexivity. Qed.
344 Hint Resolve ARtoCR_preserves_nonNeg.
345
346 Global Instance: Proper ((=) ==> iff) ARnonNeg.
347 Proof.
348 intros x1 x2 E.
349 split; intros; apply ARtoCR_preserves_nonNeg; [rewrite <-E | rewrite E]; auto.
350 Qed.
351
352 Global Instance ARle: Le AR := λ x y, ARnonNeg (y - x).
353
354 Global Instance ARle_wd: Proper ((=) ==> (=) ==> iff) ARle.
355 Proof. unfold ARle. solve_proper. Qed.
356
357 Lemma ARtoCR_preserves_le (x y : AR) : x ≤ y ↔ ' x ≤ ' y.
358 Proof.
359 unfold le, ARle, CRle.
360 now rewrite ARtoCR_preserves_nonNeg, rings.preserves_minus.
361 Qed.
362
363 Instance: PartialOrder ARle.
364 Proof.
365 apply (maps.projected_partial_order (cast AR CR)).
366 apply ARtoCR_preserves_le.
367 Qed.
368
369 Lemma ARle_trans : forall x y z : AR,
370 ARle x y -> ARle y z -> ARle x z.
371 Proof.
372 intros.
373 apply ARtoCR_preserves_le.
374 apply (@CRle_trans _ ('y)).
375 apply ARtoCR_preserves_le, H5.
376 apply ARtoCR_preserves_le, H6.
377 Qed.
378
379 Lemma ARsquare_pos : forall x : AR, ARle 0 (x*x).
380 Proof.
381 intros x.
382 apply ARtoCR_preserves_le.
383 rewrite ARtoCR_preserves_mult.
384 rewrite ARtoCR_preserves_0.
385 apply CRsquare_pos.
386 Qed.
387
388 Lemma ARplus_le_compat_l :
389 forall x y z : AR, ARle x y -> ARle (z+x) (z+y).
390 Proof.
391 intros. apply ARtoCR_preserves_le.
392 rewrite ARtoCR_preserves_plus.
393 rewrite ARtoCR_preserves_plus.
394 apply CRArith.CRplus_le_l.
395 apply ARtoCR_preserves_le in H5.
396 exact H5.
397 Qed.
398
399 Lemma ARplus_le_compat_r :
400 forall x y z : AR, ARle x y -> ARle (x+z) (y+z).
401 Proof.
402 intros. apply ARtoCR_preserves_le.
403 rewrite ARtoCR_preserves_plus.
404 rewrite ARtoCR_preserves_plus.
405 apply CRArith.CRplus_le_r.
406 apply ARtoCR_preserves_le in H5.
407 exact H5.
408 Qed.
409
410
411 Global Instance: OrderEmbedding ARtoCR.
412 Proof. repeat (split; try apply _); apply ARtoCR_preserves_le. Qed.
413
414 (* Strict order in Type *)
415 Global Instance: OrderEmbedding (cast AQ AR).
416 Proof.
417 repeat (split; try apply _); intros x y E.
418 apply (order_reflecting (cast AR CR)).
419 rewrite 2!ARtoCR_inject.
420 now do 2 apply (order_preserving _).
421 apply (order_reflecting (cast AQ Q)).
422 apply (order_reflecting (cast Q CR)).
423 rewrite <-2!ARtoCR_inject.
424 now apply (order_preserving _).
425 Qed.
426
427 Definition ARpos (x : AR) : Type := sig (λ y : AQ₊, 'y ≤ x).
428
429 Program Definition ARpos_char (ε : AQ₊) (x : AR)
430 (Pε : 'ε ≤ approximate x ((1#2) * 'ε)%Qpos) : ARpos x := Pos_shiftl ε (-1 : Z) ↾ _.
431 Next Obligation.
432 intros δ.
433 change (-('δ : Q) ≤ '(approximate x ((1 # 2) * δ)%Qpos - ('ε : AQ) ≪ (-1))).
434 transitivity (-'((1 # 2) * δ)%Qpos).
435 apply rings.flip_le_negate.
436 change ((1 # 2) * proj1_sig δ ≤ proj1_sig δ).
437 rewrite <-(rings.mult_1_l (proj1_sig δ)) at 2.
438 now apply (order_preserving (.* (proj1_sig δ))).
439 apply rings.flip_nonneg_minus.
440 transitivity (('approximate x ((1#2) * 'ε)%Qpos - 'ε)%mc : Q).
441 apply (order_preserving (cast AQ Q)) in Pε.
442 now apply rings.flip_nonneg_minus.
443 apply rings.flip_le_minus_l.
444 transitivity (((1 # 2) * 'ε + (1 # 2) * proj1_sig δ)
445 + 'approximate x ((1 # 2) * δ)%Qpos).
446 apply rings.flip_le_minus_l.
447 now destruct (regFun_prf x ((1#2) * 'ε)%Qpos ((1#2) * δ)%Qpos).
448 rewrite rings.preserves_minus, aq_shift_opp_1.
449 apply orders.eq_le.
450 change ((1 # 2) * 'ε + (1 # 2) * proj1_sig δ + 'approximate x ((1 # 2) * δ)%Qpos ==
451 'approximate x ((1 # 2) * δ)%Qpos - 'ε * (1#2) - - ((1 # 2) * proj1_sig δ) + 'ε)%Q.
452 ring.
453 Qed.
454
455 Lemma ARtoCR_preserves_pos x
456 : prod (ARpos x -> CRpos ('x))
457 (CRpos ('x) -> ARpos x).
458 Proof with auto with qarith.
459 split; intros [y E].
460 exists (cast (AQ₊) (Q₊) y).
461 change (cast Q CR (cast AQ Q (cast (AQ₊) AQ y)) ≤ cast AR CR x).
462 rewrite <-ARtoCR_inject.
463 now apply (order_preserving _).
464 destruct (aq_lt_mid 0 (proj1_sig y)) as [z [Ez1 Ez2]]...
465 assert (0 < z) as F.
466 apply (strictly_order_reflecting (cast AQ Q)). now aq_preservation...
467 exists (exist _ z F). simpl.
468 change (cast AQ AR (cast (AQ₊) AQ (z ↾ F)) ≤ x).
469 apply (order_reflecting (cast AR CR)).
470 rewrite ARtoCR_inject.
471 transitivity (cast Q CR (cast Qpos Q y)); trivial.
472 apply CRle_Qle...
473 Defined.
474
475 Lemma ARpos_wd : ∀ x1 x2, x1 = x2 → ARpos x1 → ARpos x2.
476 Proof.
477 intros x1 x2 E G.
478 destruct G. exists x.
479 rewrite <- E. exact l.
480 Defined.
481
482 Definition ARltT: AR → AR → Type := λ x y, ARpos (y - x).
483
484 Lemma ARtoCR_preserves_ltT x y
485 : prod (ARltT x y -> CRltT ('x) ('y))
486 (CRltT ('x) ('y) -> ARltT x y).
487 Proof.
488 split; intros.
489 - apply ARtoCR_preserves_pos in X.
490 eapply CRpos_wd; eauto.
491 now autorewrite with ARtoCR.
492 - apply ARtoCR_preserves_pos.
493 eapply CRpos_wd; eauto.
494 now autorewrite with ARtoCR.
495 Defined.
496
497 Lemma CRtoAR_preserves_ltT : forall x y,
498 prod (CRltT x y -> ARltT (cast CR AR x) (cast CR AR y))
499 (ARltT (cast CR AR x) (cast CR AR y) -> CRltT x y).
500 Proof.
501 intros x y.
502 pose proof (CRAR_id x) as H6.
503 pose proof (CRAR_id y) as H7.
504 split.
505 - intros. symmetry in H6. symmetry in H7.
506 pose proof (CRltT_wd H6 H7 H5).
507 apply ARtoCR_preserves_ltT in H8. exact H8.
508 - intros H5.
509 apply (CRltT_wd H6 H7).
510 apply ARtoCR_preserves_ltT. exact H5.
511 Qed.
512
513 Lemma ARltT_wd : ∀ x1 x2 : AR, x1 = x2 → ∀ y1 y2, y1 = y2 → ARltT x1 y1 → ARltT x2 y2.
514 Proof.
515 intros x1 x2 E y1 y2 F G.
516 apply (ARpos_wd (y1 + - x1)). 2: exact G.
517 rewrite E, F. reflexivity.
518 Defined.
519
520 (* Apartness in Type *)
521 Definition ARapartT: AR → AR → Type := λ x y, sum (ARltT x y) (ARltT y x).
522
523 Lemma ARapartT_wd : forall x y z t : AR,
524 msp_eq x y
525 -> msp_eq z t
526 -> ARapartT x z
527 -> ARapartT y t.
528 Proof.
529 intros. destruct X.
530 - left. apply (ARltT_wd _ _ H5 _ _ H6), a.
531 - right. apply (ARltT_wd _ _ H6 _ _ H5), a.
532 Defined.
533
534 Lemma ARtoCR_preserves_apartT x y
535 : prod (ARapartT x y -> CRapartT ('x) ('y))
536 (CRapartT ('x) ('y) -> ARapartT x y).
537 Proof. split; (intros [|]; [left|right]; now apply ARtoCR_preserves_ltT). Defined.
538
539 Lemma ARtoCR_preserves_apartT_0 x
540 : prod (ARapartT x 0 -> CRapartT ('x) 0)
541 (CRapartT ('x) 0 -> ARapartT x 0).
542 Proof.
543 split; intros.
544 - apply (@CRapartT_wd ('x)%mc _ (reflexivity _) (cast AR CR 0)).
545 apply ARtoCR_preserves_0.
546 apply ARtoCR_preserves_apartT, X.
547 - apply (@CRapartT_wd ('x)%mc _ (reflexivity _) _ (cast AR CR 0)) in H5.
548 apply ARtoCR_preserves_apartT in H5. exact H5.
549 symmetry; apply ARtoCR_preserves_0.
550 Defined.
551
552 (* Strict order in Prop *)
553
554 (* Yields Gt if x is certainly greater than 2 ^ k, Lt if x is certainly greater than -2 ^ k,
555 Eq otherwise. *)
556 Definition AR_epsilon_sign_dec (k : Z) (x : AR) : comparison :=
557 let ε : AQ₊ := Pos_shiftl 1 k in
558 let z : AQ := approximate x ((1#2) * 'ε)%Qpos in
559 if decide_rel (≤) ('ε) z
560 then Gt
561 else if decide_rel (≤) z (-'ε) then Datatypes.Lt else Eq.
562
563 Program Definition AR_epsilon_sign_dec_pos (x : AR)
564 (k : Z) (Pk : AR_epsilon_sign_dec k x ≡ Gt) : ARpos x := ARpos_char (Pos_shiftl 1 k) x _.
565 Next Obligation.
566 revert Pk. unfold AR_epsilon_sign_dec.
567 case (decide_rel (≤)); [ intros; assumption |].
568 case (decide_rel (≤)); discriminate.
569 Qed.
570
571 Program Definition AR_epsilon_sign_dec_neg (x : AR)
572 (k : Z) (Pk : AR_epsilon_sign_dec k x ≡ Datatypes.Lt) : ARpos (-x) := ARpos_char (Pos_shiftl 1 k) (-x) _.
573 Next Obligation.
574 revert Pk. unfold AR_epsilon_sign_dec.
575 case (decide_rel (≤)); [discriminate |].
576 case (decide_rel (≤)); [| discriminate].
577 intros. apply rings.flip_le_negate.
578 now rewrite rings.negate_involutive.
579 Qed.
580
581 Definition AR_epsilon_sign_dec_apartT (x y : AR)
582 (k : Z) (Pk : ¬AR_epsilon_sign_dec k (x - y) ≡ Eq) : ARapartT x y.
583 Proof.
584 revert Pk.
585 case_eq (AR_epsilon_sign_dec k (x - y)); intros E ?.
586 now destruct Pk.
587 left. apply ARpos_wd with (-(x - y)).
588 ring.
589 now apply AR_epsilon_sign_dec_neg with k.
590 right. now apply AR_epsilon_sign_dec_pos with k.
591 Defined.
592
593 Lemma AR_epsilon_sign_dec_Gt (k : Z) (x : AR) :
594 1 ≪ k ≤ approximate x (Qpos_mult (1#2) ('Pos_shiftl (1:AQ₊) k)) → AR_epsilon_sign_dec k x ≡ Gt.
595 Proof.
596 intros.
597 unfold AR_epsilon_sign_dec.
598 case (decide_rel _); intuition.
599 Qed.
600
601 Lemma AR_epsilon_sign_dec_pos_rev (x : AR) (k : Z) :
602 cast AQ AR (1 ≪ (1 + k)) ≤ x → AR_epsilon_sign_dec k x ≡ Gt.
603 Proof.
604 intros E.
605 apply AR_epsilon_sign_dec_Gt.
606 apply (order_reflecting (+ -1 ≪ (1 + k))).
607 transitivity (-1 ≪ k).
608 apply orders.eq_le.
609 rewrite (commutativity _ k), shiftl.shiftl_exp_plus, shiftl.shiftl_1.
610 rewrite rings.plus_mult_distr_r, rings.mult_1_l.
611 rewrite rings.negate_plus_distr, associativity, rings.plus_negate_r. simpl. ring.
612 apply (order_reflecting (cast AQ Q)).
613 rewrite rings.preserves_negate.
614 exact (E ('Pos_shiftl (1 : AQ₊) k)).
615 Qed.
616
617 (* Hack: we write [-1 - cast nat Z n] instead of [cast nat Z n] because
618 approximate is not Proper. *)
619 Global Instance ARlt: Lt AR := λ x y,
620 ∃ n : nat, AR_epsilon_sign_dec (-1 - cast nat Z n) (y - x) ≡ Gt.
621
622 Lemma AR_lt_ltT x y : prod (x < y -> ARltT x y)
623 (ARltT x y -> x < y).
624 Proof.
625 split.
626 - intros E.
627 apply ConstructiveEpsilon.constructive_indefinite_description_nat in E.
628 destruct E as [n En].
629 now apply AR_epsilon_sign_dec_pos with (-1 - cast nat Z n).
630 intros. now apply comparison_eq_dec.
631 - intros [ε Eε].
632 exists (Z.nat_of_Z (-Qdlog2 ('ε))).
633 apply AR_epsilon_sign_dec_pos_rev.
634 transitivity ('ε : AR); [| assumption].
635 rapply (order_preserving (cast AQ AR)).
636 apply (order_reflecting (cast AQ Q)).
637 rewrite aq_shift_correct, rings.preserves_1, rings.mult_1_l.
638 destruct (decide (('ε : Q) ≤ 1)).
639 rewrite Z.nat_of_Z_nonneg.
640 mc_setoid_replace (1 + (-1 - - Qdlog2 ('ε))) with (Qdlog2 ('ε)) by ring.
641 apply Qdlog2_spec.
642 apply semirings.preserves_pos.
643 now destruct ε.
644 change (0 ≤ -Qdlog2 ('ε)).
645 apply rings.flip_nonpos_negate.
646 now apply Qdlog2_nonpos.
647 rewrite Z.nat_of_Z_nonpos.
648 now apply orders.le_flip.
649 change (-Qdlog2 ('ε) ≤ 0).
650 apply rings.flip_nonneg_negate.
651 apply Qdlog2_nonneg.
652 now apply orders.le_flip.
653 Qed.
654
655 Instance: Proper ((=) ==> (=) ==> iff) ARlt.
656 Proof. split; intro E; apply AR_lt_ltT; apply AR_lt_ltT in E;
657 eapply ARltT_wd; eauto; now symmetry. Qed.
658
659 (* Apartness in Prop *)
660 Global Instance ARapart: Apart AR := λ x y, x < y ∨ y < x.
661
662 Lemma ARtoCR_preserves_lt (x y : AR) : x < y ↔ 'x < 'y.
663 Proof.
664 split; intros E.
665 now apply CR_lt_ltT, ARtoCR_preserves_ltT, AR_lt_ltT.
666 now apply AR_lt_ltT, ARtoCR_preserves_ltT, CR_lt_ltT.
667 Qed.
668
669 Lemma AR_apart_apartT x y : prod (x ≶ y -> ARapartT x y)
670 (ARapartT x y -> x ≶ y).
671 Proof.
672 split.
673 - intros E.
674 set (f (n : nat) := AR_epsilon_sign_dec (-1 - cast nat Z n)).
675 assert (∃ n, f n (y - x) ≡ Gt ∨ f n (x - y) ≡ Gt) as E2.
676 now destruct E as [[n En] | [n En]]; exists n; [left | right].
677 apply ConstructiveEpsilon.constructive_indefinite_description_nat in E2.
678 destruct E2 as [n E2].
679 destruct (comparison_eq_dec (f n (y - x)) Gt) as [En|En].
680 left. now apply AR_epsilon_sign_dec_pos with (-1 - cast nat Z n).
681 right. apply AR_epsilon_sign_dec_pos with (-1 - cast nat Z n).
682 destruct E2; tauto.
683 intros n.
684 destruct (comparison_eq_dec (f n (y - x)) Gt); auto.
685 destruct (comparison_eq_dec (f n (x - y)) Gt); tauto.
686 - intros [E|E].
687 left. now apply AR_lt_ltT.
688 right. now apply AR_lt_ltT.
689 Qed.
690
691 Let ARtoCR_preserves_apart x y : x ≶ y ↔ cast AR CR x ≶ cast AR CR y.
692 Proof.
693 unfold apart, ARapart, CRapart.
694 now rewrite !ARtoCR_preserves_lt.
695 Qed.
696
697 Instance: StrongSetoid AR.
698 Proof.
699 apply (strong_setoids.projected_strong_setoid (cast AR CR)).
700 split; intros E; [now rewrite E | now apply (injective (cast AR CR))].
701 now apply ARtoCR_preserves_apart.
702 Qed.
703
704 Instance: StrongSetoid_Morphism (cast AR CR).
705 Proof. split; try apply _; now apply ARtoCR_preserves_apart. Qed.
706
707 Global Instance: StrongInjective (cast AR CR).
708 Proof. split; try apply _; now apply ARtoCR_preserves_apart. Qed.
709
710 Global Instance: StrongSemiRing_Morphism (cast AR CR).
711 Proof. split; try apply _. Qed.
712
713 Global Instance: StrongSemiRing_Morphism (cast AQ AR).
714 Proof.
715 repeat (split; try apply _). intros.
716 apply (strong_extensionality (cast AQ Q)).
717 apply (strong_extensionality (cast Q CR)).
718 rewrite <-2!ARtoCR_inject.
719 now apply (strong_injective _).
720 Qed.
721
722 Global Instance: StrongInjective (cast AQ AR).
723 Proof.
724 repeat (split; try apply _). intros.
725 apply (strong_extensionality (cast AR CR)).
726 rewrite 2!ARtoCR_inject.
727 apply (strong_injective _).
728 now apply (strong_injective _).
729 Qed.
730
731 Global Instance ARfpsro: FullPseudoSemiRingOrder ARle ARlt.
732 Proof.
733 apply (rings.projected_full_pseudo_ring_order (cast AR CR)).
734 apply ARtoCR_preserves_le.
735 apply ARtoCR_preserves_lt.
736 Qed.
737
738 Lemma ARle_not_lt (x y: AR): ARle x y <-> (ARltT y x -> False).
739 Proof.
740 destruct ARfpsro as [_ flip].
741 specialize (flip x y). destruct flip.
742 split.
743 - intros. apply H5. exact H7.
744 apply AR_lt_ltT, X.
745 - intros. apply H6. intro abs. apply H7.
746 apply AR_lt_ltT, abs.
747 Qed.
748
749 Global Instance: StrictOrderEmbedding (cast AR CR).
750 Proof. repeat (split; try apply _); apply ARtoCR_preserves_lt. Qed.
751
752 (* Division *)
753 Lemma aq_mult_inv_regular_prf (x : AQ) :
754 is_RegularFunction_noInf _ (λ ε : Qpos, app_div 1 x (Qdlog2 (proj1_sig ε)) : AQ_as_MetricSpace).
755 Proof.
756 intros ε1 ε2. simpl.
757 eapply ball_triangle.
758 now eapply aq_div_dlog2.
759 now eapply ball_sym, aq_div_dlog2.
760 Qed.
761
762 Definition AQinv (x : AQ) : AR := mkRegularFunction (0 : AQ_as_MetricSpace) (aq_mult_inv_regular_prf x).
763
764 Definition AQinv_bounded (c : AQ₊) (x : AQ_as_MetricSpace) : AR := AQinv (('c) ⊔ x).
765
766 Lemma AQinv_pos_uc_prf (c : AQ₊) : is_UniformlyContinuousFunction
767 (AQinv_bounded c) (Qinv_modulus ('c)).
768 Proof.
769 intros ε x y E δ1 δ2. simpl in *.
770 eapply ball_triangle.
771 2: now eapply ball_sym, aq_div_dlog2.
772 eapply ball_triangle.
773 now eapply aq_div_dlog2.
774 simpl. aq_preservation.
775 rewrite 2!left_identity.
776 pose proof (Qinv_pos_uc_prf (' c) ε (' x) (' y)) as H5.
777 simpl in H5. apply H5.
778 exact E.
779 Qed.
780
781 Definition AQinv_pos_uc (c : AQ₊) := Build_UniformlyContinuousFunction (AQinv_pos_uc_prf c).
782
783 Definition ARinv_pos (c : AQ₊) : AR --> AR := Cbind AQPrelengthSpace (AQinv_pos_uc c).
784
785 Lemma ARtoCR_preserves_inv_pos_aux c (x : AR) : is_RegularFunction_noInf _
786 (λ γ, / Qmax (''c) ('approximate x (Qinv_modulus ('c) γ)) : Q_as_MetricSpace).
787 Proof.
788 intros ε1 ε2.
789 apply_simplified (Qinv_pos_uc_prf ('c) (ε1 + ε2)%Qpos).
790 apply AQball_fold.
791 setoid_replace (' c * ' c * (` ε1 + ` ε2))%Q
792 with (proj1_sig (Qinv_modulus ('c) ε1 + Qinv_modulus ('c) ε2)%Qpos)
793 by (unfold equiv, stdlib_rationals.Q_eq; simpl; ring).
794 apply regFun_prf.
795 Qed.
796
797 Lemma ARtoCR_preserves_inv_pos x c : 'ARinv_pos c x = CRinv_pos ('c) ('x).
798 Proof.
799 apply regFunEq_equiv, regFunEq_e. intros ε.
800 simpl. unfold Cjoin_raw. simpl.
801 setoid_replace (proj1_sig ε + proj1_sig ε)%Q
802 with (proj1_sig ((1#2) * ε + ((1#2) * ε + ε)))%Qpos
803 by (unfold equiv, stdlib_rationals.Q_eq; simpl; ring).
804 eapply ball_triangle.
805 now apply aq_div_dlog2.
806 simpl.
807 rewrite aq_preserves_max.
808 rewrite rings.preserves_1.
809 rewrite Qmult_1_l.
810 change (Qball ( (1 # 2) * ` ε + ` ε)
811 (/ Qmax (' (' c)) (' approximate x (Qinv_modulus (' c) ((1 # 2) ↾ eq_refl * ε))))%mc
812 ( / Qmax (' c) (' approximate x (Qinv_modulus (' c) ε)))).
813 apply (ARtoCR_preserves_inv_pos_aux c x ((1 # 2) * ε)%Qpos).
814 Qed.
815 Hint Rewrite ARtoCR_preserves_inv_pos : ARtoCR.
816
817 Definition ARinvT (x : AR) (x_ : ARapartT x 0) : AR :=
818 match x_ with
819 | inl (exist _ c _) => - ARinv_pos c (- x)
820 | inr (exist _ c _) => ARinv_pos c x
821 end.
822
823 Lemma ARtoCR_preserves_invT x x_ x__:
824 'ARinvT x x_ = CRinvT ('x) x__.
825 Proof with auto with qarith; try reflexivity.
826 unfold ARinvT.
827 destruct x_ as [Ec | Ec].
828 assert (CRltT ('x) 0) as Px.
829 apply CRltT_wd with ('x) (cast AR CR 0).
830 reflexivity.
831 now apply rings.preserves_0.
832 now apply ARtoCR_preserves_ltT.
833 rewrite (CRinvT_irrelevant _ (inl Px)).
834 unfold CRinvT.
835 destruct Ec as [c Ec], Px as [d Ed].
836 autorewrite with ARtoCR.
837 destruct (Qlt_le_dec (proj1_sig d) (proj1_sig ('c : Qpos))).
838 rewrite (CRinv_pos_weaken d ('c))...
839 change (cast Q CR (cast AQ Q (cast (AQ₊) AQ c)) ≤ -cast AR CR x).
840 rewrite <-ARtoCR_inject, <-rings.preserves_negate.
841 apply (order_preserving _).
842 rewrite <-(rings.plus_0_l (-x))...
843 rewrite (CRinv_pos_weaken ('c) d)...
844 rewrite <-(rings.plus_0_l (-cast AR CR x))...
845 assert (CRltT 0 ('x)) as Px.
846 apply CRltT_wd with (cast AR CR 0) ('x).
847 now apply rings.preserves_0.
848 reflexivity.
849 now apply ARtoCR_preserves_ltT.
850 rewrite (CRinvT_irrelevant _ (inr Px)).
851 unfold CRinvT.
852 destruct Ec as [c Ec], Px as [d Ed].
853 autorewrite with ARtoCR.
854 destruct (Qlt_le_dec (proj1_sig d) (proj1_sig ('c : Qpos))).
855 rewrite (CRinv_pos_weaken d ('c))...
856 change (cast Q CR (cast AQ Q (cast (AQ₊) AQ c)) ≤ cast AR CR x).
857 rewrite <-ARtoCR_inject.
858 apply (order_preserving _).
859 setoid_replace x with (x - 0) by ring...
860 rewrite (CRinv_pos_weaken ('c) d)...
861 rewrite <-(rings.plus_0_r (cast AR CR x))...
862 Qed.
863
864 Lemma ARtoCR_preserves_invT_l x x_ : {x__ | 'ARinvT x x_ = CRinvT ('x) x__}.
865 Proof.
866 exists (fst (ARtoCR_preserves_apartT_0 x) x_).
867 apply ARtoCR_preserves_invT.
868 Qed.
869
870 Lemma ARtoCR_preserves_invT_r x x__ : {x_ | 'ARinvT x x_ = CRinvT ('x) x__}.
871 Proof.
872 exists (snd (ARtoCR_preserves_apartT_0 x) x__).
873 apply ARtoCR_preserves_invT.
874 Qed.
875
876 Lemma AR_inverseT (x : AR) x_ : x * ARinvT x x_ = 1.
877 Proof.
878 apply (injective (cast AR CR)).
879 rewrite rings.preserves_mult, rings.preserves_1.
880 destruct (ARtoCR_preserves_invT_l x x_) as [x__ E]. rewrite E.
881 apply CRmult_inv_r.
882 Qed.
883
884 Lemma ARinvT_wd x y x_ y_ : x = y → ARinvT x x_ = ARinvT y y_.
885 Proof.
886 intros E.
887 apply (injective (cast AR CR)).
888 destruct (ARtoCR_preserves_invT_l x x_) as [x__ Ex],
889 (ARtoCR_preserves_invT_l y y_) as [y__ Ey].
890 rewrite Ex, Ey.
891 now apply CRinvT_wd.
892 Qed.
893
894 Lemma ARinvT_irrelevant x x_ x__ : ARinvT x x_ = ARinvT x x__.
895 Proof. now apply ARinvT_wd. Qed.
896
897 (* Division with apartness in Prop *)
898 Program Instance ARinv: Recip AR := λ x, ARinvT x _.
899 Next Obligation. apply AR_apart_apartT. now destruct x. Qed.
900
901 Global Instance: Field AR.
902 Proof.
903 split. apply _. apply _.
904 apply _. apply _.
905 apply (strong_injective (cast AQ AR)).
906 solve_propholds.
907 split. apply _. apply _.
908 intros [x Px] [y Py] E.
909 now refine (ARinvT_wd _ _ _ _ _).
910 intros x.
911 now apply AR_inverseT.
912 Qed.
913
914 (* Nat pow *)
915 Program Definition AQpower_N_uc (n : N) (c : AQ₊) :
916 AQ_as_MetricSpace --> AQ_as_MetricSpace := unary_uc
917 (cast AQ Q_as_MetricSpace)
918 (λ x : AQ_as_MetricSpace, (AQboundAbs_uc c x) ^ n : AQ_as_MetricSpace) (Qpower_N_uc n ('c)) _.
919 Next Obligation.
920 assert (∀ y : AQ, cast AQ Q (y ^ n) = 'y ^ 'n) as preserves_pow_pos.
921 intros y.
922 rewrite nat_pow.preserves_nat_pow.
923 now rewrite (int_pow.int_pow_nat_pow (f:=cast N Z)).
924 apply Qball_0.
925 rewrite preserves_pow_pos. aq_preservation.
926 Qed.
927
928 Definition ARpower_N_bounded (n : N) (c : AQ₊) : AR --> AR := Cmap AQPrelengthSpace (AQpower_N_uc n c).
929
930 Lemma ARtoCR_preserves_power_N_bounded x n c :
931 'ARpower_N_bounded n c x = CRpower_N_bounded n ('c) ('x).
932 Proof. apply preserves_unary_fun. Qed.
933
934 Global Instance ARpower_N: Pow AR N := λ x n, ucFun (ARpower_N_bounded n (AR_b x)) x.
935
936 Lemma ARtoCR_preserves_power_N (x : AR) (n : N) :
937 cast AR CR (x ^ n) = ('x) ^ n.
938 Proof.
939 unfold pow, CRpower_N, ARpower_N.
940 rewrite ARtoCR_preserves_power_N_bounded.
941 apply Cmap_wd. 2: reflexivity.
942 assert (QposEq (cast (AQ₊) (Q₊) (AR_b x)) (CR_b (1#1) ('x))).
943 { unfold QposEq. simpl.
944 now rewrite ARtoCR_approximate, <-AR_b_correct. }
945 rewrite H5. reflexivity.
946 Qed.
947
948 Hint Rewrite ARtoCR_preserves_power_N : ARtoCR.
949
950 Global Instance: NatPowSpec AR N _.
951 Proof.
952 split.
953 intros ? ? Ex ? ? En.
954 apply (injective (cast AR CR)). autorewrite with ARtoCR.
955 now rewrite Ex, En.
956 intros. apply (injective (cast AR CR)). autorewrite with ARtoCR.
957 now rewrite nat_pow_0.
958 intros. apply (injective (cast AR CR)). autorewrite with ARtoCR.
959 now rewrite nat_pow_S.
960 Qed.
961
962 (* Misc properties *)
963 Lemma ARmult_bounded_mult (x y : AR) c :
964 -'c ≤ y ≤ 'c → ARmult_bounded c x y = x * y.
965 Proof.
966 intros.
967 apply (injective (cast AR CR)).
968 rewrite ARtoCR_preserves_mult, ARtoCR_preserves_mult_bounded.
969 destruct c as [c Pc].
970 apply CRmult_bounded_mult.
971 change (cast Q CR (-cast AQ Q c) ≤ cast AR CR y).
972 rewrite <-rings.preserves_negate.
973 rewrite <-ARtoCR_inject.
974 apply (order_preserving _). intuition.
975 change (cast AR CR y ≤ cast Q CR (cast AQ Q c)).
976 rewrite <-ARtoCR_inject.
977 apply (order_preserving _). intuition.
978 Qed.
979
980 Lemma ARpower_N_bounded_N_power (n : N) (x : AR) (c : AQ₊) :
981 -'c ≤ x ≤ 'c → ARpower_N_bounded n c x = x ^ n.
982 Proof.
983 intros.
984 apply (injective (cast AR CR)).
985 rewrite ARtoCR_preserves_power_N, ARtoCR_preserves_power_N_bounded.
986 destruct c as [c Pc].
987 apply CRpower_N_bounded_N_power. split.
988 change (cast Q CR (-cast AQ Q c) ≤ cast AR CR x).
989 rewrite <-rings.preserves_negate.
990 rewrite <-ARtoCR_inject.
991 apply (order_preserving _). intuition.
992 change (cast AR CR x ≤ cast Q CR (cast AQ Q c)).
993 rewrite <-ARtoCR_inject.
994 apply (order_preserving _). intuition.
995 Qed.
996
997 Lemma inject_Q_AR_lt : ∀ q r : Q, q < r → ARltT (inject_Q_AR q) (inject_Q_AR r).
998 Proof.
999 intros.
1000 destruct (ARtoCR_preserves_ltT (' (' q)%CR) (' (' r)%CR)) as [_ a].
1001 pose proof (inject_Q_AR_CR q).
1002 pose proof (inject_Q_AR_CR r).
1003 symmetry in H6. symmetry in H7.
1004 apply (ARltT_wd _ _ H6 _ _ H7).
1005 apply a. clear a H6 H7.
1006 pose proof (CRAR_id ('q)%CR). pose proof (CRAR_id ('r)%CR).
1007 symmetry in H6. symmetry in H7.
1008 apply (@CRltT_wd _ _ H6 _ _ H7).
1009 apply CRlt_Qlt, H5.
1010 Qed.
1011
1012 Lemma inject_Q_AR_lt_rev : ∀ q r : Q, ARltT (inject_Q_AR q) (inject_Q_AR r) → q < r.
1013 Proof.
1014 intros.
1015 destruct (ARtoCR_preserves_ltT (' (' q)%CR) (' (' r)%CR)) as [c _].
1016 pose proof (inject_Q_AR_CR q) as H6.
1017 pose proof (inject_Q_AR_CR r) as H7.
1018 apply (ARltT_wd _ _ H6 _ _ H7) in X.
1019 apply c in X. clear c H6 H7.
1020 pose proof (CRAR_id ('q)%CR). pose proof (CRAR_id ('r)%CR).
1021 apply (@CRltT_wd _ _ H5 _ _ H6) in X.
1022 apply Qlt_from_CRlt, X.
1023 Qed.
1024
1025 Lemma inject_Q_AR_le : ∀ q r : Q, q <= r → ARle (inject_Q_AR q) (inject_Q_AR r).
1026 Proof.
1027 intros.
1028 apply ARle_not_lt.
1029 intro abs.
1030 apply inject_Q_AR_lt_rev in abs.
1031 exact (Qlt_not_le _ _ abs H5).
1032 Qed.
1033
1034 Lemma inject_Q_AR_plus : ∀ q r : Q,
1035 inject_Q_AR (q + r) = inject_Q_AR q + inject_Q_AR r.
1036 Proof.
1037 intros.
1038 apply (injective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace))).
1039 pose proof CRAR_id as H5.
1040 unfold cast in H5.
1041 unfold ARtoCR, ARtoCR_uc in H5.
1042 unfold cast.
1043 rewrite (inject_Q_AR_CR (q+r)).
1044 rewrite (inject_Q_AR_CR q).
1045 rewrite (inject_Q_AR_CR r).
1046 unfold cast. unfold cast in H5.
1047 rewrite H5.
1048 pose proof (ARtoCR_preserves_plus (CRtoAR (' q)%CR) (CRtoAR (' r)%CR)) as H6.
1049 rewrite H6.
1050 rewrite <- CRplus_Qplus.
1051 apply ucFun2_wd. rewrite (H5 ('q)%CR). reflexivity.
1052 rewrite (H5 ('r)%CR). reflexivity.
1053 Qed.
1054
1055 Lemma inject_Q_AR_mult : ∀ q r : Q,
1056 inject_Q_AR (q * r) = inject_Q_AR q * inject_Q_AR r.
1057 Proof.
1058 intros.
1059 apply (injective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace))).
1060 pose proof CRAR_id as H5.
1061 unfold cast in H5.
1062 unfold ARtoCR, ARtoCR_uc in H5.
1063 rewrite (inject_Q_AR_CR (q*r)).
1064 rewrite (inject_Q_AR_CR q).
1065 rewrite (inject_Q_AR_CR r).
1066 unfold cast. unfold cast in H5.
1067 rewrite H5.
1068 pose proof (ARtoCR_preserves_mult (CRtoAR (' q)%CR) (CRtoAR (' r)%CR)) as H6.
1069 rewrite H6.
1070 rewrite <- CRmult_Qmult.
1071 apply CRmult_wd. rewrite (H5 ('q)%CR). reflexivity.
1072 rewrite (H5 ('r)%CR). reflexivity.
1073 Qed.
1074
1075 Lemma inject_Q_AR_1 : inject_Q_AR (1#1) = 1.
1076 Proof.
1077 Local Transparent regFunEq.
1078 intros e1 e2. simpl.
1079 destruct aq_dense_embedding.
1080 specialize (dense_inverse 1 e1).
1081 simpl in dense_inverse.
1082 rewrite Qplus_0_r.
1083 apply (@ball_weak_le Q_as_MetricSpace (`e1) (`e1+`e2)).
1084 apply (Qle_trans _ (`e1 + 0)).
1085 rewrite Qplus_0_r. apply Qle_refl.
1086 apply Qplus_le_r, Qpos_nonneg.
1087 simpl. unfold cast.
1088 destruct aq_ring_morphism, semiringmor_mult_mor.
1089 rewrite preserves_mon_unit.
1090 exact dense_inverse.
1091 Qed.
1092
1093 Lemma inject_Q_AR_0 : inject_Q_AR (0#1) = 0.
1094 Proof.
1095 intros e1 e2. simpl.
1096 destruct aq_dense_embedding.
1097 simpl in dense_inverse.
1098 rewrite Qplus_0_r.
1099 apply (@ball_weak_le Q_as_MetricSpace (`e1) (`e1+`e2)).
1100 apply (Qle_trans _ (`e1 + 0)).
1101 rewrite Qplus_0_r. apply Qle_refl.
1102 apply Qplus_le_r, Qpos_nonneg.
1103 simpl. unfold cast.
1104 destruct aq_ring_morphism, semiringmor_plus_mor.
1105 rewrite preserves_mon_unit.
1106 apply dense_inverse.
1107 Qed.
1108
1109
1110 Lemma inject_Q_AR_wd : forall q r : Q,
1111 q == r -> inject_Q_AR q = inject_Q_AR r.
1112 Proof.
1113 intros q r qreq e1 e2.
1114 simpl.
1115 destruct aq_dense_embedding.
1116 unfold cast.
1117 rewrite Qplus_0_r.
1118 apply ball_triangle with (b:=q).
1119 apply dense_inverse.
1120 simpl.
1121 rewrite qreq.
1122 change (Qball (` e2) r (AQtoQ (app_inverse AQtoQ r e2))).
1123 apply ball_sym.
1124 apply dense_inverse.
1125 Qed.
1126
1127 Lemma AR_mult_0_lt_compat : ∀ x y : AR,
1128 ARltT (inject_Q_AR 0) x
1129 → ARltT (inject_Q_AR 0) y
1130 → ARltT (inject_Q_AR 0) (ARmult x y).
1131 Proof.
1132 intros x y X X0.
1133 destruct (ARtoCR_preserves_ltT (inject_Q_AR 0) (ARmult x y)) as [_ a].
1134 apply a. clear a.
1135 pose proof (ARtoCR_preserves_mult x y) as H5.
1136 unfold mult in H5.
1137 symmetry in H5.
1138 assert (0 = ARtoCR (inject_Q_AR 0))%CR as H7.
1139 { rewrite <- (CRAR_id 0%CR).
1140 unfold cast.
1141 rewrite (inject_Q_AR_CR 0). reflexivity. }
1142 pose proof (ARtoCR_preserves_mult x y) as H8.
1143 symmetry in H8.
1144 apply (CRltT_wd H7 H8). clear H8 H5.
1145 apply CRmult_lt_0_compat.
1146 - destruct (ARtoCR_preserves_ltT (inject_Q_AR 0) x).
1147 apply c in X. clear a c.
1148 symmetry in H7.
1149 apply (CRltT_wd H7 (reflexivity _)). exact X.
1150 - destruct (ARtoCR_preserves_ltT (inject_Q_AR 0) y).
1151 apply c in X0. clear a c.
1152 symmetry in H7.
1153 apply (CRltT_wd H7 (reflexivity _)). exact X0.
1154 Qed.
1155
1156 Lemma AR_mult_0_le_compat : ∀ x y : AR,
1157 ARle 0 x
1158 → ARle 0 y
1159 → ARle 0 (x*y).
1160 Proof.
1161 intros.
1162 apply ARtoCR_preserves_le.
1163 rewrite ARtoCR_preserves_mult.
1164 rewrite ARtoCR_preserves_0.
1165 apply (CRmult_le_0_compat ('x) ('y)).
1166 rewrite <- ARtoCR_preserves_0.
1167 apply ARtoCR_preserves_le, H5.
1168 rewrite <- ARtoCR_preserves_0.
1169 apply ARtoCR_preserves_le, H6.
1170 Qed.
1171
1172
1173 End ARarith.