Debian Codegraph @

reals/fast/Interval.v

raw
1 (*
2 Copyright © 2008 Russell O’Connor
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this proof and associated documentation files (the "Proof"), to deal in
6 the Proof without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 the Proof, and to permit persons to whom the Proof is furnished to do so,
9 subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Proof.
13
14 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
20 *)
21 From Coq Require Import ZArith.
22 Require Import CoRN.algebra.RSetoid.
23 Require Import CoRN.metric2.Metric.
24 Require Import CoRN.metric2.UniformContinuity.
25 Require Import CoRN.model.totalorder.QposMinMax.
26 Require Export CoRN.metric2.Compact.
27 Require Export CoRN.metric2.LocatedSubset.
28 Require Export CoRN.reals.fast.CRArith.
29 Require Import CoRN.reals.fast.CRabs.
30 Require Export CoRN.model.metric2.Qmetric.
31 From Coq Require Import Qround.
32 From Coq Require Import Qabs.
33 Require Import CoRN.model.totalorder.QMinMax.
34 Require Import CoRN.logic.Classic.
35
36 Local Open Scope Q_scope.
37
38 Opaque Qabs.
39
40 Set Implicit Arguments.
41
42 Section Interval.
43 (**
44 * Intervals as a Compact Set.
45 We want to make an efficent implementation of intervals as compact sets.
46 We want to minimize the number of sample points in the approximations of
47
48 a compact interval.
49 *)
50 Variable (l r:Q).
51 Hypothesis Hlr : l <= r.
52
53 Let f (n:positive) (i:Z) := l + ((r-l)*(2*i+1#1))/(2*Zpos n#1).
54
55 Fixpoint iterateN_succ (z:Z) (n:positive) : list Z :=
56 match n with
57 | xI p => z :: app (iterateN_succ (Z.succ z) p)
58 (iterateN_succ (Z.succ z + Zpos p) p)
59 | xO p => app (iterateN_succ z p) (iterateN_succ (z + Zpos p) p)
60 | xH => z :: nil
61 end.
62
63 Lemma iterateN_succ_example : iterateN_succ 4 3 = (4 :: 5 :: 6 :: nil)%Z.
64 Proof. reflexivity. Qed.
65
66 Lemma iterateN_succ_length
67 : forall n z,
68 length (iterateN_succ z n) = Pos.to_nat n.
69 Proof.
70 induction n.
71 - intro z. simpl.
72 rewrite Pos2Nat.inj_xI. apply f_equal.
73 rewrite app_length, IHn, IHn.
74 simpl.
75 rewrite Nat.add_0_r. reflexivity.
76 - intro z. simpl.
77 rewrite app_length, IHn, IHn.
78 rewrite Pos2Nat.inj_xO. simpl.
79 rewrite Nat.add_0_r. reflexivity.
80 - reflexivity.
81 Qed.
82
83 Lemma iterateN_succ_nth
84 : forall n (j:nat) s z,
85 (j < Pos.to_nat n)%nat -> nth j (iterateN_succ s n) z = (s + Z.of_nat j)%Z.
86 Proof.
87 induction n.
88 - intros. simpl.
89 destruct j. simpl. rewrite Z.add_0_r. reflexivity.
90 destruct (le_lt_dec (Pos.to_nat n) j) as [l0|l0].
91 + rewrite <- (iterateN_succ_length n (Z.succ s)) in l0.
92 rewrite (app_nth2 _ _ z l0).
93 pose proof (Nat.le_exists_sub _ _ l0) as [k [H0 _]].
94 subst j.
95 rewrite Nat.add_sub.
96 rewrite IHn.
97 rewrite iterateN_succ_length.
98 rewrite Nat2Z.inj_succ, Nat2Z.inj_add, <- positive_nat_Z.
99 ring.
100 rewrite (iterateN_succ_length n (Z.succ s)), Pos2Nat.inj_xI in H.
101 simpl in H. rewrite Nat.add_0_r in H.
102 apply le_S_n in H.
103 apply (Nat.add_le_mono_r _ _ (Pos.to_nat n)).
104 exact H.
105 + rewrite <- (iterateN_succ_length n (Z.succ s)) in l0.
106 rewrite (app_nth1 _ _ z l0).
107 rewrite IHn.
108 rewrite Nat2Z.inj_succ. ring.
109 rewrite <- (iterateN_succ_length n (Z.succ s)).
110 exact l0.
111 - intros. simpl.
112 destruct (le_lt_dec (Pos.to_nat n) j) as [l0|l0].
113 + rewrite <- (iterateN_succ_length n s) in l0.
114 rewrite (app_nth2 (iterateN_succ s n)
115 (iterateN_succ (s + Z.pos n) n) z l0).
116 pose proof (Nat.le_exists_sub _ _ l0) as [k [H0 _]].
117 subst j.
118 rewrite Nat.add_sub.
119 rewrite IHn.
120 rewrite (iterateN_succ_length n s).
121 rewrite Nat2Z.inj_add, <- positive_nat_Z.
122 ring.
123 rewrite (iterateN_succ_length n s), Pos2Nat.inj_xO in H.
124 simpl in H. rewrite Nat.add_0_r in H.
125 apply (Nat.add_le_mono_r _ _ (Pos.to_nat n)).
126 exact H.
127 + rewrite <- (iterateN_succ_length n s) in l0.
128 rewrite (app_nth1 (iterateN_succ s n)
129 (iterateN_succ (s + Z.pos n) n) z l0).
130 apply IHn.
131 rewrite <- (iterateN_succ_length n s).
132 exact l0.
133 - intros. simpl.
134 destruct j. simpl. rewrite Z.add_0_r. reflexivity.
135 exfalso. inversion H. inversion H1.
136 Qed.
137
138
139 (** [UniformPartition] produces a set of n points uniformly distributed
140 inside the interval [[l, r]]. We use binary positive instead of
141 unary nat for faster computations. *)
142 Definition UniformPartition (n:positive) : list Q :=
143 map (f n) (iterateN_succ 0%Z n).
144
145 Lemma UniformPartitionZ : forall n a z,
146 In z (iterateN_succ a n) <-> (a <= z < a + Zpos n)%Z.
147 Proof.
148 split.
149 - intro H. apply (In_nth _ _ 0%Z) in H.
150 destruct H as [p [H H0]].
151 subst z. rewrite iterateN_succ_length in H.
152 rewrite iterateN_succ_nth.
153 2: exact H. split.
154 rewrite <- (Z.add_0_r a) at 1.
155 apply Z.add_le_mono_l. apply Nat2Z.is_nonneg.
156 apply Z.add_lt_mono_l.
157 destruct p. reflexivity.
158 rewrite <- (Nat2Pos.id (S p)) in H.
159 2: discriminate.
160 apply Pos2Nat.inj_lt in H.
161 simpl.
162 rewrite Pos.of_nat_succ. exact H.
163 - revert n z a.
164 induction n; intros.
165 + simpl. destruct (Z.le_gt_cases z a).
166 left. apply Z.le_antisymm. apply H. exact H0.
167 right. destruct (Z.le_gt_cases (Z.succ a + Z.pos n) z).
168 apply in_app_iff. right. apply IHn.
169 split. apply H1.
170 rewrite <- Z.add_assoc, Z.add_diag.
171 apply (Z.lt_le_trans _ _ _ (proj2 H)).
172 rewrite <- Z.add_1_l, (Z.add_comm 1).
173 rewrite <- Z.add_assoc.
174 apply Z.le_refl.
175 apply in_app_iff. left. apply IHn.
176 split. apply Zlt_le_succ, H0. exact H1.
177 + simpl. destruct (Z.le_gt_cases (a + Z.pos n) z).
178 apply in_app_iff. right. apply IHn.
179 split. apply H0.
180 rewrite <- Z.add_assoc, Z.add_diag. apply H.
181 apply in_app_iff. left. apply IHn.
182 split. apply H. exact H0.
183 + left. destruct H. apply Z.le_antisymm. exact H.
184 rewrite Z.add_comm, Z.add_1_l in H0.
185 apply Zlt_succ_le, H0.
186 Qed.
187
188 Lemma UniformPartition_inside : forall n x, In x (UniformPartition n) -> l <= x <= r.
189 Proof.
190 intros n x.
191 unfold UniformPartition.
192 assert (forall z, In z (iterateN_succ 0%Z n) -> (0 <= z < Zpos n)%Z) as H.
193 { intros. apply UniformPartitionZ in H. exact H. }
194 revert H.
195 generalize (iterateN_succ 0%Z n).
196 intros s Hs H.
197 induction s.
198 contradiction.
199 destruct H as [H | H];auto with *.
200 rewrite <- H.
201 destruct (Hs a) as [Hz0 Hz1]; auto with *.
202 clear - Hz0 Hz1 Hlr.
203 split.
204 unfold f, Qdiv.
205 rewrite <- (Qplus_0_r l) at 1.
206 apply Qplus_le_r.
207 apply Qle_shift_div_l. reflexivity.
208 rewrite Qmult_0_l.
209 apply Qmult_le_0_compat.
210 unfold Qminus. rewrite <- Qle_minus_iff. exact Hlr.
211 unfold Qle, Qnum, Qden.
212 rewrite Z.mul_1_r, Z.mul_1_r.
213 apply (Z.le_trans _ (1*a+0)%Z).
214 rewrite Z.add_0_r, Z.mul_1_l. exact Hz0.
215 apply Z.add_le_mono. apply Z.mul_le_mono_nonneg_r.
216 exact Hz0.
217 discriminate. discriminate.
218 unfold f.
219 apply (Qplus_le_r _ _ (-l)).
220 rewrite Qplus_assoc.
221 rewrite (Qplus_comm (-l)), Qplus_opp_r, Qplus_0_l.
222 apply Qle_shift_div_r. reflexivity.
223 rewrite (Qplus_comm (-l)), Qmult_comm, (Qmult_comm (r+-l)).
224 apply Qmult_le_compat_r.
225 unfold Qle, Qnum, Qden. rewrite Z.mul_1_r, Z.mul_1_r.
226 rewrite Z.add_comm, Z.add_1_l.
227 apply Zlt_le_succ.
228 apply Z.mul_lt_mono_pos_l.
229 reflexivity. exact Hz1.
230 rewrite <- Qle_minus_iff. exact Hlr.
231 Qed.
232
233 (** Given a point [x] in the interval [[l, r]], one can find a
234 nearby point in our [UniformPartition]. n is the number of points in
235 the partition, ie the step is (r-l)/n. This function computes the
236 maximum index k such that l+k(r-l)/n <= x. *)
237 Definition rasterize1 (n:positive) (x:Q) : Z
238 := Qfloor (inject_Z (Zpos n)*(x-l)/(r-l)).
239
240 Lemma rasterize1_close : l < r -> forall (n:positive) (x:Q),
241 Qabs (x - f n (rasterize1 n x))
242 <= ((r-l)/((2#1) * inject_Z (Zpos n))).
243 Proof.
244 clear Hlr.
245 intros Hlr' n x.
246 rewrite -> Qlt_minus_iff in Hlr'.
247 assert (A:~ r - l == 0 /\ ~ inject_Z (Zpos n) == 0)
248 by (split;auto with *;discriminate).
249 setoid_replace ((r - l) / ((2#1) * inject_Z (Zpos n)))
250 with ((1#2)/(inject_Z (Zpos n)/(r - l)))
251 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field; auto).
252 apply Qle_shift_div_l.
253 apply Qlt_shift_div_l; auto with *.
254 rewrite <- (Qabs_pos (inject_Z (Zpos n)/(r-l))); [|apply Qle_shift_div_l; auto with *].
255 rewrite <- Qabs_Qmult.
256 unfold f.
257 change (2*Zpos n # 1) with ((2#1)*inject_Z (Zpos n)).
258 setoid_replace ((x - (l + (r - l) * (2 * rasterize1 n x + 1 # 1) / ((2#1) * inject_Z (Zpos n)))) * (inject_Z (Zpos n) / (r - l)))
259 with (inject_Z (Zpos n)*(x-l)/(r-l) - (2*rasterize1 n x + 1 # 1)/(2#1))
260 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field; auto).
261 rewrite -> Qmake_Qdiv.
262 rewrite Q.Zplus_Qplus.
263 unfold Qdiv.
264 change (inject_Z 1) with 1%Q.
265 rewrite Qmult_1_r.
266 rewrite Q.Zmult_Qmult.
267 change (inject_Z 2) with (2#1).
268 setoid_replace (((2#1) * inject_Z (rasterize1 n x) + 1) / (2#1))
269 with (inject_Z (rasterize1 n x) + (1#2))
270 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field; auto).
271 unfold rasterize1.
272 unfold Qdiv.
273 generalize (inject_Z (Zpos n) * (x - l) * / (r - l)).
274 intros q.
275 clear - q.
276 apply Qabs_case; intros H; rewrite -> Qle_minus_iff.
277 setoid_replace ((1 # 2) + - (q - (inject_Z (Qfloor q) + (1 # 2))))
278 with (inject_Z (Qfloor q) + 1 + - q)
279 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
280 rewrite <- Qle_minus_iff.
281 apply Qlt_le_weak.
282 change 1 with (inject_Z 1).
283 rewrite <- (Q.Zplus_Qplus (Qfloor q) 1).
284 apply Qlt_floor.
285 setoid_replace ((1 # 2) + - - (q - (inject_Z (Qfloor q) + (1 # 2))))
286 with (q + -inject_Z (Qfloor q))
287 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
288 rewrite <- Qle_minus_iff.
289 apply Qfloor_le.
290 Qed.
291
292 Definition rasterize1_boundL : forall n (x:Q), l <= x -> (0 <= rasterize1 n x)%Z.
293 Proof.
294 intros n x Hx.
295 change 0%Z with (Qfloor 0).
296 apply Qfloor_resp_le.
297 destruct (Qle_lt_or_eq _ _ Hlr) as [Hlr' | Hlr'].
298 rewrite -> Qlt_minus_iff in Hlr'.
299 rewrite -> Qle_minus_iff in Hx.
300 apply Qle_shift_div_l; auto with *.
301 rewrite Qmult_0_l.
302 apply Qmult_le_0_compat; simpl; auto with *.
303 rewrite -> Hlr'.
304 unfold Qminus.
305 rewrite Qplus_opp_r.
306 unfold Qdiv.
307 change (/0) with 0.
308 ring_simplify.
309 auto with *.
310 Qed.
311
312 Definition rasterize1_boundR : forall n (x:Q), x < r -> (rasterize1 n x < Zpos n)%Z.
313 Proof.
314 intros n x Hx.
315 rewrite Zlt_Qlt.
316 unfold rasterize1.
317 apply (Qle_lt_trans _ _ _ (Qfloor_le _)).
318 destruct (Qle_lt_or_eq _ _ Hlr) as [Hlr' | Hlr'].
319 rewrite -> Qlt_minus_iff in Hlr'.
320 apply Qlt_shift_div_r.
321 auto with *.
322 apply Qmult_lt_l;simpl; auto with *.
323 rewrite -> Qlt_minus_iff.
324 setoid_replace (r - l + - (x - l))
325 with (r + - x)
326 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
327 rewrite <- Qlt_minus_iff; auto.
328 rewrite -> Hlr'.
329 unfold Qminus.
330 rewrite Qplus_opp_r.
331 unfold Qdiv.
332 change (/0) with 0.
333 rewrite Qmult_0_r.
334 auto with *.
335 Qed.
336
337 (* Index of x = r in the partition. *)
338 Lemma UniformPartition_fine_aux
339 : forall (n : positive) (x : Q) (Hx : l <= x <= r) (q : r <= x),
340 In (f n (Zpos n - 1)) (UniformPartition n) /\
341 Qabs (x - f n (Zpos n - 1)) <= (r - l) / ((2#1) * inject_Z (Zpos n)).
342 Proof.
343 intros.
344 split.
345 - apply in_map; rewrite -> UniformPartitionZ.
346 split. apply Z.le_0_sub, Pos.le_1_l.
347 rewrite Z.add_comm.
348 apply Z.add_lt_mono_l. reflexivity.
349 - destruct Hx as [_ Hx].
350 setoid_replace x with r by (apply Qle_antisym; assumption).
351 unfold f.
352 replace (2 * (Z.pos n - 1) + 1)%Z with (2 * Z.pos n - 1)%Z by ring.
353 change (2*Zpos n #1) with ((2#1)*inject_Z (Zpos n)).
354 change (2*Zpos n - 1#1) with (inject_Z (2*Zpos n + - 1)).
355 rewrite Q.Zplus_Qplus.
356 rewrite Q.Zmult_Qmult.
357 change (inject_Z 2) with (2#1).
358 change (inject_Z (-1)) with (-1#1).
359 setoid_replace (r - (l + (r - l) * ((2#1) * inject_Z (Zpos n) + (-1#1))
360 / ((2#1) * (inject_Z (Zpos n)))))
361 with (((r-l) / ((2#1) * (inject_Z (Zpos n)))))
362 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field; auto).
363 rewrite -> Qabs_pos.
364 apply Qle_refl.
365 apply Qle_shift_div_l. reflexivity.
366 rewrite Qmult_0_l; rewrite -> Qle_minus_iff in Hlr; auto.
367 Qed.
368
369 (* For any point x in [[l,r]], there is a point y in the uniform partition
370 that is close to x within half the partition's step. *)
371 Lemma UniformPartition_fine : forall (n:positive) (x:Q),
372 l <= x <= r
373 -> {y | In y (UniformPartition n)
374 /\ Qabs (x - y) <= ((r-l)/((2#1)*inject_Z (Zpos n)))}.
375 Proof.
376 intros n x Hx.
377 destruct (Qlt_le_dec_fast x r).
378 - (* x < r *)
379 exists (f n (rasterize1 n x)).
380 abstract ( destruct Hx as [Hlx Hxr]; split;
381 [apply in_map; rewrite -> UniformPartitionZ; split;
382 [apply rasterize1_boundL; auto |apply rasterize1_boundR; auto]
383 |apply rasterize1_close; apply Qle_lt_trans with x; auto]).
384 - (* x = r *)
385 exists (f n (Zpos n - 1)).
386 apply UniformPartition_fine_aux; assumption.
387 Defined.
388
389 (** Construct the compact set. *)
390 Lemma CompactIntervalQ_nat : forall (e:Qpos),
391 (0 <= Qceiling ((r-l)/(inject_Z 2*proj1_sig e)))%Z.
392 Proof.
393 intros e.
394 change (0%Z) with (Qceiling 0).
395 apply Qceiling_resp_le.
396 apply Qle_shift_div_l.
397 auto with *.
398 rewrite Qmult_0_l.
399 unfold Qminus.
400 rewrite <- Qle_minus_iff.
401 exact Hlr.
402 Qed.
403
404 (* The finite approximation of real interval [l,r] by rational numbers,
405 at precision e. *)
406 Definition CompactIntervalQ_raw (e:QposInf) : list Q :=
407 match e with
408 | QposInfinity => nil
409 | Qpos2QposInf e' =>
410 UniformPartition (Z.to_pos (Qceiling ((r - l) / (inject_Z 2 * proj1_sig e'))))
411 end.
412
413 Lemma CompactIntervalQ_prf
414 : is_RegularFunction (@ball (FinEnum Q_as_MetricSpace)) CompactIntervalQ_raw.
415 Proof.
416 cut (forall (e1 e2:Qpos), hemiMetric Q_as_MetricSpace (proj1_sig e1 + proj1_sig e2) (fun a : Q_as_MetricSpace =>
417 InFinEnumC a (CompactIntervalQ_raw e1)) (fun a : Q_as_MetricSpace =>
418 InFinEnumC a (CompactIntervalQ_raw e2))).
419 { intros Z e1 e2.
420 split. apply (Qpos_nonneg (e1+e2)). split.
421 apply Z.
422 eapply hemiMetric_wd1;[|apply Z].
423 unfold QposEq; simpl; ring. }
424 intros e1 e2 a Ha.
425 assert (l <= a <= r).
426 { unfold CompactIntervalQ_raw in Ha.
427 set (e1':=Z.to_pos (Qceiling ((r - l) / (inject_Z 2 * proj1_sig e1)))) in *.
428 assert (L:=UniformPartition_inside e1').
429 induction (UniformPartition e1').
430 exfalso; exact (FinSubset_ball_nil Ha).
431 destruct (Qeq_dec a a0) as [A|A].
432 rewrite -> A.
433 auto with *.
434 apply IHl0; auto with *.
435 apply FinSubset_ball_orC in Ha.
436 destruct Ha as [G | Ha | Ha] using orC_ind.
437 intro abs. contradict G; intro G. contradiction.
438 elim A.
439 apply Qball_0 in Ha. exact Ha.
440 assumption. }
441 unfold CompactIntervalQ_raw.
442 set (e2':=Z.to_pos (Qceiling ((r - l) / (inject_Z 2 * proj1_sig e2)))).
443 pose proof (UniformPartition_fine e2' H) as [y [Hy0 Hy1]].
444 apply existsWeaken.
445 exists y.
446 split.
447 - apply InFinEnumC_weaken, Hy0.
448 - simpl.
449 rewrite -> Qball_Qabs.
450 eapply Qle_trans;[apply Hy1|].
451 apply Qle_trans with (proj1_sig e2).
452 apply Qle_shift_div_r.
453 destruct e2'; auto with *.
454 rewrite Qmult_comm, (Qmult_comm (2#1)), <- Qmult_assoc.
455 rewrite <- (Qinv_involutive (inject_Z 2*proj1_sig e2)).
456 apply Qle_shift_div_l.
457 + apply Qinv_lt_0_compat.
458 exact (Qpos_ispos ((2#1)*e2)).
459 + unfold e2'.
460 generalize (CompactIntervalQ_nat e2).
461 unfold Qdiv.
462 generalize ((r - l) * / (inject_Z 2 * proj1_sig e2)).
463 intros q He.
464 apply Qle_trans with (inject_Z (Qceiling q)).
465 apply Qle_ceiling.
466 destruct (Qceiling q). discriminate.
467 rewrite Z2Pos.id.
468 apply Z.le_refl.
469 reflexivity. discriminate.
470 + rewrite <- Qplus_0_l at 1.
471 apply Qplus_le_l.
472 apply Qpos_nonneg.
473 Qed.
474
475 Definition CompactIntervalQ : Compact Q_as_MetricSpace :=
476 Build_RegularFunction CompactIntervalQ_prf.
477
478 Local Open Scope CR_scope.
479
480 Opaque max.
481
482 (** The compact set indeed represents the interval [[l, r]]. *)
483 Lemma CompactIntervalQ_correct1 : forall (x:CR),
484 inCompact x CompactIntervalQ -> ('l <= x /\ x <= 'r).
485 Proof.
486 intros x Hx.
487 split.
488 unfold CRle.
489 assert (x - 'l == '(-l)%Q + x)%CR. ring. rewrite -> H. clear H.
490 rewrite -> CRplus_translate.
491 intros e.
492 simpl.
493 rewrite -> Qle_minus_iff.
494 setoid_replace (- l + approximate x e + - - proj1_sig e)%Q
495 with (proj1_sig e + - (l - approximate x e))%Q
496 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
497 rewrite <- Qle_minus_iff.
498 apply Qle_closed.
499 intros e2.
500 assert (L:=Hx e e2).
501 simpl in L.
502 set (a:=Z.to_pos (Qceiling ((r - l) / (inject_Z 2 * proj1_sig e2)))) in *.
503 assert (L0:=UniformPartition_inside a).
504 induction (UniformPartition a).
505 exfalso; exact (FinSubset_ball_nil L).
506 apply FinSubset_ball_orC in L.
507 destruct L as [ G | L | L] using orC_ind.
508 auto with *.
509 rewrite -> Qball_Qabs in L.
510 eapply Qle_trans;[|apply L].
511 rewrite <- Qabs_opp.
512 eapply Qle_trans;[|apply Qle_Qabs].
513 rewrite -> Qle_minus_iff.
514 setoid_replace (- (approximate x e - a0) + - (l - approximate x e))%Q
515 with (a0 + - l)%Q
516 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
517 rewrite <- Qle_minus_iff.
518 destruct (L0 a0); auto with *.
519 apply IHl0; auto with *.
520 unfold CRle.
521 rewrite -> CRplus_translate.
522 intros e.
523 simpl.
524 rewrite -> Qle_minus_iff.
525 setoid_replace (r + - approximate x e + - - proj1_sig e)%Q
526 with (proj1_sig e + - (approximate x e - r))%Q
527 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
528 rewrite <- Qle_minus_iff.
529 apply Qle_closed.
530 intros e2.
531 assert (L:=Hx e e2).
532 simpl in L.
533 set (a:=Z.to_pos (Qceiling ((r - l) / (inject_Z 2 * proj1_sig e2)))) in *.
534 assert (L0:=UniformPartition_inside a).
535 induction (UniformPartition a).
536 exfalso; exact (FinSubset_ball_nil L).
537 apply FinSubset_ball_orC in L.
538 destruct L as [ G | L | L] using orC_ind.
539 auto with *.
540 rewrite -> Qball_Qabs in L.
541 eapply Qle_trans;[|apply L].
542 eapply Qle_trans;[|apply Qle_Qabs].
543 rewrite -> Qle_minus_iff.
544 setoid_replace (approximate x e - a0 + - (approximate x e - r))%Q
545 with (r + - a0)%Q
546 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
547 rewrite <- Qle_minus_iff.
548 destruct (L0 a0); auto with *.
549 apply IHl0; auto with *.
550 Qed.
551
552 Lemma CompactIntervalQ_correct2 : forall (x:CR),
553 ('l <= x /\ x <= 'r) -> inCompact x CompactIntervalQ.
554 Proof.
555 intros x [Hlx Hxr] e1 e2.
556 simpl.
557 set (y:= (Qmax (Qmin (approximate x e1) r) l)).
558 apply (@FinSubset_ball_triangle_l _ (proj1_sig e1) (proj1_sig e2) (approximate x e1) y).
559 - unfold y.
560 apply Qmin_case.
561 apply Qmax_case.
562 auto with *.
563 intros H _.
564 split; simpl.
565 unfold CRle in Hlx.
566 assert (x - 'l == '(-l)%Q + x). ring. rewrite -> H0 in Hlx. clear H0.
567 rewrite -> CRplus_translate in Hlx.
568 assert (H0:=Hlx e1).
569 simpl in H0.
570 clear - H0.
571 unfold Qminus. rewrite Qplus_comm.
572 exact H0.
573 apply Qle_trans with 0%Q; auto with *.
574 clear - H.
575 rewrite Qle_minus_iff in *.
576 setoid_replace (0 + - (approximate x e1 - l))%Q
577 with (l + - approximate x e1)%Q
578 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
579 exact H.
580 intros H.
581 rewrite -> Qle_max_l in Hlr.
582 simpl.
583 rewrite -> Hlr.
584 split; simpl.
585 clear - H.
586 apply Qle_trans with 0%Q.
587 apply (Qopp_le_compat 0), Qpos_nonneg.
588 rewrite -> Qle_minus_iff in *.
589 rewrite Qplus_0_r.
590 auto.
591 unfold CRle in Hxr.
592 rewrite -> CRplus_translate in Hxr.
593 assert (H0:=Hxr e1).
594 simpl in H0.
595 clear - H0.
596 rewrite -> Qle_minus_iff in *.
597 setoid_replace (proj1_sig e1 + - (approximate x e1 - r))%Q
598 with ( r + - approximate x e1 + - - proj1_sig e1)%Q
599 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
600 exact H0.
601 - assert (L: l <= y <= r).
602 { unfold y. auto with *. }
603 set (n:=Z.to_pos (Qceiling ((r - l) / (inject_Z 2 * proj1_sig e2)))).
604 destruct (UniformPartition_fine n L) as [z Hz].
605 clear - Hz.
606 destruct Hz as [Hz0 Hz1].
607 induction (UniformPartition n).
608 contradiction.
609 destruct Hz0 as [Hz0 | Hz0].
610 + intro abs; contradict abs. exists a.
611 split. left. reflexivity.
612 rewrite Hz0.
613 simpl.
614 rewrite -> Qball_Qabs.
615 eapply Qle_trans;[apply Hz1|].
616 clear Hz1.
617 apply Qle_shift_div_r.
618 reflexivity.
619 unfold Qdiv in n.
620 unfold n. clear n.
621 rewrite (Qmult_comm (r-l)).
622 apply (Qmult_le_l _ _ (/(inject_Z 2 * proj1_sig e2))).
623 apply Qinv_lt_0_compat. apply (Qpos_ispos ((2#1)*e2)).
624 generalize (/ (inject_Z 2 * proj1_sig e2) * (r-l))%Q.
625 intro q.
626 rewrite Qmult_assoc, Qmult_assoc.
627 setoid_replace (/ (inject_Z 2 * proj1_sig e2) * proj1_sig e2 * (2#1))%Q with 1%Q
628 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; field).
629 rewrite Qmult_1_l.
630 apply (Qle_trans _ (inject_Z (Qceiling q)) _ (Qle_ceiling _)).
631 rewrite <- Zle_Qle.
632 destruct (Qceiling q).
633 discriminate.
634 apply Z.le_refl.
635 discriminate. apply Qpos_nonzero.
636 + apply FinSubset_ball_cons.
637 apply IHl0, Hz0.
638 Qed.
639
640 Lemma CompactIntervalQ_bonus_correct : forall e x,
641 In x (approximate CompactIntervalQ e) -> (l <= x <= r).
642 Proof.
643 intros [e|] x H.
644 simpl in H.
645 eapply UniformPartition_inside.
646 apply H.
647 elim H.
648 Qed.
649
650 End Interval.
651
652 (* Located subsets are more general than compact subsets. *)
653 Lemma InfiniteIntervalLocated
654 : forall a : CR, LocatedSubset CR (fun x => a <= x)%CR.
655 Proof.
656 intros a d e x ltde.
657 (* The distance between x and [a,+\infty[ is CRmax 0 (a-x). *)
658 destruct (CRlt_linear _ (CRmax 0%CR (a-x)%CR) _ (CRlt_Qlt d e ltde))
659 as [far|close].
660 - left. intros y H abs.
661 clear ltde e.
662 destruct (Qlt_le_dec d 0).
663 apply (msp_nonneg (msp CR)) in abs.
664 exact (Qlt_not_le _ _ q abs).
665 assert (~(('d < a - x)%CR -> False)).
666 { intros H0. apply CRle_not_lt in H0.
667 revert far. apply CRle_not_lt, CRmax_lub.
668 apply CRle_Qle, q. exact H0. }
669 clear far.
670 contradict H0. apply CRle_not_lt.
671 apply CRabs_ball, CRabs_AbsSmall in abs.
672 destruct abs as [abs _].
673 rewrite (CRplus_le_r _ _ (y+('d)))%CR in abs.
674 ring_simplify in abs.
675 apply (CRle_trans H) in abs.
676 clear H y.
677 rewrite (CRplus_le_r _ _ x).
678 ring_simplify.
679 rewrite CRplus_comm. exact abs.
680 - destruct (Qlt_le_dec d 0).
681 left. intros y H abs.
682 apply (msp_nonneg (msp CR)) in abs.
683 exact (Qlt_not_le _ _ q abs).
684 right. exists (CRmax a x).
685 split. apply CRmax_ub_l.
686 apply CRabs_ball, CRabs_AbsSmall.
687 split.
688 + rewrite (CRplus_le_r _ _ (CRmax a x + 'e))%CR.
689 ring_simplify.
690 apply CRmax_lub.
691 rewrite (CRplus_le_r _ _ (-x))%CR.
692 rewrite <- CRplus_assoc.
693 rewrite CRplus_opp, CRplus_0_r.
694 apply CRle_not_lt. intro abs.
695 apply (CRlt_trans _ _ _ close) in abs.
696 clear close. revert abs.
697 apply CRle_not_lt.
698 apply CRmax_ub_r.
699 apply (@CRle_trans _ (0+x)%CR).
700 rewrite CRplus_0_l. apply CRle_refl.
701 apply CRplus_le_r.
702 apply CRle_Qle, (Qle_trans _ _ _ q).
703 apply Qlt_le_weak, ltde.
704 + rewrite (CRplus_le_r _ _ (CRmax a x)).
705 ring_simplify.
706 apply (@CRle_trans _ (CRmax a x + 0)%CR).
707 rewrite CRplus_0_r. apply CRmax_ub_r.
708 apply CRplus_le_l, CRle_Qle.
709 apply (Qle_trans _ _ _ q).
710 apply Qlt_le_weak, ltde.
711 Qed.