Debian Codegraph @

reals/stdlib/ConstructiveFasterReals.v

raw
1 (*
2 Copyright © 2020 Vincent Semeria
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
5
6 The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
7
8 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
9 *)
10
11
12 (** Proof that CoRN's faster reals implement the standard library's
13 interface ConstructiveReals. *)
14
15 Require Import Coq.Reals.Abstract.ConstructiveReals.
16 Require Import CoRN.reals.faster.ARArith.
17 Require Import CoRN.reals.faster.ARabs.
18 Require Import CoRN.metric2.Metric.
19 Require Import CoRN.metric2.Complete.
20 Require Import CoRN.metric2.MetricMorphisms.
21 Require Import CoRN.model.metric2.Qmetric.
22 Require Import CoRN.model.totalorder.QposMinMax.
23 Require Import CoRN.reals.fast.CRArith.
24 Require Import CoRN.reals.fast.CRabs.
25 Require Import ConstructiveFastReals.
26
27 Section ConstructiveFaster.
28
29 Context {AQ : Set} `{AppRationals AQ}.
30
31 (* Redefine ARltT in sort Set *)
32 Definition AQPosS : Set := sig (lt zero).
33 Definition ARposS (x : AR) : Set := sig (λ y : AQPosS, 'y ≤ x).
34 Definition ARltS: AR → AR → Set := λ x y, ARposS (ARplus y (ARopp x)).
35
36 Lemma ARltS_correct : eq ARltT ARltS.
37 Proof. reflexivity. Qed.
38
39 Lemma ARltS_linear : @isLinearOrder (RegularFunction (Eball (cast AQ Q))) ARltS.
40 Proof.
41 destruct ARfpsro, full_pseudo_srorder_pso.
42 destruct pseudo_srorder_strict.
43 split. split.
44 - intros x y J J0.
45 pose proof (AR_lt_ltT x y) as [_ J1].
46 pose proof (AR_lt_ltT y x) as [_ J2].
47 exact (pseudo_order_antisym x y (conj (J1 J) (J2 J0))).
48 - intros.
49 destruct (ARtoCR_preserves_ltT x z) as [_ a].
50 apply a. clear a.
51 destruct (ARtoCR_preserves_ltT x y) as [a _].
52 apply a in H5. clear a.
53 destruct (ARtoCR_preserves_ltT y z) as [a _].
54 apply a in H6.
55 apply (CRlt_trans _ _ _ H5 H6).
56 - intros x y z J.
57 destruct (CRlt_linear (cast AR CR x) (cast AR CR y) (cast AR CR z)).
58 apply (ARtoCR_preserves_ltT x z), J.
59 left. destruct (ARtoCR_preserves_ltT x y). apply a, c.
60 right. destruct (ARtoCR_preserves_ltT y z). apply a, c.
61 Qed.
62
63 Lemma ARlt_or_epsilon : forall a b c d : AR,
64 ARlt a b \/ ARlt c d -> ARltS a b + ARltS c d.
65 Proof.
66 intros. destruct (CRlt_or_epsilon (cast AR CR a) (cast AR CR b)
67 (cast AR CR c) (cast AR CR d)).
68 - destruct H5. left.
69 apply CR_lt_ltT, (ARtoCR_preserves_ltT a b), AR_lt_ltT. exact H5.
70 right.
71 apply CR_lt_ltT, (ARtoCR_preserves_ltT c d), AR_lt_ltT. exact H5.
72 - left.
73 apply (ARtoCR_preserves_ltT a b). exact c0.
74 - right.
75 apply (ARtoCR_preserves_ltT c d). exact c0.
76 Qed.
77
78 Lemma AReq_nlt : forall a b : AR,
79 msp_eq a b
80 <-> (fun x y : AR =>
81 (fun x0 y0 : AR => (ARltS y0 x0) -> False) y x /\
82 (fun x0 y0 : AR => (ARltS y0 x0) -> False) x y) a b.
83 Proof.
84 split.
85 - split.
86 pose proof (ARle_not_lt b a) as [H6 _]. apply H6.
87 rewrite H5. apply PreOrder_Reflexive.
88 pose proof (ARle_not_lt a b) as [H6 _]. apply H6.
89 rewrite H5. apply PreOrder_Reflexive.
90 - intros [J J0]. apply po_antisym.
91 pose proof (ARle_not_lt a b) as [_ H6].
92 apply (H6 J0).
93 pose proof (ARle_not_lt b a) as [_ H6].
94 apply (H6 J).
95 Qed.
96
97 Lemma inject_Q_AR_plus_nlt : ∀ q r : Q,
98 (ARltS (inject_Q_AR (q + r)) (ARplus (inject_Q_AR q) (inject_Q_AR r)) → False)
99 ∧ (ARltS (ARplus (inject_Q_AR q) (inject_Q_AR r)) (inject_Q_AR (q + r)) → False).
100 Proof.
101 intros. rewrite <- AReq_nlt.
102 pose proof (inject_Q_AR_plus q r).
103 simpl in H5. simpl. exact H5.
104 Qed.
105
106 Lemma inject_Q_AR_mult_nlt : ∀ q r : Q,
107 (ARltS (inject_Q_AR (q * r)) (ARmult (inject_Q_AR q) (inject_Q_AR r)) → False)
108 ∧ (ARltS (ARmult (inject_Q_AR q) (inject_Q_AR r)) (inject_Q_AR (q * r)) → False).
109 Proof.
110 intros. rewrite <- AReq_nlt.
111 pose proof (inject_Q_AR_mult q r).
112 simpl in H5. exact H5.
113 Qed.
114
115 Lemma AR_zero : msp_eq (inject_Q_AR 0) (cast AQ AR zero0).
116 Proof.
117 pose proof (ARtoCR_inject zero0) as H5.
118 unfold cast in H5. unfold cast.
119 rewrite inject_Q_AR_CR.
120 apply (injective ARtoCR).
121 rewrite H5.
122 pose proof CRAR_id as H6.
123 unfold cast in H6. rewrite (H6 (0%CR)).
124 apply inject_Q_CR_wd.
125 symmetry. apply rings.preserves_0.
126 Qed.
127
128 Lemma AR_one : msp_eq (inject_Q_AR 1) (cast AQ AR one0).
129 Proof.
130 pose proof (ARtoCR_inject one0) as H5.
131 unfold cast in H5. unfold cast.
132 rewrite inject_Q_AR_CR.
133 apply (injective ARtoCR).
134 rewrite H5.
135 pose proof CRAR_id.
136 unfold cast in H6. rewrite (H6 (1%CR)).
137 apply inject_Q_CR_wd.
138 symmetry. apply rings.preserves_1.
139 Qed.
140
141 Lemma AR_ring : ring_theory (inject_Q_AR 0) (inject_Q_AR 1) ARplus ARmult
142 (λ x y : AR, ARplus x (ARopp y)) ARopp
143 (λ x y : AR,
144 (λ x0 y0 : AR, ARltS y0 x0 → False) y x
145 ∧ (λ x0 y0 : AR, ARltS y0 x0 → False) x y).
146 Proof.
147 destruct (rings.stdlib_ring_theory AR).
148 split.
149 - intros. apply AReq_nlt. rewrite AR_zero. apply (Radd_0_l x).
150 - intros. apply AReq_nlt. apply (Radd_comm x y).
151 - intros. apply AReq_nlt. apply (Radd_assoc x y z).
152 - intros. apply AReq_nlt. rewrite AR_one. apply (Rmul_1_l x).
153 - intros. apply AReq_nlt. apply (Rmul_comm x y).
154 - intros. apply AReq_nlt. apply (Rmul_assoc x y z).
155 - intros. apply AReq_nlt. apply (Rdistr_l x y z).
156 - intros. apply AReq_nlt. reflexivity.
157 - intros. apply AReq_nlt. rewrite AR_zero. apply (Ropp_def x).
158 Qed.
159
160 Lemma AR_ring_ext : ring_eq_ext ARplus ARmult ARopp
161 (λ x y : AR,
162 (λ x0 y0 : AR, ARltS y0 x0 → False) y x
163 ∧ (λ x0 y0 : AR, ARltS y0 x0 → False) x y).
164 Proof.
165 split.
166 - intros x y J z t J0.
167 apply AReq_nlt. apply AReq_nlt in J.
168 apply AReq_nlt in J0. rewrite J, J0. reflexivity.
169 - intros x y J z t J0.
170 apply AReq_nlt. apply AReq_nlt in J.
171 apply AReq_nlt in J0. rewrite J, J0. reflexivity.
172 - intros x y J.
173 apply AReq_nlt. apply AReq_nlt in J.
174 rewrite J. reflexivity.
175 Qed.
176
177 Lemma AR_lt_0_1 : ARltT (inject_Q_AR 0) (inject_Q_AR 1).
178 Proof.
179 pose proof (inject_Q_AR_CR 0).
180 pose proof (inject_Q_AR_CR 1).
181 symmetry in H5.
182 symmetry in H6.
183 apply (ARltT_wd _ _ H5 _ _ H6).
184 destruct (CRtoAR_preserves_ltT 0%CR 1%CR).
185 exact (a (CRlt_Qlt 0 1 eq_refl)).
186 Qed.
187
188 Lemma AR_plus_lt : ∀ r r1 r2 : AR,
189 ARltS r1 r2 → ARltS (ARplus r r1) (ARplus r r2).
190 Proof.
191 intros.
192 destruct (ARtoCR_preserves_ltT (ARplus r r1) (ARplus r r2)) as [_ a].
193 apply a. clear a.
194 pose proof (ARtoCR_preserves_plus r r1).
195 pose proof (ARtoCR_preserves_plus r r2).
196 symmetry in H6. symmetry in H7.
197 apply (CRltT_wd H6 H7).
198 apply CRplus_lt_l.
199 apply (ARtoCR_preserves_ltT r1 r2).
200 exact H5.
201 Qed.
202
203 Lemma AR_plus_lt_rev : ∀ r r1 r2 : AR,
204 ARltS (ARplus r r1) (ARplus r r2) → ARltS r1 r2.
205 Proof.
206 intros.
207 destruct (ARtoCR_preserves_ltT r1 r2) as [_ a].
208 apply a. clear a.
209 pose proof (ARtoCR_preserves_plus r r1).
210 pose proof (ARtoCR_preserves_plus r r2).
211 destruct (ARtoCR_preserves_ltT (ARplus r r1) (ARplus r r2)) as [a _].
212 apply a in H5. clear a.
213 apply (CRltT_wd H6 H7) in H5.
214 pose proof (CRplus_lt_l ('r1) ('r2) ('r)) as [_ H8].
215 apply H8, H5.
216 Qed.
217
218 Definition ARinvS (x : AR)
219 : ARltS x (inject_Q_AR 0) + ARltS (inject_Q_AR 0) x → AR
220 := fun H => ARinvT x (ARapartT_wd _ _ _ _ (reflexivity _) (AR_zero) H).
221
222 Lemma ARmult_inv_r
223 : (∀ (r : AR)
224 (rnz : (ARltS r (inject_Q_AR 0) + ARltS (inject_Q_AR 0) r)%type),
225 (λ x y : AR,
226 (λ x0 y0 : AR, ARltS y0 x0 → False) y x
227 ∧ (λ x0 y0 : AR, ARltS y0 x0 → False) x
228 y) (ARmult (ARinvS r rnz) r) (inject_Q_AR 1)).
229 Proof.
230 intros. rewrite <- AReq_nlt.
231 rewrite (commutativity _ r).
232 unfold ARinvS.
233 pose proof (AR_inverseT r (ARapartT_wd r r (inject_Q_AR 0) (' zero0)
234 (reflexivity r) AR_zero rnz)).
235 rewrite H5.
236 symmetry. apply AR_one.
237 Qed.
238
239 Lemma ARinv_0_lt_compat
240 : ∀ (r : AR)
241 (rnz : (ARltS r (inject_Q_AR 0) + ARltS (inject_Q_AR 0) r)%type),
242 ARltS (inject_Q_AR 0) r
243 → ARltS (inject_Q_AR 0) (ARinvS r rnz).
244 Proof.
245 intros r rnz H5.
246 destruct (ARtoCR_preserves_ltT (inject_Q_AR 0) (ARinvS r rnz)) as [_ a].
247 apply a. clear a.
248 assert (0 = ARtoCR (inject_Q_AR 0))%CR as H7.
249 { rewrite <- (CRAR_id 0%CR).
250 unfold cast.
251 rewrite (inject_Q_AR_CR 0). reflexivity. }
252 pose proof (ARtoCR_preserves_apartT_0 r ) as [ap _].
253 pose proof (ARtoCR_preserves_invT
254 r (ARapartT_wd r r (inject_Q_AR 0) (' zero0) (reflexivity r)
255 AR_zero rnz)
256 (ap (ARapartT_wd r r (inject_Q_AR 0) (' zero0) (reflexivity r)
257 AR_zero rnz))) as H6.
258 symmetry in H6.
259 apply (CRltT_wd H7 H6). clear H6.
260 apply CRinv_0_lt_compat.
261 destruct (ARtoCR_preserves_ltT (inject_Q_AR 0) r) as [a _].
262 apply a in H5. clear a. symmetry in H7.
263 apply (CRltT_wd H7 (reflexivity _)). exact H5.
264 Qed.
265
266 Definition AR_Q_dense (x y : AR)
267 : ARltS x y
268 → sigT (fun q : Q => prod (ARltS x (inject_Q_AR q)) (ARltS (inject_Q_AR q) y)).
269 Proof.
270 intro J.
271 destruct (ARtoCR_preserves_ltT x y) as [a _].
272 apply a in J. clear a.
273 destruct (CRlt_Qmid (cast AR CR x) (cast AR CR y) J) as [q [J0 J1]].
274 exists q. split.
275 destruct (ARtoCR_preserves_ltT x (inject_Q_AR q)) as [_ a].
276 apply a; clear a.
277 pose proof (CRAR_id ('q)%CR). symmetry in H5.
278 rewrite <- (inject_Q_AR_CR q) in H5.
279 apply (CRltT_wd (reflexivity _) H5), J0.
280 destruct (ARtoCR_preserves_ltT (inject_Q_AR q) y) as [_ a].
281 apply a; clear a.
282 pose proof (CRAR_id ('q)%CR).
283 rewrite <- (inject_Q_AR_CR q) in H5.
284 symmetry in H5.
285 apply (CRltT_wd H5 (reflexivity _)), J1.
286 Qed.
287
288 Definition ARup (x : AR)
289 : sigT (fun n : positive => ARltS x (inject_Q_AR (Z.pos n # 1))).
290 Proof.
291 destruct (CRup (cast AR CR x)) as [n J].
292 exists n.
293 destruct (ARtoCR_preserves_ltT x (inject_Q_AR (Z.pos n # 1))) as [_ a].
294 apply a; clear a.
295 pose proof (CRAR_id ('(Z.pos n#1))%CR).
296 rewrite <- inject_Q_AR_CR in H5.
297 symmetry in H5.
298 apply (CRltT_wd (reflexivity _) H5), J.
299 Qed.
300
301 Lemma ARabs_spec : ∀ x y : AR,
302 (ARltS y x → False) ∧ (ARltS y (ARopp x) → False) ↔ (ARltS y (ARabs x) → False).
303 Proof.
304 intros x y.
305 split.
306 - intros [H6 H7].
307 apply (ARle_not_lt (ARabs x) y).
308 apply (ARle_not_lt x y) in H6.
309 apply (ARle_not_lt (ARopp x) y) in H7.
310 pose proof (ARabs_AbsSmall y x) as [_ H5].
311 apply H5. split. 2: exact H6.
312 rewrite <- (rings.negate_involutive x).
313 apply rings.flip_le_negate. exact H7.
314 - intro H6.
315 apply (ARle_not_lt (ARabs x) y) in H6.
316 pose proof (ARabs_AbsSmall y x) as [H5 _].
317 split.
318 + apply (ARle_not_lt x y).
319 apply H5. exact H6.
320 + apply (ARle_not_lt (ARopp x) y).
321 rewrite <- (rings.negate_involutive y).
322 apply rings.flip_le_negate.
323 apply H5, H6.
324 Qed.
325
326 Definition ARcauchy_sequence (xn : nat -> AR) : Set
327 := ∀ p : positive,
328 {n : nat
329 | ∀ i j : nat,
330 (n <= i)%nat
331 → (n <= j)%nat
332 → ARltT (inject_Q_AR (1 # p)) (ARabs (ARplus (xn i) (ARopp (xn j))))
333 → False}.
334
335 Lemma ARtoCR_preserves_cauchy
336 : forall xn : nat → AR,
337 ARcauchy_sequence xn
338 -> CRcauchy_sequence (fun n => cast AR CR (xn n)).
339 Proof.
340 intros xn xncau p.
341 specialize (xncau p) as [n J].
342 exists n. intros.
343 apply (J i j H5 H6); clear J.
344 destruct (CRtoAR_preserves_ltT (' (1 # p))%CR
345 (CRabs (' ARplus (xn i) (ARopp (xn j))))) as [c _].
346 apply (ARltT_wd _ _ (reflexivity _) (' CRabs (' ARplus (xn i) (ARopp (xn j))))).
347 - rewrite <- ARtoCR_preserves_abs.
348 apply CRAR_id.
349 - pose proof (inject_Q_AR_CR (1#p)).
350 symmetry in H8.
351 apply (ARltT_wd _ _ H8 _ _ (reflexivity _)). clear H8.
352 apply c; clear c.
353 apply (CRlt_le_trans _ _ _ H7); clear H7.
354 setoid_replace ((' xn i)%mc - (' xn j)%mc)%CR
355 with (cast AR CR (ARplus (xn i) (ARopp (xn j)))).
356 apply CRle_refl.
357 pose proof (ARtoCR_preserves_plus (xn i) (ARopp (xn j))).
358 rewrite H7.
359 apply ucFun2_wd. reflexivity.
360 pose proof (ARtoCR_preserves_opp (xn j)).
361 rewrite H8. apply Cmap_wd.
362 reflexivity. reflexivity.
363 Qed.
364
365 Lemma ARcauchy_complete
366 : ∀ xn : nat → AR,
367 ARcauchy_sequence xn
368 → sigT (fun l : AR =>
369 ∀ p : positive,
370 {n : nat
371 | ∀ i : nat,
372 (n <= i)%nat
373 → ARltT (inject_Q_AR (1 # p)) (ARabs (ARplus (xn i) (ARopp l))) → False}).
374 Proof.
375 intros.
376 destruct (CRcauchy_complete _ (ARtoCR_preserves_cauchy xn H5)) as [l J].
377 exists (cast CR AR l).
378 intro p. specialize (J p) as [n J]. exists n.
379 intros i H6 H7. specialize (J i H6). apply J.
380 unfold ARabs in H7.
381 destruct (CRtoAR_preserves_ltT (' (1 # p))%CR
382 (CRabs (' ARplus (xn i) (ARopp (' l))))) as [_ c].
383 apply (ARltT_wd _ _ (reflexivity _)
384 _ (' CRabs (' ARplus (xn i) (ARopp ('l))))) in H7.
385 - pose proof (inject_Q_AR_CR (1#p)).
386 apply (ARltT_wd _ _ H8 _ _ (reflexivity _)) in H7. clear H8.
387 apply c in H7; clear c.
388 apply (CRlt_le_trans _ _ _ H7).
389 setoid_replace ((' xn i)%mc - l)%CR
390 with (cast AR CR (ARplus (xn i) (ARopp (' l)))).
391 apply CRle_refl.
392 pose proof (ARtoCR_preserves_plus (xn i) (ARopp ('l))).
393 rewrite H8.
394 apply ucFun2_wd. reflexivity.
395 pose proof (ARtoCR_preserves_opp ('l)).
396 rewrite H9. apply Cmap_wd. reflexivity.
397 symmetry. apply CRAR_id.
398 - rewrite <- ARtoCR_preserves_abs.
399 symmetry. apply CRAR_id.
400 Qed.
401
402 Definition FasterRealsConstructive : ConstructiveReals
403 := Build_ConstructiveReals
404 (RegularFunction (Eball (cast AQ Q)))
405 ARltS ARltS_linear ARlt
406 (fun x y H => fst (AR_lt_ltT x y) H)
407 (fun x y H => snd (AR_lt_ltT x y) H)
408 ARlt_or_epsilon
409 inject_Q_AR inject_Q_AR_lt inject_Q_AR_lt_rev
410 ARplus ARopp ARmult
411 inject_Q_AR_plus_nlt inject_Q_AR_mult_nlt
412 AR_ring AR_ring_ext
413 AR_lt_0_1 AR_plus_lt AR_plus_lt_rev
414 AR_mult_0_lt_compat
415 ARinvS ARmult_inv_r ARinv_0_lt_compat
416 AR_Q_dense ARup ARabs ARabs_spec
417 ARcauchy_complete.
418
419 End ConstructiveFaster.