Debian Codegraph @

reals/stdlib/ConstructiveFastReals.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 fast reals implement the standard library's
13 interface ConstructiveReals. *)
14
15 From Coq Require Import ZArith ConstructiveReals.
16 Require Import CoRN.model.metric2.Qmetric.
17 Require Import CoRN.model.metric2.CRmetric.
18 Require Import CoRN.reals.fast.CRFieldOps.
19 Require Import CoRN.reals.fast.CRArith.
20 Require Import CoRN.reals.fast.CRabs.
21 Require Import CoRN.model.totalorder.QposMinMax.
22 From Coq Require Import ConstructiveEpsilon.
23
24 Lemma CRltT_linear : @isLinearOrder (RegularFunction Qball) CRltT.
25 Proof.
26 split. split.
27 - intros. apply (CRlt_trans _ _ _ H) in H0.
28 apply (CRlt_irrefl x H0).
29 - intros. exact (CRlt_trans _ _ _ H H0).
30 - apply CRlt_linear.
31 Qed.
32
33 Lemma CRlt_equiv : forall x y : CR,
34 CRlt x y
35 <-> exists n:nat, approximate x (Qpos2QposInf (1#Pos.of_nat n)) + (2#Pos.of_nat n)
36 < approximate y (Qpos2QposInf (1#Pos.of_nat n)).
37 Proof.
38 split.
39 - intros H. apply CR_lt_ltT in H. destruct H as [q H].
40 destruct q as [q qpos]; unfold proj1_sig in H.
41 destruct q as [a b]. destruct a as [|a|a].
42 exfalso; inversion qpos.
43 2: exfalso; inversion qpos. clear qpos.
44 assert (translate (1#b) x <= y)%CR.
45 { rewrite (CRplus_le_r _ _ x) in H.
46 ring_simplify in H.
47 rewrite <- CRplus_translate.
48 apply (@CRle_trans _ (' (Z.pos a # b) + x)%CR).
49 2: exact H.
50 apply CRplus_le_r, CRle_Qle.
51 change (b <= a*b)%positive.
52 apply (Pos.le_trans _ (1*b)).
53 apply Pos.le_refl.
54 apply Pos.mul_le_mono_r. apply Pos.le_1_l. }
55 clear H a.
56 exists (Pos.to_nat (5*b)).
57 rewrite Pos2Nat.id.
58 apply (CRle_trans (lower_CRapproximation (translate (1#b) x) (1#5*b)%Qpos))
59 in H0.
60 pose proof (upper_CRapproximation y (1#5*b)%Qpos) as H.
61 apply (CRle_trans H0) in H. clear H0.
62 apply CRle_Qle in H. simpl in H.
63 rewrite Qplus_comm in H.
64 unfold Qminus in H. rewrite <- Qplus_assoc in H.
65 setoid_replace ((1 # b) + - (1 # b + b~0~0))
66 with ((3#5*b) + (1#5*b)) in H.
67 rewrite Qplus_assoc in H. apply Qplus_le_l in H.
68 refine (Qlt_le_trans _ _ _ _ H).
69 apply Qplus_lt_r.
70 apply Pos.mul_lt_mono_r. reflexivity.
71 unfold canonical_names.equiv, stdlib_rationals.Q_eq.
72 rewrite Qinv_plus_distr.
73 setoid_replace (1#b) with (5#5*b) by reflexivity.
74 rewrite Qinv_minus_distr. reflexivity.
75 - intros [n H].
76 apply CR_lt_ltT.
77 apply (@CRle_lt_trans _ _ _ (upper_CRapproximation x (1#Pos.of_nat n)%Qpos)).
78 refine (CRlt_le_trans _ _ _ _ (lower_CRapproximation y (1#Pos.of_nat n)%Qpos)).
79 apply CRlt_Qlt. simpl.
80 apply (Qplus_lt_l _ _ (1# Pos.of_nat n)).
81 ring_simplify.
82 refine (Qle_lt_trans _ _ _ _ H).
83 apply Qplus_le_r. apply Qle_refl.
84 Qed.
85
86 Lemma CRlt_or_epsilon : (forall a b c d : CR,
87 CRlt a b \/ CRlt c d -> (a < b)%CR + (c < d)%CR).
88 Proof.
89 intros.
90 assert (exists n:nat,
91 approximate a (Qpos2QposInf (1#Pos.of_nat n)) + (2#Pos.of_nat n)
92 < approximate b (Qpos2QposInf (1#Pos.of_nat n))
93 \/ approximate c (Qpos2QposInf (1#Pos.of_nat n)) + (2#Pos.of_nat n)
94 < approximate d (Qpos2QposInf (1#Pos.of_nat n))).
95 { destruct H.
96 - apply CRlt_equiv in H. destruct H as [n H].
97 exists n. left. exact H.
98 - apply CRlt_equiv in H. destruct H as [n H].
99 exists n. right. exact H. }
100 apply constructive_indefinite_ground_description_nat in H0.
101 - destruct H0 as [n H0].
102 destruct (Qlt_le_dec (approximate a (Qpos2QposInf (1 # Pos.of_nat n)) + (2 # Pos.of_nat n))
103 (approximate b (Qpos2QposInf (1 # Pos.of_nat n)))).
104 + left. apply CR_lt_ltT, CRlt_equiv.
105 exists n. exact q.
106 + right. apply CR_lt_ltT, CRlt_equiv.
107 exists n. destruct H0. 2: exact H0. exfalso.
108 exact (Qlt_not_le _ _ H0 q).
109 - intro n. clear H0 H.
110 destruct (Qlt_le_dec (approximate a (Qpos2QposInf (1 # Pos.of_nat n)) + (2 # Pos.of_nat n))
111 (approximate b (Qpos2QposInf (1 # Pos.of_nat n)))).
112 left. left. exact q.
113 destruct (Qlt_le_dec (approximate c (Qpos2QposInf (1 # Pos.of_nat n)) + (2 # Pos.of_nat n))
114 (approximate d (Qpos2QposInf (1 # Pos.of_nat n)))).
115 left. right. exact q0.
116 right. intros [H|H].
117 exact (Qlt_not_le _ _ H q).
118 exact (Qlt_not_le _ _ H q0).
119 Qed.
120
121 Lemma CReq_nlt : forall a b : CR,
122 msp_eq a b
123 <-> (fun x y : CR =>
124 (fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\
125 (fun x0 y0 : CR => (y0 < x0)%CR -> False) x y) a b.
126 Proof.
127 split.
128 - split. intro abs.
129 exact (CRlt_irrefl _ (@CRltT_wd _ _ H b _ (reflexivity _) abs)).
130 intro abs.
131 exact (CRlt_irrefl _ (@CRltT_wd b _ (reflexivity _) _ _ H abs)).
132 - intros [H H0]. apply CRle_antisym. split.
133 apply CRle_not_lt in H0. exact H0.
134 apply CRle_not_lt in H. exact H.
135 Qed.
136
137 Lemma inject_Q_CR_plus : forall q r : Q,
138 (fun x y : CR =>
139 (fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\
140 (fun x0 y0 : CR => (y0 < x0)%CR -> False) x y)
141 (' (q + r)%Q)%CR (CRplus (' q)%CR (' r)%CR).
142 Proof.
143 intros q r. apply CReq_nlt, (CRplus_Qplus q r).
144 Qed.
145
146 Lemma inject_Q_CR_mult : forall q r : Q,
147 (fun x y : CR =>
148 (fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\
149 (fun x0 y0 : CR => (y0 < x0)%CR -> False) x y)
150 (' (q * r)%Q)%CR (CRmult (' q)%CR (' r)%CR).
151 Proof.
152 intros q r.
153 apply CReq_nlt. symmetry. apply (CRmult_Qmult q r).
154 Qed.
155
156 Lemma CR_ring_nlt : ring_theory 0%CR 1%CR CRplus CRmult
157 (fun x y : CR => CRplus x (- y)%CR) CRopp
158 (fun x y : CR =>
159 (fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\
160 (fun x0 y0 : CR => (y0 < x0)%CR -> False) x y).
161 Proof.
162 destruct CR_ring_theory. split.
163 - intro x. apply CReq_nlt, Radd_0_l.
164 - intros x y. apply CReq_nlt, Radd_comm.
165 - intros x y z. apply CReq_nlt, Radd_assoc.
166 - intro x. apply CReq_nlt, Rmul_1_l.
167 - intros x y. apply CReq_nlt, Rmul_comm.
168 - intros x y z. apply CReq_nlt, Rmul_assoc.
169 - intros x y z. apply CReq_nlt, Rdistr_l.
170 - intros x y. apply CReq_nlt, Rsub_def.
171 - intro x. apply CReq_nlt, Ropp_def.
172 Qed.
173
174 Lemma CR_ring_ext_nlt : ring_eq_ext CRplus CRmult CRopp
175 (fun x y : CR =>
176 (fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\
177 (fun x0 y0 : CR => (y0 < x0)%CR -> False) x y).
178 Proof.
179 split.
180 - intros x y H z t H0.
181 apply CReq_nlt.
182 apply CReq_nlt in H.
183 apply CReq_nlt in H0.
184 rewrite H, H0. reflexivity.
185 - intros x y H z t H0.
186 apply CReq_nlt.
187 apply CReq_nlt in H.
188 apply CReq_nlt in H0.
189 rewrite H, H0. reflexivity.
190 - intros x y H.
191 apply CReq_nlt.
192 apply CReq_nlt in H.
193 rewrite H. reflexivity.
194 Qed.
195
196 Lemma CRmult_inv_r_nlt : (forall (r : CR)
197 (rnz : (fun x y : CR => ((x < y)%CR + (y < x)%CR)%type) r 0%CR),
198 (fun x y : CR =>
199 (fun x0 y0 : CR => (y0 < x0)%CR -> False) y x /\
200 (fun x0 y0 : CR => (y0 < x0)%CR -> False) x y)
201 (CRinvT r rnz * r)%CR 1%CR).
202 Proof.
203 intros. apply CReq_nlt.
204 rewrite CRmult_comm. apply CRmult_inv_r.
205 Qed.
206
207 Definition CRup (x : CR)
208 : {n : positive & (x < ' (Z.pos n # 1))%CR}.
209 Proof.
210 exists (match Qnum (proj1_sig (CR_b (1#1)%Qpos x)) with
211 | Z0 => 1%positive
212 | Zpos p => Pos.succ p
213 | Zneg p => 1%positive end).
214 apply (CRle_lt_trans _ _ _ (CR_b_upperBound (1#1)%Qpos x)).
215 apply CRlt_Qlt.
216 destruct (CR_b (1 # 1) x), x0. simpl.
217 destruct Qnum.
218 - reflexivity.
219 - change (p*1 < Pos.succ p * Qden)%positive.
220 apply (Pos.le_lt_trans _ (p * Qden)).
221 apply Pos.mul_le_mono_l. apply Pos.le_1_l.
222 apply Pos.mul_lt_mono_r.
223 apply Pos.lt_succ_diag_r.
224 - reflexivity.
225 Qed.
226
227 Lemma CRabs_nlt : forall x y : CR,
228 (((y < x)%CR -> False) /\ ((y < -x)%CR -> False))
229 <-> ((y < CRabs x)%CR -> False).
230 Proof.
231 split.
232 - intros [H H0] H1.
233 apply CRle_not_lt in H1. contradiction. clear H2 H1.
234 pose proof (CRdistance_CRle y x 0%CR) as [H2 _].
235 unfold CRdistance in H2. rewrite CRopp_0, CRplus_0_r in H2.
236 apply H2. clear H2. split.
237 apply (CRplus_le_r _ _ y).
238 apply CRle_not_lt in H.
239 ring_simplify. exact H.
240 apply CRle_not_lt in H0.
241 rewrite (CRplus_le_r _ _ x) in H0.
242 ring_simplify in H0. exact H0.
243 - split.
244 apply CRle_not_lt in H.
245 apply CRle_not_lt.
246 apply (@CRle_trans _ (CRabs x)). 2: exact H.
247 apply CRle_abs.
248 apply CRle_not_lt in H.
249 apply CRle_not_lt.
250 apply (@CRle_trans _ (CRabs x)). 2: exact H.
251 rewrite <- CRabs_opp.
252 apply CRle_abs.
253 Qed.
254
255 Definition CRcauchy_sequence (xn : nat -> CR) : Set
256 := forall p : positive,
257 {n : nat
258 | forall i j : nat,
259 (n <= i)%nat ->
260 (n <= j)%nat -> (' (1 # p) < CRabs (xn i - xn j))%CR -> False}.
261
262 Lemma Qarchimedean_le : forall q : Q, { p : positive | q <= Z.pos p # 1 }.
263 Proof.
264 intros. destruct q as [a b]. destruct a.
265 - exists xH. discriminate.
266 - exists p. unfold Qle; simpl.
267 apply Pos.mul_le_mono_l, Pos.le_1_l.
268 - exists xH. discriminate.
269 Defined.
270
271 Definition CRstandard_modulus (xn : nat -> CR)
272 (xncau : CRcauchy_sequence xn)
273 (e : QposInf) : CR
274 := match e with
275 | Qpos2QposInf q
276 => xn (proj1_sig (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig q)))))
277 | QposInfinity => 0%CR
278 end.
279
280 Lemma CRstandard_regular : forall (xn : nat -> CR)
281 (xncau : CRcauchy_sequence xn),
282 is_RegularFunction (@ball CR) (CRstandard_modulus xn xncau).
283 Proof.
284 intros xn xncau e1 e2.
285 apply CRabs_ball. unfold CRstandard_modulus.
286 destruct (le_ge_dec
287 (proj1_sig (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig e1)))))
288 (proj1_sig (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig e2)))))).
289 - destruct (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig e1)))) as [n H].
290 simpl in l.
291 destruct e1 as [e1 e1pos].
292 destruct e2 as [e2 e2pos].
293 unfold proj1_sig. specialize (H n _ (Nat.le_refl _) l).
294 apply CRle_not_lt in H.
295 apply (CRle_trans H). clear H.
296 apply CRle_Qle. unfold proj1_sig.
297 destruct (Qarchimedean_le (/ e1)) as [p H].
298 apply (Qle_trans _ (e1+0)).
299 2: apply Qplus_le_r, Qlt_le_weak, e2pos.
300 rewrite Qplus_0_r.
301 apply (Qmult_le_l _ _ e1) in H. 2: exact e1pos.
302 rewrite Qmult_inv_r in H.
303 change (1#p) with (/(Z.pos p#1)).
304 apply Qle_shift_inv_r. reflexivity.
305 apply H.
306 apply (Qpos_nonzero (exist _ e1 e1pos)).
307 - destruct (xncau (proj1_sig (Qarchimedean_le (/ proj1_sig e2)))) as [n H].
308 simpl in g.
309 destruct e1 as [e1 e1pos].
310 destruct e2 as [e2 e2pos].
311 unfold proj1_sig. specialize (H _ n g (Nat.le_refl _)).
312 apply CRle_not_lt in H.
313 apply (CRle_trans H). clear H.
314 apply CRle_Qle. unfold proj1_sig.
315 destruct (Qarchimedean_le (/ e2)) as [p H].
316 apply (Qle_trans _ (0+e2)).
317 2: apply Qplus_le_l, Qlt_le_weak, e1pos.
318 rewrite Qplus_0_l.
319 apply (Qmult_le_l _ _ e2) in H. 2: exact e2pos.
320 rewrite Qmult_inv_r in H.
321 change (1#p) with (/(Z.pos p#1)).
322 apply Qle_shift_inv_r. reflexivity.
323 apply H.
324 apply (Qpos_nonzero (exist _ e2 e2pos)).
325 Qed.
326
327 Lemma CRcauchy_complete : forall xn : nat -> CR,
328 CRcauchy_sequence xn ->
329 {l : CR &
330 forall p : positive,
331 {n : nat
332 | forall i : nat,
333 (n <= i)%nat -> (' (1 # p) < CRabs (xn i - l))%CR -> False}}.
334 Proof.
335 intros xn xncau.
336 exists (Cjoin_fun (Build_RegularFunction (CRstandard_regular xn xncau))).
337 intro p.
338 exists (proj1_sig (xncau (2*p)%positive)).
339 intros i H. apply CRle_not_lt.
340 apply (CRle_trans (CRdistance_triangle _ (CRstandard_modulus xn xncau (Qpos2QposInf (1#2*p))) _)).
341 apply (@CRle_trans _ ('(1#2*p) + '(1#2*p))%CR).
342 apply CRplus_le_compat.
343 - simpl.
344 destruct (xncau (2*p)%positive) as [n H0] eqn:des.
345 apply CRle_not_lt. apply H0.
346 exact H. clear H i.
347 simpl in des. rewrite des. apply Nat.le_refl.
348 - apply CRabs_ball, ball_sym.
349 apply (Cjoin_ball (Build_RegularFunction (CRstandard_regular xn xncau))
350 (1#2*p)).
351 - rewrite CRplus_Qplus.
352 apply CRle_Qle.
353 rewrite Qinv_plus_distr.
354 apply Z.le_refl.
355 Qed.
356
357 Definition FastRealsConstructive : ConstructiveReals
358 := Build_ConstructiveReals
359 (RegularFunction Qball)
360 CRltT CRltT_linear CRlt
361 (fun x y => fst (CR_lt_ltT x y))
362 (fun x y => snd (CR_lt_ltT x y))
363 CRlt_or_epsilon
364 inject_Q_CR CRlt_Qlt Qlt_from_CRlt
365 CRplus CRopp CRmult
366 inject_Q_CR_plus inject_Q_CR_mult
367 CR_ring_nlt CR_ring_ext_nlt
368 (CRlt_Qlt 0 1 eq_refl)
369 (fun r r1 r2 => fst (CRplus_lt_l r1 r2 r))
370 (fun r r1 r2 => snd (CRplus_lt_l r1 r2 r))
371 CRmult_lt_0_compat CRinvT
372 CRmult_inv_r_nlt CRinv_0_lt_compat
373 CRlt_Qmid CRup CRabs CRabs_nlt
374 CRcauchy_complete.