Debian Codegraph @

reals/stdlib/ConstructiveUniformCont.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
13 (*
14 The uniformly continuous functions R -> R.
15 *)
16
17 From Coq Require Import List Permutation Orders Sorted Mergesort.
18 From Coq Require Import ZArith QArith Qpower.
19 From Coq Require Import ConstructiveReals.
20 From Coq Require Import ConstructiveAbs.
21 From Coq Require Import ConstructiveMinMax.
22 From Coq Require Import ConstructiveSum.
23 From Coq Require Import ConstructivePower.
24 From Coq Require Import ConstructiveLimits.
25 Require Import ConstructiveDiagonal.
26
27 Local Open Scope ConstructiveReals.
28
29
30 Definition UniformCont {R : ConstructiveReals}
31 (f : CRcarrier R -> CRcarrier R)
32 (cont_mod : forall x:CRcarrier R, 0 < x -> CRcarrier R) : Set
33 := prod (forall (x:CRcarrier R) (xPos : 0 < x), 0 < cont_mod x xPos) (* otherwise any function is trivially continuous *)
34 (forall (eps x y : CRcarrier R) (epsPos : 0 < eps),
35 CRabs _ (x - y) < cont_mod eps epsPos
36 -> CRabs _ (f x - f y) < eps).
37
38 Definition Lipschitz {R : ConstructiveReals}
39 (f : CRcarrier R -> CRcarrier R) (k : CRcarrier R) : Set
40 := forall (x y : CRcarrier R),
41 CRabs _ (f x - f y) <= k * CRabs _ (x - y).
42
43 Lemma UniformContProper :
44 forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
45 (cont_mod : forall x:CRcarrier R, 0 < x -> CRcarrier R),
46 UniformCont f cont_mod
47 -> (forall x y : CRcarrier R, x == y -> f x == f y).
48 Proof.
49 intros. destruct H. split.
50 - intro abs.
51 assert (0 < f y - f x) as epsPos.
52 { rewrite <- (CRplus_opp_r (f x)).
53 apply CRplus_lt_compat_r. exact abs. }
54 specialize (c0 (f y - f x) x y epsPos).
55 apply (CRle_abs (f y - f x)).
56 rewrite CRabs_minus_sym. apply c0.
57 apply (CRle_lt_trans _ (CRabs _ 0)).
58 rewrite H0. unfold CRminus. rewrite CRplus_opp_r.
59 apply CRle_refl. rewrite CRabs_right. apply c.
60 apply CRle_refl.
61 - intro abs.
62 assert (0 < f x - f y) as epsPos.
63 { rewrite <- (CRplus_opp_r (f y)).
64 apply CRplus_lt_compat_r. exact abs. }
65 specialize (c0 (f x - f y) x y epsPos).
66 apply (CRle_abs (f x - f y)).
67 apply c0. apply (CRle_lt_trans _ (CRabs _ 0)).
68 rewrite H0. unfold CRminus. rewrite CRplus_opp_r.
69 apply CRle_refl. rewrite CRabs_right. apply c.
70 apply CRle_refl.
71 Qed.
72
73 Lemma LipschitzUC
74 : forall {R : ConstructiveReals}
75 (f : CRcarrier R -> CRcarrier R)
76 (k : CRcarrier R) (kPos : 0 < k),
77 Lipschitz f k
78 -> UniformCont f (fun eps epsPos => eps * CRinv R k (inr kPos)).
79 Proof.
80 split.
81 - intros eps epsPos.
82 apply (CRle_lt_trans _ (eps * 0)). rewrite CRmult_0_r.
83 apply CRle_refl. apply CRmult_lt_compat_l. exact epsPos.
84 apply CRinv_0_lt_compat, kPos.
85 - intros. apply (CRle_lt_trans _ _ _ (H x y)).
86 apply (CRmult_lt_compat_r k) in H0.
87 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in H0.
88 rewrite CRmult_comm. exact H0. exact kPos.
89 Qed.
90
91
92 (* Compact support and uniformly continuous.
93 On R we simplify this by segment support and uniformly continuous. *)
94 Definition CSUC {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
95 (a b : CRcarrier R) (cont_mod : forall x:CRcarrier R, 0 < x -> CRcarrier R) : Set
96 := prod (UniformCont f cont_mod)
97 (forall x : CRcarrier R, (sum (x < a) (b < x)) -> f x == 0).
98
99 Lemma CSUC_connect_support
100 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
101 (a b : CRcarrier R) (cont_mod : forall x:CRcarrier R, 0 < x -> CRcarrier R),
102 CSUC f a b cont_mod
103 -> (forall x : CRcarrier R, (sum (x <= a) (b <= x)) -> f x == 0).
104 Proof.
105 intros. destruct H, u. split.
106 - intro abs. destruct H0.
107 + apply CRopp_gt_lt_contravar in abs. rewrite CRopp_0 in abs.
108 specialize (c1 (-f x) (x - (cont_mod (-f x) abs) * CR_of_Q R (1#2)) x abs).
109 apply (CRle_abs (-f x)).
110 apply (CRle_lt_trans
111 _ (CRabs _ (f (x - cont_mod (- f x) abs * CR_of_Q R (1 # 2)) - f x))).
112 rewrite (c (x - cont_mod (-f x) abs * CR_of_Q R (1#2))).
113 unfold CRminus. rewrite CRplus_0_l. apply CRle_refl.
114 left. apply (CRlt_le_trans _ (x + 0)).
115 apply CRplus_lt_compat_l. rewrite <- CRopp_0. apply CRopp_gt_lt_contravar.
116 apply CRmult_lt_0_compat. apply c0.
117 apply CR_of_Q_pos; reflexivity.
118 rewrite CRplus_0_r. exact c2. apply c1.
119 setoid_replace (x + - (cont_mod (-f x) abs * CR_of_Q R (1#2)) + - x)
120 with (- (cont_mod (-f x) abs * CR_of_Q R (1#2))).
121 rewrite CRabs_opp. rewrite CRabs_right.
122 rewrite <- (CRmult_1_r (cont_mod (- f x) abs)).
123 rewrite CRmult_assoc. apply CRmult_lt_compat_l. apply c0.
124 rewrite CRmult_1_l. apply CR_of_Q_lt; reflexivity.
125 apply CRlt_asym.
126 apply CRmult_lt_0_compat. apply c0.
127 apply CR_of_Q_pos; reflexivity.
128 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
129 reflexivity.
130 + apply CRopp_gt_lt_contravar in abs. rewrite CRopp_0 in abs.
131 specialize (c1 (-f x) (x + (cont_mod (-f x) abs) * CR_of_Q R (1#2)) x abs).
132 apply (CRle_abs (-f x)).
133 apply (CRle_lt_trans
134 _ (CRabs _ (f (x + cont_mod (- f x) abs * CR_of_Q R (1 # 2)) - f x))).
135 rewrite (c (x + cont_mod (-f x) abs * CR_of_Q R (1#2))).
136 unfold CRminus. rewrite CRplus_0_l. apply CRle_refl.
137 right. apply (CRle_lt_trans _ (x + 0)).
138 rewrite CRplus_0_r. exact c2. apply CRplus_lt_compat_l.
139 apply CRmult_lt_0_compat. apply c0.
140 apply CR_of_Q_pos; reflexivity.
141 apply c1.
142 setoid_replace (x + (cont_mod (-f x) abs * CR_of_Q R (1#2)) + - x)
143 with (cont_mod (-f x) abs * CR_of_Q R (1#2)).
144 rewrite CRabs_right. rewrite <- (CRmult_1_r (cont_mod (- f x) abs)).
145 rewrite CRmult_assoc. apply CRmult_lt_compat_l. apply c0.
146 rewrite CRmult_1_l.
147 apply CR_of_Q_lt; reflexivity.
148 apply CRlt_asym.
149 apply CRmult_lt_0_compat. apply c0.
150 apply CR_of_Q_pos; reflexivity.
151 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
152 reflexivity.
153 - intro abs. destruct H0.
154 + specialize (c1 (f x) (x - (cont_mod (f x) abs) * CR_of_Q R (1#2)) x abs).
155 apply (CRle_abs (f x)).
156 apply (CRle_lt_trans
157 _ (CRabs _ (f (x - cont_mod (f x) abs * CR_of_Q R (1 # 2)) - f x))).
158 rewrite (c (x - cont_mod (f x) abs * CR_of_Q R (1#2))).
159 unfold CRminus. rewrite CRplus_0_l, CRabs_opp.
160 apply CRle_refl. left. apply (CRlt_le_trans _ (x + 0)).
161 apply CRplus_lt_compat_l. rewrite <- CRopp_0. apply CRopp_gt_lt_contravar.
162 apply CRmult_lt_0_compat. apply c0.
163 apply CR_of_Q_pos; reflexivity.
164 rewrite CRplus_0_r. exact c2. apply c1.
165 setoid_replace (x + - (cont_mod (f x) abs * CR_of_Q R (1#2)) + - x)
166 with (- (cont_mod (f x) abs * CR_of_Q R (1#2))).
167 rewrite CRabs_opp. rewrite CRabs_right.
168 rewrite <- (CRmult_1_r (cont_mod (f x) abs)).
169 rewrite CRmult_assoc. apply CRmult_lt_compat_l. apply c0.
170 rewrite CRmult_1_l. apply CR_of_Q_lt; reflexivity.
171 apply CRlt_asym.
172 apply CRmult_lt_0_compat. apply c0.
173 apply CR_of_Q_pos; reflexivity.
174 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
175 reflexivity.
176 + specialize (c1 (f x) (x + (cont_mod (f x) abs) * CR_of_Q R (1#2)) x abs).
177 apply (CRle_abs (f x)).
178 apply (CRle_lt_trans
179 _ (CRabs _ (f (x + cont_mod (f x) abs * CR_of_Q R (1 # 2)) - f x))).
180 rewrite (c (x + cont_mod (f x) abs * CR_of_Q R (1#2))).
181 unfold CRminus. rewrite CRplus_0_l, CRabs_opp.
182 apply CRle_refl. right. apply (CRle_lt_trans _ (x + 0)).
183 rewrite CRplus_0_r. exact c2. apply CRplus_lt_compat_l.
184 apply CRmult_lt_0_compat. apply c0.
185 apply CR_of_Q_pos; reflexivity.
186 apply c1.
187 setoid_replace (x + (cont_mod (f x) abs * CR_of_Q R (1#2)) + - x)
188 with (cont_mod (f x) abs * CR_of_Q R (1#2)).
189 rewrite CRabs_right. rewrite <- (CRmult_1_r (cont_mod (f x) abs)).
190 rewrite CRmult_assoc. apply CRmult_lt_compat_l. apply c0.
191 rewrite CRmult_1_l. apply CR_of_Q_lt; reflexivity.
192 apply CRlt_asym.
193 apply CRmult_lt_0_compat. apply c0.
194 apply CR_of_Q_pos; reflexivity.
195 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
196 reflexivity.
197 Qed.
198
199 Lemma UC_constant : forall {R : ConstructiveReals} (c : CRcarrier R),
200 UniformCont (fun _:CRcarrier R => c) (fun _ _ => 1).
201 Proof.
202 split. intros. apply CRzero_lt_one.
203 intros. unfold CRminus.
204 rewrite CRplus_opp_r, CRabs_right.
205 exact epsPos. apply CRle_refl.
206 Qed.
207
208 Lemma eps2_Rgt_R0 : forall {R : ConstructiveReals} (eps : CRcarrier R),
209 0 < eps -> 0 < eps * CR_of_Q R (1#2).
210 Proof.
211 intros.
212 apply CRmult_lt_0_compat. apply H.
213 apply CR_of_Q_pos; reflexivity.
214 Qed.
215
216 Lemma UC_plus : forall {R : ConstructiveReals} (f g : CRcarrier R -> CRcarrier R)
217 (modF modG : forall x:CRcarrier R, 0 < x -> CRcarrier R),
218 UniformCont f modF
219 -> UniformCont g modG
220 -> UniformCont (fun x:CRcarrier R => f x + g x)
221 (fun eps epsPos => CRmin (modF (eps * CR_of_Q R (1#2)) (eps2_Rgt_R0 eps epsPos))
222 (modG (eps * CR_of_Q R (1#2)) (eps2_Rgt_R0 eps epsPos))).
223 Proof.
224 split.
225 - intros. apply CRmin_lt. destruct H. apply c.
226 destruct H0. apply c.
227 - intros.
228 setoid_replace (f x + g x - (f y + g y))
229 with (f x - f y + (g x - g y)).
230 apply (CRle_lt_trans _ _ _ (CRabs_triang _ _)).
231 setoid_replace eps with (eps* CR_of_Q R (1#2) + eps* CR_of_Q R (1#2)).
232 apply CRplus_le_lt_compat. apply CRlt_asym.
233 destruct H.
234 apply (c0 _ _ _ (eps2_Rgt_R0 eps epsPos)).
235 apply (CRlt_le_trans
236 _ (CRmin (modF (eps * CR_of_Q R (1#2)) (eps2_Rgt_R0 eps epsPos))
237 (modG (eps * CR_of_Q R (1#2)) (eps2_Rgt_R0 eps epsPos)))).
238 apply H1. apply CRmin_l.
239 destruct H0. apply (c0 _ _ _ (eps2_Rgt_R0 eps epsPos)).
240 apply (CRlt_le_trans
241 _ (CRmin (modF (eps * CR_of_Q R (1#2)) (eps2_Rgt_R0 eps epsPos))
242 (modG (eps * CR_of_Q R (1#2)) (eps2_Rgt_R0 eps epsPos)))).
243 apply H1. apply CRmin_r.
244 rewrite <- CRmult_plus_distr_l, <- CR_of_Q_plus.
245 setoid_replace ((1 # 2) + (1#2))%Q with 1%Q.
246 rewrite CRmult_1_r.
247 reflexivity. reflexivity.
248 unfold CRminus. do 2 rewrite CRplus_assoc. apply CRplus_morph.
249 reflexivity. rewrite CRplus_comm, CRopp_plus_distr.
250 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
251 rewrite CRplus_comm. reflexivity.
252 Qed.
253
254 Fixpoint UC_sum {R : ConstructiveReals} (fn : nat -> CRcarrier R -> CRcarrier R)
255 (fnMod : nat -> forall x:CRcarrier R, 0 < x -> CRcarrier R)
256 (fnCont : forall n:nat, UniformCont (fn n) (fnMod n))
257 (n : nat)
258 : { sMod : forall x:CRcarrier R, 0 < x -> CRcarrier R
259 & UniformCont (fun x:CRcarrier R => CRsum (fun i => fn i x) n) sMod }.
260 Proof.
261 destruct n.
262 - exists (fnMod O). apply fnCont.
263 - destruct (UC_sum R fn fnMod fnCont n) as [sMod sCont].
264 exists (fun eps epsPos => CRmin (sMod (eps* CR_of_Q R (1#2)) (eps2_Rgt_R0 eps epsPos))
265 (fnMod (S n) (eps* CR_of_Q R (1#2)) (eps2_Rgt_R0 eps epsPos))).
266 simpl. apply UC_plus. apply sCont. apply fnCont.
267 Qed.
268
269 Lemma UC_translate : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
270 (a : CRcarrier R)
271 (modF : forall x:CRcarrier R, 0 < x -> CRcarrier R),
272 UniformCont f modF
273 -> UniformCont (fun x:CRcarrier R => f x + a) modF.
274 Proof.
275 split. apply H. intros.
276 setoid_replace (f x + a - (f y + a)) with (f x - f y).
277 destruct H. apply (c0 _ _ _ epsPos). apply H0.
278 unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph.
279 reflexivity.
280 rewrite CRplus_comm, CRopp_plus_distr.
281 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r. reflexivity.
282 Qed.
283
284 Lemma UC_translate_horizontal
285 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
286 (a : CRcarrier R)
287 (modF : forall x:CRcarrier R, 0 < x -> CRcarrier R),
288 UniformCont f modF
289 -> UniformCont (fun x:CRcarrier R => f (x + a)) modF.
290 Proof.
291 split. apply H. intros.
292 destruct H. apply (c0 _ _ _ epsPos).
293 setoid_replace (x + a - (y + a)) with (x-y).
294 apply H0.
295 unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph.
296 reflexivity.
297 rewrite CRplus_comm, CRopp_plus_distr.
298 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r. reflexivity.
299 Qed.
300
301 Lemma UC_modExt : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
302 (modF modG : forall x:CRcarrier R, 0 < x -> CRcarrier R),
303 UniformCont f modF
304 -> (forall x xPos, modF x xPos == modG x xPos)
305 -> UniformCont f modG.
306 Proof.
307 split.
308 - intros. rewrite <- H0. destruct H. apply c.
309 - intros. rewrite <- H0 in H1. destruct H.
310 apply (c0 _ _ _ epsPos). apply H1.
311 Qed.
312
313 Lemma UC_ext : forall {R : ConstructiveReals} (f g : CRcarrier R -> CRcarrier R)
314 (modF : forall x:CRcarrier R, 0 < x -> CRcarrier R),
315 UniformCont f modF
316 -> (forall x:CRcarrier R, f x == g x)
317 -> UniformCont g modF.
318 Proof.
319 intros. destruct H. split.
320 - apply c.
321 - intros. do 2 rewrite <- H0. exact (c0 eps x y epsPos H).
322 Qed.
323
324 Lemma posScale : forall {R : ConstructiveReals} (a : CRcarrier R),
325 0 < CRmax 1 (CRabs _ a).
326 Proof.
327 intros. apply (CRlt_le_trans 0 1).
328 apply CRzero_lt_one. apply CRmax_l.
329 Qed.
330
331 Lemma UC_scale : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
332 (modF : forall x:CRcarrier R, 0 < x -> CRcarrier R)
333 (a : CRcarrier R),
334 UniformCont f modF
335 -> UniformCont
336 (fun x:CRcarrier R => a * f x)
337 (fun (eps:CRcarrier R) epsPos => modF (eps * (CRinv R (CRmax 1 (CRabs _ a)) (inr (posScale a))))
338 (CRmult_lt_0_compat _
339 eps _ epsPos (CRinv_0_lt_compat _
340 _ (inr (posScale a)) (posScale a)))).
341 Proof.
342 split.
343 - intros x xPos. destruct H. apply c.
344 - intros. unfold CRminus.
345 rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l.
346 rewrite CRabs_mult.
347 apply (CRle_lt_trans
348 _ (CRmax 1 (CRabs _ a) * CRabs _ (f x - f y))).
349 apply CRmult_le_compat_r. apply CRabs_pos. apply CRmax_r.
350 destruct H. specialize (c0 _ _ _ _ H0).
351 apply (CRmult_lt_compat_r (CRmax 1 (CRabs _ a))) in c0.
352 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in c0.
353 rewrite CRmult_comm. exact c0. apply posScale.
354 Qed.
355
356 Lemma TelescopicSum : forall {R : ConstructiveReals} (un : nat -> CRcarrier R) (n : nat),
357 CRsum (fun k => un (S k) - un k) n == un (S n) - (un O).
358 Proof.
359 induction n.
360 - reflexivity.
361 - simpl. rewrite IHn. rewrite CRplus_comm.
362 unfold CRminus. rewrite CRplus_assoc.
363 apply CRplus_morph. reflexivity.
364 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
365 Qed.
366
367 Lemma Rsum_minus : forall {R : ConstructiveReals} (un vn : nat -> CRcarrier R) (n : nat),
368 CRsum (fun k => un k - vn k) n
369 == CRsum un n - CRsum vn n.
370 Proof.
371 induction n.
372 - reflexivity.
373 - simpl. rewrite IHn.
374 unfold CRminus. do 2 rewrite CRplus_assoc.
375 apply CRplus_morph. reflexivity. rewrite CRplus_comm.
376 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
377 rewrite CRplus_comm, CRopp_plus_distr. reflexivity.
378 Qed.
379
380 Lemma Rsmaller_interval : forall {R : ConstructiveReals} (a b c d : CRcarrier R),
381 a <= c -> c <= b
382 -> a <= d -> d <= b
383 -> CRabs _ (d - c) <= b-a.
384 Proof.
385 intros. apply CRabs_le. split.
386 - apply (CRplus_le_reg_l (c+b)).
387 unfold CRminus. rewrite CRopp_plus_distr.
388 rewrite CRplus_assoc, <- (CRplus_assoc b).
389 rewrite CRplus_opp_r, (CRplus_comm c b), CRplus_assoc.
390 apply CRplus_le_compat. exact H0.
391 rewrite CRopp_involutive, CRplus_0_l, CRplus_comm.
392 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r. exact H1.
393 - apply (CRplus_le_reg_r (a+c)).
394 unfold CRminus. rewrite (CRplus_assoc b), <- (CRplus_assoc (-a)).
395 rewrite CRplus_opp_l, CRplus_0_l, CRplus_assoc.
396 apply CRplus_le_compat. exact H2. rewrite CRplus_comm.
397 rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r. exact H.
398 Qed.
399
400 Lemma sum_by_packets
401 : forall {R : ConstructiveReals} (xn : nat -> CRcarrier R) (Pn : nat -> nat) (n : nat),
402 (forall k, le k n -> lt (Pn k) (Pn (S k)))
403 -> Pn O = O
404 -> CRsum (fun i => CRsum (fun k => xn (k + Pn i))%nat
405 (pred (Pn (S i) - Pn i))) n
406 == CRsum xn (pred (Pn (S n))).
407 Proof.
408 induction n.
409 - intros. simpl. rewrite H0.
410 replace (pred (Pn 1 - 0))%nat with (pred (Pn 1%nat)).
411 apply CRsum_eq. intros. rewrite Nat.add_comm. reflexivity.
412 rewrite Nat.sub_0_r. reflexivity.
413 - intros.
414 assert (forall k : nat, k <= n -> Pn k < Pn (S k))%nat.
415 { intros. apply H. apply (Nat.le_trans _ n _ H1). apply le_S, Nat.le_refl. }
416 specialize (IHn H1 H0). clear H1. simpl.
417 rewrite IHn.
418 destruct (Pn (S (S n)) - Pn (S n))%nat eqn:des.
419 exfalso. apply Nat.sub_0_le in des.
420 apply (proj1 (Nat.le_ngt _ _) des). apply H, Nat.le_refl. simpl.
421 pose proof (H n). destruct (Pn (S n)).
422 exfalso. apply (proj1 (Nat.le_ngt 0 (Pn n)) (Nat.le_0_l _)). apply H1, le_S, Nat.le_refl.
423 clear H1. simpl.
424 rewrite (CRsum_eq (fun k : nat => xn (k + S n1)%nat)
425 (fun k : nat => xn (S n1 + k)%nat)).
426 2: intros; rewrite Nat.add_comm; reflexivity.
427 rewrite <- (sum_assoc xn n1).
428 replace (S n1 + n0)%nat with (Init.Nat.pred (Pn (S (S n)))).
429 reflexivity.
430 pose proof (H (S n) (Nat.le_refl _)). destruct (Pn (S (S n))). exfalso.
431 inversion H1.
432 simpl. simpl in des.
433 replace (S (n1 + n0)) with (n1 + S n0)%nat.
434 2: apply Nat.add_succ_r.
435 rewrite <- des. rewrite Nat.add_comm. rewrite Nat.sub_add.
436 reflexivity. destruct (le_lt_dec n2 n1).
437 apply Nat.sub_0_le in l. rewrite l in des. discriminate.
438 apply (Nat.le_trans _ (S n1)). apply le_S, Nat.le_refl. exact l.
439 Qed.
440
441
442 (* TODO replace SubSeqCv *)
443 Lemma ShouldReplaceSubSeq : forall (sub : SubSeq) (n : nat),
444 le n (proj1_sig sub n).
445 Proof.
446 induction n.
447 - apply Nat.le_0_l.
448 - destruct sub; simpl. simpl in IHn. specialize (l n (S n) (Nat.le_refl _)).
449 apply (Nat.le_trans _ (S (x n))). apply le_n_S, IHn. exact l.
450 Qed.
451
452 Lemma SubSeqCvMerge : forall {R : ConstructiveReals} (un : nat -> CRcarrier R)
453 (sub : nat -> nat) (l : CRcarrier R),
454 (forall n:nat, le n (sub n))
455 -> CR_cv R un l -> CR_cv R (fun n => un (sub n)) l.
456 Proof.
457 intros. intros n. specialize (H0 n) as [p pmaj].
458 exists p. intros. apply pmaj.
459 apply (Nat.le_trans _ i _ H0), H.
460 Qed.
461
462 Lemma Qpower_positive : forall (q : Q) (n : nat),
463 Qlt 0 q -> Qlt 0 (q^Z.of_nat n).
464 Proof.
465 induction n.
466 - intros. reflexivity.
467 - intros. rewrite Nat2Z.inj_succ. unfold Z.succ. rewrite Qpower_plus.
468 rewrite <- (Qmult_0_l q). apply Qmult_lt_r. exact H. exact (IHn H).
469 intro abs. rewrite abs in H. inversion H.
470 Qed.
471
472 Lemma pow_inject_Q : forall {R : ConstructiveReals} (q : Q) (n : nat),
473 ~(q == 0)%Q
474 -> (CR_of_Q R (q ^ Z.of_nat n) == CRpow (CR_of_Q R q) n).
475 Proof.
476 induction n.
477 - intros. reflexivity.
478 - intros. rewrite Nat2Z.inj_succ. unfold Z.succ. rewrite Qpower_plus.
479 rewrite CR_of_Q_mult, IHn. simpl. apply CRmult_comm. exact H. exact H.
480 Qed.
481
482 Definition UCUnitHeaviside {R : ConstructiveReals}
483 (a b : CRcarrier R) (ltab : a < b)
484 : CRcarrier R -> CRcarrier R
485 := fun x => (CRmax 0 (CRmin 1 ((x - a) * (CRinv R (b-a) (inr (CRlt_minus _ _ ltab)))))).
486
487 Lemma LipschitzMin
488 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
489 (k m : CRcarrier R),
490 Lipschitz f k
491 -> Lipschitz (fun x => CRmin m (f x)) k.
492 Proof.
493 intros R f k m fl x y.
494 rewrite CRmin_sym, (CRmin_sym m).
495 apply (CRle_trans _ _ _ (CRmin_contract _ _ _)).
496 apply fl.
497 Qed.
498
499 Lemma UCmin : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
500 (m : CRcarrier R)
501 (fMod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R),
502 0 <= m
503 -> UniformCont f fMod -> UniformCont (fun x => CRmin m (f x)) fMod.
504 Proof.
505 intros R f m fMod mPos H. destruct H. split. exact c.
506 intros. apply (CRle_lt_trans _ (CRabs _ (f x - f y))).
507 2: apply (c0 eps _ _ epsPos H).
508 rewrite CRmin_sym, (CRmin_sym m). apply CRmin_contract.
509 Qed.
510
511 Lemma UCmax : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
512 (m : CRcarrier R)
513 (fMod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R),
514 0 <= m
515 -> UniformCont f fMod -> UniformCont (fun x => CRmax m (f x)) fMod.
516 Proof.
517 intros R f m fMod mPos H. destruct H. split. exact c.
518 intros. apply (CRle_lt_trans _ (CRabs _ (f x - f y))).
519 2: apply (c0 eps _ _ epsPos H).
520 rewrite CRmax_sym, (CRmax_sym m). apply CRmax_contract.
521 Qed.
522
523 Lemma UCHeaviside_cont
524 : forall {R : ConstructiveReals} (a b : CRcarrier R) (ltab : a < b),
525 UniformCont (UCUnitHeaviside a b ltab)
526 (fun eps epsPos => eps * (b-a)).
527 Proof.
528 intros.
529 apply UCmax. apply CRle_refl. apply UCmin. apply CRlt_asym, CRzero_lt_one.
530 assert (0 < (b - a)). apply CRlt_minus. apply ltab.
531 split.
532 - intros. apply CRmult_lt_0_compat; assumption.
533 - intros.
534 rewrite (CRabs_morph
535 _ ((x - y) * (CRinv R (b - a) (inr (CRlt_minus a b ltab))))).
536 rewrite CRabs_mult.
537 rewrite (CRabs_right (CRinv R (b - a) (inr (CRlt_minus a b ltab)))).
538 apply (CRlt_le_trans
539 _ (eps * (b-a) * (CRinv R (b - a) (inr (CRlt_minus a b ltab))))).
540 apply CRmult_lt_compat_r. 2: exact H0.
541 apply CRinv_0_lt_compat, H.
542 rewrite CRmult_assoc, CRinv_r, CRmult_1_r. apply CRle_refl.
543 apply CRlt_asym, CRinv_0_lt_compat, H.
544 unfold CRminus. rewrite CRopp_mult_distr_l.
545 rewrite <- CRmult_plus_distr_r.
546 setoid_replace (x + - a + - (y + - a)) with (x+-y). reflexivity.
547 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
548 rewrite CRplus_comm, CRopp_plus_distr.
549 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r. reflexivity.
550 Qed.
551
552 Lemma UCHeavisideBounded : forall {R : ConstructiveReals} (a b x : CRcarrier R)
553 (ltab : a < b),
554 (0 <= UCUnitHeaviside a b ltab x <= 1).
555 Proof.
556 intros. unfold UCUnitHeaviside. split.
557 - apply CRmax_l.
558 - apply CRmax_lub. apply CRlt_asym, CRzero_lt_one. apply CRmin_l.
559 Qed.
560
561 Lemma Rplus_pos_higher : forall {R : ConstructiveReals} (a eps:CRcarrier R),
562 0 < eps -> a < (a+eps).
563 Proof.
564 intros.
565 rewrite <- (CRplus_0_r a). rewrite CRplus_assoc.
566 apply CRplus_lt_compat_l. rewrite CRplus_0_l.
567 exact H.
568 Qed.
569
570 Lemma Rminus_pos_lower : forall {R : ConstructiveReals} (a eps:CRcarrier R),
571 0 < eps -> (a-eps) < a.
572 Proof.
573 intros. apply (CRplus_lt_reg_r eps).
574 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
575 apply Rplus_pos_higher. apply H.
576 Qed.
577
578 Definition CSUCUnitTrapeze {R : ConstructiveReals}
579 (a b eta : CRcarrier R) (etaPos : 0 < eta)
580 (x : CRcarrier R) : CRcarrier R
581 := UCUnitHeaviside (a-eta) a (Rminus_pos_lower a eta etaPos) x
582 - UCUnitHeaviside b (b+eta) (Rplus_pos_higher b eta etaPos) x.
583
584 Lemma CSUCUnitTrapeze_cont
585 : forall {R : ConstructiveReals} (a b eta : CRcarrier R) (etaPos : 0 < eta),
586 a <= b -> UniformCont (CSUCUnitTrapeze a b eta etaPos)
587 (* The modulus could be improved to eps*eta *)
588 (fun eps epsPos => eps * CR_of_Q R (1#2) * eta).
589 Proof.
590 intros.
591 apply (UC_modExt _ (fun eps epsPos =>
592 CRmin (eps * CR_of_Q R (1#2) * (a - (a - eta)))
593 (eps * CR_of_Q R (1#2) * (b + eta - b)))).
594 - apply (UC_plus _ _
595 (fun eps epsPos => eps * (a-(a-eta)))
596 (fun eps epsPos => eps * (b+eta-b))).
597 apply UCHeaviside_cont. split.
598 intros. rewrite CRplus_comm. unfold CRminus.
599 rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r.
600 rewrite <- (CRmult_0_r x). apply CRmult_lt_compat_l.
601 exact xPos. exact etaPos.
602 intros. unfold CRminus.
603 rewrite <- CRopp_plus_distr. rewrite CRabs_opp.
604 apply UCHeaviside_cont. apply epsPos. apply H0.
605 - intros. rewrite CRmin_left.
606 unfold CRminus.
607 rewrite CRopp_plus_distr, <- CRplus_assoc, CRplus_opp_r, CRplus_0_l.
608 rewrite CRopp_involutive. reflexivity.
609 setoid_replace (a - (a - eta)) with eta.
610 setoid_replace (b + eta - b) with eta. apply CRle_refl.
611 unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
612 rewrite CRplus_opp_l, CRplus_0_l. reflexivity.
613 unfold CRminus. rewrite CRopp_plus_distr, <- CRplus_assoc.
614 rewrite CRplus_opp_r, CRplus_0_l, CRopp_involutive. reflexivity.
615 Qed.
616
617 Lemma UCHeavisideIn : forall {R : ConstructiveReals} (a b x : CRcarrier R) (altb : a < b),
618 b <= x -> UCUnitHeaviside a b altb x == 1.
619 Proof.
620 intros. unfold UCUnitHeaviside.
621 rewrite CRmin_left, CRmax_right. reflexivity.
622 apply CRlt_asym, CRzero_lt_one.
623 apply (CRmult_le_reg_r (b-a)).
624 unfold CRminus. rewrite <- (CRplus_opp_r a).
625 apply CRplus_lt_compat_r. exact altb.
626 rewrite CRmult_assoc, CRinv_l, CRmult_1_l, CRmult_1_r.
627 unfold CRminus. rewrite CRplus_comm, (CRplus_comm x).
628 apply CRplus_le_compat_l. apply H.
629 Qed.
630
631 Lemma CSUCTrapezePlateau
632 : forall {R : ConstructiveReals} (a b eta x : CRcarrier R) (etaPos : 0 < eta),
633 (a <= x <= b) -> CSUCUnitTrapeze a b eta etaPos x == 1.
634 Proof.
635 intros. unfold CSUCUnitTrapeze. rewrite UCHeavisideIn. 2: apply H.
636 unfold UCUnitHeaviside. rewrite CRmax_left.
637 unfold CRminus. rewrite CRopp_0, CRplus_0_r. reflexivity.
638 apply (CRle_trans _ _ _ (CRmin_r _ _)).
639 apply (CRmult_le_reg_r (b+eta-b)).
640 unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
641 rewrite CRplus_opp_l, CRplus_0_l. apply etaPos.
642 rewrite CRmult_assoc, CRinv_l, CRmult_0_l, CRmult_1_r.
643 unfold CRminus. rewrite CRplus_comm.
644 rewrite <- (CRplus_opp_l b). apply CRplus_le_compat_l. apply H.
645 Qed.
646
647 Lemma CSUCTrapezeInPlateau
648 : forall {R : ConstructiveReals} (a b eta x : CRcarrier R) (etaPos : 0 < eta),
649 0 < CSUCUnitTrapeze a b eta etaPos x
650 -> (a-eta < x < b+eta).
651 Proof.
652 intros. unfold CSUCUnitTrapeze in H.
653 apply (CRplus_lt_compat_r
654 (UCUnitHeaviside b (b + eta) (Rplus_pos_higher b eta etaPos) x)) in H.
655 unfold CRminus in H.
656 rewrite CRplus_0_l, CRplus_assoc, CRplus_opp_l, CRplus_0_r in H.
657 split.
658 - assert (0 < UCUnitHeaviside (a - eta) a (Rminus_pos_lower a eta etaPos) x).
659 { apply (CRle_lt_trans
660 _ (UCUnitHeaviside b (b + eta) (Rplus_pos_higher b eta etaPos) x)).
661 2: exact H. apply UCHeavisideBounded. }
662 unfold UCUnitHeaviside in H0.
663 rewrite CRmax_right in H0. apply CRlt_min in H0. destruct H0.
664 apply (CRmult_lt_compat_r (a-(a-eta))) in c0.
665 rewrite CRmult_0_l, CRmult_assoc, CRinv_l, CRmult_1_r in c0.
666 rewrite <- (CRplus_opp_r (a-eta)) in c0. apply CRplus_lt_reg_r in c0.
667 exact c0. unfold CRminus.
668 rewrite CRopp_plus_distr, <- CRplus_assoc, CRplus_opp_r, CRplus_0_l.
669 rewrite CRopp_involutive. exact etaPos.
670 intro abs. rewrite CRmax_left in H0. exact (CRlt_asym 0 0 H0 H0).
671 apply CRlt_asym, abs.
672 - assert (UCUnitHeaviside b (b+eta) (Rplus_pos_higher b eta etaPos) x < 1).
673 { apply (CRlt_le_trans _ _ _ H). apply UCHeavisideBounded. }
674 unfold UCUnitHeaviside in H0. apply CRlt_max in H0. destruct H0 as [_ H0].
675 rewrite CRmin_right in H0.
676 apply (CRmult_lt_compat_r (b+eta-b)) in H0.
677 rewrite CRmult_1_l, CRmult_assoc, CRinv_l, CRmult_1_r in H0.
678 apply CRplus_lt_reg_r in H0. exact H0. unfold CRminus.
679 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
680 exact etaPos.
681 intro abs. rewrite CRmin_left in H0. exact (CRlt_asym 1 1 H0 H0).
682 apply CRlt_asym, abs.
683 Qed.
684
685 Lemma CSUCTrapezePositive
686 : forall {R : ConstructiveReals} (a b eta x : CRcarrier R)
687 (etaPos : 0 < eta) (leab : a <= b),
688 prod (a-eta < x) (x < b+eta)
689 -> 0 < (CSUCUnitTrapeze a b eta etaPos x).
690 Proof.
691 intros. unfold CSUCUnitTrapeze, UCUnitHeaviside.
692 rewrite CRmax_right.
693 rewrite (CRmin_right
694 1 ((x - b) *
695 CRinv R (b + eta - b) (inr (CRlt_minus b (b + eta) (Rplus_pos_higher b eta etaPos))))).
696 - apply (CRle_lt_trans
697 _ (CRmax 0
698 ((x - b) *
699 CRinv R (b + eta - b) (inr (CRlt_minus b (b + eta) (Rplus_pos_higher b eta etaPos))))
700 - CRmax 0
701 ((x - b) *
702 CRinv R (b + eta - b) (inr (CRlt_minus b (b + eta) (Rplus_pos_higher b eta etaPos)))))).
703 unfold CRminus. rewrite CRplus_opp_r. apply CRle_refl.
704 apply CRplus_lt_compat_r.
705 apply CRmin_lt. apply CRmax_lub_lt. apply CRzero_lt_one.
706 2: apply CRmax_lub_lt.
707 + apply (CRmult_lt_reg_r (b+eta-b)).
708 unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
709 rewrite CRplus_opp_l, CRplus_0_l. exact etaPos.
710 rewrite CRmult_assoc, CRinv_l, CRmult_1_l, CRmult_1_r.
711 unfold CRminus. apply CRplus_lt_compat_r. apply H.
712 + apply (CRmult_lt_reg_r (a-(a-eta))).
713 unfold CRminus. rewrite CRopp_plus_distr, <- CRplus_assoc.
714 rewrite CRplus_opp_r, CRplus_0_l, CRopp_involutive. exact etaPos.
715 rewrite CRmult_assoc, CRinv_l, CRmult_0_l, CRmult_1_r.
716 rewrite <- (CRplus_opp_r (a-eta)).
717 apply CRplus_lt_compat_r. apply H.
718 + apply (CRmult_lt_reg_r (b+eta-b)).
719 unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
720 rewrite CRplus_opp_l, CRplus_0_l. exact etaPos.
721 rewrite CRmult_assoc, CRinv_l, CRmult_1_r.
722 setoid_replace (b + eta - b) with eta.
723 rewrite <- (CRmult_comm eta).
724 apply (CRmult_lt_reg_r (a-(a-eta))).
725 unfold CRminus. rewrite CRopp_plus_distr, <- CRplus_assoc.
726 rewrite CRplus_opp_r, CRplus_0_l, CRopp_involutive. exact etaPos.
727 rewrite CRmult_assoc, CRmult_assoc, CRinv_l, CRmult_1_r.
728 setoid_replace (a - (a - eta)) with eta.
729 rewrite CRmult_comm. apply CRmult_lt_compat_l. exact etaPos.
730 apply CRplus_lt_compat_l. apply CRopp_gt_lt_contravar.
731 apply (CRlt_le_trans _ a). apply (CRplus_lt_reg_r eta).
732 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l.
733 apply CRplus_lt_compat_l, etaPos. exact leab.
734 unfold CRminus. rewrite CRopp_plus_distr, <- CRplus_assoc.
735 rewrite CRplus_opp_r, CRplus_0_l, CRopp_involutive. reflexivity.
736 unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
737 rewrite CRplus_opp_l, CRplus_0_l. reflexivity.
738 - apply (CRmult_le_reg_r (b+eta-b)).
739 unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
740 rewrite CRplus_opp_l, CRplus_0_l. exact etaPos.
741 rewrite CRmult_assoc, CRinv_l, CRmult_1_l, CRmult_1_r.
742 unfold CRminus. rewrite CRplus_comm.
743 rewrite <- (CRplus_comm (-b)). apply CRplus_le_compat_l.
744 apply CRlt_asym, H.
745 - apply CRmin_glb. apply CRlt_asym, CRzero_lt_one.
746 apply (CRmult_le_reg_r (a-(a-eta))).
747 unfold CRminus. rewrite CRopp_plus_distr, <- CRplus_assoc.
748 rewrite CRplus_opp_r, CRplus_0_l, CRopp_involutive. exact etaPos.
749 rewrite CRmult_assoc, CRinv_l, CRmult_0_l, CRmult_1_r.
750 unfold CRminus.
751 rewrite <- (CRplus_opp_l (a-eta)), (CRplus_comm x).
752 apply CRplus_le_compat_l. apply CRlt_asym, H.
753 Qed.
754
755 Lemma CSUCTrapezeBounded
756 : forall {R : ConstructiveReals} (a b eta x : CRcarrier R) (etaPos : 0 < eta),
757 a <= b
758 -> (0 <= CSUCUnitTrapeze a b eta etaPos x <= 1).
759 Proof.
760 intros. unfold CSUCUnitTrapeze, UCUnitHeaviside.
761 rewrite (CRinv_morph (a - (a-eta)) eta _ (inr etaPos)).
762 rewrite (CRinv_morph (b + eta - b) eta _ (inr etaPos)).
763 destruct (CRltLinear R). destruct (s a x (b+eta)).
764 - apply (CRle_lt_trans _ (b+0)). rewrite CRplus_0_r. exact H.
765 apply CRplus_lt_compat_l. exact etaPos.
766 - (* a < x *)
767 rewrite CRmax_right, CRmin_left.
768 split.
769 + apply (CRle_trans _ (1-1)).
770 unfold CRminus. rewrite CRplus_opp_r. apply CRle_refl.
771 apply CRplus_le_compat_l. apply CRopp_ge_le_contravar.
772 apply CRmax_lub. apply CRlt_asym, CRzero_lt_one. apply CRmin_l.
773 + apply (CRle_trans _ (1-0)). apply CRplus_le_compat_l.
774 apply CRopp_ge_le_contravar. apply CRmax_l.
775 unfold CRminus. rewrite CRopp_0, CRplus_0_r. apply CRle_refl.
776 + unfold CRminus. rewrite CRopp_plus_distr, CRopp_involutive.
777 rewrite <- CRplus_assoc, CRmult_plus_distr_r, CRinv_r.
778 apply (CRle_trans _ (0+1)). rewrite CRplus_0_l. apply CRle_refl.
779 apply CRplus_le_compat_r. apply (CRle_trans _ ((x-a)*0)).
780 rewrite CRmult_0_r. apply CRle_refl. apply CRlt_asym.
781 apply CRmult_lt_compat_l.
782 rewrite <- (CRplus_opp_r a). apply CRplus_lt_compat_r, c.
783 apply CRinv_0_lt_compat. exact etaPos.
784 + apply CRmin_glb.
785 apply CRlt_asym, CRzero_lt_one.
786 apply (CRle_trans _ ((x-(a-eta))*0)).
787 rewrite CRmult_0_r. apply CRle_refl. apply CRlt_asym.
788 apply CRmult_lt_compat_l.
789 apply (CRplus_lt_reg_r (a-eta)). unfold CRminus.
790 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_0_l.
791 apply (CRlt_trans _ a). 2: apply c.
792 apply (CRplus_lt_reg_r eta). rewrite CRplus_assoc, CRplus_opp_l.
793 apply CRplus_lt_compat_l. exact etaPos.
794 apply CRinv_0_lt_compat. exact etaPos.
795 - rewrite (CRmin_right 1 ((x - b) * CRinv R eta (inr etaPos))). split.
796 + unfold CRminus. rewrite CRplus_comm.
797 apply (CRle_trans _ (-(CRmax 0 ((x - b) * CRinv R eta (inr etaPos)))
798 + CRmax 0 ((x - b)* CRinv R eta (inr etaPos)))).
799 rewrite CRplus_opp_l. apply CRle_refl.
800 apply CRplus_le_compat_l.
801 apply CRmax_lub. apply CRmax_l.
802 apply (CRle_trans
803 _ (CRmin 1 ((x + - (a + - eta)) * CRinv R eta (inr etaPos)))).
804 2: apply CRmax_r. apply CRmin_glb.
805 apply (CRmult_le_reg_r eta _ 1). exact etaPos.
806 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_1_l.
807 apply (CRplus_le_reg_r b). unfold CRminus.
808 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
809 rewrite CRplus_comm. apply CRlt_asym, c.
810 apply CRmult_le_compat_r.
811 apply CRlt_asym, CRinv_0_lt_compat. exact etaPos.
812 apply CRplus_le_compat_l. apply CRopp_ge_le_contravar.
813 apply (CRplus_le_reg_r eta).
814 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
815 apply (CRle_trans _ (b+0)). rewrite CRplus_0_r. exact H.
816 apply CRplus_le_compat_l. apply CRlt_asym, etaPos.
817 + apply (CRplus_le_reg_r (CRmax 0 ((x - b) * CRinv R eta (inr etaPos)))).
818 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
819 apply CRmax_lub. apply (CRle_trans _ (1+0)).
820 rewrite CRplus_0_r. apply CRlt_asym, CRzero_lt_one.
821 apply CRplus_le_compat_l. apply CRmax_l.
822 apply (CRle_trans _ (1+0)).
823 rewrite CRplus_0_r. apply CRmin_l.
824 apply CRplus_le_compat_l. apply CRmax_l.
825 + apply (CRmult_le_reg_r eta _ 1). exact etaPos.
826 rewrite CRmult_assoc, CRinv_l, CRmult_1_l, CRmult_1_r.
827 apply (CRplus_le_reg_r b).
828 unfold CRminus. rewrite CRplus_assoc.
829 rewrite CRplus_opp_l, CRplus_0_r.
830 rewrite CRplus_comm. apply CRlt_asym, c.
831 - unfold CRminus. rewrite CRplus_comm.
832 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
833 - unfold CRminus. rewrite CRopp_plus_distr.
834 rewrite <- CRplus_assoc, CRplus_opp_r, CRplus_0_l.
835 rewrite CRopp_involutive. reflexivity.
836 Qed.
837
838 Lemma TrapezeIncluded
839 : forall {R : ConstructiveReals} (a b c d eta mu x : CRcarrier R)
840 (etaPos : 0 < eta) (muPos : 0 < mu),
841 a - eta == c - mu
842 -> b + eta == d + mu
843 -> eta <= mu
844 -> CSUCUnitTrapeze c d mu muPos x
845 <= CSUCUnitTrapeze a b eta etaPos x.
846 Proof.
847 intros.
848 assert (CRinv R mu (inr muPos) <= CRinv R eta (inr etaPos)) as invLe.
849 { apply (CRmult_le_reg_l mu _ _ muPos). rewrite CRinv_r.
850 apply (CRmult_le_reg_r eta _ _ etaPos).
851 rewrite CRmult_1_l, CRmult_assoc, CRinv_l, CRmult_1_r. exact H1. }
852 apply CRplus_le_compat.
853 - unfold UCUnitHeaviside.
854 rewrite (CRinv_morph (a - (a-eta)) eta _ (inr etaPos)).
855 rewrite (CRinv_morph (c - (c-mu)) mu _ (inr muPos)).
856 apply CRmax_lub. apply CRmax_l. rewrite <- H.
857 destruct (CRltLinear R). destruct (s (a-eta) x a).
858 + apply (CRplus_lt_reg_r eta). unfold CRminus.
859 rewrite CRplus_assoc. apply CRplus_lt_compat_l.
860 rewrite CRplus_opp_l. exact etaPos.
861 + apply (CRle_trans _ (CRmin 1 ((x - (a - eta)) * CRinv R eta (inr etaPos)))).
862 2: apply CRmax_r. apply CRmin_glb. apply CRmin_l.
863 apply (CRle_trans _ ((x - (a - eta)) * CRinv R mu (inr muPos))).
864 apply CRmin_r. apply CRmult_le_compat_l.
865 rewrite <- (CRplus_opp_r (a-eta)). apply CRplus_le_compat_r, CRlt_asym, c0.
866 exact invLe.
867 + rewrite CRmin_right. rewrite CRmin_right.
868 apply (CRmult_le_reg_r mu _ _ muPos).
869 rewrite CRmult_assoc, CRinv_l, CRmult_1_r.
870 apply (CRle_trans
871 _ (eta * CRmax 0 ((x - (a - eta)) * CRinv R eta (inr etaPos)))).
872 rewrite <- CRmax_mult. rewrite CRmult_0_r, CRmult_comm.
873 rewrite CRmult_assoc, CRinv_l, CRmult_1_r. apply CRmax_r.
874 apply CRlt_asym, etaPos. rewrite CRmult_comm.
875 apply CRmult_le_compat_l. apply CRmax_l. exact H1.
876 apply (CRmult_le_reg_r eta _ _ etaPos).
877 rewrite CRmult_1_l, CRmult_assoc, CRinv_l, CRmult_1_r.
878 apply (CRplus_le_reg_l a). unfold CRminus.
879 rewrite CRopp_plus_distr, CRopp_involutive, <- CRplus_assoc, <- CRplus_assoc.
880 apply CRplus_le_compat_r.
881 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
882 apply CRlt_asym, c0.
883 apply (CRmult_le_reg_r mu _ _ muPos).
884 rewrite CRmult_1_l, CRmult_assoc, CRinv_l, CRmult_1_r.
885 apply (CRle_trans _ eta).
886 apply (CRplus_le_reg_l a). unfold CRminus.
887 rewrite CRopp_plus_distr, CRopp_involutive, <- CRplus_assoc, <- CRplus_assoc.
888 apply CRplus_le_compat_r.
889 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
890 apply CRlt_asym, c0. exact H1.
891 + unfold CRminus. rewrite CRopp_plus_distr, CRopp_involutive, <- CRplus_assoc.
892 rewrite CRplus_opp_r, CRplus_0_l. reflexivity.
893 + unfold CRminus. rewrite CRopp_plus_distr, CRopp_involutive, <- CRplus_assoc.
894 rewrite CRplus_opp_r, CRplus_0_l. reflexivity.
895 - apply CRopp_ge_le_contravar. unfold UCUnitHeaviside.
896 rewrite (CRinv_morph (b + eta - b) eta _ (inr etaPos)).
897 rewrite (CRinv_morph (d + mu - d) mu _ (inr muPos)).
898 apply CRmax_lub. apply CRmax_l.
899 destruct (CRltLinear R). destruct (s b x (b+eta)).
900 + apply (CRplus_lt_reg_r 0).
901 rewrite CRplus_assoc. apply CRplus_lt_compat_l.
902 rewrite CRplus_0_r. exact etaPos.
903 + apply (CRle_trans _ (CRmin 1 ((x - d) * CRinv R mu (inr muPos)))).
904 2: apply CRmax_r. apply CRmin_glb. apply CRmin_l.
905 apply (CRmult_le_reg_r mu _ _ muPos).
906 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_comm.
907 rewrite <- (CRplus_0_r 1).
908 setoid_replace ((x - b) * CRinv R eta (inr etaPos))
909 with (1 + (x - (b+eta)) * CRinv R eta (inr etaPos)).
910 rewrite <- CRmin_plus, CRmult_plus_distr_l, CRmult_1_r.
911 apply (CRplus_le_reg_l (-mu)).
912 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
913 apply (CRle_trans _ (x - (b + eta))).
914 assert (0 == CRinv R eta (inr etaPos) * 0).
915 symmetry. apply CRmult_0_r. rewrite (CRmult_comm (x - (b + eta))).
916 rewrite (CRmin_morph R 0 (CRinv R eta (inr etaPos) * 0) H2 _ _ (CReq_refl _)).
917 rewrite CRmin_mult. apply (CRle_trans _ (CRmin 0 (x - (b + eta)))).
918 2: apply CRmin_r.
919 rewrite <- CRopp_involutive, <- (CRopp_involutive (CRmin 0 (x - (b + eta)))).
920 apply CRopp_ge_le_contravar.
921 rewrite CRopp_involutive, CRopp_mult_distr_r, CRopp_mult_distr_r.
922 rewrite <- (CRmult_1_l (- CRmin 0 (x - (b + eta)))), <- CRmult_assoc.
923 rewrite <- CRmult_assoc. apply CRmult_le_compat_r.
924 rewrite <- CRopp_0. apply CRopp_ge_le_contravar.
925 apply (CRle_trans _ (-0)). apply CRmin_l. rewrite CRopp_0. apply CRle_refl.
926 rewrite CRmult_1_r. apply (CRmult_le_reg_r eta _ _ etaPos).
927 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_1_l. exact H1.
928 apply CRlt_asym, CRinv_0_lt_compat, etaPos.
929 unfold CRminus. rewrite H0, CRopp_plus_distr, (CRplus_comm (-mu)).
930 rewrite CRplus_assoc. apply CRle_refl.
931 unfold CRminus. rewrite (CRplus_comm 1), CRmult_plus_distr_r.
932 rewrite CRmult_plus_distr_r, CRopp_plus_distr, CRmult_plus_distr_r.
933 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
934 rewrite <- (CRopp_mult_distr_l eta), CRinv_r.
935 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r. reflexivity.
936 + rewrite CRmin_right. rewrite CRmin_right.
937 apply (CRle_trans _ ((x - d) * CRinv R mu (inr muPos))). 2: apply CRmax_r.
938 apply (CRplus_le_reg_r (-(1))).
939 apply (CRle_trans _ ((x - (b+eta)) * CRinv R eta (inr etaPos))).
940 unfold CRminus. do 2 rewrite CRmult_plus_distr_r.
941 rewrite CRopp_plus_distr, CRmult_plus_distr_r, <- (CRopp_mult_distr_l eta).
942 rewrite CRinv_r, <- CRplus_assoc. apply CRle_refl.
943 apply (CRle_trans _ ((x - (d+mu)) * CRinv R mu (inr muPos))).
944 rewrite <- H0. rewrite <- CRopp_involutive.
945 rewrite <- (CRopp_involutive ((x - (b + eta)) * CRinv R mu (inr muPos))).
946 apply CRopp_ge_le_contravar. do 2 rewrite CRopp_mult_distr_l.
947 apply CRmult_le_compat_l. unfold CRminus.
948 rewrite CRopp_plus_distr, CRopp_involutive, <- (CRplus_opp_l x).
949 apply CRplus_le_compat_l. apply CRlt_asym, c0. exact invLe.
950 unfold CRminus. do 2 rewrite CRmult_plus_distr_r.
951 rewrite CRopp_plus_distr, CRmult_plus_distr_r, <- (CRopp_mult_distr_l mu).
952 rewrite CRinv_r, <- CRplus_assoc. apply CRle_refl.
953 apply (CRmult_le_reg_r mu _ _ muPos).
954 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_1_l.
955 apply (CRplus_le_reg_r d). unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l.
956 rewrite CRplus_0_r, CRplus_comm, <- H0. apply CRlt_asym, c0.
957 apply (CRmult_le_reg_r eta _ _ etaPos).
958 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_1_l.
959 apply (CRplus_le_reg_r b). unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l.
960 rewrite CRplus_0_r, CRplus_comm. apply CRlt_asym, c0.
961 + unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
962 rewrite CRplus_opp_l, CRplus_0_l. reflexivity.
963 + unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
964 rewrite CRplus_opp_l, CRplus_0_l. reflexivity.
965 Qed.
966
967 Lemma Rminus_plus_one_lower : forall {R : ConstructiveReals} (a b : CRcarrier R),
968 a <= b -> (a-1) <= (b+1).
969 Proof.
970 intros. apply (CRle_trans _ a).
971 apply CRlt_asym, Rminus_pos_lower. apply CRzero_lt_one.
972 apply (CRle_trans _ b _ H).
973 apply CRlt_asym, Rplus_pos_higher. apply CRzero_lt_one.
974 Qed.
975
976 Lemma UC_x : forall {R : ConstructiveReals},
977 UniformCont (fun x:CRcarrier R => x) (fun eps _ => eps).
978 Proof.
979 split. intros. exact xPos. intros. exact H.
980 Qed.
981
982 Lemma S_INR : forall {R : ConstructiveReals} (n:nat),
983 INR (S n) == @INR R n + 1.
984 Proof.
985 intros R n. unfold INR. rewrite <- CR_of_Q_plus.
986 apply CR_of_Q_morph. rewrite Qinv_plus_distr.
987 unfold Qeq, Qnum, Qden. do 2 rewrite Z.mul_1_r.
988 fold (1 + n)%nat.
989 rewrite (Nat2Z.inj_add 1 n). rewrite Z.add_comm. reflexivity.
990 Qed.
991
992 Lemma sum_INR :
993 forall {R : ConstructiveReals} (n:nat),
994 CRsum INR n
995 == INR n * (INR (S n)) * CR_of_Q R (1#2).
996 Proof.
997 induction n.
998 - unfold CRsum, INR, Z.of_nat. rewrite CRmult_0_l, CRmult_0_l.
999 reflexivity.
1000 - transitivity (CRsum INR n + @INR R (S n)).
1001 reflexivity. rewrite IHn. clear IHn.
1002 transitivity (INR (S n) * (INR n * CR_of_Q R (1#2) + 1)).
1003 rewrite CRmult_plus_distr_l. apply CRplus_morph.
1004 rewrite <- CRmult_assoc. apply CRmult_morph. 2: reflexivity.
1005 apply CRmult_comm. rewrite CRmult_1_r. reflexivity.
1006 rewrite CRmult_assoc. apply CRmult_morph.
1007 reflexivity.
1008 apply (CRmult_eq_reg_r (CR_of_Q R 2)).
1009 left. apply CR_of_Q_pos; reflexivity.
1010 rewrite CRmult_plus_distr_r, CRmult_1_l.
1011 rewrite CRmult_assoc, <- CR_of_Q_mult.
1012 rewrite CRmult_assoc, <- (CR_of_Q_mult _ (1#2)).
1013 setoid_replace ((1 # 2) * 2)%Q with 1%Q. 2: reflexivity.
1014 do 2 rewrite CRmult_1_r. rewrite (CR_of_Q_plus R 1 1).
1015 do 2 rewrite S_INR. rewrite CRplus_assoc.
1016 reflexivity.
1017 Qed.
1018
1019 Lemma CSUCTrapeze_CSUC
1020 : forall {R : ConstructiveReals} (a b eta : CRcarrier R) (etaPos : 0 < eta),
1021 a <= b -> CSUC (CSUCUnitTrapeze a b eta etaPos)
1022 (a-eta) (b+eta) (fun eps epsPos => eps * CR_of_Q R (1#2) * eta).
1023 Proof.
1024 intros. split.
1025 - apply CSUCUnitTrapeze_cont. apply H.
1026 - intros. unfold CSUCUnitTrapeze, UCUnitHeaviside.
1027 rewrite (CRinv_morph (a - (a-eta)) eta _ (inr etaPos)).
1028 rewrite (CRinv_morph (b + eta - b) eta _ (inr etaPos)).
1029 destruct H0 as [H0|H0].
1030 + assert (x < a).
1031 { apply (CRlt_trans x (a-eta)). apply H0.
1032 apply Rminus_pos_lower. exact etaPos. }
1033 assert (x < b).
1034 { exact (CRlt_le_trans x a _ H1 H). }
1035 rewrite CRmax_left, CRmax_left.
1036 unfold CRminus. rewrite CRplus_opp_r. reflexivity.
1037 apply (CRle_trans _ _ _ (CRmin_r _ _)).
1038 apply (CRmult_le_reg_r eta). exact etaPos.
1039 rewrite CRmult_0_l, CRmult_assoc, CRinv_l, CRmult_1_r.
1040 apply (CRplus_le_reg_r b). unfold CRminus.
1041 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_l, CRplus_0_r.
1042 apply CRlt_asym, H2.
1043 apply (CRle_trans _ _ _ (CRmin_r _ _)).
1044 apply (CRmult_le_reg_r eta). exact etaPos.
1045 rewrite CRmult_0_l, CRmult_assoc, CRinv_l, CRmult_1_r.
1046 apply (CRplus_le_reg_r (a-eta)). unfold CRminus.
1047 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_l, CRplus_0_r.
1048 apply CRlt_asym, H0.
1049 + assert (b < x).
1050 { apply (CRlt_trans b (b+eta)). apply Rplus_pos_higher.
1051 exact etaPos. apply H0. }
1052 assert (a < x).
1053 { exact (CRle_lt_trans a b _ H H1). }
1054 rewrite CRmax_right, CRmax_right.
1055 rewrite CRmin_left, CRmin_left.
1056 unfold CRminus. apply CRplus_opp_r.
1057 apply (CRmult_le_reg_r eta _ _ etaPos).
1058 rewrite CRmult_1_l, CRmult_assoc, CRinv_l, CRmult_1_r.
1059 apply (CRplus_le_reg_r b). unfold CRminus.
1060 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_comm.
1061 apply CRlt_asym, H0.
1062 apply (CRmult_le_reg_r eta _ _ etaPos).
1063 rewrite CRmult_1_l, CRmult_assoc, CRinv_l, CRmult_1_r.
1064 apply (CRplus_le_reg_r (a-eta)). unfold CRminus.
1065 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_comm.
1066 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1067 apply CRlt_asym, H2.
1068 apply CRmin_glb. apply CRlt_asym, CRzero_lt_one.
1069 apply (CRmult_le_reg_r eta _ _ etaPos).
1070 rewrite CRmult_0_l, CRmult_assoc, CRinv_l, CRmult_1_r.
1071 apply (CRplus_le_reg_r b). unfold CRminus.
1072 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_0_l.
1073 apply CRlt_asym, H1.
1074 apply CRmin_glb. apply CRlt_asym, CRzero_lt_one.
1075 apply (CRmult_le_reg_r eta _ _ etaPos).
1076 rewrite CRmult_0_l, CRmult_assoc, CRinv_l, CRmult_1_r.
1077 apply (CRplus_le_reg_r (a-eta)). unfold CRminus.
1078 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_0_l.
1079 apply (CRle_trans _ a). 2: apply CRlt_asym, H2.
1080 apply (CRplus_le_reg_r eta).
1081 rewrite CRplus_assoc, CRplus_opp_l.
1082 apply CRplus_le_compat_l. apply CRlt_asym, etaPos.
1083 + unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
1084 rewrite CRplus_opp_l, CRplus_0_l. reflexivity.
1085 + unfold CRminus. rewrite CRopp_plus_distr, <- CRplus_assoc.
1086 rewrite CRplus_opp_r, CRplus_0_l, CRopp_involutive. reflexivity.
1087 Qed.
1088
1089 Definition UC_bounded {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
1090 (a b : CRcarrier R) (fMod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
1091 (fUC : UniformCont f fMod)
1092 : a <= b -> { B : CRcarrier R & forall x:CRcarrier R, a <= x -> x <= b -> CRabs _ (f x) < B }.
1093 Proof.
1094 (* Evaluate the modulus of uniform continuity for 1,
1095 then divide the segment [a,b] by this length and
1096 take the highest value of f at those points, plus 1. *)
1097 pose proof ((snd fUC) 1). intros.
1098 (* Divide the modulus by 2, because constructively there is no exact
1099 comparison of real numbers. *)
1100 pose (nat_rec (fun n => CRcarrier R) (CRabs _ (f a))
1101 (fun n x => CRmax x (CRabs _ (f (a + INR (S n) * fMod 1 (CRzero_lt_one R) * CR_of_Q R (1#2))))))
1102 as maxou.
1103 assert (forall i k : nat, le i k
1104 -> CRabs _ (f (a + INR i * fMod 1 (CRzero_lt_one R) * CR_of_Q R (1# 2)))
1105 <= (maxou k))
1106 as maxouSpec.
1107 { induction k.
1108 - intros. inversion H1. unfold INR, Z.of_nat.
1109 rewrite (UniformContProper f fMod fUC _ a).
1110 apply CRle_refl.
1111 rewrite CRmult_0_l. rewrite CRmult_0_l, CRplus_0_r. reflexivity.
1112 - intros. apply Nat.le_succ_r in H1. destruct H1.
1113 apply (CRle_trans _ (maxou k) _ (IHk H1)). apply CRmax_l.
1114 subst i. apply CRmax_r. }
1115 (* Get maximal index k of subdivision *)
1116 destruct (CRup_nat ((b - a) * CR_of_Q R 2
1117 * (CRinv R (fMod 1 (CRzero_lt_one R)) (inr ((fst fUC) 1 (CRzero_lt_one R))))))
1118 as [k kmaj].
1119 exists (maxou k + 1). intros.
1120 assert (0 < fMod 1 (CRzero_lt_one R)) as stepPos.
1121 { apply (fst fUC). }
1122 (* Find 2 columns around x *)
1123 destruct (CRfloor ((x-a) * CR_of_Q R 2 * (CRinv R (fMod 1 (CRzero_lt_one R))
1124 (inr ((fst fUC) 1 (CRzero_lt_one R))))))
1125 as [i [H4 H5]].
1126 apply (CRmult_lt_compat_r (fMod 1 (CRzero_lt_one R))) in H4.
1127 rewrite CRmult_assoc in H4. rewrite CRinv_l in H4.
1128 rewrite CRmult_1_r in H4.
1129 apply (CRmult_lt_compat_r (fMod 1 (CRzero_lt_one R))) in H5.
1130 rewrite CRmult_assoc in H5. rewrite CRinv_l in H5.
1131 rewrite CRmult_1_r in H5.
1132 2: apply (fst fUC).
1133 2: apply (fst fUC). apply CRltEpsilon.
1134 destruct (Z.le_gt_cases i 0).
1135 - (* i <= 0 *)
1136 clear H4. apply CRltForget.
1137 apply (CRlt_le_trans _ (CRabs _ (f a) + 1)).
1138 apply (CRplus_lt_reg_r (-CRabs _ (f a))).
1139 rewrite (CRplus_comm (CRabs _ (f a))), CRplus_assoc.
1140 rewrite CRplus_opp_r, CRplus_0_r.
1141 apply (CRle_lt_trans _ _ _ (CRabs_triang_inv _ _)).
1142 apply (H _ _ (CRzero_lt_one R)).
1143 rewrite CRabs_right. apply (CRmult_lt_reg_r (CR_of_Q R 2)).
1144 apply CR_of_Q_pos; reflexivity.
1145 apply (CRlt_le_trans _ _ _ H5). rewrite CRmult_comm.
1146 apply CRmult_le_compat_l. apply CRlt_asym, (fst fUC).
1147 rewrite <- (CRplus_0_l (CR_of_Q R 2)), <- CRplus_assoc.
1148 apply CRplus_le_compat. 2: apply CRle_refl.
1149 rewrite CRplus_0_r. apply CR_of_Q_le.
1150 unfold Qle,Qnum,Qden. simpl. rewrite Z.mul_1_r. exact H3.
1151 apply CRle_minus. exact H1.
1152 rewrite (UniformContProper
1153 f fMod fUC _ (a + INR 0 * fMod 1 (CRzero_lt_one R) * CR_of_Q R (1#2))).
1154 apply CRplus_le_compat. 2: apply CRle_refl.
1155 apply maxouSpec, Nat.le_0_l. unfold INR, Z.of_nat.
1156 rewrite CRmult_0_l, CRmult_0_l, CRplus_0_r. reflexivity.
1157 - (* 0 < i *)
1158 apply CRltForget.
1159 apply (CRlt_le_trans
1160 _ (CRabs _ (f (a + CR_of_Q R (i#1) * fMod 1 (CRzero_lt_one R) * CR_of_Q R (1#2))) + 1)).
1161 + apply (CRplus_lt_reg_l _
1162 (-CRabs _ (f (a + CR_of_Q R (i#1)
1163 * fMod 1 (CRzero_lt_one R) * CR_of_Q R (1#2))))).
1164 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l, CRplus_comm.
1165 apply (CRle_lt_trans _ _ _ (CRabs_triang_inv _ _)).
1166 apply (H _ _ (CRzero_lt_one R)).
1167 rewrite CRabs_right.
1168 apply (CRplus_lt_reg_r
1169 (a + CR_of_Q R (i#1) * (fMod 1 (CRzero_lt_one R) * CR_of_Q R (1#2)))).
1170 unfold CRminus.
1171 rewrite CRplus_assoc, <- CRmult_assoc, CRplus_opp_l, CRplus_0_r.
1172 rewrite CRplus_comm. apply (CRplus_lt_reg_l _ (-a)).
1173 do 2 rewrite <- CRplus_assoc. rewrite CRplus_opp_l, CRplus_0_l.
1174 rewrite CRplus_comm. apply (CRmult_lt_reg_r (CR_of_Q R 2)).
1175 apply CR_of_Q_pos; reflexivity.
1176 apply (CRlt_le_trans _ _ _ H5).
1177 do 2 rewrite CRmult_plus_distr_r. apply CRplus_le_compat.
1178 2: rewrite CRmult_comm; apply CRle_refl.
1179 do 2 rewrite CRmult_assoc. rewrite <- CR_of_Q_mult.
1180 setoid_replace ((1 # 2) * 2)%Q with 1%Q.
1181 rewrite CRmult_1_r, CRmult_comm. apply CRle_refl. reflexivity.
1182 unfold CRminus. rewrite CRopp_plus_distr, <- CRplus_assoc.
1183 apply (CRle_minus (CR_of_Q R (i # 1) * fMod 1 (CRzero_lt_one R) * CR_of_Q R (1 # 2))
1184 (x - a)).
1185 apply CRlt_asym, (CRmult_lt_reg_r (CR_of_Q R 2)).
1186 apply CR_of_Q_pos; reflexivity.
1187 do 2 rewrite CRmult_assoc. rewrite <- CR_of_Q_mult.
1188 setoid_replace ((1 # 2) * 2)%Q with 1%Q.
1189 rewrite CRmult_1_r. exact H4. reflexivity.
1190 + clear H5. apply CRplus_le_compat. 2: apply CRle_refl.
1191 unfold INR in maxouSpec.
1192 destruct i. exfalso; inversion H3. 2: exfalso; inversion H3.
1193 specialize (maxouSpec (Pos.to_nat p) k).
1194 rewrite positive_nat_Z in maxouSpec. apply maxouSpec.
1195 apply (CRmult_lt_compat_r (fMod 1 (CRzero_lt_one R))) in kmaj.
1196 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in kmaj.
1197 2: apply (fst fUC).
1198 assert ((x-a)*CR_of_Q R 2 <= (b-a)*CR_of_Q R 2).
1199 { apply CRmult_le_compat_r.
1200 apply CR_of_Q_le; discriminate.
1201 apply CRplus_le_compat. exact H2. apply CRle_refl. }
1202 apply (CRlt_le_trans _ _ _ H4) in H5. clear H4.
1203 apply (CRlt_trans _ _ _ H5) in kmaj. clear H5.
1204 apply CRmult_lt_reg_r in kmaj. 2: apply (fst fUC).
1205 destruct (Q_dec (Z.pos p # 1) (Z.of_nat k # 1)). destruct s.
1206 unfold Qlt, Qnum, Qden in q.
1207 apply le_S_n. apply (Nat.le_trans _ k).
1208 apply Nat2Z.inj_lt. rewrite positive_nat_Z.
1209 do 2 rewrite Z.mul_1_r in q. exact q.
1210 apply le_S, Nat.le_refl. exfalso. apply (CR_of_Q_lt R) in q.
1211 exact (CRlt_asym _ _ q kmaj). exfalso.
1212 rewrite q in kmaj. exact (CRlt_asym _ _ kmaj kmaj).
1213 Qed.
1214
1215 Definition CSUC_bounded {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
1216 (a b : CRcarrier R) (fMod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
1217 (fCSUC : CSUC f a b fMod)
1218 : a <= b -> { B : CRcarrier R & forall x:CRcarrier R, CRabs _ (f x) < B }.
1219 Proof.
1220 intros. destruct fCSUC as [H0 H1].
1221 destruct (UC_bounded f (a-1) (b+1) fMod H0) as [B Bmaj].
1222 apply Rminus_plus_one_lower. apply H. exists B.
1223 assert (0 < B) as Bpos.
1224 { specialize (Bmaj a). apply (CRle_lt_trans _ (CRabs _ (f a))).
1225 apply CRabs_pos. apply Bmaj.
1226 apply CRlt_asym, Rminus_pos_lower. apply CRzero_lt_one.
1227 apply (CRle_trans _ b _ H).
1228 apply CRlt_asym, Rplus_pos_higher. apply CRzero_lt_one. }
1229 intros. destruct (CRltLinear R).
1230 destruct (s (a-1) x a (Rminus_pos_lower a 1 (CRzero_lt_one R))).
1231 - destruct (s b x (b+1) (Rplus_pos_higher b 1 (CRzero_lt_one R))).
1232 rewrite H1. rewrite CRabs_right. apply Bpos.
1233 apply CRle_refl.
1234 right. exact c0. apply Bmaj. apply CRlt_asym, c.
1235 apply CRlt_asym, c0.
1236 - rewrite H1. rewrite CRabs_right. apply Bpos.
1237 apply CRle_refl. left. exact c.
1238 Qed.
1239
1240 (* Used to zoom in subdomains in the proof of Icontinuous below *)
1241 Lemma CSUC_func_mult_stable
1242 : forall {R : ConstructiveReals} (f g : CRcarrier R -> CRcarrier R) (a b : CRcarrier R)
1243 (modF modG : forall x:CRcarrier R, 0 < x -> CRcarrier R),
1244 CSUC f a b modF
1245 -> a <= b
1246 -> UniformCont g modG
1247 -> { modFG : forall x:CRcarrier R, 0 < x -> CRcarrier R
1248 & CSUC (fun x => f x * g x) a b modFG }.
1249 Proof.
1250 intros.
1251 destruct (CSUC_bounded f a b modF H H0)
1252 as [Bf majf].
1253 destruct H. assert (0 < Bf) as Bfpos.
1254 { specialize (majf a). apply (CRle_lt_trans _ (CRabs _ (f a))).
1255 apply CRabs_pos. apply majf. }
1256 destruct (UC_bounded g (a-1) (b+1) modG H1 (Rminus_plus_one_lower a b H0))
1257 as [Bg majg].
1258 assert (0 < Bg) as Bgpos.
1259 { specialize (majg a). apply (CRle_lt_trans _ (CRabs _ (g a))).
1260 apply CRabs_pos. apply majg.
1261 apply CRlt_asym, Rminus_pos_lower. apply CRzero_lt_one.
1262 apply (CRle_trans _ b _ H0).
1263 apply CRlt_asym, Rplus_pos_higher. apply CRzero_lt_one. }
1264 assert (forall eps:CRcarrier R, 0 < eps -> 0 < eps * CR_of_Q R (1#2) * (CRinv R Bg (inr Bgpos))).
1265 { intros. apply CRmult_lt_0_compat.
1266 apply CRmult_lt_0_compat. exact H.
1267 apply CR_of_Q_pos; reflexivity.
1268 apply CRinv_0_lt_compat, Bgpos. }
1269 assert (forall eps:CRcarrier R, 0 < eps -> 0 < eps * CR_of_Q R (1#2) * (CRinv R Bf (inr Bfpos))).
1270 { intros. apply CRmult_lt_0_compat.
1271 apply CRmult_lt_0_compat. exact H2.
1272 apply CR_of_Q_pos; reflexivity.
1273 apply CRinv_0_lt_compat, Bfpos. }
1274 exists (fun eps epsPos => CRmin (modF (eps * CR_of_Q R (1#2) * CRinv R Bg (inr Bgpos))
1275 (H eps epsPos))
1276 (modG (eps * CR_of_Q R (1#2) * CRinv R Bf (inr Bfpos))
1277 (H2 eps epsPos))).
1278 split. split.
1279 - intros. apply CRmin_lt. apply (fst u). apply (fst H1).
1280 - intros. destruct (CRltLinear R).
1281 destruct (s (a-1) x a (Rminus_pos_lower a 1 (CRzero_lt_one R))).
1282 + destruct (s b x (b+1) (Rplus_pos_higher b 1 (CRzero_lt_one R))).
1283 (* x is out to the right. *)
1284 destruct (s (a-1) y a (Rminus_pos_lower a 1 (CRzero_lt_one R))).
1285 destruct (s b y (b+1) (Rplus_pos_higher b 1 (CRzero_lt_one R))).
1286 rewrite c,c. do 2 rewrite CRmult_0_l.
1287 unfold CRminus. rewrite CRplus_0_l. rewrite CRopp_0.
1288 rewrite CRabs_right. apply epsPos.
1289 apply CRle_refl. right. exact c3. right. exact c1.
1290 (* y is inside *)
1291 specialize (c x (inr c1)).
1292 setoid_replace (f x * g x - f y * g y) with ((f x - f y) * g y).
1293 2: rewrite c.
1294 rewrite CRabs_mult. rewrite CRmult_comm.
1295 apply (CRle_lt_trans _ (Bg * CRabs _ (f x - f y))).
1296 apply CRmult_le_compat_r. apply CRabs_pos.
1297 apply CRlt_asym, majg.
1298 apply CRlt_asym, c2. apply CRlt_asym, c3.
1299 apply (CRlt_le_trans _ (Bg * (eps * CR_of_Q R (1#2) * CRinv R Bg (inr Bgpos)))).
1300 apply CRmult_lt_compat_l. apply Bgpos. destruct u.
1301 apply (c5 _ _ _ (H _ epsPos)).
1302 apply (CRlt_le_trans _ _ _ H3). apply CRmin_l.
1303 rewrite CRmult_comm, CRmult_assoc, CRinv_l, CRmult_1_r.
1304 rewrite <- (CRmult_1_r eps), CRmult_assoc.
1305 apply CRmult_le_compat_l. apply CRlt_asym, epsPos.
1306 rewrite CRmult_1_l. apply CR_of_Q_le; discriminate.
1307
1308 unfold CRminus. rewrite CRmult_0_l, CRplus_0_l, CRplus_0_l.
1309 apply CRopp_mult_distr_l.
1310 (* y < a *)
1311 rewrite c, c.
1312 do 2 rewrite CRmult_0_l.
1313 unfold CRminus. rewrite CRplus_0_l. rewrite CRopp_0.
1314 rewrite CRabs_right. apply epsPos.
1315 apply CRle_refl. left. exact c2. right. exact c1.
1316
1317 (* x is inside *)
1318 setoid_replace (f x * g x - f y * g y)
1319 with (g x * (f x - f y) + f y *(g x - g y)).
1320 apply (CRle_lt_trans _ _ _ (CRabs_triang _ _)).
1321 setoid_replace eps
1322 with (eps*CR_of_Q R (1#2) + eps*CR_of_Q R (1#2)).
1323 apply CRplus_le_lt_compat. apply CRlt_asym.
1324 * (* delta f *) rewrite CRabs_mult.
1325 apply (CRle_lt_trans _ (Bg * CRabs _ (f x - f y))).
1326 apply CRmult_le_compat_r. apply CRabs_pos.
1327 apply CRlt_asym, majg.
1328 apply CRlt_asym, c0. apply CRlt_asym, c1.
1329 apply (CRlt_le_trans
1330 _ (Bg * (eps * CR_of_Q R (1#2) * CRinv R Bg (inr Bgpos)))).
1331 apply CRmult_lt_compat_l. apply Bgpos. destruct u.
1332 apply (c3 _ _ _ (H _ epsPos)).
1333 apply (CRlt_le_trans _ _ _ H3). apply CRmin_l.
1334 rewrite CRmult_comm, CRmult_assoc, CRinv_l.
1335 rewrite CRmult_1_r. apply CRle_refl.
1336 * (* delta g *) rewrite CRabs_mult.
1337 apply (CRle_lt_trans _ (Bf * CRabs _ (g x - g y))).
1338 apply CRmult_le_compat_r. apply CRabs_pos.
1339 apply CRlt_asym, majf.
1340 apply (CRlt_le_trans
1341 _ (Bf * (eps *CR_of_Q R (1#2) * CRinv R Bf (inr Bfpos)))).
1342 apply CRmult_lt_compat_l. apply Bfpos. destruct H1.
1343 apply (c3 _ _ _ (H2 _ epsPos)).
1344 apply (CRlt_le_trans _ _ _ H3). apply CRmin_r.
1345 rewrite CRmult_comm, CRmult_assoc, CRinv_l.
1346 rewrite CRmult_1_r. apply CRle_refl.
1347 * rewrite <- CRmult_plus_distr_l, <- CR_of_Q_plus.
1348 setoid_replace ((1#2) + (1#2))%Q with 1%Q.
1349 rewrite CRmult_1_r. reflexivity. reflexivity.
1350 * unfold CRminus. do 2 rewrite CRmult_plus_distr_l.
1351 rewrite CRplus_assoc. apply CRplus_morph.
1352 apply CRmult_comm. rewrite <- CRplus_assoc, (CRmult_comm (g x)).
1353 rewrite <- CRmult_plus_distr_r, CRplus_opp_l, CRmult_0_l.
1354 rewrite CRplus_0_l, CRopp_mult_distr_r. reflexivity.
1355 + (* x is out to the left. *)
1356 destruct (s (a-1) y a (Rminus_pos_lower a 1 (CRzero_lt_one R))).
1357 destruct (s b y (b+1) (Rplus_pos_higher b 1 (CRzero_lt_one R))).
1358 * rewrite c,c. do 2 rewrite CRmult_0_l.
1359 unfold CRminus. rewrite CRplus_0_l. rewrite CRopp_0.
1360 rewrite CRabs_right. apply epsPos.
1361 apply CRle_refl. right. exact c2. left. exact c0.
1362 * (* y is inside *)
1363 specialize (c x (inl c0)).
1364 setoid_replace (f x * g x - f y * g y)
1365 with ((f x - f y) * g y).
1366 2: rewrite c.
1367 rewrite CRabs_mult. rewrite CRmult_comm.
1368 apply (CRle_lt_trans _ (Bg * CRabs _ (f x - f y))).
1369 apply CRmult_le_compat_r. apply CRabs_pos.
1370 apply CRlt_asym, majg.
1371 apply CRlt_asym, c1. apply CRlt_asym, c2.
1372 apply (CRlt_le_trans
1373 _ (Bg * (eps * CR_of_Q R (1#2) * CRinv R Bg (inr Bgpos)))).
1374 apply CRmult_lt_compat_l. apply Bgpos. destruct u.
1375 apply (c4 _ _ _ (H _ epsPos)).
1376 apply (CRlt_le_trans _ _ _ H3). apply CRmin_l.
1377 rewrite CRmult_comm, CRmult_assoc, CRinv_l.
1378 rewrite CRmult_1_r.
1379 rewrite <- (CRmult_1_r eps), CRmult_assoc.
1380 apply CRmult_le_compat_l. apply CRlt_asym, epsPos.
1381 rewrite CRmult_1_l. apply CR_of_Q_le; discriminate.
1382 rewrite CRmult_0_l. unfold CRminus. do 2 rewrite CRplus_0_l.
1383 rewrite CRopp_mult_distr_l. reflexivity.
1384 * rewrite c,c. do 2 rewrite CRmult_0_l.
1385 unfold CRminus. rewrite CRplus_0_l. rewrite CRopp_0.
1386 rewrite CRabs_right. apply epsPos.
1387 apply CRle_refl. left. exact c1. left. exact c0.
1388 - intros. destruct H3. rewrite c, CRmult_0_l. reflexivity.
1389 left. exact c0. rewrite c, CRmult_0_l. reflexivity.
1390 right. exact c0.
1391 Qed.
1392
1393 Lemma Rplus_lt_epsilon : forall {R : ConstructiveReals} (a b c d : CRcarrier R),
1394 (a + b) < (c + d) -> sum (a < c) (b < d).
1395 Proof.
1396 intros. destruct (CRltLinear R). destruct (s (a+b) (a+d) (c+d) H).
1397 - right. apply CRplus_lt_reg_l in c0. exact c0.
1398 - left. apply CRplus_lt_reg_r in c0. exact c0.
1399 Qed.
1400
1401 Lemma EnlargePointMajorationZero
1402 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R) (x : CRcarrier R)
1403 (modF : forall x:CRcarrier R, 0 < x -> CRcarrier R),
1404 UniformCont f modF
1405 -> 0 < f x
1406 -> { eta : CRcarrier R & prod (0 < eta) (forall y:CRcarrier R, CRabs _ (x-y) < eta -> 0 < (f y)) }.
1407 Proof.
1408 intros. destruct H as [H H1]. exists (modF (f x) H0).
1409 split.
1410 - apply H.
1411 - intros. specialize (H1 (f x) x y H0 H2).
1412 apply (CRle_lt_trans _ _ _ (CRle_abs _)) in H1.
1413 apply (CRplus_lt_reg_l _ (f x - f y)).
1414 rewrite CRplus_0_r. unfold CRminus.
1415 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1416 exact H1.
1417 Qed.
1418
1419 Lemma EnlargePointMajoration
1420 : forall {R : ConstructiveReals} (f g : CRcarrier R -> CRcarrier R) (x : CRcarrier R)
1421 (modF modG : forall x:CRcarrier R, 0 < x -> CRcarrier R),
1422 UniformCont f modF
1423 -> UniformCont g modG
1424 -> f x < g x
1425 -> { eta : CRcarrier R & prod (0 < eta) (forall y:CRcarrier R, CRabs _ (x-y) < eta -> f y < g y) }.
1426 Proof.
1427 intros.
1428 pose proof (UC_scale f modF (-(1)) H).
1429 pose proof (UC_plus (fun x => -(1)*f x) g _ modG H2 H0).
1430 destruct (EnlargePointMajorationZero (fun t => -(1)*f t + g t) x _ H3).
1431 rewrite <- CRopp_mult_distr_l, CRopp_mult_distr_r. rewrite CRmult_1_l.
1432 apply (CRplus_lt_reg_l _ (f x)).
1433 rewrite <- CRplus_assoc, CRplus_opp_r.
1434 rewrite CRplus_0_l, CRplus_0_r. exact H1.
1435 exists x0. destruct p. split. exact c. intros.
1436 specialize (c0 y H4). apply (CRplus_lt_compat_l _ (f y)) in c0.
1437 rewrite CRplus_0_r in c0.
1438 setoid_replace (g y) with (f y + (- (1) * f y + g y)).
1439 exact c0. rewrite <- CRopp_mult_distr_l, CRmult_1_l.
1440 rewrite <- CRplus_assoc, CRplus_opp_r. rewrite CRplus_0_l. reflexivity.
1441 Qed.