Debian Codegraph @

reals/stdlib/ConstructiveCauchyIntegral.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 Cauchy integral of uniformly continuous functions R -> R.
15 It is the simplest integration theory, and the one used in
16 the proof of the Picard-Lindelhöf theorem.
17
18 The Cauchy integral approximates uniformly continuous functions
19 by histograms, which widths tend to 0. In other words,
20 it is the proof that sequences of rectangles integrate continuous
21 functions.
22 *)
23
24 From Coq Require Import List Permutation Orders Sorted Mergesort.
25 From Coq Require Import ZArith QArith Qpower.
26 From Coq Require Import ConstructiveReals.
27 From Coq Require Import ConstructiveAbs.
28 From Coq Require Import ConstructiveMinMax.
29 From Coq Require Import ConstructiveSum.
30 From Coq Require Import ConstructiveLimits.
31 From Coq Require Import ConstructiveRcomplete.
32 Require Import ConstructiveDiagonal.
33 Require Import ConstructiveUniformCont.
34
35 Local Open Scope ConstructiveReals.
36
37
38 (* Elementary theory of integration for the uniformly continuous
39 functions. To integrate discontinuous functions, the full
40 constructive measure theory will be developped later. *)
41
42 Record IntervalPartition {R : ConstructiveReals} {a b : CRcarrier R} : Set :=
43 {
44 ipt_seq : nat -> CRcarrier R;
45 ipt_last : nat;
46 ipt_head : a == ipt_seq 0;
47 ipt_lastB : b == ipt_seq (S ipt_last);
48 ipt_ordered : forall n:nat, le n ipt_last -> ipt_seq n <= ipt_seq (S n);
49 }.
50
51 Lemma ipt_ordered_transit : forall {R : ConstructiveReals} (a b : CRcarrier R)
52 (P : @IntervalPartition R a b) (n p : nat),
53 le n p -> le p (S (ipt_last P)) -> ipt_seq P n <= ipt_seq P p.
54 Proof.
55 induction p.
56 - intros. inversion H. apply CRle_refl.
57 - intros. apply Nat.le_succ_r in H. destruct H.
58 + apply (CRle_trans _ (ipt_seq P p)). apply (IHp H).
59 apply (Nat.le_trans _ (ipt_last P)). apply le_S_n. exact H0.
60 apply le_S, Nat.le_refl. apply P. apply le_S_n. exact H0.
61 + subst n. apply CRle_refl.
62 Qed.
63
64 Fixpoint PartitionMesh {R : ConstructiveReals}
65 (points : nat -> CRcarrier R) (len : nat) : CRcarrier R
66 := match len with
67 | O => 0
68 | S l => CRmax (points len - points l) (PartitionMesh points l)
69 end.
70
71 Lemma PartitionMesh_ext : forall {R : ConstructiveReals}
72 (un vn : nat -> CRcarrier R) (len : nat),
73 (forall n:nat, le n len -> un n == vn n)
74 -> PartitionMesh un len == PartitionMesh vn len.
75 Proof.
76 induction len.
77 - intros. reflexivity.
78 - intros. simpl.
79 rewrite IHlen. rewrite (H (S len)), (H len). reflexivity.
80 apply le_S, Nat.le_refl. apply Nat.le_refl.
81 intros. apply H. apply le_S, H0.
82 Qed.
83
84 Lemma PartitionMesh_nonneg
85 : forall {R : ConstructiveReals} (xn : nat -> CRcarrier R) (n : nat),
86 0 <= PartitionMesh xn n.
87 Proof.
88 induction n. apply CRle_refl. simpl.
89 apply (CRle_trans _ _ _ IHn), CRmax_r.
90 Qed.
91
92 Lemma AllIntervalsSmallerThanMesh
93 : forall {R : ConstructiveReals} (a b : CRcarrier R)
94 (P : @IntervalPartition R a b) (n : nat),
95 le n (ipt_last P)
96 -> ipt_seq P (S n) - ipt_seq P n
97 <= PartitionMesh (ipt_seq P) (S (ipt_last P)).
98 Proof.
99 intros. destruct P; unfold ipt_seq, ipt_last; simpl in H.
100 clear ipt_lastB0 b.
101 generalize dependent ipt_last0. induction ipt_last0.
102 - intros. inversion H. apply CRmax_l.
103 - intros.
104 assert (forall n : nat, le n ipt_last0 -> (ipt_seq0 n <= ipt_seq0 (S n))).
105 { intros. apply ipt_ordered0. apply (Nat.le_trans _ ipt_last0 _ H0).
106 apply le_S, Nat.le_refl. }
107 specialize (IHipt_last0 H0). apply Nat.le_succ_r in H.
108 destruct H.
109 + specialize (IHipt_last0 H).
110 apply (CRle_trans _ _ _ IHipt_last0). apply CRmax_r.
111 + rewrite <- H. apply CRmax_l.
112 Qed.
113
114 Definition IntegralFiniteSum {R : ConstructiveReals}
115 (f : CRcarrier R -> CRcarrier R)
116 (x partition : nat -> CRcarrier R) (last : nat) : CRcarrier R
117 := CRsum (fun n:nat => f (x n) * (partition (S n) - partition n)) last.
118
119 Definition WeavedLists {R : ConstructiveReals}
120 (x partition : nat -> CRcarrier R) (last : nat) : Prop
121 := forall n:nat, le n last -> (partition n <= x n /\ x n <= partition (S n)).
122
123 Definition IntervalPartitionRefinement {R : ConstructiveReals}
124 (a b : CRcarrier R)
125 (small big : @IntervalPartition R a b) (subseq : nat -> nat) : Prop
126 := (forall n:nat, le n (S (ipt_last small))
127 -> ipt_seq big (subseq n) == ipt_seq small n)
128 /\ (forall n p:nat, n < p -> p <= S (ipt_last small) -> subseq n < subseq p)%nat
129 /\ (forall n:nat, n <= S (ipt_last small) -> subseq n <= S (ipt_last big))%nat.
130
131 Lemma in_refinement_packet
132 : forall {R : ConstructiveReals} (a b : CRcarrier R) (n i : nat)
133 (x y : nat -> CRcarrier R)
134 (P Q : @IntervalPartition R a b)
135 (subseq : nat -> nat),
136 WeavedLists x (ipt_seq P) (ipt_last P)
137 -> WeavedLists y (ipt_seq Q) (ipt_last Q)
138 -> IntervalPartitionRefinement _ _ P Q subseq
139 -> le n (ipt_last P)
140 -> le (subseq n) i
141 -> lt i (subseq (S n)) (* i = S n can overflow in the last packet *)
142 -> CRabs _ (x n - y i)
143 <= PartitionMesh (ipt_seq P) (S (ipt_last P)).
144 Proof.
145 intros.
146 assert (ipt_seq P n <= y i /\ y i <= ipt_seq P (S n)).
147 { specialize (H0 i). split.
148 apply (CRle_trans _ (ipt_seq Q i)).
149 apply (CRle_trans _ (ipt_seq Q (subseq n))).
150 destruct H1. rewrite H1. apply CRle_refl.
151 apply (Nat.le_trans _ _ _ H2). apply le_S, Nat.le_refl.
152 apply ipt_ordered_transit. exact H3.
153 destruct H1. apply (Nat.le_trans _ (subseq (S n))).
154 apply (Nat.le_trans _ (S i)). apply le_S, Nat.le_refl. exact H4.
155 apply H5. apply le_n_S. exact H2.
156 apply H0. destruct H1.
157 apply le_S_n. apply (Nat.le_trans _ _ _ H4).
158 apply H5, le_n_S, H2.
159 apply (CRle_trans _ (ipt_seq Q (S i))). apply H0.
160 apply le_S_n. apply (Nat.le_trans _ _ _ H4). destruct H1.
161 apply H5, le_n_S, H2.
162 destruct H1.
163 apply (CRle_trans _ (ipt_seq Q (subseq (S n)))).
164 apply ipt_ordered_transit. exact H4.
165 apply H5, le_n_S, H2.
166 rewrite H1. apply CRle_refl. apply le_n_S, H2.
167 }
168 apply (CRle_trans _ (ipt_seq P (S n) - ipt_seq P n)).
169 apply Rsmaller_interval. apply H5. apply H5.
170 apply H. exact H2. apply H. exact H2.
171 apply AllIntervalsSmallerThanMesh. exact H2.
172 Qed.
173
174 Lemma partition_before_start
175 : forall {R : ConstructiveReals} (a b : CRcarrier R)
176 (P : @IntervalPartition R a b) (n : nat),
177 le n (S (ipt_last P))
178 -> ipt_seq P n == a -> (forall p:nat, le p n -> ipt_seq P p == a).
179 Proof.
180 intros. pose proof (ipt_ordered_transit a b P).
181 destruct P; unfold ipt_seq; simpl in H,H0,H2. split.
182 - fold (a <= ipt_seq0 p). rewrite ipt_head0. apply H2. apply Nat.le_0_l.
183 apply (Nat.le_trans _ _ _ H1). exact H.
184 - intro abs. rewrite <- H0 in abs. apply (H2 p n).
185 exact H1. exact H. exact abs.
186 Qed.
187
188 Lemma partition_after_end
189 : forall {R : ConstructiveReals} (a b : CRcarrier R)
190 (P : @IntervalPartition R a b) (n : nat),
191 ipt_seq P n == b
192 -> (forall p:nat, le n p -> le p (S (ipt_last P)) -> ipt_seq P p == b).
193 Proof.
194 intros. pose proof (ipt_ordered_transit a b P).
195 destruct P; unfold ipt_seq; simpl in H,H1,H2. split.
196 - fold (b <= ipt_seq0 p). rewrite <- H. apply H2. exact H0. exact H1.
197 - fold (ipt_seq0 p <= b).
198 rewrite ipt_lastB0. apply H2. exact H1. apply Nat.le_refl.
199 Qed.
200
201 (* Sum on the refined partition, either grouped or not. *)
202 Lemma partition_sum_by_packets
203 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
204 (a b : CRcarrier R)
205 (y : nat -> CRcarrier R)
206 (P Q : @IntervalPartition R a b)
207 (subseq : nat -> nat),
208 IntervalPartitionRefinement _ _ P Q subseq
209 -> CRsum
210 (fun n : nat =>
211 CRsum
212 (fun i : nat =>
213 (f (y (i + subseq n)%nat) *
214 (ipt_seq Q (S i + subseq n) - ipt_seq Q (i + subseq n))))
215 (pred (subseq (S n) - subseq n))) (ipt_last P)
216 == CRsum (fun n : nat => (f (y n) * (ipt_seq Q (S n) - ipt_seq Q n)))
217 (ipt_last Q).
218 Proof.
219 intros. destruct H, H0.
220 (* Get rid of the last points equal to b *)
221 transitivity (CRsum (fun n : nat => (f (y n) * (ipt_seq Q (S n) - ipt_seq Q n)))
222 (pred (subseq (S (ipt_last P))))).
223 (* Get rid of the first points equal to a *)
224 pose (fun n:nat => match n with O => O | S p => subseq n end) as shiftSubseq.
225 transitivity ( CRsum
226 (fun n0 : nat =>
227 CRsum
228 (fun i : nat =>
229 (f (y (i + shiftSubseq n0)%nat) *
230 (ipt_seq Q (S i + shiftSubseq n0) - ipt_seq Q (i + shiftSubseq n0))))
231 (pred (shiftSubseq (S n0) - shiftSubseq n0))) (ipt_last P)).
232 - apply CRsum_eq. intros. destruct i.
233 2: apply CRsum_eq; reflexivity. unfold shiftSubseq.
234 destruct (Nat.le_exists_sub (S (subseq O)) (subseq 1%nat)) as [p [peq _]].
235 apply H0. auto. apply le_n_S, Nat.le_0_l.
236 rewrite Nat.sub_0_r. rewrite peq.
237 rewrite Nat.add_succ_r.
238 replace (S (p + subseq 0%nat) - subseq 0)%nat with (S p).
239 simpl. destruct (subseq O) eqn:des. rewrite Nat.add_0_r.
240 apply CRsum_eq; reflexivity. rewrite <- (Nat.add_comm (S n)).
241 rewrite sum_assoc. symmetry.
242 rewrite <- (CRplus_0_l
243 (CRsum
244 (fun i : nat =>
245 f (y (i + S n)%nat) * (ipt_seq Q (S (i + S n)) - ipt_seq Q (i + S n))) p)).
246 apply CRplus_morph.
247 rewrite (CRsum_eq _ (fun _ => 0 * 0)).
248 rewrite sum_scale, CRmult_0_r. reflexivity.
249 intros. rewrite CRmult_0_l. rewrite Nat.add_0_r.
250 setoid_replace (ipt_seq Q (S i)) with a. setoid_replace (ipt_seq Q i) with a.
251 unfold CRminus. rewrite CRplus_opp_r, CRmult_0_r.
252 reflexivity. symmetry. rewrite (partition_before_start _ _ _ (subseq O)).
253 reflexivity.
254 apply H1, Nat.le_0_l. rewrite H. symmetry. apply P.
255 apply Nat.le_0_l. rewrite des. apply (Nat.le_trans _ _ _ H3).
256 apply le_S, Nat.le_refl.
257 rewrite (partition_before_start _ _ _ (subseq O)). reflexivity.
258 apply H1, Nat.le_0_l. rewrite H. symmetry. apply P.
259 apply Nat.le_0_l. rewrite des. apply le_n_S. exact H3.
260 apply CRsum_eq. intros. rewrite Nat.add_0_r, Nat.add_comm. reflexivity.
261 rewrite Nat.sub_succ_l. apply f_equal.
262 rewrite Nat.add_sub. reflexivity.
263 rewrite <- (Nat.add_0_l (subseq O)). rewrite Nat.add_assoc.
264 apply Nat.add_le_mono_r. apply Nat.le_0_l.
265 - replace (pred (subseq (S (ipt_last P))))
266 with (pred (shiftSubseq (S (ipt_last P)))).
267 apply (sum_by_packets (fun n : nat => (f (y n) * (ipt_seq Q (S n) - ipt_seq Q n)))).
268 intros. unfold shiftSubseq. destruct k. apply (Nat.le_lt_trans _ (subseq O)).
269 apply Nat.le_0_l. apply H0. auto. apply le_n_S. exact H2.
270 apply H0. apply Nat.le_refl. apply le_n_S. exact H2. reflexivity.
271 reflexivity.
272 - destruct (Nat.le_exists_sub (subseq (S (ipt_last P)))
273 (S (ipt_last Q))) as [p [peq _]].
274 apply H1. apply Nat.le_refl.
275 destruct p.
276 replace (Init.Nat.pred (subseq (S (ipt_last P))))
277 with (ipt_last Q). reflexivity.
278 simpl in peq.
279 rewrite <- peq. reflexivity.
280 inversion peq. clear peq.
281 assert (subseq (S (ipt_last P)) <> 0%nat).
282 { intro abs. specialize (H0 (ipt_last P) (S (ipt_last P))
283 (Nat.le_refl _) (Nat.le_refl _)).
284 rewrite abs in H0. inversion H0. }
285 pose proof (Nat.succ_pred (subseq (S (ipt_last P))) H2).
286 replace (ipt_last Q) with
287 (S (pred (subseq (S (ipt_last P)))) + p)%nat.
288 rewrite sum_assoc. symmetry.
289 rewrite <- (CRplus_0_r
290 (CRsum (fun n : nat => f (y n) * (ipt_seq Q (S n) - ipt_seq Q n))
291 (Init.Nat.pred (subseq (S (ipt_last P)))))).
292 apply CRplus_morph. rewrite CRplus_0_r. reflexivity.
293 rewrite (CRsum_eq _ (fun _ => 0 * 0)).
294 rewrite sum_scale, CRmult_0_r. reflexivity.
295 intros. rewrite CRmult_0_l. rewrite H4.
296 setoid_replace (ipt_seq Q (S (subseq (S (ipt_last P)) + i))) with b.
297 setoid_replace (ipt_seq Q (subseq (S (ipt_last P)) + i)) with b.
298 unfold CRminus. rewrite CRplus_opp_r, CRmult_0_r.
299 reflexivity.
300 rewrite (partition_after_end _ _ _ (subseq (S (ipt_last P)))).
301 reflexivity. rewrite H. symmetry. apply P. apply Nat.le_refl.
302 rewrite <- (Nat.add_0_r (subseq (S (ipt_last P)))).
303 rewrite <- Nat.add_assoc. apply Nat.add_le_mono_l, Nat.le_0_l.
304 apply (Nat.le_trans _ (subseq (S (ipt_last P)) + p)).
305 apply Nat.add_le_mono_l. exact H5. rewrite Nat.add_comm, H3.
306 apply le_S, Nat.le_refl.
307 rewrite (partition_after_end _ _ _ (subseq (S (ipt_last P)))).
308 reflexivity. rewrite H. symmetry. apply P. apply Nat.le_refl.
309 apply (Nat.le_trans _ (S (subseq (S (ipt_last P))))).
310 apply le_S, Nat.le_refl. apply le_n_S.
311 rewrite <- (Nat.add_0_r (subseq (S (ipt_last P)))).
312 rewrite <- Nat.add_assoc. apply Nat.add_le_mono_l, Nat.le_0_l.
313 apply le_n_S. apply (Nat.le_trans _ (subseq (S (ipt_last P)) + p)).
314 apply Nat.add_le_mono_l. exact H5. rewrite Nat.add_comm, H3.
315 apply Nat.le_refl. rewrite H4, H3. rewrite Nat.add_comm. reflexivity.
316 Qed.
317
318 Lemma UC_refine_integral
319 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
320 (a b eps : CRcarrier R)
321 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
322 (x y : nat -> CRcarrier R)
323 (P Q : @IntervalPartition R a b) (epsPos : 0 < eps)
324 (subseq : nat -> nat),
325 UniformCont f cont_mod
326 -> WeavedLists x (ipt_seq P) (ipt_last P)
327 -> WeavedLists y (ipt_seq Q) (ipt_last Q)
328 -> IntervalPartitionRefinement _ _ P Q subseq
329 -> (PartitionMesh (ipt_seq P) (S (ipt_last P))) < (cont_mod eps epsPos)
330 -> CRabs _ (IntegralFiniteSum f x (ipt_seq P) (ipt_last P)
331 - IntegralFiniteSum f y (ipt_seq Q) (ipt_last Q))
332 <= eps * (b-a).
333 Proof.
334 (* Use subseq to make packets of summations *)
335 intros.
336 setoid_replace (IntegralFiniteSum f x (ipt_seq P) (ipt_last P)
337 - IntegralFiniteSum f y (ipt_seq Q) (ipt_last Q))
338 with (CRsum (fun n:nat => f (x n) *
339 (CRsum (fun i => ipt_seq Q (S i + subseq n)
340 - ipt_seq Q (i + subseq n))
341 (pred (subseq (S n) - subseq n))))
342 (ipt_last P)
343 - (CRsum (fun n:nat => CRsum (fun i => f (y (i + subseq n)%nat) *
344 (ipt_seq Q (S i + subseq n)
345 - ipt_seq Q (i + subseq n)))
346 (pred (subseq (S n) - subseq n)))
347 (ipt_last P))).
348 - rewrite <- Rsum_minus.
349 apply (CRle_trans _ _ _ (multiTriangleIneg _ _)).
350 apply (CRle_trans _ (CRsum (fun k => eps * (ipt_seq P (S k) - ipt_seq P k))
351 (ipt_last P))).
352 + apply sum_Rle. intros n H4.
353 rewrite CRmult_comm, <- sum_scale, <- Rsum_minus.
354 apply (CRle_trans _ _ _ (multiTriangleIneg _ _)).
355 apply (CRle_trans
356 _ (CRsum
357 (fun k : nat =>
358 CRabs _ (f (x n) - f (y (plus k (subseq n))))
359 * (ipt_seq Q (S k + subseq n) - ipt_seq Q (k + subseq n)))
360 (pred (subseq (S n) - subseq n)))).
361 apply sum_Rle. intros. rewrite <- (CRmult_comm (f (x n))).
362 unfold CRminus. rewrite CRopp_mult_distr_l.
363 rewrite <- CRmult_plus_distr_r, CRabs_mult. apply CRmult_le_compat_l.
364 apply CRabs_pos. rewrite CRabs_right. apply CRle_refl.
365 rewrite <- (CRplus_opp_r (ipt_seq Q (k + subseq n))).
366 apply CRplus_le_compat. 2: apply CRle_refl.
367 apply ipt_ordered.
368 apply le_S_n. apply le_n_S in H5.
369 apply (Nat.le_trans _ (subseq (S n))).
370 rewrite Nat.succ_pred in H5.
371 rewrite Nat.add_comm. apply Nat.lt_add_lt_sub_l. exact H5.
372 intro abs.
373 destruct H2, H6. specialize (H6 n (S n) (Nat.le_refl _)).
374 apply Nat.sub_0_le in abs. apply (proj1 (Nat.le_ngt _ _) abs).
375 apply H6, le_n_S, H4. apply H2. apply le_n_S, H4.
376 apply (CRle_trans
377 _ (CRsum
378 (fun k : nat =>
379 (ipt_seq Q (S k + subseq n) - ipt_seq Q (k + subseq n))
380 * eps)
381 (Init.Nat.pred (subseq (S n) - subseq n)))).
382 apply sum_Rle. intros n0 H5. rewrite CRmult_comm.
383 apply CRmult_le_compat_l.
384 rewrite <- (CRplus_opp_r (ipt_seq Q (n0 + subseq n))).
385 apply CRplus_le_compat. 2: apply CRle_refl.
386 apply (ipt_ordered Q).
387 apply le_n_S in H5. rewrite Nat.succ_pred in H5.
388 apply le_S_n.
389 apply (Nat.le_trans _ (subseq (S n))).
390 rewrite Nat.add_comm. apply Nat.lt_add_lt_sub_l. exact H5.
391 apply H2, le_n_S, H4.
392 intro abs.
393 destruct H2, H6. specialize (H6 n (S n) (Nat.le_refl _)).
394 apply Nat.sub_0_le in abs. apply (proj1 (Nat.le_ngt _ _) abs).
395 apply H6, le_n_S, H4.
396 destruct H. apply CRlt_asym. apply (c0 eps _ _ epsPos).
397 apply (CRle_lt_trans _ (PartitionMesh (ipt_seq P) (S (ipt_last P)))).
398 2: exact H3.
399 apply (in_refinement_packet a b n (n0 + subseq n) x y P Q subseq H0 H1 H2 H4).
400 apply le_n_S in H5. rewrite Nat.succ_pred in H5.
401 apply (Nat.le_trans _ (0 + subseq n)). apply Nat.le_refl.
402 apply Nat.add_le_mono_r. apply Nat.le_0_l.
403 intro abs.
404 destruct H2, H2. specialize (H2 n (S n) (Nat.le_refl _)).
405 apply Nat.sub_0_le in abs. apply (proj1 (Nat.le_ngt _ _) abs).
406 apply H2. apply le_n_S, H4.
407 rewrite Nat.add_comm. apply Nat.lt_add_lt_sub_l.
408 apply le_n_S in H5. rewrite Nat.succ_pred in H5. exact H5.
409 intro abs.
410 destruct H2, H2. specialize (H2 n (S n) (Nat.le_refl _)).
411 apply Nat.sub_0_le in abs. apply (proj1 (Nat.le_ngt _ _) abs).
412 apply H2. apply le_n_S, H4.
413 rewrite sum_scale, CRmult_comm. apply CRmult_le_compat_l.
414 apply CRlt_asym, epsPos.
415 rewrite (TelescopicSum (fun i => ipt_seq Q (i + subseq n))).
416 simpl.
417 replace (S (pred (subseq (S n) - subseq n) + subseq n))
418 with (subseq (S n)).
419 destruct H2. rewrite H2. 2: apply le_n_S, H4. rewrite H2. apply CRle_refl.
420 apply (Nat.le_trans _ _ _ H4). apply le_S, Nat.le_refl.
421 replace (S (Init.Nat.pred (subseq (S n) - subseq n) + subseq n))
422 with (S (Init.Nat.pred (subseq (S n) - subseq n)) + subseq n)%nat.
423 2: reflexivity. rewrite Nat.succ_pred.
424 rewrite Nat.sub_add. reflexivity.
425 apply (Nat.le_trans _ (S (subseq n))). apply le_S, Nat.le_refl. apply H2.
426 apply Nat.le_refl. apply le_n_S, H4.
427 intro abs.
428 destruct H2, H5.
429 specialize (H5 n (S n) (Nat.le_refl _)).
430 apply Nat.sub_0_le in abs. apply (proj1 (Nat.le_ngt _ _) abs), H5, le_n_S, H4.
431 + rewrite (CRsum_eq _ (fun k : nat => (ipt_seq P (S k) - ipt_seq P k) * eps)).
432 rewrite sum_scale, CRmult_comm. apply CRmult_le_compat_l.
433 apply CRlt_asym, epsPos.
434 rewrite TelescopicSum. destruct P; simpl.
435 rewrite <- ipt_lastB0, <- ipt_head0. apply CRle_refl.
436 intros. rewrite CRmult_comm. reflexivity.
437 - apply CRplus_morph.
438 + apply CRsum_eq. intros. apply CRmult_morph. reflexivity.
439 rewrite (TelescopicSum (fun n => ipt_seq Q (n + subseq i))).
440 simpl.
441 replace (S (pred (subseq (S i) - subseq i) + subseq i))
442 with (subseq (S i)).
443 destruct H2. rewrite (H2 i). rewrite (H2 (S i)). reflexivity.
444 apply le_n_S, H4. apply (Nat.le_trans _ _ _ H4), le_S, Nat.le_refl.
445 replace (S (Init.Nat.pred (subseq (S i) - subseq i) + subseq i))
446 with (S (Init.Nat.pred (subseq (S i) - subseq i)) + subseq i)%nat.
447 2: reflexivity. rewrite Nat.succ_pred.
448 rewrite Nat.sub_add. reflexivity.
449 apply (Nat.le_trans _ (S (subseq i))). apply le_S, Nat.le_refl. apply H2.
450 apply Nat.le_refl. apply le_n_S, H4.
451 intro abs.
452 destruct H2, H5.
453 specialize (H5 i (S i) (Nat.le_refl _)).
454 apply Nat.sub_0_le in abs. apply (proj1 (Nat.le_ngt _ _) abs), H5, le_n_S, H4.
455 + unfold IntegralFiniteSum.
456 rewrite partition_sum_by_packets. reflexivity. exact H2.
457 Qed.
458
459 Definition IntervalEquiPartition
460 {R : ConstructiveReals} (a b : CRcarrier R) (last : nat)
461 : a <= b -> @IntervalPartition R a b.
462 Proof.
463 intros.
464 apply (Build_IntervalPartition
465 R a b
466 (fun n:nat => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last).
467 setoid_replace (Z.of_nat 0 # Pos.of_nat (S last))%Q with 0%Q.
468 rewrite CRmult_0_r, CRplus_0_r.
469 reflexivity. reflexivity.
470 setoid_replace (Z.of_nat (S last) # Pos.of_nat (S last))%Q with 1%Q.
471 rewrite CRmult_1_r. unfold CRminus.
472 rewrite CRplus_comm, CRplus_assoc, CRplus_opp_l.
473 rewrite CRplus_0_r. reflexivity.
474 unfold Qeq, Qnum, Qden. rewrite Z.mul_1_r, Z.mul_1_l.
475 rewrite <- positive_nat_Z, Nat2Pos.id. reflexivity. discriminate.
476 intros. apply CRplus_le_compat_l.
477 apply CRmult_le_compat_l.
478 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
479 exact H. apply CRle_refl.
480 apply CR_of_Q_le.
481 unfold Qle, Qnum, Qden. apply Z.mul_le_mono_nonneg_r.
482 discriminate. apply Nat2Z.inj_le, le_S, Nat.le_refl.
483 Defined.
484
485 Lemma WeavedListSelf : forall {R : ConstructiveReals} (xn : nat -> CRcarrier R) (last : nat),
486 (forall n:nat, le n last -> (xn n) <= (xn (S n)))
487 -> WeavedLists xn xn last.
488 Proof.
489 intros R xn last H n H0.
490 split. apply CRle_refl. apply H. exact H0.
491 Qed.
492
493 Lemma EquiPartitionMesh
494 : forall {R : ConstructiveReals} (a b : CRcarrier R) (n last : nat) (leab : a <= b),
495 PartitionMesh (ipt_seq (IntervalEquiPartition a b last leab)) (S n)
496 == (b-a) * CR_of_Q R (1 # Pos.of_nat (S last)).
497 Proof.
498 induction n.
499 - intros. unfold PartitionMesh, IntervalEquiPartition, ipt_seq.
500 setoid_replace (Z.of_nat 0 # Pos.of_nat (S last))%Q with 0%Q.
501 2: reflexivity.
502 rewrite CRmult_0_r, CRplus_0_r.
503 unfold CRminus. rewrite CRplus_assoc, <- (CRplus_comm (-a)), <- CRplus_assoc.
504 rewrite CRplus_opp_r, CRplus_0_l.
505 rewrite CRmax_left. reflexivity. rewrite <- (CRmult_0_r (b-a)).
506 apply CRmult_le_compat_l.
507 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
508 exact leab. apply CRle_refl.
509 apply CR_of_Q_le. discriminate.
510 - intros.
511 specialize (IHn last leab).
512 unfold IntervalEquiPartition, ipt_seq.
513 transitivity (CRmax ((a + (b - a) * CR_of_Q R (Z.of_nat (2+n) # Pos.of_nat (S last)))
514 - (a + (b - a) * CR_of_Q R (Z.of_nat (1+n) # Pos.of_nat (S last))))
515 (PartitionMesh (ipt_seq (IntervalEquiPartition a b last leab)) (S n))).
516 reflexivity. rewrite IHn. clear IHn.
517 setoid_replace (a + (b - a) * CR_of_Q R (Z.of_nat (2 + n) # Pos.of_nat (S last))
518 - (a + (b - a) * CR_of_Q R (Z.of_nat (1 + n) # Pos.of_nat (S last))))
519 with ((b - a) * CR_of_Q R (1 # Pos.of_nat (S last))).
520 rewrite CRmax_left. reflexivity. apply CRle_refl.
521 rewrite CRplus_comm. unfold CRminus.
522 rewrite CRopp_plus_distr, CRplus_assoc.
523 rewrite <- (CRplus_assoc a), CRplus_opp_r, CRplus_0_l.
524 rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l.
525 apply CRmult_morph. reflexivity.
526 rewrite <- CR_of_Q_opp, <- CR_of_Q_plus. apply CR_of_Q_morph.
527 rewrite Qinv_minus_distr.
528 unfold Qeq, Qnum, Qden. apply f_equal2. 2: reflexivity.
529 simpl (2+n)%nat. rewrite (Nat2Z.inj_succ (S n)). unfold Z.succ.
530 simpl (1+n)%nat. ring.
531 Qed.
532
533 Lemma UC_compare_integrals
534 : forall {Re : ConstructiveReals} (f : CRcarrier Re -> CRcarrier Re)
535 (a b eps epsR : CRcarrier Re)
536 (cont_mod : forall eps:CRcarrier Re, 0 < eps -> CRcarrier Re)
537 (P R Q : @IntervalPartition Re a b)
538 (epsPos : 0 < eps) (epsPosR : 0 < epsR)
539 (subseq : nat -> nat) (subseqR : nat -> nat),
540 UniformCont f cont_mod
541 -> IntervalPartitionRefinement _ _ P Q subseq
542 -> IntervalPartitionRefinement _ _ R Q subseqR
543 -> (PartitionMesh (ipt_seq P) (S (ipt_last P))) < (cont_mod eps epsPos)
544 -> (PartitionMesh (ipt_seq R) (S (ipt_last R))) < (cont_mod epsR epsPosR)
545 -> CRabs _ (IntegralFiniteSum f (ipt_seq P) (ipt_seq P) (ipt_last P)
546 - IntegralFiniteSum f (ipt_seq R) (ipt_seq R) (ipt_last R))
547 <= (eps+epsR) * (b-a).
548 Proof.
549 intros.
550 setoid_replace (IntegralFiniteSum f (ipt_seq P) (ipt_seq P) (ipt_last P) -
551 IntegralFiniteSum f (ipt_seq R) (ipt_seq R) (ipt_last R))
552 with (IntegralFiniteSum f (ipt_seq P) (ipt_seq P) (ipt_last P) -
553 (IntegralFiniteSum f (ipt_seq Q) (ipt_seq Q) (ipt_last Q))
554 + (IntegralFiniteSum f (ipt_seq Q) (ipt_seq Q) (ipt_last Q)
555 - IntegralFiniteSum f (ipt_seq R) (ipt_seq R) (ipt_last R))).
556 apply (CRle_trans _ _ _ (CRabs_triang _ _)).
557 rewrite CRmult_plus_distr_r. apply CRplus_le_compat.
558 - apply (UC_refine_integral
559 f a b eps cont_mod
560 _ _ _ _ epsPos subseq).
561 exact H. apply WeavedListSelf, ipt_ordered.
562 apply WeavedListSelf, ipt_ordered. exact H0. exact H2.
563 - rewrite CRabs_minus_sym.
564 apply (UC_refine_integral
565 f a b epsR cont_mod
566 _ _ _ _ epsPosR subseqR).
567 exact H. apply WeavedListSelf, ipt_ordered.
568 apply WeavedListSelf, ipt_ordered. exact H1. exact H3.
569 - unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph.
570 reflexivity. rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
571 Qed.
572
573 (* This definition can be generalized to function uniformly
574 continuous on an interval. Just multiply f by a trapeze of
575 height 1. *)
576 Lemma UC_integral_cauchy
577 : forall {R : ConstructiveReals}
578 (f : CRcarrier R -> CRcarrier R) (a b : CRcarrier R)
579 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R),
580 UniformCont f cont_mod
581 -> a <= b
582 -> CR_cauchy R
583 (fun last : nat => IntegralFiniteSum
584 f (fun n => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
585 (fun n => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last).
586 Proof.
587 intros. intros n.
588 (* eps = / INR (S (2 * n)) * / (b - a) *)
589 assert (0 < CR_of_Q R (Z.pos (2*n) # 1) * (1+b-a)) as invStepPos.
590 { apply CRmult_lt_0_compat.
591 apply CR_of_Q_lt. reflexivity.
592 apply (CRlt_le_trans _ (1+0)). rewrite CRplus_0_r. apply CRzero_lt_one.
593 unfold CRminus. rewrite CRplus_assoc. apply CRplus_le_compat_l.
594 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
595 exact H0. apply CRle_refl. }
596 assert (0 < CRinv R (CR_of_Q R (Z.pos (2*n) # 1) * (1+b-a))
597 (inr invStepPos)) as stepPos.
598 { apply CRinv_0_lt_compat. exact invStepPos. }
599 destruct H.
600 destruct (CRup_nat ((b-a) * (CRinv R (cont_mod _ stepPos) (inr (c _ stepPos)))))
601 as [p pmaj].
602 exists p. intros.
603 apply (CRle_trans
604 _ (((CRinv R (CR_of_Q R (Z.pos (2*n) # 1) * (1+b-a)) (inr invStepPos))
605 + (CRinv R (CR_of_Q R (Z.pos (2*n) # 1) * (1+b-a)) (inr invStepPos)))
606 * (b-a))).
607 assert (0 < S i * S j)%nat as sisjPos.
608 { apply Nat.mul_pos_pos; apply le_n_S, Nat.le_0_l. }
609 apply (UC_compare_integrals
610 f a b
611 (CRinv R (CR_of_Q R (Z.pos (2*n) # 1) * (1+b-a)) (inr invStepPos))
612 (CRinv R (CR_of_Q R (Z.pos (2*n) # 1) * (1+b-a)) (inr invStepPos))
613 cont_mod (IntervalEquiPartition a b i H0)
614 (IntervalEquiPartition a b j H0)
615 (IntervalEquiPartition a b (pred (S i * S j)) H0)
616 stepPos stepPos (fun n => S j * n)%nat (fun n => S i * n)%nat).
617 split; assumption.
618 - split. intros. unfold IntervalEquiPartition, ipt_seq.
619 rewrite Nat.succ_pred. apply CRplus_morph. reflexivity.
620 apply CRmult_morph. reflexivity. apply CR_of_Q_morph.
621 rewrite Nat2Z.inj_mul, Nat2Pos.inj_mul.
622 unfold Qeq, Qnum, Qden. do 2 rewrite <- positive_nat_Z.
623 rewrite Pos2Nat.inj_mul. rewrite Nat2Pos.id. rewrite Nat2Pos.id.
624 rewrite Nat2Z.inj_mul. ring. discriminate. discriminate. discriminate.
625 discriminate. discriminate.
626 split.
627 intros. apply Nat.mul_lt_mono_pos_l. apply le_n_S, Nat.le_0_l. exact H2.
628 unfold IntervalEquiPartition, ipt_last.
629 intros. rewrite Nat.succ_pred. rewrite Nat.mul_comm.
630 apply Nat.mul_le_mono_nonneg_r. apply Nat.le_0_l. exact H2.
631 intro abs. rewrite abs in sisjPos. inversion sisjPos.
632 - split. intros. unfold IntervalEquiPartition, ipt_seq.
633 rewrite Nat.succ_pred. apply CRplus_morph. reflexivity.
634 apply CRmult_morph. reflexivity. apply CR_of_Q_morph.
635 rewrite Nat2Z.inj_mul, Nat2Pos.inj_mul.
636 unfold Qeq, Qnum, Qden. do 2 rewrite <- positive_nat_Z.
637 rewrite Pos2Nat.inj_mul. rewrite Nat2Pos.id. rewrite Nat2Pos.id.
638 rewrite Nat2Z.inj_mul. ring. discriminate. discriminate. discriminate.
639 discriminate. discriminate.
640 split.
641 intros. apply Nat.mul_lt_mono_pos_l. apply le_n_S, Nat.le_0_l. exact H2.
642 unfold IntervalEquiPartition, ipt_last.
643 intros. rewrite Nat.succ_pred.
644 apply Nat.mul_le_mono_nonneg_l. apply Nat.le_0_l. exact H2.
645 intro abs. rewrite abs in sisjPos. inversion sisjPos.
646 - rewrite EquiPartitionMesh.
647 unfold IntervalEquiPartition, ipt_last.
648 apply (CRle_lt_trans _ ((b - a) * CR_of_Q R (1 # Pos.of_nat (S p)))).
649 apply CRmult_le_compat_l.
650 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
651 exact H0. apply CRle_refl. apply CR_of_Q_le.
652 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
653 apply Pos2Z.pos_le_pos. apply Pos2Nat.inj_le.
654 rewrite Nat2Pos.id. rewrite Nat2Pos.id. apply le_n_S, H.
655 discriminate. discriminate.
656 apply (CRmult_lt_compat_r (cont_mod _ stepPos)) in pmaj.
657 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in pmaj.
658 apply (CRmult_lt_reg_l (INR (S p))).
659 apply CR_of_Q_lt; reflexivity.
660 rewrite CRmult_comm, CRmult_assoc. unfold INR.
661 rewrite <- CR_of_Q_mult.
662 setoid_replace ((1 # Pos.of_nat (S p)) * (Z.of_nat (S p) # 1))%Q with 1%Q.
663 rewrite CRmult_1_r. apply (CRlt_le_trans _ _ _ pmaj).
664 apply CRmult_le_compat_r. apply CRlt_asym, c.
665 apply CR_of_Q_le. unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
666 apply Nat2Z.inj_le, le_S, Nat.le_refl.
667 unfold Qmult, Qeq, Qnum, Qden.
668 do 2 rewrite Z.mul_1_l. rewrite Z.mul_1_r, <- positive_nat_Z.
669 apply f_equal. rewrite Pos.mul_1_r. rewrite Nat2Pos.id.
670 reflexivity. discriminate. apply c.
671 - rewrite EquiPartitionMesh.
672 unfold IntervalEquiPartition, ipt_last.
673 apply (CRle_lt_trans _ ((b - a) * CR_of_Q R (1 # Pos.of_nat (S p)))).
674 apply CRmult_le_compat_l.
675 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
676 exact H0. apply CRle_refl. apply CR_of_Q_le.
677 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
678 apply Pos2Z.pos_le_pos. apply Pos2Nat.inj_le.
679 rewrite Nat2Pos.id. rewrite Nat2Pos.id. apply le_n_S, H1.
680 discriminate. discriminate.
681 apply (CRmult_lt_compat_r (cont_mod _ stepPos)) in pmaj.
682 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in pmaj.
683 apply (CRmult_lt_reg_l (INR (S p))).
684 apply CR_of_Q_lt; reflexivity.
685 rewrite CRmult_comm, CRmult_assoc. unfold INR.
686 rewrite <- CR_of_Q_mult.
687 setoid_replace ((1 # Pos.of_nat (S p)) * (Z.of_nat (S p) # 1))%Q with 1%Q.
688 rewrite CRmult_1_r. apply (CRlt_le_trans _ _ _ pmaj).
689 apply CRmult_le_compat_r. apply CRlt_asym, c.
690 apply CR_of_Q_le. unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
691 apply Nat2Z.inj_le, le_S, Nat.le_refl.
692 unfold Qmult, Qeq, Qnum, Qden.
693 do 2 rewrite Z.mul_1_l. rewrite Z.mul_1_r, <- positive_nat_Z.
694 apply f_equal. rewrite Pos.mul_1_r. rewrite Nat2Pos.id.
695 reflexivity. discriminate. apply c.
696 - rewrite <- (CRmult_1_r
697 (CRinv R (CR_of_Q R (Z.pos (2 * n) # 1) * (1 + b - a)) (inr invStepPos))).
698 rewrite <- CRmult_plus_distr_l.
699 apply (CRmult_le_reg_l (CR_of_Q R (Z.pos (2 * n) # 1) * (1 + b - a))).
700 exact invStepPos. do 2 rewrite <- CRmult_assoc.
701 rewrite CRinv_r, CRmult_1_l.
702 rewrite <- (CRmult_comm (1 + b - a)), CRmult_assoc.
703 rewrite <- CR_of_Q_mult.
704 setoid_replace ((Z.pos (2 * n) # 1) * (1 # n))%Q with 2%Q.
705 rewrite CRmult_comm, <- CR_of_Q_plus.
706 apply CRmult_le_compat_r.
707 apply CR_of_Q_le. discriminate.
708 rewrite <- (CRplus_0_l (b-a)).
709 unfold CRminus. rewrite CRplus_assoc.
710 apply CRplus_le_compat_r. apply CRlt_asym, CRzero_lt_one.
711 unfold Qeq, Qnum, Qden. simpl. do 2 rewrite Pos.mul_1_r.
712 reflexivity.
713 Qed.
714
715 Definition UC_integral {R : ConstructiveReals}
716 (f : CRcarrier R -> CRcarrier R) (a b : CRcarrier R)
717 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
718 : UniformCont f cont_mod
719 -> a <= b
720 -> CRcarrier R
721 := fun H H0 => let (i,_) := CR_complete R (fun last : nat => IntegralFiniteSum
722 f (fun n => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
723 (fun n => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
724 (UC_integral_cauchy f a b cont_mod H H0)
725 in i.
726
727
728 (* Give the convergence speed of the integral more explicitly.
729 This formula is useful for numerical computations of integrals
730 in practice, to majorate the error. *)
731 Lemma UC_compare_integrals_limit
732 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
733 (a b : CRcarrier R) (leab : a <= b) (n : nat)
734 (eps : CRcarrier R) (epsPos : 0 < eps)
735 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
736 (fCont : UniformCont f cont_mod),
737 PartitionMesh (ipt_seq (IntervalEquiPartition a b n leab))
738 (S (ipt_last (IntervalEquiPartition a b n leab)))
739 < cont_mod eps epsPos
740 -> CRabs _ (IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b n leab))
741 (ipt_seq (IntervalEquiPartition a b n leab))
742 (ipt_last (IntervalEquiPartition a b n leab))
743 - UC_integral f a b cont_mod fCont leab)
744 <= eps * (b-a).
745 Proof.
746 intros.
747 assert (forall k:nat, 0 < CR_of_Q R (1 # Pos.of_nat (S k))) as kPos.
748 { intros. apply CR_of_Q_lt. reflexivity. }
749 assert (forall k:nat,
750 let (q,_) := CRup_nat ((b-a) * (CRinv R (cont_mod _ (kPos k)) (inr ((fst fCont) _ (kPos k))))) in
751 CRabs _
752 (IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b n leab))
753 (ipt_seq (IntervalEquiPartition a b n leab)) (ipt_last (IntervalEquiPartition a b n leab))
754 - IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b (max k q) leab))
755 (ipt_seq (IntervalEquiPartition a b (max k q) leab))
756 (ipt_last (IntervalEquiPartition a b (max k q) leab)))
757 <= (eps + (CR_of_Q R (1# Pos.of_nat (S k)))) * (b-a)).
758 { intro k.
759 destruct (CRup_nat ((b-a) * (CRinv R (cont_mod _ (kPos k)) (inr ((fst fCont) _ (kPos k)))))) as [q qmaj].
760 assert (0 < S n * S (max k q))%nat as sisjPos.
761 apply Nat.mul_pos_pos; apply le_n_S, Nat.le_0_l.
762 apply (UC_compare_integrals
763 f a b _ _ cont_mod
764 _ _ (IntervalEquiPartition a b (pred (S n * S (max k q))) leab)
765 epsPos (kPos k) (fun i => S (max k q) * i)%nat (fun i => S n * i)%nat
766 fCont).
767 - split. intros. unfold IntervalEquiPartition, ipt_seq.
768 rewrite Nat.succ_pred.
769 apply CRplus_morph. reflexivity.
770 apply CRmult_morph. reflexivity. apply CR_of_Q_morph.
771 rewrite Nat2Z.inj_mul, Nat2Pos.inj_mul.
772 unfold Qeq, Qnum, Qden. do 2 rewrite <- positive_nat_Z.
773 rewrite Pos2Nat.inj_mul. rewrite Nat2Pos.id. rewrite Nat2Pos.id.
774 rewrite Nat2Z.inj_mul. ring. discriminate. discriminate. discriminate.
775 discriminate. discriminate.
776 split.
777 intros. apply Nat.mul_lt_mono_pos_l. apply le_n_S, Nat.le_0_l. exact H0.
778 unfold IntervalEquiPartition, ipt_last.
779 intros. rewrite Nat.succ_pred. rewrite Nat.mul_comm.
780 apply Nat.mul_le_mono_nonneg_r. apply Nat.le_0_l. exact H0.
781 intro abs. rewrite abs in sisjPos. inversion sisjPos.
782 - split. intros. unfold IntervalEquiPartition, ipt_seq.
783 rewrite Nat.succ_pred.
784 apply CRplus_morph. reflexivity.
785 apply CRmult_morph. reflexivity. apply CR_of_Q_morph.
786 rewrite Nat2Z.inj_mul, Nat2Pos.inj_mul.
787 unfold Qeq, Qnum, Qden. do 2 rewrite <- positive_nat_Z.
788 rewrite Pos2Nat.inj_mul. rewrite Nat2Pos.id. rewrite Nat2Pos.id.
789 rewrite Nat2Z.inj_mul. ring. discriminate. discriminate. discriminate.
790 discriminate. discriminate.
791 split.
792 intros. apply Nat.mul_lt_mono_pos_l. apply le_n_S, Nat.le_0_l. exact H0.
793 unfold IntervalEquiPartition, ipt_last.
794 intros. rewrite Nat.succ_pred.
795 apply Nat.mul_le_mono_nonneg_l. apply Nat.le_0_l. exact H0.
796 intro abs. rewrite abs in sisjPos. inversion sisjPos.
797 - exact H.
798 - rewrite EquiPartitionMesh.
799 apply (CRle_lt_trans _ ((b - a) * CR_of_Q R (1# Pos.of_nat (S q)))).
800 apply CRmult_le_compat_l.
801 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
802 exact leab. apply CRle_refl. apply CR_of_Q_le.
803 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
804 apply Pos2Z.pos_le_pos. apply Pos2Nat.inj_le.
805 rewrite Nat2Pos.id. rewrite Nat2Pos.id. apply le_n_S, Nat.le_max_r.
806 discriminate. discriminate.
807 apply (CRmult_lt_compat_r (cont_mod _ (kPos k))) in qmaj.
808 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in qmaj.
809 apply (CRmult_lt_reg_l (INR (S q))).
810 apply CR_of_Q_lt; reflexivity.
811 rewrite CRmult_comm, CRmult_assoc. unfold INR.
812 rewrite <- CR_of_Q_mult.
813 setoid_replace ((1 # Pos.of_nat (S q)) * (Z.of_nat (S q) # 1))%Q with 1%Q.
814 rewrite CRmult_1_r. apply (CRlt_le_trans _ _ _ qmaj).
815 apply CRmult_le_compat_r. apply CRlt_asym. destruct fCont. apply c.
816 apply CR_of_Q_le. unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
817 apply Nat2Z.inj_le, le_S, Nat.le_refl.
818 unfold Qmult, Qeq, Qnum, Qden.
819 do 2 rewrite Z.mul_1_l. rewrite Z.mul_1_r, <- positive_nat_Z.
820 apply f_equal. rewrite Pos.mul_1_r. rewrite Nat2Pos.id.
821 reflexivity. discriminate. destruct fCont. apply c. }
822 apply (CR_cv_le
823 (fun k => let (q, _) :=
824 CRup_nat
825 ((b - a) *
826 (CRinv R (cont_mod (CR_of_Q R (1 # Pos.of_nat (S k))) (kPos k))
827 (inr (fst fCont (CR_of_Q R (1 # Pos.of_nat (S k))) (kPos k))))) in
828 CRabs _
829 (IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b n leab))
830 (ipt_seq (IntervalEquiPartition a b n leab)) (ipt_last (IntervalEquiPartition a b n leab)) -
831 IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b (Init.Nat.max k q) leab))
832 (ipt_seq (IntervalEquiPartition a b (Init.Nat.max k q) leab))
833 (ipt_last (IntervalEquiPartition a b (Init.Nat.max k q) leab))))
834 (fun k => (eps + CR_of_Q R (1 # Pos.of_nat (S k))) * (b - a))).
835 - intros. specialize (H0 n0).
836 destruct (CRup_nat
837 ((b - a) *
838 (CRinv R (cont_mod (CR_of_Q R (1 # Pos.of_nat (S n0))) (kPos n0))
839 (inr (fst fCont (CR_of_Q R (1 # Pos.of_nat (S n0))) (kPos n0)))))).
840 exact H0.
841 - intros eta. unfold UC_integral.
842 destruct (CR_complete R
843 (fun last : nat =>
844 IntegralFiniteSum f
845 (fun n1 : nat => a + (b - a) * CR_of_Q R (Z.of_nat n1 # Pos.of_nat (S last)))
846 (fun n1 : nat => a + (b - a) * CR_of_Q R (Z.of_nat n1 # Pos.of_nat (S last))) last)
847 (UC_integral_cauchy f a b cont_mod fCont leab)).
848 specialize (c eta) as [N u].
849 exists N. intros n0 H1.
850 destruct (CRup_nat
851 ((b - a) *
852 (CRinv R (cont_mod (CR_of_Q R (1 # Pos.of_nat (S n0))) (kPos n0))
853 (inr (fst fCont (CR_of_Q R (1 # Pos.of_nat (S n0))) (kPos n0)))))).
854 apply (CRle_trans _ _ _ (CRabs_triang_inv2 _ _)).
855 setoid_replace (IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b n leab))
856 (ipt_seq (IntervalEquiPartition a b n leab)) (ipt_last (IntervalEquiPartition a b n leab)) -
857 IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b (Init.Nat.max n0 x0) leab))
858 (ipt_seq (IntervalEquiPartition a b (Init.Nat.max n0 x0) leab))
859 (ipt_last (IntervalEquiPartition a b (Init.Nat.max n0 x0) leab)) -
860 (IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b n leab))
861 (ipt_seq (IntervalEquiPartition a b n leab)) (ipt_last (IntervalEquiPartition a b n leab)) -
862 x))
863 with (-(IntegralFiniteSum f (ipt_seq (IntervalEquiPartition a b (Init.Nat.max n0 x0) leab))
864 (ipt_seq (IntervalEquiPartition a b (Init.Nat.max n0 x0) leab))
865 (ipt_last (IntervalEquiPartition a b (Init.Nat.max n0 x0) leab)) - x)).
866 rewrite CRabs_opp. apply u.
867 unfold IntervalEquiPartition, ipt_last.
868 apply (Nat.le_trans _ _ _ H1), Nat.le_max_l.
869 unfold CRminus. do 2 rewrite CRopp_plus_distr.
870 rewrite <- CRplus_assoc. apply CRplus_morph. 2: reflexivity.
871 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l.
872 rewrite CRplus_0_l. reflexivity.
873 - apply CR_cv_scale. intros i.
874 exists (Pos.to_nat i). intros.
875 setoid_replace (eps + CR_of_Q R (1 # Pos.of_nat (S i0)) - eps)
876 with (CR_of_Q R (1 # Pos.of_nat (S i0))).
877 rewrite CRabs_right.
878 apply CR_of_Q_le. unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
879 apply Pos2Z.pos_le_pos. apply Pos2Nat.inj_le.
880 rewrite Nat2Pos.id. apply (Nat.le_trans _ _ _ H1), le_S, Nat.le_refl.
881 discriminate. apply CR_of_Q_le. discriminate.
882 unfold CRminus.
883 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
884 reflexivity.
885 Qed.
886
887 Lemma UC_integral_translate
888 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
889 (a b t : CRcarrier R) (leab : a <= b) (leabt : a+t <= b+t)
890 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
891 (fCont : UniformCont f cont_mod),
892 UC_integral f a b cont_mod fCont leab
893 == UC_integral (fun x => f (x-t)) (a+t) (b+t) cont_mod
894 (UC_translate_horizontal f (-t) cont_mod fCont) leabt.
895 Proof.
896 intros. unfold UC_integral.
897 assert (forall i j k : CRcarrier R, i + j - (i + k) == j - k) as addSub.
898 { intros. unfold CRminus. rewrite CRopp_plus_distr.
899 rewrite <- CRplus_assoc. apply CRplus_morph. 2: reflexivity.
900 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity. }
901 destruct (CR_complete R
902 (fun last : nat =>
903 IntegralFiniteSum (fun x : CRcarrier R => f (x - t))
904 (fun n : nat => a + t + (b + t - (a + t)) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
905 (fun n : nat => a + t + (b + t - (a + t)) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
906 last)
907 (UC_integral_cauchy (fun x : CRcarrier R => f (x - t)) (a + t) (b + t) cont_mod
908 (UC_translate_horizontal f (- t) cont_mod fCont) leabt)).
909 apply (CR_cv_unique (fun last : nat =>
910 IntegralFiniteSum (fun x : CRcarrier R => f (x - t))
911 (fun n : nat => a + t + (b + t - (a + t)) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
912 (fun n : nat => a + t + (b + t - (a + t)) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
913 last)).
914 2: exact c.
915 destruct (CR_complete R
916 (fun last : nat =>
917 IntegralFiniteSum f
918 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
919 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
920 (UC_integral_cauchy f a b cont_mod fCont leab)).
921 apply (CR_cv_eq _ (fun last : nat =>
922 IntegralFiniteSum f
923 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
924 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)).
925 2: exact c0.
926 intro n. apply CRsum_eq. intros. apply CRmult_morph.
927 - apply (UniformContProper f cont_mod fCont).
928 setoid_replace (b + t - (a + t)) with (b-a). unfold CRminus.
929 do 2 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
930 rewrite (CRplus_comm t), CRplus_assoc, CRplus_opp_l, CRplus_0_r. reflexivity.
931 rewrite (CRplus_comm b), (CRplus_comm a). rewrite addSub. reflexivity.
932 - setoid_replace (b + t - (a + t)) with (b-a). rewrite addSub, addSub. reflexivity.
933 rewrite (CRplus_comm b), (CRplus_comm a). rewrite addSub. reflexivity.
934 Qed.
935
936 Lemma UC_integral_bound_proper :
937 forall {R : ConstructiveReals}
938 f (a b c d : CRcarrier R)
939 (modF : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
940 (fCont : UniformCont f modF)
941 (leab : a <= b) (lecd : c <= d),
942 a == c
943 -> b == d
944 -> UC_integral f a b modF fCont leab
945 == UC_integral f c d modF fCont lecd.
946 Proof.
947 intros. unfold UC_integral.
948 destruct (CR_complete R
949 (fun last : nat =>
950 IntegralFiniteSum f
951 (fun n : nat => c + (d - c) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
952 (fun n : nat => c + (d - c) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
953 (UC_integral_cauchy f c d modF fCont lecd) ).
954 apply (CR_cv_unique (fun last : nat =>
955 IntegralFiniteSum f
956 (fun n : nat => c + (d - c) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
957 (fun n : nat => c + (d - c) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)).
958 2: exact c0.
959 destruct (CR_complete R
960 (fun last : nat =>
961 IntegralFiniteSum f
962 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
963 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
964 (UC_integral_cauchy f a b modF fCont leab)).
965 apply (CR_cv_eq _ (fun last : nat =>
966 IntegralFiniteSum f
967 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
968 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)).
969 2: exact c1.
970 intro n. apply CRsum_eq. intros. clear c1 x0 c0 x.
971 apply CRmult_morph. apply (UniformContProper f modF fCont).
972 rewrite H, H0. reflexivity.
973 rewrite H, H0. reflexivity.
974 Qed.
975
976 Lemma UC_right_bound_continuous
977 : forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
978 (a b : CRcarrier R) (leab : a <= b)
979 (eps : CRcarrier R) (epsPos : 0 < eps)
980 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
981 (fCont : UniformCont f cont_mod),
982 { eta : CRcarrier R
983 & prod (0 < eta)
984 (forall (c:CRcarrier R) (leac : prod (b <= c) (c < b+eta)),
985 CRabs R (UC_integral f a b cont_mod fCont leab
986 - UC_integral f a c cont_mod fCont (CRle_trans a b c leab (fst leac)))
987 <= eps) }.
988 Proof.
989 intros.
990 (* When f is a constant function, its integral on [a,b] equals
991 (b-a)f, so pushing b is weighted by f. *)
992 destruct (UC_bounded f a b cont_mod fCont leab) as [B Bmaj].
993 assert (forall i j k : CRcarrier R, i + j - (i + k) == j - k) as addSub.
994 { intros. unfold CRminus. rewrite CRopp_plus_distr.
995 rewrite <- CRplus_assoc. apply CRplus_morph. 2: reflexivity.
996 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity. }
997 assert (0 < b-a+1).
998 { rewrite <- (CRplus_opp_l a). unfold CRminus.
999 rewrite (CRplus_comm b), CRplus_assoc. apply CRplus_lt_compat_l.
1000 apply (CRle_lt_trans _ (b+0)). rewrite CRplus_0_r. exact leab.
1001 apply CRplus_lt_compat_l, CRzero_lt_one. }
1002 assert (0 < B) as Bpos.
1003 { apply (CRle_lt_trans _ (CRabs R (f a))). apply CRabs_pos.
1004 apply Bmaj. apply CRle_refl. exact leab. }
1005 assert (0 < eps * CR_of_Q R (1#2) * CRinv R (b-a+1) (inr H)).
1006 { destruct fCont. apply CRmult_lt_0_compat. apply CRmult_lt_0_compat.
1007 exact epsPos. apply CR_of_Q_pos. reflexivity.
1008 apply CRinv_0_lt_compat, H. }
1009 exists (CRmin (cont_mod (eps * CR_of_Q R (1#2) * CRinv R (b-a+1) (inr H)) H0)
1010 (CRmin (eps * CR_of_Q R (1#2) * CRinv R B (inr Bpos)) 1)).
1011 split. apply CRmin_lt. apply (fst fCont). apply CRmin_lt.
1012 apply CRmult_lt_0_compat. apply CRmult_lt_0_compat. exact epsPos.
1013 apply CR_of_Q_pos. reflexivity. apply CRinv_0_lt_compat, Bpos.
1014 exact (CRzero_lt_one R). intros.
1015 apply (CR_cv_bound_up
1016 (fun last : nat => CRabs R (IntegralFiniteSum
1017 f (fun n => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
1018 (fun n => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last
1019 - IntegralFiniteSum
1020 f (fun n => a + (c-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
1021 (fun n => a + (c-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last))
1022 eps _ O).
1023 - intros n _. unfold IntegralFiniteSum.
1024 unfold CRminus. rewrite <- sum_opp, <- sum_plus.
1025 rewrite (CRsum_eq _ (fun n0 => ((f (a + (b + - a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S n)))
1026 * (b + - a)
1027 - f (a + (c + - a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S n)))
1028 * (c + - a)) * CR_of_Q R (1 # Pos.of_nat (S n))))).
1029 rewrite sum_scale, CRmult_comm.
1030 rewrite CRabs_mult, CRabs_right.
1031 2: apply CR_of_Q_le; discriminate.
1032 apply (CRle_trans _ (CR_of_Q R (1 # Pos.of_nat (S n)) *
1033 CRsum (fun k => CRabs R (f (a + (b + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n))) * (b-a) -
1034 f (a + (c + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n))) * (c-a))) n)).
1035 apply CRmult_le_compat_l.
1036 apply CR_of_Q_le; discriminate.
1037 apply multiTriangleIneg.
1038 apply (CRle_trans _ (CR_of_Q R (1 # Pos.of_nat (S n)) * CRsum (fun _ => eps) n)).
1039 + (* Prove that each element of the sum is lower than eps. *)
1040 apply CRmult_le_compat_l.
1041 apply CR_of_Q_le; discriminate.
1042 apply sum_Rle. intros.
1043 assert (CR_of_Q R (Z.of_nat k # Pos.of_nat (S n)) <= 1) as inInterval.
1044 { apply CR_of_Q_le.
1045 unfold Qle, Qnum, Qden. rewrite Z.mul_1_r, Z.mul_1_l.
1046 destruct k. discriminate. unfold Z.of_nat.
1047 apply Pos2Z.pos_le_pos. rewrite Pos.of_nat_succ. apply Pos2Nat.inj_le.
1048 rewrite Nat2Pos.id, Nat2Pos.id. apply le_S, H1. discriminate. discriminate. }
1049 setoid_replace (f (a + (b + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n))) * (b - a) -
1050 f (a + (c + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n))) * (c - a))
1051 with (f (a + (b + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n))) * (b - a) -
1052 f (a + (b + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n))) * (c - a) +
1053 (f (a + (b + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n))) * (c - a) -
1054 f (a + (c + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n))) * (c - a))).
1055 apply (CRle_trans _ _ _ (CRabs_triang _ _)).
1056 apply (CRle_trans _ (eps * CR_of_Q R (1#2) + eps * CR_of_Q R (1#2))).
1057 apply CRplus_le_compat.
1058 unfold CRminus. rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l, CRabs_mult.
1059 setoid_replace (b + - a + - (c + - a)) with (b-c).
1060 apply (CRle_trans _ (B * CRabs R (b-c))). apply CRmult_le_compat_r.
1061 apply CRabs_pos. apply CRlt_asym, Bmaj.
1062 apply (CRle_trans _ (a + 0)). rewrite CRplus_0_r. apply CRle_refl.
1063 apply CRplus_le_compat_l. apply CRmult_le_0_compat.
1064 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat_r. exact leab.
1065 apply CR_of_Q_le.
1066 unfold Qle; simpl. rewrite Z.mul_1_r. apply Nat2Z.is_nonneg.
1067 apply (CRplus_le_reg_l (-a)). rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
1068 rewrite <- (CRmult_1_r (-a+b)), (CRplus_comm (-a)).
1069 apply CRmult_le_compat_l. rewrite <- (CRplus_opp_r a).
1070 apply CRplus_le_compat_r. exact leab. exact inInterval.
1071 rewrite CRabs_minus_sym, CRabs_right.
1072 apply (CRmult_le_reg_r (CRinv R B (inr Bpos))).
1073 apply CRinv_0_lt_compat, Bpos.
1074 rewrite CRmult_comm, <- CRmult_assoc, CRinv_l, CRmult_1_l.
1075 destruct leac. apply (CRplus_lt_compat_l R (-b)) in c1.
1076 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l, CRplus_comm in c1.
1077 apply CRlt_asym, (CRlt_le_trans _ _ _ c1).
1078 apply (CRle_trans _ _ _ (CRmin_r _ _)). apply CRmin_l.
1079 rewrite <- (CRplus_opp_r b). apply CRplus_le_compat_r. exact (fst leac).
1080 do 2 rewrite <- (CRplus_comm (-a)). exact (addSub (-a) b c).
1081 unfold CRminus. rewrite CRopp_mult_distr_l, <- CRmult_plus_distr_r.
1082 rewrite CRabs_mult.
1083 apply (CRle_trans
1084 _ (eps * CR_of_Q R (1 # 2) * CRinv R (b - a + 1) (inr H) * CRabs R (c + - a))).
1085 apply CRmult_le_compat_r. apply CRabs_pos.
1086 apply CRlt_asym. apply (snd fCont _ _ _ H0). rewrite addSub.
1087 apply (CRle_lt_trans _ (c-b)).
1088 unfold CRminus. rewrite CRopp_mult_distr_l, <- CRmult_plus_distr_r, CRabs_mult.
1089 rewrite <- (CRplus_comm (-a)), <- (CRplus_comm (-a)), (addSub (-a) b c).
1090 rewrite <- (CRmult_1_r (c+-b)), CRabs_minus_sym, CRabs_right.
1091 apply CRmult_le_compat_l. rewrite <- (CRplus_opp_r b).
1092 apply CRplus_le_compat_r. exact (fst leac).
1093 rewrite CRabs_right. exact inInterval.
1094 apply CR_of_Q_le. unfold Qle; simpl.
1095 rewrite Z.mul_1_r. apply Nat2Z.is_nonneg.
1096 rewrite <- (CRplus_opp_r b).
1097 apply CRplus_le_compat_r. exact (fst leac).
1098 destruct leac. apply (CRplus_lt_compat_l R (-b)) in c1.
1099 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l, CRplus_comm in c1.
1100 apply (CRlt_le_trans _ _ _ c1). apply CRmin_l.
1101 rewrite <- (CRmult_1_r (eps * CR_of_Q R (1 # 2))).
1102 do 2 rewrite CRmult_assoc. apply CRmult_le_compat_l. apply CRmult_le_0_compat.
1103 apply CRlt_asym, epsPos. apply CRlt_asym, CR_of_Q_pos. reflexivity.
1104 rewrite CRmult_1_l. apply (CRmult_le_reg_l (b-a+1) _ _ H).
1105 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l, CRmult_1_r.
1106 rewrite CRabs_right. unfold CRminus. rewrite (CRplus_comm c), (CRplus_comm b).
1107 rewrite CRplus_assoc. apply CRplus_le_compat_l.
1108 apply CRlt_asym. destruct leac. apply (CRlt_le_trans _ _ _ c1).
1109 apply CRplus_le_compat_l. apply (CRle_trans _ _ _ (CRmin_r _ _)), CRmin_r.
1110 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat_r.
1111 apply (CRle_trans _ _ _ leab). exact (fst leac).
1112 rewrite <- CRmult_plus_distr_l, <- CR_of_Q_plus.
1113 rewrite Qinv_plus_distr. setoid_replace (1 + 1 # 2)%Q with 1%Q.
1114 rewrite CRmult_1_r. apply CRle_refl. reflexivity.
1115 unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
1116 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
1117 + rewrite sum_const. rewrite CRmult_comm, CRmult_assoc.
1118 unfold INR. rewrite <- CR_of_Q_mult.
1119 setoid_replace ((Z.of_nat (S n) # 1) * (1 # Pos.of_nat (S n)))%Q with 1%Q.
1120 rewrite CRmult_1_r. apply CRle_refl.
1121 unfold Z.of_nat. rewrite Pos.of_nat_succ.
1122 unfold Qeq. simpl. do 2 rewrite Pos.mul_1_r. reflexivity.
1123 + intros. unfold CRminus. unfold CRminus in addSub.
1124 do 2 rewrite (addSub a).
1125 rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l.
1126 rewrite (CRopp_mult_distr_r (c+-a)), <- CRmult_plus_distr_l.
1127 setoid_replace (CR_of_Q R (Z.of_nat (S i) # Pos.of_nat (S n))
1128 + - CR_of_Q R (Z.of_nat i # Pos.of_nat (S n)))
1129 with (CR_of_Q R (1 # Pos.of_nat (S n))).
1130 rewrite <- CRmult_assoc, <- CRmult_assoc, CRopp_mult_distr_l.
1131 rewrite <- CRmult_plus_distr_r. reflexivity.
1132 rewrite <- CR_of_Q_opp, <- CR_of_Q_plus. apply CR_of_Q_morph.
1133 rewrite Qinv_minus_distr.
1134 replace (Z.of_nat (S i) - Z.of_nat i)%Z with 1%Z. reflexivity.
1135 rewrite Nat2Z.inj_succ. unfold Z.succ. ring.
1136 - apply CR_cv_abs_cont. apply CR_cv_minus.
1137 unfold UC_integral.
1138 destruct (CR_complete R
1139 (fun last : nat =>
1140 IntegralFiniteSum f
1141 (fun n0 : nat => a + (b - a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last)))
1142 (fun n0 : nat => a + (b - a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last))) last)
1143 (UC_integral_cauchy f a b cont_mod fCont leab)).
1144 exact c0.
1145 unfold UC_integral.
1146 destruct (CR_complete R
1147 (fun last : nat =>
1148 IntegralFiniteSum f
1149 (fun n0 : nat => a + (c - a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last)))
1150 (fun n0 : nat => a + (c - a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last))) last)
1151 (UC_integral_cauchy f a c cont_mod fCont (CRle_trans a b c leab (fst leac)))).
1152 exact c0.
1153 Qed.
1154
1155 Definition ConcatSequences {R : ConstructiveReals}
1156 (xn yn : nat -> CRcarrier R) (lenX n : nat) : CRcarrier R
1157 := if lt_dec n lenX then xn n else yn (n - lenX)%nat.
1158
1159 Definition IntervalPartitionConcat
1160 {R : ConstructiveReals} {a b c : CRcarrier R}
1161 : @IntervalPartition R a b
1162 -> @IntervalPartition R b c
1163 -> @IntervalPartition R a c.
1164 Proof.
1165 intros P Q.
1166 apply (Build_IntervalPartition
1167 R a c
1168 (* do not count b twice *)
1169 (ConcatSequences (ipt_seq P) (ipt_seq Q) (S (ipt_last P)))
1170 (S (ipt_last P) + ipt_last Q)).
1171 - apply P.
1172 - unfold ConcatSequences.
1173 destruct (lt_dec (S (S (ipt_last P) + ipt_last Q)) (S (ipt_last P))).
1174 + exfalso. apply (proj1 (Nat.lt_nge _ _) l), le_n_S, (Nat.le_trans _ (S (ipt_last P) + 0)).
1175 rewrite Nat.add_0_r. apply le_S, Nat.le_refl. apply Nat.add_le_mono_l, Nat.le_0_l.
1176 + replace (S (S (ipt_last P) + ipt_last Q) - (S (ipt_last P)))%nat
1177 with (S (ipt_last Q)).
1178 apply Q. rewrite Nat.sub_succ. simpl plus.
1179 rewrite Nat.sub_succ_l. apply f_equal.
1180 rewrite Nat.add_comm, Nat.add_sub. reflexivity.
1181 apply (Nat.le_trans _ (ipt_last P + 0)). rewrite Nat.add_comm. apply Nat.le_refl.
1182 apply Nat.add_le_mono_l, Nat.le_0_l.
1183 - intros. unfold ConcatSequences.
1184 destruct (lt_dec (S n) (S (ipt_last P))).
1185 + destruct (lt_dec n (S (ipt_last P))). apply P, le_S_n, l0.
1186 exfalso. apply n0. apply le_S, le_S_n, l.
1187 + destruct (lt_dec n (S (ipt_last P))).
1188 apply (CRle_trans _ (ipt_seq P (S (ipt_last P)))).
1189 apply ipt_ordered_transit. apply le_S, le_S_n, l. apply Nat.le_refl.
1190 rewrite <- (ipt_lastB P). apply (CRle_trans _ (ipt_seq Q 0)).
1191 rewrite <- (ipt_head Q). apply CRle_refl. apply ipt_ordered_transit.
1192 apply Nat.le_0_l. simpl. apply Nat.le_sub_le_add_l.
1193 rewrite Nat.add_succ_r. exact H. clear n0.
1194 apply ipt_ordered_transit. apply Nat.le_sub_le_add_r.
1195 rewrite Nat.sub_add. apply le_S, Nat.le_refl.
1196 apply Nat.nlt_ge in n1. apply le_n_S, (Nat.le_trans _ (S (ipt_last P))).
1197 apply le_S, Nat.le_refl. exact n1. apply Nat.le_sub_le_add_r.
1198 simpl. apply le_n_S. rewrite Nat.add_comm. exact H.
1199 Defined.
1200
1201 Definition IntervalPartitionConcatSum
1202 : forall {R : ConstructiveReals}
1203 (a b c : CRcarrier R) (f : CRcarrier R -> CRcarrier R)
1204 (P : @IntervalPartition R a b)
1205 (Q : @IntervalPartition R b c),
1206 IntegralFiniteSum f (ipt_seq P) (ipt_seq P) (ipt_last P)
1207 + IntegralFiniteSum f (ipt_seq Q) (ipt_seq Q) (ipt_last Q)
1208 == IntegralFiniteSum
1209 f (ipt_seq (IntervalPartitionConcat P Q))
1210 (ipt_seq (IntervalPartitionConcat P Q))
1211 (ipt_last (IntervalPartitionConcat P Q)).
1212 Proof.
1213 intros. destruct P,Q; simpl. unfold IntegralFiniteSum.
1214 replace (S (ipt_last0 + ipt_last1)) with (S ipt_last0 + ipt_last1)%nat.
1215 2: reflexivity.
1216 rewrite sum_assoc. apply CRplus_morph.
1217 - apply CRsum_eq. intros. unfold ConcatSequences.
1218 destruct (lt_dec i (S ipt_last0)). clear l.
1219 2: apply le_n_S in H; contradiction.
1220 destruct (lt_dec (S i) (S ipt_last0)). reflexivity.
1221 apply CRmult_morph. reflexivity.
1222 apply CRplus_morph. 2: reflexivity.
1223 replace i with ipt_last0.
1224 + rewrite <- ipt_lastB0. rewrite Nat.sub_diag.
1225 rewrite <- ipt_head1. reflexivity.
1226 + apply Nat.le_antisymm. apply le_S_n, Nat.nlt_ge, n. exact H.
1227 - apply CRsum_eq. intros. unfold ConcatSequences.
1228 destruct (lt_dec (S ipt_last0 + i) (S ipt_last0)).
1229 exfalso. apply (proj1 (Nat.lt_nge _ _) l).
1230 apply (Nat.le_trans _ (S ipt_last0 + 0)).
1231 rewrite Nat.add_0_r. apply Nat.le_refl. apply Nat.add_le_mono_l, Nat.le_0_l.
1232 clear n.
1233 destruct (lt_dec (S (S ipt_last0 + i)) (S ipt_last0)).
1234 exfalso. apply Nat.lt_nge in l. apply l, le_n_S.
1235 apply (Nat.le_trans _ (S ipt_last0 + 0)).
1236 rewrite Nat.add_0_r. apply le_S, Nat.le_refl. apply Nat.add_le_mono_l, Nat.le_0_l.
1237 clear n.
1238 replace (S ipt_last0 + i - S ipt_last0)%nat with i.
1239 2: rewrite Nat.add_comm, Nat.add_sub; reflexivity.
1240 apply CRmult_morph. reflexivity.
1241 apply CRplus_morph. 2: reflexivity.
1242 replace (S (S ipt_last0 + i) - S ipt_last0)%nat with (S i).
1243 reflexivity.
1244 rewrite Nat.sub_succ. simpl plus.
1245 rewrite <- Nat.add_succ_r, Nat.add_comm, Nat.add_sub.
1246 reflexivity.
1247 Qed.
1248
1249 (* The last point of the first list must be equal to
1250 the first point of the second list, otherwise the
1251 concatenation would introduce a parasite difference. *)
1252 Lemma PartitionMeshConcat
1253 : forall {R : ConstructiveReals} (a b c : CRcarrier R)
1254 (P : @IntervalPartition R a b)
1255 (Q : @IntervalPartition R b c),
1256 PartitionMesh (ipt_seq (IntervalPartitionConcat P Q))
1257 (S (ipt_last (IntervalPartitionConcat P Q)))
1258 == CRmax (PartitionMesh (ipt_seq P) (S (ipt_last P)))
1259 (PartitionMesh (ipt_seq Q) (S (ipt_last Q))).
1260 Proof.
1261 intro R.
1262 assert (forall (xn yn : nat -> CRcarrier R) (p n : nat),
1263 xn n == yn O
1264 -> PartitionMesh (ConcatSequences xn yn n) (n + p)
1265 == CRmax (PartitionMesh xn n) (PartitionMesh yn p)).
1266 { induction p.
1267 - intros. unfold ConcatSequences.
1268 rewrite CRmax_left. 2: apply PartitionMesh_nonneg.
1269 rewrite Nat.add_0_r.
1270 rewrite (PartitionMesh_ext (fun n0 : nat => if lt_dec n0 n then xn n0 else yn (n0 - n)%nat) xn).
1271 reflexivity.
1272 intros. destruct (lt_dec n0 n). reflexivity.
1273 replace n0 with n. rewrite Nat.sub_diag. symmetry. exact H.
1274 apply Nat.le_antisymm. 2: exact H0. apply Nat.nlt_ge. exact n1.
1275 - intros. rewrite Nat.add_succ_r. simpl.
1276 rewrite IHp. 2: exact H.
1277 assert (forall a b c : CRcarrier R,
1278 CRmax a (CRmax b c) == CRmax b (CRmax a c)).
1279 intros. rewrite CRmax_assoc, (CRmax_sym a), <- CRmax_assoc. reflexivity.
1280 setoid_replace (ConcatSequences xn yn n (S (n + p)) - ConcatSequences xn yn n (n+p))
1281 with (yn (S p) - yn p).
1282 apply H0. unfold ConcatSequences.
1283 destruct (lt_dec (S (n + p)) n). exfalso. apply (proj1 (Nat.lt_nge _ _) l).
1284 apply (Nat.le_trans _ (S n + 0)). rewrite Nat.add_0_r. apply le_S, Nat.le_refl.
1285 simpl. apply le_n_S, Nat.add_le_mono_l, Nat.le_0_l.
1286 clear n0. destruct (lt_dec (n + p) n). exfalso. apply (proj1 (Nat.lt_nge _ _) l).
1287 apply (Nat.le_trans _ (n + 0)). rewrite Nat.add_0_r. apply Nat.le_refl.
1288 apply Nat.add_le_mono_l, Nat.le_0_l. clear n0.
1289 rewrite (Nat.add_comm n), Nat.add_sub. apply CRplus_morph.
1290 2: reflexivity.
1291 replace (S (p+n)) with (S p + n)%nat. 2: reflexivity.
1292 rewrite Nat.add_sub. reflexivity. }
1293 intros. unfold IntervalPartitionConcat, ipt_seq, ipt_last.
1294 destruct P, Q.
1295 replace (S (S ipt_last0 + ipt_last1))
1296 with (S ipt_last0 + S ipt_last1)%nat.
1297 rewrite H. apply CRmax_morph. reflexivity. reflexivity.
1298 rewrite <- ipt_lastB0. rewrite <- ipt_head1. reflexivity.
1299 rewrite Nat.add_succ_r. reflexivity.
1300 Qed.
1301
1302 Fixpoint Fun2List (xn : nat -> Q) (len : nat) : list Q
1303 := match len with
1304 | O => Datatypes.nil
1305 | S p => Fun2List xn p ++ (Datatypes.cons (xn p) Datatypes.nil)
1306 end.
1307
1308 Lemma Fun2ListLength : forall (xn : nat -> Q) (len : nat),
1309 length (Fun2List xn len) = len.
1310 Proof.
1311 induction len.
1312 - reflexivity.
1313 - simpl. rewrite app_length, IHlen, Nat.add_comm. reflexivity.
1314 Qed.
1315
1316 Lemma Fun2ListNth : forall (xn : nat -> Q) (len n : nat),
1317 lt n len -> nth n (Fun2List xn len) 0%Q = xn n.
1318 Proof.
1319 induction len.
1320 - intros. exfalso; inversion H.
1321 - intros. simpl. apply Nat.le_succ_r in H. destruct H.
1322 rewrite app_nth1. apply IHlen. exact H.
1323 rewrite Fun2ListLength. exact H. inversion H.
1324 rewrite app_nth2. rewrite Fun2ListLength, Nat.sub_diag.
1325 reflexivity. rewrite Fun2ListLength. apply Nat.le_refl.
1326 Qed.
1327
1328 Definition IntervalPartitionRational
1329 {R : ConstructiveReals} {a b : CRcarrier R}
1330 (P : @IntervalPartition R a b)
1331 : Set
1332 := { rat : list Q
1333 | (length rat = plus 2 (ipt_last P))
1334 /\ forall n:nat, le n (S (ipt_last P)) -> ipt_seq P n == CR_of_Q R (nth n rat 0%Q) }.
1335
1336 Lemma EquiPartitionRational
1337 : forall {R : ConstructiveReals} (a b : Q) (k : nat)
1338 (leab : (CR_of_Q R a) <= (CR_of_Q R b)),
1339 IntervalPartitionRational (IntervalEquiPartition (CR_of_Q R a) (CR_of_Q R b) k leab).
1340 Proof.
1341 intros. exists (Fun2List (fun n => a + (b-a) * (Z.of_nat n # Pos.of_nat (S k)))%Q (2+k)).
1342 intros. split.
1343 - rewrite Fun2ListLength. reflexivity.
1344 - intros. unfold IntervalEquiPartition, ipt_seq.
1345 unfold IntervalEquiPartition, ipt_last in H.
1346 rewrite Fun2ListNth. 2: apply le_n_S, H.
1347 rewrite CR_of_Q_plus. apply CRplus_morph. reflexivity.
1348 rewrite CR_of_Q_mult. unfold Qminus. rewrite CR_of_Q_plus, CR_of_Q_opp.
1349 reflexivity.
1350 Qed.
1351
1352 Lemma PartitionRationalConcat
1353 : forall {R : ConstructiveReals} (a b c : CRcarrier R)
1354 (P : @IntervalPartition R a b)
1355 (Q : @IntervalPartition R b c),
1356 IntervalPartitionRational P
1357 -> IntervalPartitionRational Q
1358 -> IntervalPartitionRational (IntervalPartitionConcat P Q).
1359 Proof.
1360 intros. destruct H, a0, H0, a0.
1361 exists (x ++ tl x0).
1362 intros. destruct P, Q; simpl; simpl in H, H2, H1, H0.
1363 split.
1364 - rewrite app_length, H. destruct x0.
1365 exfalso; inversion H0. simpl. simpl in H0. inversion H0.
1366 rewrite H4. rewrite Nat.add_succ_r. reflexivity.
1367 - intros. unfold ConcatSequences.
1368 destruct (lt_dec n (S ipt_last0)).
1369 + rewrite app_nth1. apply H1. apply le_S_n in l.
1370 apply (Nat.le_trans _ ipt_last0 _ l), le_S, Nat.le_refl.
1371 rewrite H. apply (Nat.lt_trans _ _ _ l), Nat.le_refl.
1372 + destruct (Nat.lt_trichotomy n (S ipt_last0)).
1373 contradiction. destruct H4. subst n.
1374 rewrite app_nth1. rewrite Nat.sub_diag, <- ipt_head1.
1375 rewrite <- H1. rewrite <- ipt_lastB0. reflexivity.
1376 apply Nat.le_refl. rewrite H. apply Nat.le_refl.
1377 clear n0. rewrite app_nth2, H.
1378 2: rewrite H; exact H4.
1379 destruct x0. exfalso; inversion H0. simpl.
1380 specialize (H2 (S(n - S (S(ipt_last0))))%nat). simpl in H2.
1381 rewrite <- H2.
1382 replace (n - S ipt_last0)%nat with (S (n - S (S ipt_last0))).
1383 reflexivity.
1384 rewrite (Nat.sub_succ_r _ (S ipt_last0)).
1385 rewrite Nat.succ_pred. reflexivity.
1386 intro abs. apply Nat.sub_0_le in abs.
1387 exact (proj1 (Nat.lt_nge _ _) H4 abs).
1388 rewrite (Nat.sub_succ_r _ (S ipt_last0)).
1389 rewrite Nat.succ_pred.
1390 rewrite Nat.le_sub_le_add_l, Nat.add_succ_r. exact H3.
1391 intro abs. apply Nat.sub_0_le in abs.
1392 exact (proj1 (Nat.lt_nge _ _) H4 abs).
1393 Qed.
1394
1395 Lemma FunLocSorted : forall (xn : list Q),
1396 (forall n:nat, lt (S n) (length xn) -> Qle (nth n xn 0%Q) (nth (S n) xn 0%Q))
1397 -> LocallySorted (fun x x0 : QArith_base.Q => is_true (Qle_bool x x0)) xn.
1398 Proof.
1399 induction xn.
1400 - intros. apply LSorted_nil.
1401 - intros. destruct xn. apply LSorted_cons1.
1402 apply LSorted_consn. apply IHxn.
1403 intros. apply (H (S n)). apply le_n_S, H0.
1404 unfold is_true. rewrite Qle_bool_iff. apply (H O).
1405 apply le_n_S, le_n_S, Nat.le_0_l.
1406 Qed.
1407
1408 Lemma LocSortedFun : forall (xn : list Q),
1409 LocallySorted (fun x x0 : QArith_base.Q => is_true (Qle_bool x x0)) xn
1410 -> (forall n:nat, lt (S n) (length xn) -> Qle (nth n xn 0%Q) (nth (S n) xn 0%Q)).
1411 Proof.
1412 induction xn.
1413 - intros. exfalso; inversion H0.
1414 - intros. simpl in H0.
1415 destruct xn. exfalso; inversion H0; inversion H2.
1416 destruct n. simpl. inversion H. unfold is_true in H5.
1417 rewrite Qle_bool_iff in H5. exact H5.
1418 apply IHxn. inversion H; exact H3.
1419 apply le_S_n in H0. exact H0.
1420 Qed.
1421
1422 Lemma PartitionRationalLocSorted
1423 : forall {R : ConstructiveReals} (a b : CRcarrier R)
1424 (P : @IntervalPartition R a b)
1425 (rat : IntervalPartitionRational P),
1426 LocallySorted (fun x x0 : QArith_base.Q => is_true (Qle_bool x x0)) (proj1_sig rat).
1427 Proof.
1428 intros. apply FunLocSorted.
1429 intros. destruct rat; simpl; unfold proj1_sig in H.
1430 destruct (Q_dec (nth n x 0) (nth (S n) x 0))%Q. destruct s.
1431 apply Qlt_le_weak, q. exfalso.
1432 destruct a0.
1433 rewrite H0 in H. apply le_S_n, le_S_n in H.
1434 apply (CR_of_Q_lt R) in q.
1435 rewrite <- H1 in q. rewrite <- (H1 n) in q. destruct P.
1436 simpl in q, H1. apply (ipt_ordered0 n). exact H. exact q.
1437 apply le_S, H. apply le_n_S, H.
1438 rewrite q. apply Qle_refl.
1439 Qed.
1440
1441 Module QOrder <: TotalLeBool.
1442 Definition t := Q.
1443 Definition leb := Qle_bool.
1444 Theorem leb_total : forall a1 a2:Q, leb a1 a2 = true \/ leb a2 a1 = true.
1445 Proof.
1446 intros. unfold leb.
1447 do 2 rewrite Qle_bool_iff. destruct (Qlt_le_dec a1 a2).
1448 left. apply Qlt_le_weak, q. right. exact q.
1449 Qed.
1450 End QOrder.
1451
1452 Module Import QSort := Sort QOrder.
1453
1454 Lemma MergeLength : forall (xn yn : list Q),
1455 length (merge xn yn) = plus (length xn) (length yn).
1456 Proof.
1457 intros. pose proof (Permuted_merge xn yn).
1458 apply Permutation_length in H.
1459 rewrite <- H. apply app_length.
1460 Qed.
1461
1462 (* index of xn n inside merge xn yn.
1463 Inner fixpoint allows to prove that recursive calls terminate. *)
1464 Fixpoint MergeInjectL (xn yn : list Q) (n : nat) { struct xn } : nat
1465 := let fix merge_aux yn n :=
1466 match xn with
1467 | Datatypes.nil => O (* shouldn't happen *)
1468 | Datatypes.cons x tx
1469 => match yn with
1470 | Datatypes.nil => n
1471 | Datatypes.cons y ty
1472 => if Qlt_le_dec y x then
1473 S (merge_aux ty n)
1474 else (match n with O => O | S p => S (MergeInjectL tx yn p) end)
1475 end
1476 end
1477 in merge_aux yn n.
1478
1479 Lemma MergeInjectLSpec
1480 : forall (gas n : nat) (xn yn : list Q),
1481 lt (length xn + length yn) gas
1482 -> lt n (length xn)
1483 -> nth (MergeInjectL xn yn n) (merge xn yn) 0%Q
1484 = nth n xn 0%Q.
1485 Proof.
1486 induction gas.
1487 - intros. exfalso; inversion H.
1488 - intros. destruct xn.
1489 + simpl. destruct yn. destruct n; reflexivity.
1490 exfalso; inversion H0.
1491 + destruct yn.
1492 simpl; destruct n; reflexivity. simpl.
1493 destruct (Qlt_le_dec q0 q).
1494 * destruct (Qle_bool q q0) eqn:des.
1495 exfalso. pose proof (Qle_bool_iff q q0) as [H1 _].
1496 apply (Qlt_not_le _ _ q1), H1, des.
1497 simpl. specialize (IHgas n (q :: xn) yn). simpl in IHgas.
1498 rewrite IHgas. reflexivity.
1499 simpl (length (q0 :: yn)) in H. rewrite Nat.add_succ_r in H.
1500 apply le_S_n in H. exact H. exact H0.
1501 * (* head of x first *)
1502 destruct n. (* equal q, no need of induction hypo *)
1503 destruct (Qle_bool q q0) eqn:des. reflexivity.
1504 exfalso. pose proof (Qle_bool_iff q q0) as [_ H1].
1505 rewrite H1 in des. discriminate. exact q1.
1506 specialize (IHgas n xn (q0 :: yn)).
1507 destruct (Qle_bool q q0) eqn:des.
1508 simpl. rewrite IHgas. reflexivity. simpl.
1509 simpl in H. apply le_S_n in H. exact H. simpl in H0.
1510 apply le_S_n in H0. exact H0.
1511 exfalso. pose proof (Qle_bool_iff q q0) as [_ H1].
1512 rewrite H1 in des. discriminate. exact q1.
1513 Qed.
1514
1515 Lemma MergeInjectLInc
1516 : forall (gas n : nat) (xn yn : list Q),
1517 lt (length xn + length yn) gas
1518 -> lt (S n) (length xn)
1519 -> lt (MergeInjectL xn yn n) (MergeInjectL xn yn (S n)).
1520 Proof.
1521 induction gas.
1522 - intros. exfalso; inversion H.
1523 - intros. destruct xn. exfalso; inversion H0.
1524 destruct yn. apply Nat.le_refl.
1525 simpl. destruct (Qlt_le_dec q0 q).
1526 + apply le_n_S. apply (IHgas n (q :: xn) yn).
1527 simpl in H. apply le_S_n in H. simpl. rewrite Nat.add_succ_r in H.
1528 exact H. exact H0.
1529 + destruct n. apply le_n_S, Nat.le_0_l. apply le_n_S.
1530 apply IHgas. simpl in H. apply le_S_n in H. exact H.
1531 simpl in H0. apply le_S_n in H0. exact H0.
1532 Qed.
1533
1534 Lemma MergeInjectLBound
1535 : forall (gas n : nat) (xn yn : list Q),
1536 lt (length xn + length yn) gas
1537 -> lt n (length xn)
1538 -> lt (MergeInjectL xn yn n) (length xn + length yn).
1539 Proof.
1540 induction gas.
1541 - intros. exfalso; inversion H.
1542 - intros. destruct xn. exfalso; inversion H0.
1543 destruct yn. simpl. rewrite Nat.add_0_r. exact H0.
1544 simpl. destruct (Qlt_le_dec q0 q).
1545 + apply le_n_S. specialize (IHgas n (q :: xn) yn).
1546 rewrite Nat.add_succ_r. apply IHgas. simpl in H.
1547 apply le_S_n in H. rewrite Nat.add_succ_r in H.
1548 exact H. exact H0.
1549 + destruct n. apply le_n_S, Nat.le_0_l. apply le_n_S.
1550 apply IHgas. simpl in H. apply le_S_n in H. exact H.
1551 simpl in H0. apply le_S_n in H0. exact H0.
1552 Qed.
1553
1554 (* index of yn n inside merge xn yn.
1555 Inner fixpoint allows to prove that recursive calls terminate. *)
1556 Fixpoint MergeInjectR (xn yn : list Q) (n : nat) { struct xn } : nat
1557 := let fix merge_aux yn n :=
1558 match xn with
1559 | Datatypes.nil => n
1560 | Datatypes.cons x tx
1561 => match yn with
1562 | Datatypes.nil => O (* shouldn't happen *)
1563 | Datatypes.cons y ty
1564 => if Qlt_le_dec y x then
1565 (match n with O => O | S p => S (merge_aux ty p) end)
1566 else S (MergeInjectR tx yn n)
1567 end
1568 end
1569 in merge_aux yn n.
1570
1571 Lemma MergeInjectRSpec
1572 : forall (gas n : nat) (xn yn : list Q),
1573 lt (length xn + length yn) gas
1574 -> lt n (length yn)
1575 -> nth (MergeInjectR xn yn n) (merge xn yn) 0%Q
1576 = nth n yn 0%Q.
1577 Proof.
1578 induction gas.
1579 - intros. exfalso; inversion H.
1580 - intros. destruct xn.
1581 + simpl. destruct yn; reflexivity.
1582 + destruct yn. exfalso; inversion H0.
1583 simpl. destruct (Qlt_le_dec q0 q).
1584 * destruct n. destruct (Qle_bool q q0) eqn:des.
1585 exfalso. pose proof (Qle_bool_iff q q0) as [H1 _].
1586 apply (Qlt_not_le _ _ q1), H1, des. reflexivity.
1587 destruct (Qle_bool q q0) eqn:des.
1588 exfalso. pose proof (Qle_bool_iff q q0) as [H1 _].
1589 apply (Qlt_not_le _ _ q1), H1, des.
1590 specialize (IHgas n (q :: xn) yn). simpl. simpl in IHgas.
1591 rewrite IHgas. reflexivity. clear IHgas.
1592 simpl in H. apply le_S_n in H. rewrite Nat.add_succ_r in H.
1593 exact H. simpl in H0. apply le_S_n in H0. exact H0.
1594 * (* head of x first *)
1595 destruct (Qle_bool q q0) eqn:des.
1596 simpl. rewrite IHgas. reflexivity. simpl.
1597 simpl in H. apply le_S_n in H. exact H. simpl in H0.
1598 exact H0. exfalso. pose proof (Qle_bool_iff q q0) as [_ H1].
1599 rewrite H1 in des. discriminate. exact q1.
1600 Qed.
1601
1602 Lemma MergeInjectRInc
1603 : forall (gas n : nat) (xn yn : list Q),
1604 lt (length xn + length yn) gas
1605 -> lt (S n) (length yn)
1606 -> lt (MergeInjectR xn yn n) (MergeInjectR xn yn (S n)).
1607 Proof.
1608 induction gas.
1609 - intros. exfalso; inversion H.
1610 - intros. destruct yn as [|q0 yn]. exfalso; inversion H0.
1611 destruct xn as [|q xn]. apply Nat.le_refl.
1612 simpl. destruct (Qlt_le_dec q0 q).
1613 + destruct n. apply le_n_S, Nat.le_0_l. apply le_n_S.
1614 apply (IHgas n (q :: xn) yn).
1615 simpl in H. apply le_S_n in H. simpl. rewrite Nat.add_succ_r in H.
1616 exact H. simpl in H0. apply le_S_n in H0. exact H0.
1617 + apply le_n_S. apply IHgas.
1618 simpl in H. apply le_S_n in H. simpl.
1619 exact H. exact H0.
1620 Qed.
1621
1622 Lemma MergeInjectRBound
1623 : forall (gas n : nat) (xn yn : list Q),
1624 lt (length xn + length yn) gas
1625 -> lt n (length yn)
1626 -> lt (MergeInjectR xn yn n) (length xn + length yn).
1627 Proof.
1628 induction gas.
1629 - intros. exfalso; inversion H.
1630 - intros. destruct yn as [|q0 yn]. exfalso; inversion H0.
1631 destruct xn as [|q xn]. simpl. exact H0.
1632 simpl. destruct (Qlt_le_dec q0 q).
1633 + destruct n. apply le_n_S, Nat.le_0_l. apply le_n_S.
1634 rewrite Nat.add_succ_r.
1635 apply (IHgas n (q :: xn) yn). simpl in H.
1636 apply le_S_n in H. rewrite Nat.add_succ_r in H. exact H.
1637 simpl in H0. apply le_S_n in H0. exact H0.
1638 + apply le_n_S. apply (IHgas n xn (q0 :: yn)).
1639 simpl in H.
1640 apply le_S_n in H. exact H. exact H0.
1641 Qed.
1642
1643 Lemma LastCons : forall (xn : list Q) (q : Q),
1644 lt 0 (length xn) -> last (q :: xn) 0%Q = last xn 0%Q.
1645 Proof.
1646 intros. destruct xn. exfalso; inversion H. reflexivity.
1647 Qed.
1648
1649 Lemma MergeLast : forall (gas : nat) (xn yn : list Q),
1650 lt (length xn + length yn) gas
1651 -> (lt 0 (length xn) \/ lt 0 (length yn))
1652 -> ((lt 0 (length xn) /\ last (merge xn yn) 0%Q = last xn 0%Q)
1653 \/ (lt 0 (length yn) /\ last (merge xn yn) 0%Q = last yn 0%Q)).
1654 Proof.
1655 induction gas.
1656 - intros. exfalso; inversion H.
1657 - intros.
1658 destruct xn. right. split.
1659 destruct H0. exfalso; inversion H0. exact H0.
1660 destruct yn; reflexivity.
1661 (* xn not empty *)
1662 destruct yn. left.
1663 split. simpl. apply le_n_S, Nat.le_0_l. simpl. reflexivity.
1664 simpl. destruct (Qle_bool q q0) eqn:des.
1665 + specialize (IHgas xn (q0 :: yn)). simpl in IHgas.
1666 destruct IHgas.
1667 simpl in H. apply le_S_n in H. exact H.
1668 right. apply le_n_S, Nat.le_0_l.
1669 * destruct H1. left. split. apply le_n_S, Nat.le_0_l.
1670 rewrite LastCons.
1671 rewrite H2. destruct xn. exfalso; inversion H1. reflexivity.
1672 rewrite MergeLength. simpl.
1673 rewrite Nat.add_succ_r. apply le_n_S, Nat.le_0_l.
1674 * destruct H1 as [_ H1]. right. split.
1675 apply le_n_S, Nat.le_0_l. rewrite <- H1.
1676 pose proof (MergeLength xn (q0 :: yn)). simpl.
1677 destruct (merge xn (q0 :: yn)). exfalso. simpl in H2.
1678 rewrite Nat.add_succ_r in H2. discriminate. reflexivity.
1679 + specialize (IHgas (q :: xn) yn). destruct IHgas.
1680 simpl in H. apply le_S_n in H. rewrite Nat.add_succ_r in H.
1681 exact H. left. apply le_n_S, Nat.le_0_l.
1682 * destruct H1 as [_ H1]. left. split. apply le_n_S, Nat.le_0_l.
1683 rewrite LastCons. simpl in H1. rewrite H1. reflexivity.
1684 pose proof (MergeLength (q :: xn) yn). simpl in H2.
1685 rewrite H2. apply le_n_S, Nat.le_0_l.
1686 * destruct H1. right. split. apply le_n_S, Nat.le_0_l.
1687 rewrite LastCons. simpl in H2. rewrite H2.
1688 destruct yn. exfalso; inversion H1. reflexivity.
1689 pose proof (MergeLength (q :: xn) yn). simpl in H3.
1690 rewrite H3. apply le_n_S, Nat.le_0_l.
1691 Qed.
1692
1693 Lemma LastNth : forall (xn : list Q),
1694 lt 0 (length xn)
1695 -> last xn 0%Q = nth (pred (length xn)) xn 0%Q.
1696 Proof.
1697 induction xn.
1698 - reflexivity.
1699 - intros. clear H. destruct xn. reflexivity.
1700 transitivity (last (q :: xn) 0%Q). reflexivity.
1701 rewrite IHxn. reflexivity. simpl. apply le_n_S, Nat.le_0_l.
1702 Qed.
1703
1704
1705 Definition RationalPartitionMerge
1706 {R : ConstructiveReals} (a b : CRcarrier R)
1707 (P Q : @IntervalPartition R a b)
1708 : IntervalPartitionRational P
1709 -> IntervalPartitionRational Q
1710 -> @IntervalPartition R a b.
1711 Proof.
1712 intros.
1713 apply (Build_IntervalPartition
1714 R a b (fun n:nat => CR_of_Q R (nth n (merge (proj1_sig H) (proj1_sig H0)) 0%Q))
1715 (2+ipt_last P + ipt_last Q)).
1716 - destruct H, H0; unfold proj1_sig.
1717 destruct a0, a1. destruct x. exfalso; inversion H.
1718 destruct x0. exfalso; inversion H1.
1719 specialize (H0 O). simpl in H0. specialize (H2 O). simpl in H2.
1720 simpl. destruct (Qle_bool q q0) eqn:des.
1721 + simpl. rewrite <- H0. apply P. apply Nat.le_0_l.
1722 + exfalso. assert (q == q0)%Q.
1723 apply (@eq_inject_Q R). rewrite <- H0, <- H2.
1724 transitivity a. symmetry. apply P. apply Q.
1725 apply Nat.le_0_l. apply Nat.le_0_l.
1726 rewrite <- H3 in des. clear H3.
1727 pose proof (Qle_bool_iff q q) as [_ H4]. rewrite H4 in des.
1728 discriminate. apply Qle_refl.
1729 - destruct H, H0; unfold proj1_sig.
1730 destruct a0, a1.
1731 destruct (MergeLast (S (2+ ipt_last P + (2+ipt_last Q))) x x0).
1732 rewrite H, H1. apply Nat.le_refl. left. rewrite H. apply le_n_S, Nat.le_0_l.
1733 + rewrite LastNth, MergeLength in H3.
1734 rewrite (LastNth x), H in H3.
1735 simpl in H3. transitivity (ipt_seq P (S (ipt_last P))).
1736 apply P. rewrite H0. 2: apply Nat.le_refl. apply CR_of_Q_morph.
1737 destruct H3. rewrite <- H4, H1.
1738 replace (ipt_last P + (2 + ipt_last Q))%nat
1739 with (2 + ipt_last P + ipt_last Q)%nat.
1740 reflexivity. rewrite (Nat.add_comm 2), Nat.add_assoc. reflexivity.
1741 rewrite H. apply le_n_S, Nat.le_0_l.
1742 rewrite MergeLength. apply (Nat.lt_trans _ (0 + length x0)).
1743 simpl. rewrite H1. apply le_n_S, Nat.le_0_l.
1744 apply Nat.add_lt_mono_r. rewrite H. apply le_n_S, Nat.le_0_l.
1745 + rewrite LastNth, MergeLength in H3.
1746 rewrite (LastNth x0), H1 in H3.
1747 simpl in H3. transitivity (ipt_seq Q (S (ipt_last Q))).
1748 apply Q. rewrite H2. 2: apply Nat.le_refl. apply CR_of_Q_morph.
1749 destruct H3. rewrite <- H4, H. simpl.
1750 replace (ipt_last P + S (S (ipt_last Q)))%nat
1751 with (2 + ipt_last P + ipt_last Q)%nat.
1752 reflexivity. rewrite (Nat.add_comm 2), <- Nat.add_assoc. reflexivity.
1753 rewrite H1. apply le_n_S, Nat.le_0_l.
1754 rewrite MergeLength. apply (Nat.lt_trans _ (0 + length x0)).
1755 simpl. rewrite H1. apply le_n_S, Nat.le_0_l.
1756 apply Nat.add_lt_mono_r. rewrite H. apply le_n_S, Nat.le_0_l.
1757 - pose proof (PartitionRationalLocSorted
1758 a b P H) as sortP.
1759 pose proof (PartitionRationalLocSorted
1760 a b Q H0) as sortQ.
1761 intros. apply CR_of_Q_le.
1762 destruct H, H0; unfold proj1_sig; unfold proj1_sig in sortP, sortQ.
1763 pose proof (Sorted_merge x x0 sortP sortQ).
1764 apply (LocSortedFun _ H n).
1765 rewrite MergeLength. destruct a0, a1. rewrite H0, H3.
1766 simpl. apply le_n_S, le_n_S. apply (Nat.le_trans _ _ _ H1).
1767 do 2 rewrite Nat.add_succ_r. apply Nat.le_refl.
1768 Defined.
1769
1770 Lemma ordered_transit
1771 : forall (xn : nat -> nat) (last : nat),
1772 (forall n:nat, S n <= last -> xn n < xn (S n))%nat
1773 -> (forall n p:nat, lt n p -> p <= last -> (xn n < xn p))%nat.
1774 Proof.
1775 induction p.
1776 - intros. exfalso. inversion H0.
1777 - intros. apply Nat.le_succ_r in H0. destruct H0.
1778 apply (Nat.lt_trans _ (xn p)). apply IHp. exact H0.
1779 apply (Nat.le_trans _ (S p)). apply le_S, Nat.le_refl. exact H1.
1780 apply H. exact H1. inversion H0. subst n.
1781 apply H. exact H1.
1782 Qed.
1783
1784 Definition CommonChaslesRefinement
1785 {R : ConstructiveReals} {a b : CRcarrier R}
1786 (P Q : @IntervalPartition R a b)
1787 : Prop
1788 := exists (ccr_subseqP : nat -> nat) (ccr_subseqQ : nat -> nat)
1789 (ccr_refinement : @IntervalPartition R a b),
1790 IntervalPartitionRefinement
1791 a b P ccr_refinement ccr_subseqP
1792 /\ IntervalPartitionRefinement
1793 a b Q ccr_refinement ccr_subseqQ.
1794
1795 (* The rational numbers have a total order, which allows
1796 to merge 2 sorted lists. *)
1797 Lemma CommonRationalRefinement
1798 : forall {R : ConstructiveReals} (a b : CRcarrier R)
1799 (P Q : @IntervalPartition R a b),
1800 IntervalPartitionRational P
1801 -> IntervalPartitionRational Q
1802 -> @CommonChaslesRefinement R a b P Q.
1803 Proof.
1804 intros.
1805 exists (fun n => MergeInjectL (proj1_sig H) (proj1_sig H0) n),
1806 (fun n => MergeInjectR (proj1_sig H) (proj1_sig H0) n),
1807 (RationalPartitionMerge a b P Q H H0).
1808 split.
1809 - destruct H,H0; unfold proj1_sig.
1810 split. 2: split.
1811 + intros. unfold RationalPartitionMerge, ipt_seq; unfold proj1_sig.
1812 destruct P,Q; simpl in a0; unfold ipt_last in H; unfold ipt_last;
1813 unfold ipt_last, ipt_seq in a1.
1814 destruct a0, a1. rewrite H1. 2: exact H.
1815 apply CR_of_Q_morph.
1816 rewrite (MergeInjectLSpec (S (2 + ipt_last0 + (2+ ipt_last1)))).
1817 reflexivity.
1818 rewrite H0, H2. apply Nat.le_refl.
1819 rewrite H0. apply le_n_S, H.
1820 + apply ordered_transit. intros. destruct a0, a1.
1821 apply (MergeInjectLInc (S (2 + ipt_last P + (2+ ipt_last Q)))).
1822 rewrite H0, H2. apply Nat.le_refl.
1823 rewrite H0. apply le_n_S, H.
1824 + unfold RationalPartitionMerge, ipt_last.
1825 destruct P,Q; simpl in a0, a1.
1826 intros. destruct a0, a1. apply le_S_n.
1827 apply (Nat.le_trans _ (S (S ipt_last0) + S (S ipt_last1))).
1828 rewrite <- H0, <- H2.
1829 apply (MergeInjectLBound (S (2 + ipt_last0 + (2+ ipt_last1)))).
1830 rewrite H0, H2. apply Nat.le_refl.
1831 rewrite H0. apply le_n_S, H.
1832 simpl. do 2 rewrite Nat.add_succ_r. apply Nat.le_refl.
1833 - destruct H,H0; unfold proj1_sig.
1834 split. 2: split.
1835 + intros. unfold RationalPartitionMerge, ipt_seq; unfold proj1_sig.
1836 destruct P,Q; simpl in a0; unfold ipt_last in H; unfold ipt_last;
1837 unfold ipt_last, ipt_seq in a1.
1838 destruct a0, a1. rewrite H3. 2: exact H.
1839 apply CR_of_Q_morph.
1840 rewrite (MergeInjectRSpec (S (2 + ipt_last0 + (2+ ipt_last1)))).
1841 reflexivity.
1842 rewrite H0, H2. apply Nat.le_refl.
1843 rewrite H2. apply le_n_S, H.
1844 + apply ordered_transit. intros. destruct a0, a1.
1845 apply (MergeInjectRInc (S (2 + ipt_last P + (2+ ipt_last Q)))).
1846 rewrite H0, H2. apply Nat.le_refl.
1847 rewrite H2. apply le_n_S, H.
1848 + unfold RationalPartitionMerge, ipt_last.
1849 destruct P,Q; simpl in a0, a1.
1850 intros. destruct a0, a1. apply le_S_n.
1851 apply (Nat.le_trans _ (S (S ipt_last0) + S (S ipt_last1))).
1852 rewrite <- H0, <- H2.
1853 apply (MergeInjectRBound (S (2 + ipt_last0 + (2+ ipt_last1)))).
1854 rewrite H0, H2. apply Nat.le_refl.
1855 rewrite H2. apply le_n_S, H.
1856 simpl. do 2 rewrite Nat.add_succ_r. apply Nat.le_refl.
1857 Qed.
1858
1859 (* Need a total order to merge partitions. Keep them rational for now,
1860 it is sufficient to bootstrap the constructive theory of measure. *)
1861 Lemma UC_integral_chasles_rat
1862 : forall {R : ConstructiveReals} (a b c : Q)
1863 (f : CRcarrier R -> CRcarrier R)
1864 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
1865 (fCont : UniformCont f cont_mod)
1866 (leab : (CR_of_Q R a) <= (CR_of_Q R b))
1867 (lebc : (CR_of_Q R b) <= (CR_of_Q R c))
1868 (leac : (CR_of_Q R a) <= (CR_of_Q R c)),
1869 UC_integral f (CR_of_Q R a) (CR_of_Q R c) cont_mod fCont leac
1870 == UC_integral f (CR_of_Q R a) (CR_of_Q R b) cont_mod fCont leab
1871 + UC_integral f (CR_of_Q R b) (CR_of_Q R c) cont_mod fCont lebc.
1872 Proof.
1873 intros. unfold UC_integral.
1874 destruct (CR_complete R
1875 (fun last : nat =>
1876 IntegralFiniteSum
1877 f (fun n : nat => (CR_of_Q R a + (CR_of_Q R c - CR_of_Q R a)
1878 * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))))
1879 (fun n : nat => (CR_of_Q R a + (CR_of_Q R c - CR_of_Q R a)
1880 * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))) last)
1881 (UC_integral_cauchy f (CR_of_Q R a) (CR_of_Q R c) cont_mod fCont leac)) as [l lcv].
1882 destruct (CR_complete R
1883 (fun last : nat =>
1884 IntegralFiniteSum f
1885 (fun n : nat =>
1886 CR_of_Q R a + (CR_of_Q R b - CR_of_Q R a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
1887 (fun n : nat =>
1888 CR_of_Q R a + (CR_of_Q R b - CR_of_Q R a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
1889 (UC_integral_cauchy f (CR_of_Q R a) (CR_of_Q R b) cont_mod fCont leab)) as [lab H].
1890 destruct (CR_complete R
1891 (fun last : nat =>
1892 IntegralFiniteSum f
1893 (fun n : nat =>
1894 CR_of_Q R b + (CR_of_Q R c - CR_of_Q R b) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
1895 (fun n : nat =>
1896 CR_of_Q R b + (CR_of_Q R c - CR_of_Q R b) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
1897 (UC_integral_cauchy f (CR_of_Q R b) (CR_of_Q R c) cont_mod fCont lebc)) as [lbc H0].
1898 apply (CR_cv_unique _ _ _ lcv).
1899 intros n.
1900 assert (0 < 1+CR_of_Q R c - CR_of_Q R a) as invStepPos.
1901 { apply (CRlt_le_trans _ (1 + 0)).
1902 rewrite CRplus_0_r. apply CRzero_lt_one. unfold CRminus. rewrite CRplus_assoc.
1903 apply CRplus_le_compat_l. rewrite <- (CRplus_opp_r (CR_of_Q R a)).
1904 apply CRplus_le_compat. exact leac. apply CRle_refl. }
1905 assert (0 < CR_of_Q R (1 # 4*n) * CRinv R (1+CR_of_Q R c - CR_of_Q R a) (inr invStepPos))
1906 as stepPos.
1907 { apply CRmult_lt_0_compat.
1908 apply CR_of_Q_lt; reflexivity.
1909 apply CRinv_0_lt_compat. exact invStepPos. }
1910 destruct (CRup_nat ((CR_of_Q R c-CR_of_Q R a) * CRinv R (cont_mod _ stepPos) (inr ((fst fCont) _ stepPos))))
1911 as [p pmaj].
1912 destruct (CRup_nat ((CR_of_Q R b-CR_of_Q R a) * CRinv R (cont_mod _ stepPos) (inr ((fst fCont) _ stepPos))))
1913 as [q qmaj].
1914 destruct (CRup_nat ((CR_of_Q R c-CR_of_Q R b) * CRinv R (cont_mod _ stepPos) (inr ((fst fCont) _ stepPos))))
1915 as [r rmaj].
1916 specialize (H (4*n)%positive) as [i imaj].
1917 specialize (H0 (4*n)%positive) as [j jmaj].
1918 exists p. intros i0 H.
1919 pose (IntervalPartitionConcat
1920 (IntervalEquiPartition (CR_of_Q R a) (CR_of_Q R b) (max i q) leab)
1921 (IntervalEquiPartition (CR_of_Q R b) (CR_of_Q R c) (max j r) lebc))
1922 as conc.
1923 setoid_replace (IntegralFiniteSum f
1924 (fun n0 : nat =>
1925 CR_of_Q R a + (CR_of_Q R c - CR_of_Q R a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S i0)))
1926 (fun n0 : nat =>
1927 CR_of_Q R a + (CR_of_Q R c - CR_of_Q R a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S i0))) i0 -
1928 (lab + lbc))
1929 with (IntegralFiniteSum f
1930 (fun n0 : nat =>
1931 CR_of_Q R a + (CR_of_Q R c - CR_of_Q R a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S i0)))
1932 (fun n0 : nat =>
1933 CR_of_Q R a + (CR_of_Q R c - CR_of_Q R a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S i0))) i0
1934 - IntegralFiniteSum f (ipt_seq conc) (ipt_seq conc) (ipt_last conc)
1935 + (IntegralFiniteSum f (ipt_seq conc) (ipt_seq conc) (ipt_last conc)
1936 - (lab + lbc))).
1937 apply (CRle_trans _ _ _ (CRabs_triang _ _)).
1938 setoid_replace (CR_of_Q R (1 # n))
1939 with (CR_of_Q R (1 # 2*n) + CR_of_Q R (1 # 2*n)).
1940 apply CRplus_le_compat.
1941 - apply (CRle_trans
1942 _ ((CR_of_Q R (1# 4*n) * CRinv R (1+CR_of_Q R c - CR_of_Q R a) (inr invStepPos)
1943 + CR_of_Q R (1# 4*n) * CRinv R (1+CR_of_Q R c - CR_of_Q R a) (inr invStepPos))
1944 * (CR_of_Q R c-CR_of_Q R a))).
1945 destruct (CommonRationalRefinement
1946 (CR_of_Q R a) (CR_of_Q R c) (IntervalEquiPartition (CR_of_Q R a) (CR_of_Q R c) i0 leac) conc)
1947 as [ccr_subseqP0 [ccr_subseqQ0 [ccr_refinement0 [ccr_refineP0 ccr_refineQ0]]]].
1948 apply EquiPartitionRational. apply PartitionRationalConcat.
1949 apply EquiPartitionRational. apply EquiPartitionRational.
1950 apply (UC_compare_integrals
1951 f (CR_of_Q R a) (CR_of_Q R c) _ _
1952 cont_mod (IntervalEquiPartition (CR_of_Q R a) (CR_of_Q R c) i0 leac)
1953 conc ccr_refinement0
1954 stepPos stepPos ccr_subseqP0 ccr_subseqQ0
1955 fCont ccr_refineP0 ccr_refineQ0).
1956 + rewrite EquiPartitionMesh.
1957 apply (CRmult_lt_compat_r (cont_mod _ stepPos)) in pmaj.
1958 2: apply (fst fCont).
1959 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in pmaj.
1960 apply (CRmult_lt_reg_r (CR_of_Q R (Z.of_nat (S i0) # 1))).
1961 apply CR_of_Q_lt; reflexivity.
1962 rewrite CRmult_assoc, <- CR_of_Q_mult.
1963 setoid_replace ((1 # Pos.of_nat (S i0)) * (Z.of_nat (S i0) # 1))%Q with 1%Q.
1964 rewrite CRmult_1_r. apply (CRlt_le_trans _ _ _ pmaj).
1965 rewrite CRmult_comm. apply CRmult_le_compat_l.
1966 apply CRlt_asym, (fst fCont). apply CR_of_Q_le.
1967 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r. apply Nat2Z.inj_le, le_S, H.
1968 unfold Qmult, Qeq, Qnum, Qden.
1969 do 2 rewrite Z.mul_1_l. rewrite Z.mul_1_r, Pos.mul_1_r.
1970 rewrite <- positive_nat_Z. rewrite Nat2Pos.id. reflexivity. discriminate.
1971 + assert (PartitionMesh (ipt_seq conc) (S (ipt_last conc))
1972 == CRmax ((CR_of_Q R b- CR_of_Q R a) * CR_of_Q R (1# Pos.of_nat (S (max i q))))
1973 ((CR_of_Q R c- CR_of_Q R b) * CR_of_Q R (1# Pos.of_nat (S (max j r))))).
1974 { unfold conc. rewrite PartitionMeshConcat.
1975 apply CRmax_morph; apply EquiPartitionMesh. }
1976 rewrite H0. apply CRmax_lub_lt.
1977 apply (CRmult_lt_compat_r (cont_mod _ stepPos)) in qmaj.
1978 2: apply (fst fCont).
1979 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in qmaj.
1980 apply (CRmult_lt_reg_r
1981 (CR_of_Q R (Z.of_nat (S (Init.Nat.max i q)) # 1))).
1982 apply CR_of_Q_lt; reflexivity.
1983 rewrite CRmult_assoc, <- CR_of_Q_mult.
1984 setoid_replace ((1 # Pos.of_nat (S (Init.Nat.max i q))) * (Z.of_nat (S (Init.Nat.max i q)) # 1))%Q
1985 with 1%Q.
1986 rewrite CRmult_1_r. apply (CRlt_le_trans _ _ _ qmaj).
1987 rewrite CRmult_comm. apply CRmult_le_compat_l.
1988 apply CRlt_asym, (fst fCont). apply CR_of_Q_le.
1989 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
1990 apply Nat2Z.inj_le, le_S, Nat.le_max_r.
1991 unfold Qmult, Qeq, Qnum, Qden.
1992 do 2 rewrite Z.mul_1_l. rewrite Z.mul_1_r, Pos.mul_1_r.
1993 rewrite <- positive_nat_Z. rewrite Nat2Pos.id. reflexivity. discriminate.
1994
1995 apply (CRmult_lt_compat_r (cont_mod _ stepPos)) in rmaj.
1996 2: apply (fst fCont).
1997 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in rmaj.
1998 apply (CRmult_lt_reg_r
1999 (CR_of_Q R (Z.of_nat (S (Init.Nat.max j r)) # 1))).
2000 apply CR_of_Q_lt; reflexivity.
2001 rewrite CRmult_assoc, <- CR_of_Q_mult.
2002 setoid_replace ((1 # Pos.of_nat (S (Init.Nat.max j r))) * (Z.of_nat (S (Init.Nat.max j r)) # 1))%Q
2003 with 1%Q.
2004 rewrite CRmult_1_r. apply (CRlt_le_trans _ _ _ rmaj).
2005 rewrite CRmult_comm. apply CRmult_le_compat_l.
2006 apply CRlt_asym, (fst fCont). apply CR_of_Q_le.
2007 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
2008 apply Nat2Z.inj_le, le_S, Nat.le_max_r.
2009 unfold Qmult, Qeq, Qnum, Qden.
2010 do 2 rewrite Z.mul_1_l. rewrite Z.mul_1_r, Pos.mul_1_r.
2011 rewrite <- positive_nat_Z. rewrite Nat2Pos.id. reflexivity. discriminate.
2012 + rewrite <- (CRmult_1_r
2013 (CR_of_Q R (1 # 4 * n) * CRinv R (1 + CR_of_Q R c - CR_of_Q R a) (inr invStepPos))).
2014 rewrite <- CRmult_plus_distr_l. rewrite (CRmult_comm (CR_of_Q R (1#4*n))).
2015 apply (CRmult_le_reg_l (1 + CR_of_Q R c - CR_of_Q R a)).
2016 exact invStepPos.
2017 do 3 rewrite <- CRmult_assoc. rewrite CRinv_r, CRmult_1_l.
2018 setoid_replace (CR_of_Q R (1 # 4 * n) * (1 + 1))
2019 with (CR_of_Q R (1 # 2 * n)).
2020 rewrite CRmult_comm. apply CRmult_le_compat_r.
2021 apply CR_of_Q_le. discriminate.
2022 rewrite <- (CRplus_0_l (CR_of_Q R c - CR_of_Q R a)).
2023 unfold CRminus. rewrite CRplus_assoc.
2024 apply CRplus_le_compat_r.
2025 exact (CRlt_asym 0 1 (CRzero_lt_one R)).
2026 rewrite <- (CR_of_Q_plus R 1 1), <- CR_of_Q_mult.
2027 apply CR_of_Q_morph. unfold Qeq, Qnum, Qden. simpl.
2028 rewrite Pos.mul_1_r. reflexivity.
2029 - unfold conc.
2030 rewrite <- IntervalPartitionConcatSum.
2031 unfold IntervalEquiPartition, ipt_seq, ipt_last.
2032 setoid_replace (CR_of_Q R (1 # 2 * n))
2033 with (CR_of_Q R (1 # 4 * n) + CR_of_Q R (1 # 4 * n)).
2034 assert (forall a b c d : CRcarrier R,
2035 CRabs _ (a + b - (c + d)) <= CRabs _ (a - c) + CRabs _ (b - d)).
2036 intros.
2037 setoid_replace (a0 + b0 - (c0 + d)) with ((a0 - c0) + (b0 - d)).
2038 apply CRabs_triang. unfold CRminus.
2039 do 2 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
2040 rewrite (CRplus_comm (-c0)).
2041 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
2042 rewrite CRopp_plus_distr, CRplus_comm. reflexivity.
2043 apply (CRle_trans _ _ _ (H0 _ _ _ _)). apply CRplus_le_compat.
2044 apply imaj, Nat.le_max_l.
2045 apply jmaj, Nat.le_max_l.
2046 rewrite <- CR_of_Q_plus, Qinv_plus_distr. apply CR_of_Q_morph.
2047 reflexivity.
2048 - rewrite <- CR_of_Q_plus, Qinv_plus_distr. apply CR_of_Q_morph.
2049 reflexivity.
2050 - unfold CRminus. rewrite CRplus_assoc.
2051 apply CRplus_morph. reflexivity.
2052 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
2053 Qed.
2054
2055 Lemma UC_right_bound_cv
2056 : forall {R : ConstructiveReals} (a b : CRcarrier R)
2057 (bn : nat -> CRcarrier R)
2058 (f : CRcarrier R -> CRcarrier R)
2059 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2060 (fCont : UniformCont f cont_mod)
2061 (leab : a <= b)
2062 (lebbn : forall n:nat, b <= bn n),
2063 CR_cv R bn b
2064 -> CR_cv R
2065 (fun n : nat =>
2066 UC_integral f a (bn n) cont_mod fCont
2067 (CRle_trans a b (bn n) leab (lebbn n)))
2068 (UC_integral f a b cont_mod fCont leab).
2069 Proof.
2070 intros. intro p.
2071 assert (0 < CR_of_Q R (1 # p)).
2072 { apply CR_of_Q_pos. reflexivity. }
2073 destruct (UC_right_bound_continuous
2074 f a b leab _ H0 cont_mod fCont) as [eta [etaPos etaMaj]].
2075 pose proof (Un_cv_nat_real _ _ H eta etaPos) as [n nmaj].
2076 exists n. intros. rewrite CRabs_minus_sym.
2077 assert (bn i < b + eta).
2078 { specialize (nmaj i H1). apply (CRplus_lt_reg_l R (-b)).
2079 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l, CRplus_comm.
2080 exact (CRle_lt_trans _ _ _ (CRle_abs _) nmaj). }
2081 apply (etaMaj (bn i) (pair (lebbn i) H2)).
2082 Qed.
2083
2084 Lemma UC_integral_chasles_rat_rat
2085 : forall {R : ConstructiveReals} (a b : Q) (c : CRcarrier R)
2086 (f : CRcarrier R -> CRcarrier R)
2087 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2088 (fCont : UniformCont f cont_mod)
2089 (leab : (CR_of_Q R a) <= (CR_of_Q R b))
2090 (lebc : (CR_of_Q R b) <= c)
2091 (leac : (CR_of_Q R a) <= c),
2092 UC_integral f (CR_of_Q R a) c cont_mod fCont leac
2093 == UC_integral f (CR_of_Q R a) (CR_of_Q R b) cont_mod fCont leab
2094 + UC_integral f (CR_of_Q R b) c cont_mod fCont lebc.
2095 Proof.
2096 intros.
2097 assert (forall n : nat, c < c + CR_of_Q R (1 # Pos.of_nat (S n))).
2098 { intro n. apply (CRle_lt_trans _ (c+0)). rewrite CRplus_0_r.
2099 apply CRle_refl. apply CRplus_lt_compat_l, CR_of_Q_pos. reflexivity. }
2100 pose (fun n => let (q,_) := CR_Q_dense R c (c + CR_of_Q R (1 # Pos.of_nat (S n))) (H n) in q)
2101 as cn.
2102 assert (forall n:nat, c <= CR_of_Q R (cn n)) as H0.
2103 { intro n. unfold cn.
2104 destruct (CR_Q_dense R c (c + CR_of_Q R (1 # Pos.of_nat (S n))) (H n)).
2105 apply CRlt_asym, p. }
2106 assert (CR_cv R (fun n : nat => CR_of_Q R (cn n)) c) as cvRight.
2107 { intro p. exists (Pos.to_nat p).
2108 intros. unfold cn.
2109 destruct (CR_Q_dense R c (c + CR_of_Q R (1 # Pos.of_nat (S i))) (H i)).
2110 rewrite CRabs_right.
2111 apply (CRplus_le_reg_r c). unfold CRminus.
2112 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_comm.
2113 apply CRlt_asym, (CRlt_le_trans _ _ _ (snd p0)).
2114 apply CRplus_le_compat_l. apply CR_of_Q_le. apply Pos2Z.pos_le_pos.
2115 unfold Qden. do 2 rewrite Pos.mul_1_l. apply Pos2Nat.inj_le.
2116 rewrite Nat2Pos.id. apply le_S, H1. discriminate.
2117 rewrite <- (CRplus_opp_r c). apply CRplus_le_compat_r.
2118 apply CRlt_asym, p0. }
2119 apply (CR_cv_unique (fun n => UC_integral f (CR_of_Q R a)
2120 (CR_of_Q R (cn n))
2121 cont_mod fCont
2122 (CRle_trans _ _ _ leac (H0 n)))).
2123 - apply (UC_right_bound_cv
2124 (CR_of_Q R a) c (fun n => CR_of_Q R (cn n)) f cont_mod fCont leac).
2125 exact cvRight.
2126 - apply (CR_cv_eq _ (fun n : nat =>
2127 UC_integral f (CR_of_Q R a) (CR_of_Q R b) cont_mod fCont leab
2128 + UC_integral f (CR_of_Q R b) (CR_of_Q R (cn n))
2129 cont_mod fCont (CRle_trans _ _ _ lebc (H0 n)))).
2130 intro n. symmetry.
2131 apply (UC_integral_chasles_rat a b (cn n) f).
2132 apply CR_cv_plus. apply CR_cv_const.
2133 exact (UC_right_bound_cv (CR_of_Q R b) c (fun n => CR_of_Q R (cn n)) f _ _ _ _ cvRight).
2134 Qed.
2135
2136 Lemma UC_integral_slide_cv
2137 : forall {R : ConstructiveReals}
2138 (a b : CRcarrier R)
2139 (f : CRcarrier R -> CRcarrier R)
2140 (cont_mod : forall eps : CRcarrier R, 0 < eps -> CRcarrier R)
2141 (fCont : UniformCont f cont_mod)
2142 (leab : a <= b)
2143 (an : nat -> CRcarrier R)
2144 (lebbn : forall n:nat, an n <= b + (an n - a)),
2145 CR_cv R an a
2146 -> CR_cv R
2147 (fun n : nat => UC_integral f (an n) (b + (an n - a))
2148 cont_mod fCont (lebbn n))
2149 (UC_integral f a b cont_mod fCont leab).
2150 Proof.
2151 intros. intro p.
2152 assert (forall i j k : CRcarrier R, i + j - (i + k) == j - k) as addSub.
2153 { intros. unfold CRminus. rewrite CRopp_plus_distr.
2154 rewrite <- CRplus_assoc. apply CRplus_morph. 2: reflexivity.
2155 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity. }
2156 assert (0 < b-a+1).
2157 { rewrite <- (CRplus_opp_l a). unfold CRminus.
2158 rewrite (CRplus_comm b), CRplus_assoc. apply CRplus_lt_compat_l.
2159 apply (CRle_lt_trans _ (b+0)). rewrite CRplus_0_r. exact leab.
2160 apply CRplus_lt_compat_l, CRzero_lt_one. }
2161 assert (0 < CR_of_Q R (1#p) * CRinv R (b-a+1) (inr H0)) as H1.
2162 { destruct fCont. apply CRmult_lt_0_compat.
2163 apply CR_of_Q_pos. reflexivity.
2164 apply CRinv_0_lt_compat, H0. }
2165 pose proof (Un_cv_nat_real _ _ H _ (fst fCont _ H1)) as [n nmaj].
2166 exists n. intros.
2167 apply (CR_cv_bound_up
2168 (fun last : nat => CRabs R (IntegralFiniteSum
2169 f (fun n => an i + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2170 (fun n => an i + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last
2171 - IntegralFiniteSum
2172 f (fun n => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2173 (fun n => a + (b-a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last))
2174 (CR_of_Q R (1#p)) _ O).
2175 - intros n0 _. unfold IntegralFiniteSum.
2176 unfold CRminus. rewrite <- sum_opp, <- sum_plus.
2177 rewrite (CRsum_eq _ (fun n1 => (f (an i + (b + - a) * CR_of_Q R (Z.of_nat n1 # Pos.of_nat (S n0)))
2178 - f (a + (b + - a) * CR_of_Q R (Z.of_nat n1 # Pos.of_nat (S n0))))
2179 * (b + - a) * CR_of_Q R (1 # Pos.of_nat (S n0)))).
2180 + rewrite sum_scale, sum_scale.
2181 specialize (nmaj i H2). rewrite CRmult_assoc, CRabs_mult.
2182 apply (CRle_trans
2183 _ ((CRsum (fun _ : nat => CR_of_Q R (1 # p) * CRinv R (b - a + 1) (inr H0)) n0) * CRabs R (CR_of_Q R (1 # Pos.of_nat (S n0)) * (b + - a)))).
2184 rewrite <- (CRmult_comm (b+-a)).
2185 apply CRmult_le_compat_r. apply CRabs_pos.
2186 apply (CRle_trans _ _ _ (multiTriangleIneg _ _)). apply sum_Rle.
2187 intros. apply CRlt_asym, (snd fCont _ _ _ H1).
2188 rewrite (CRplus_comm (an i)), (CRplus_comm a), addSub. exact nmaj.
2189 rewrite sum_const, CRabs_right,
2190 CRmult_assoc, <- (CRmult_1_r (CR_of_Q R (1 # p))).
2191 do 2 rewrite CRmult_assoc. apply CRmult_le_compat_l.
2192 apply CRlt_asym, CR_of_Q_pos. reflexivity. rewrite CRmult_1_l.
2193 unfold INR. rewrite CRmult_comm, <- CRmult_assoc. rewrite <- CR_of_Q_mult.
2194 setoid_replace ((Z.of_nat (S n0) # 1) * (1 # Pos.of_nat (S n0)))%Q with 1%Q.
2195 rewrite CRmult_1_l. apply (CRmult_le_reg_r (b-a+1) _ _ H0).
2196 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_1_l.
2197 apply (CRle_trans _ (b-a + 0)). rewrite CRplus_0_r. apply CRle_refl.
2198 apply CRplus_le_compat_l. apply CRlt_asym, CRzero_lt_one.
2199 unfold Z.of_nat. rewrite Pos.of_nat_succ.
2200 unfold Qeq. simpl. do 2 rewrite Pos.mul_1_r. reflexivity.
2201 apply CRmult_le_0_compat.
2202 apply CR_of_Q_le. discriminate.
2203 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat_r. exact leab.
2204 + intros.
2205 rewrite (addSub (an i) ((b + - a) * CR_of_Q R (Z.of_nat (S i0) # Pos.of_nat (S n0))) ((b + - a) * CR_of_Q R (Z.of_nat i0 # Pos.of_nat (S n0)))).
2206 rewrite (addSub a ((b + - a) * CR_of_Q R (Z.of_nat (S i0) # Pos.of_nat (S n0))) ((b + - a) * CR_of_Q R (Z.of_nat i0 # Pos.of_nat (S n0)))).
2207 rewrite CRopp_mult_distr_l, <- CRmult_plus_distr_r.
2208 unfold CRminus. rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l.
2209 rewrite CRmult_assoc. apply CRmult_morph. reflexivity.
2210 apply CRmult_morph. reflexivity.
2211 rewrite <- CR_of_Q_opp, <- CR_of_Q_plus. apply CR_of_Q_morph.
2212 rewrite Qinv_minus_distr.
2213 replace (Z.of_nat (S i0) - Z.of_nat i0)%Z with 1%Z. reflexivity.
2214 rewrite Nat2Z.inj_succ. unfold Z.succ. ring.
2215 - apply CR_cv_abs_cont. apply CR_cv_minus.
2216 unfold UC_integral.
2217 destruct (CR_complete R
2218 (fun last : nat =>
2219 IntegralFiniteSum f
2220 (fun n0 : nat => an i + (b + (an i - a) - an i) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last)))
2221 (fun n0 : nat => an i + (b + (an i - a) - an i) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last))) last)
2222 (UC_integral_cauchy f (an i) (b + (an i - a)) cont_mod fCont (lebbn i))).
2223 apply (CR_cv_eq _ (fun last : nat =>
2224 IntegralFiniteSum f
2225 (fun n0 : nat =>
2226 an i +
2227 (b + (an i - a) - an i) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last)))
2228 (fun n0 : nat =>
2229 an i +
2230 (b + (an i - a) - an i) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last)))
2231 last)).
2232 2: exact c. intros. apply CRsum_eq. intros.
2233 rewrite (UniformContProper f cont_mod fCont
2234 _ (an i + (b - a) * CR_of_Q R (Z.of_nat i0 # Pos.of_nat (S n0)))).
2235 setoid_replace (b + (an i - a) - an i) with (b-a). reflexivity.
2236 unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph.
2237 reflexivity. rewrite CRplus_comm, <- CRplus_assoc.
2238 rewrite CRplus_opp_l. apply CRplus_0_l.
2239 apply CRplus_morph. reflexivity. apply CRmult_morph.
2240 2: reflexivity.
2241 unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph.
2242 reflexivity. rewrite CRplus_comm, <- CRplus_assoc.
2243 rewrite CRplus_opp_l. apply CRplus_0_l.
2244 unfold UC_integral.
2245 destruct (CR_complete R
2246 (fun last : nat =>
2247 IntegralFiniteSum f
2248 (fun n0 : nat => a + (b - a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last)))
2249 (fun n0 : nat => a + (b - a) * CR_of_Q R (Z.of_nat n0 # Pos.of_nat (S last))) last)
2250 (UC_integral_cauchy f a b cont_mod fCont leab)).
2251 exact c.
2252 Qed.
2253
2254 Lemma UC_integral_chasles_rat_rat_rat
2255 : forall {R : ConstructiveReals} (a : Q) (b c : CRcarrier R)
2256 (f : CRcarrier R -> CRcarrier R)
2257 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2258 (fCont : UniformCont f cont_mod)
2259 (leab : (CR_of_Q R a) <= b)
2260 (lebc : b <= c)
2261 (leac : (CR_of_Q R a) <= c),
2262 UC_integral f (CR_of_Q R a) c cont_mod fCont leac
2263 == UC_integral f (CR_of_Q R a) b cont_mod fCont leab
2264 + UC_integral f b c cont_mod fCont lebc.
2265 Proof.
2266 intros.
2267 assert (forall n : nat, b < b + CR_of_Q R (1 # Pos.of_nat (S n))).
2268 { intro n. apply (CRle_lt_trans _ (b+0)). rewrite CRplus_0_r.
2269 apply CRle_refl. apply CRplus_lt_compat_l, CR_of_Q_pos. reflexivity. }
2270 pose (fun n => let (q,_) := CR_Q_dense R b (b + CR_of_Q R (1 # Pos.of_nat (S n))) (H n) in q)
2271 as bn.
2272 assert (CR_cv R (fun n : nat => CR_of_Q R (bn n)) b) as cvb.
2273 { intro p. exists (Pos.to_nat p).
2274 intros. unfold bn.
2275 destruct (CR_Q_dense R b (b + CR_of_Q R (1 # Pos.of_nat (S i))) (H i)).
2276 rewrite CRabs_right.
2277 apply (CRplus_le_reg_r b). unfold CRminus.
2278 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_comm.
2279 apply CRlt_asym, (CRlt_le_trans _ _ _ (snd p0)).
2280 apply CRplus_le_compat_l. apply CR_of_Q_le. apply Pos2Z.pos_le_pos.
2281 unfold Qden. do 2 rewrite Pos.mul_1_l. apply Pos2Nat.inj_le.
2282 rewrite Nat2Pos.id. apply le_S, H0. discriminate.
2283 rewrite <- (CRplus_opp_r b). apply CRplus_le_compat_r.
2284 apply CRlt_asym, p0. }
2285 assert (forall n:nat, b <= CR_of_Q R (bn n)) as H0.
2286 { intro n. unfold bn.
2287 destruct (CR_Q_dense R b (b + CR_of_Q R (1 # Pos.of_nat (S n))) (H n)).
2288 apply CRlt_asym, p. }
2289 pose (fun n => c + (CR_of_Q R (bn n) - b)) as cn.
2290 assert (forall n:nat, CR_of_Q R (bn n) <= cn n).
2291 { intro n. unfold cn. rewrite CRplus_comm.
2292 apply (CRplus_le_reg_r (-c)).
2293 rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r.
2294 apply CRplus_le_compat_l, CRopp_ge_le_contravar. exact lebc. }
2295 apply (CR_cv_unique (fun n => UC_integral f (CR_of_Q R a)
2296 (CR_of_Q R (bn n))
2297 cont_mod fCont
2298 (CRle_trans _ _ _ leab (H0 n))
2299 + UC_integral f (CR_of_Q R (bn n)) (cn n)
2300 cont_mod fCont
2301 (H1 n))).
2302 - (* Use Chasles relation *)
2303 assert (forall n:nat, c <= cn n) as H2.
2304 { intro n. unfold cn.
2305 apply (CRle_trans _ (c+0)). rewrite CRplus_0_r. apply CRle_refl.
2306 apply CRplus_le_compat_l. rewrite <- (CRplus_opp_r b).
2307 apply CRplus_le_compat_r. apply H0. }
2308 apply (CR_cv_eq _ (fun n : nat =>
2309 UC_integral f (CR_of_Q R a) (cn n) cont_mod fCont
2310 (CRle_trans _ _ _ leac (H2 n)))).
2311 intro n. apply UC_integral_chasles_rat_rat.
2312 apply UC_right_bound_cv. unfold cn.
2313 apply (CR_cv_proper _ (b+(c-b))).
2314 apply (CR_cv_eq _ (fun n : nat => CR_of_Q R (bn n) + (c - b))).
2315 intro n. rewrite (CRplus_comm c). unfold CRminus.
2316 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
2317 apply CRplus_comm. apply CR_cv_plus. exact cvb. apply CR_cv_const.
2318 unfold CRminus. rewrite CRplus_comm, CRplus_assoc, CRplus_opp_l.
2319 apply CRplus_0_r.
2320 - (* Split sum *)
2321 apply CR_cv_plus.
2322 + apply UC_right_bound_cv. exact cvb.
2323 + unfold cn.
2324 apply (UC_integral_slide_cv b c f cont_mod fCont lebc
2325 (fun n => CR_of_Q R (bn n))).
2326 exact cvb.
2327 Qed.
2328
2329 Lemma UC_integral_chasles
2330 : forall {R : ConstructiveReals} (a b c : CRcarrier R)
2331 (f : CRcarrier R -> CRcarrier R)
2332 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2333 (fCont : UniformCont f cont_mod)
2334 (leab : a <= b) (lebc : b <= c) (leac : a <= c),
2335 UC_integral f a c cont_mod fCont leac
2336 == UC_integral f a b cont_mod fCont leab
2337 + UC_integral f b c cont_mod fCont lebc.
2338 Proof.
2339 intros.
2340 assert (a-a <= c-a).
2341 { apply CRplus_le_compat_r, leac. }
2342 assert (CR_of_Q R 0 <= c-a).
2343 { rewrite <- (CRplus_opp_r a). exact H. }
2344 rewrite (UC_integral_translate f a c (-a) _ H).
2345 rewrite (UC_integral_bound_proper
2346 _ (a+-a) (c+-a) (CR_of_Q R 0) (c+-a)
2347 cont_mod _ _ H0).
2348 assert (CR_of_Q R 0 <= b-a).
2349 { rewrite <- (CRplus_opp_r a).
2350 apply CRplus_le_compat_r. exact leab. }
2351 assert (b-a <= c-a).
2352 { apply CRplus_le_compat_r. exact lebc. }
2353 rewrite (UC_integral_chasles_rat_rat_rat
2354 0 (b-a) (c+-a) _ _ _ H1 H2).
2355 apply CRplus_morph.
2356 - assert (a-a <= b-a).
2357 { apply CRplus_le_compat_r. exact leab. }
2358 rewrite (UC_integral_translate f a b (-a) _ H3).
2359 apply UC_integral_bound_proper.
2360 rewrite CRplus_opp_r. reflexivity. reflexivity.
2361 - rewrite (UC_integral_translate f b c (-a) _ H2).
2362 apply UC_integral_bound_proper. reflexivity. reflexivity.
2363 - rewrite CRplus_opp_r. reflexivity.
2364 - reflexivity.
2365 Qed.
2366
2367 Lemma UC_integral_constant :
2368 forall {R : ConstructiveReals}
2369 f a b c (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2370 (fCont : UniformCont f cont_mod) (leab : a <= b),
2371 (forall x, (a <= x /\ x <= b) -> f x == c)
2372 -> UC_integral f a b cont_mod fCont leab == (b-a) * c.
2373 Proof.
2374 intros. unfold UC_integral.
2375 destruct (CR_complete R
2376 (fun last : nat =>
2377 IntegralFiniteSum f (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2378 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
2379 (UC_integral_cauchy f a b cont_mod fCont leab)).
2380 apply (CR_cv_unique
2381 (fun last : nat =>
2382 IntegralFiniteSum
2383 f (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))))
2384 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))) last) ).
2385 exact c0. intros n.
2386 exists O. intros. unfold IntegralFiniteSum, CRminus.
2387 rewrite (CRsum_eq _ (fun k => c * (b-a) * CR_of_Q R (1# Pos.of_nat (S i)))).
2388 rewrite sum_const.
2389 setoid_replace (c * (b - a) * CR_of_Q R (1 # Pos.of_nat (S i)) * INR (S i) + - ((b + - a) * c))
2390 with (CR_of_Q R 0).
2391 rewrite CRabs_right. apply CR_of_Q_le; discriminate.
2392 apply CRle_refl. unfold INR.
2393 rewrite CRmult_assoc, <- CR_of_Q_mult.
2394 setoid_replace ((1 # Pos.of_nat (S i)) * (Z.of_nat (S i) # 1))%Q with 1%Q.
2395 rewrite CRmult_1_r, CRmult_comm.
2396 unfold CRminus. rewrite CRplus_opp_r. reflexivity.
2397 unfold Qmult, Qeq, Qnum, Qden.
2398 do 2 rewrite Z.mul_1_l. rewrite Z.mul_1_r, Pos.mul_1_r.
2399 rewrite <- positive_nat_Z. rewrite Nat2Pos.id. reflexivity. discriminate.
2400 intros. rewrite H. rewrite CRmult_assoc.
2401 apply CRmult_morph. reflexivity.
2402 transitivity ((b + - a) * (CR_of_Q R (Z.of_nat (S i0) # Pos.of_nat (S i))
2403 - CR_of_Q R (Z.of_nat i0 # Pos.of_nat (S i)))).
2404 unfold CRminus. do 3 rewrite CRmult_plus_distr_r.
2405 do 2 rewrite CRopp_plus_distr. do 2 rewrite CRmult_plus_distr_l.
2406 do 2 rewrite CRopp_mult_distr_l.
2407 do 4 rewrite <- CRplus_assoc.
2408 apply CRplus_morph.
2409 2: rewrite CRopp_involutive, <- CRopp_mult_distr_l,
2410 <- CRopp_mult_distr_r, CRopp_involutive; reflexivity.
2411 rewrite (CRplus_comm a). do 4 rewrite CRplus_assoc.
2412 apply CRplus_morph. reflexivity.
2413 do 2 rewrite <- CRplus_assoc.
2414 rewrite (CRplus_comm (b * - CR_of_Q R (Z.of_nat i0 # Pos.of_nat (S i)))).
2415 apply CRplus_morph. rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l.
2416 rewrite CRplus_0_l. reflexivity.
2417 rewrite <- CRopp_mult_distr_l, <- CRopp_mult_distr_r. reflexivity.
2418 apply CRmult_morph. reflexivity.
2419 unfold CRminus. rewrite <- CR_of_Q_opp, <- CR_of_Q_plus.
2420 apply CR_of_Q_morph. rewrite Qinv_minus_distr.
2421 replace (Z.of_nat (S i0) - Z.of_nat i0)%Z with 1%Z. reflexivity.
2422 rewrite Nat2Z.inj_succ. ring.
2423
2424 split. apply (CRle_trans _ (a + 0)). rewrite CRplus_0_r. apply CRle_refl.
2425 apply CRplus_le_compat_l. rewrite <- (CRmult_0_r (b-a)).
2426 apply CRmult_le_compat_l.
2427 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
2428 exact leab. apply CRle_refl.
2429 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
2430 rewrite Z.mul_0_l, Z.mul_1_r. apply Nat2Z.is_nonneg.
2431 apply (CRplus_le_reg_l (-a)).
2432 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
2433 rewrite <- (CRmult_1_r (-a+b)), (CRplus_comm (-a)).
2434 apply CRmult_le_compat_l.
2435 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
2436 exact leab. apply CRle_refl.
2437 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
2438 rewrite Z.mul_1_r, Z.mul_1_l. rewrite <- positive_nat_Z.
2439 rewrite Nat2Pos.id. apply Nat2Z.inj_le, le_S, H1. discriminate.
2440 Qed.
2441
2442 Lemma UC_integral_zero :
2443 forall {R : ConstructiveReals} f a b
2444 (cont_mod : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2445 (fCont : UniformCont f cont_mod) (leab : a <= b),
2446 (forall x, (a <= x /\ x <= b) -> f x == 0)
2447 -> UC_integral f a b cont_mod fCont leab == 0.
2448 Proof.
2449 intros. rewrite (UC_integral_constant _ _ _ 0).
2450 rewrite CRmult_0_r. reflexivity. exact H.
2451 Qed.
2452
2453 Lemma UC_integral_nonneg :
2454 forall {R : ConstructiveReals}
2455 f g a b (modF : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2456 (modG : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2457 (fCont : UniformCont f modF)
2458 (gCont : UniformCont g modG)
2459 (leab leabb : a <= b),
2460 (forall x, (a <= x /\ x <= b) -> (f x) <= (g x))
2461 -> UC_integral f a b modF fCont leab
2462 <= (UC_integral g a b modG gCont leabb).
2463 Proof.
2464 intros. unfold UC_integral.
2465 destruct (CR_complete R
2466 (fun last : nat =>
2467 IntegralFiniteSum f (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2468 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
2469 (UC_integral_cauchy f a b modF fCont leab)).
2470 destruct (CR_complete R
2471 (fun last : nat =>
2472 IntegralFiniteSum g (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2473 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
2474 (UC_integral_cauchy g a b modG gCont leabb)).
2475 assert (forall n:nat, ((fun last : nat =>
2476 IntegralFiniteSum f (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))))
2477 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))) last) n)
2478 <=
2479 ((fun last : nat =>
2480 IntegralFiniteSum g (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))))
2481 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))) last) n)).
2482 { intros. unfold IntegralFiniteSum, CRminus.
2483 apply sum_Rle. intros. apply CRmult_le_compat_r.
2484 apply (CRle_minus
2485 (a + (b + - a) * CR_of_Q R (Z.of_nat k # Pos.of_nat (S n)))
2486 ( a + (b + - a) * CR_of_Q R (Z.of_nat (S k) # Pos.of_nat (S n)))).
2487 apply CRplus_le_compat_l.
2488 apply CRmult_le_compat_l.
2489 apply (CRle_minus a b), leab. apply CR_of_Q_le.
2490 unfold Qle, Qnum, Qden.
2491 apply Z.mul_le_mono_nonneg_r. discriminate.
2492 apply Nat2Z.inj_le, le_S, Nat.le_refl.
2493 apply H.
2494 split. apply (CRle_trans _ (a + 0)).
2495 rewrite CRplus_0_r. apply CRle_refl.
2496 apply CRplus_le_compat_l. rewrite <- (CRmult_0_r (b-a)).
2497 apply CRmult_le_compat_l.
2498 apply (CRle_minus a b), leab.
2499 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
2500 rewrite Z.mul_0_l, Z.mul_1_r. apply Nat2Z.is_nonneg.
2501 apply (CRplus_le_reg_l (-a)).
2502 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
2503 rewrite <- (CRmult_1_r (-a+b)), (CRplus_comm (-a)).
2504 apply CRmult_le_compat_l.
2505 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat.
2506 exact leab. apply CRle_refl.
2507 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
2508 rewrite Z.mul_1_r, Z.mul_1_l. rewrite <- positive_nat_Z.
2509 rewrite Nat2Pos.id. apply Nat2Z.inj_le, le_S, H0. discriminate. }
2510 apply (CR_cv_le _ _ _ _ H0); assumption.
2511 Qed.
2512
2513 Lemma UC_integral_pos :
2514 forall {R : ConstructiveReals}
2515 f a b (modF : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2516 (fCont : UniformCont f modF)
2517 (leab : a <= b),
2518 (forall x, (a <= x /\ x <= b) -> 0 <= f x)
2519 -> 0 <= UC_integral f a b modF fCont leab.
2520 Proof.
2521 intros.
2522 rewrite <- (UC_integral_zero (fun _ => 0) a b
2523 (fun _ _ => 1) (UC_constant 0) leab).
2524 apply UC_integral_nonneg. exact H.
2525 intros. reflexivity.
2526 Qed.
2527
2528 Lemma UC_integral_extens :
2529 forall {R : ConstructiveReals}
2530 f g a b (modF : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2531 (modG : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2532 (fCont : UniformCont f modF)
2533 (gCont : UniformCont g modG)
2534 (leab leabb : a <= b),
2535 (forall x, (a <= x /\ x <= b) -> f x == g x)
2536 -> UC_integral f a b modF fCont leab
2537 == UC_integral g a b modG gCont leabb.
2538 Proof.
2539 intros. split; apply UC_integral_nonneg.
2540 intros. rewrite H. apply CRle_refl. exact H0.
2541 intros. rewrite H. apply CRle_refl. exact H0.
2542 Qed.
2543
2544 Lemma UC_integral_extend_zero
2545 : forall {R : ConstructiveReals}
2546 (f : CRcarrier R -> CRcarrier R)
2547 (modF : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2548 (a b c d : CRcarrier R) (fCont : UniformCont f modF)
2549 (leab : a <= b) (lecd : c <= d),
2550 c <= a
2551 -> b <= d
2552 -> (forall x : CRcarrier R, (c <= x /\ x <= a) -> f x == 0)
2553 -> (forall x : CRcarrier R, (b <= x /\ x <= d) -> f x == 0)
2554 -> UC_integral f a b modF fCont leab
2555 == UC_integral f c d modF fCont lecd.
2556 Proof.
2557 intros.
2558 assert (a <= d).
2559 { apply (CRle_trans _ _ _ leab H0). }
2560 rewrite (UC_integral_chasles c a d f modF fCont H H3).
2561 rewrite (UC_integral_chasles a b d f modF fCont leab H0).
2562 rewrite (UC_integral_zero f c a).
2563 rewrite (UC_integral_zero f b d).
2564 rewrite CRplus_0_l, CRplus_0_r. reflexivity.
2565 exact H2. exact H1.
2566 Qed.
2567
2568 Lemma UC_integral_extend_nonneg
2569 : forall {R : ConstructiveReals}
2570 (f : CRcarrier R -> CRcarrier R)
2571 (modF : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2572 (a b c d : CRcarrier R) (fCont : UniformCont f modF)
2573 (leab : a <= b) (lecd : c <= d),
2574 c <= a
2575 -> b <= d
2576 -> (forall x : CRcarrier R, 0 <= (f x))
2577 -> UC_integral f a b modF fCont leab
2578 <= UC_integral f c d modF fCont lecd.
2579 Proof.
2580 intros.
2581 assert (a <= d).
2582 { apply (CRle_trans _ _ _ leab). exact H0. }
2583 rewrite (UC_integral_chasles c a d f modF fCont H H2).
2584 rewrite (UC_integral_chasles a b d f modF fCont leab H0).
2585 apply (CRplus_le_reg_l (- UC_integral f a b modF fCont leab)).
2586 apply CRplus_le_compat_l. rewrite CRplus_comm.
2587 rewrite <- (CRplus_0_r (UC_integral f a b modF fCont leab)).
2588 do 2 rewrite CRplus_assoc. apply CRplus_le_compat_l.
2589 rewrite CRplus_0_l. rewrite <- (CRplus_0_r 0).
2590 apply CRplus_le_compat.
2591 apply UC_integral_pos. intros. apply H1.
2592 apply UC_integral_pos. intros. apply H1.
2593 Qed.
2594
2595 Lemma UC_integral_plus :
2596 forall {R : ConstructiveReals}
2597 (f g : CRcarrier R -> CRcarrier R) (a b : CRcarrier R)
2598 (modF modG modS : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2599 (fCont : UniformCont f modF)
2600 (gCont : UniformCont g modG)
2601 (sCont : UniformCont (fun x => (f x) + (g x)) modS)
2602 (leab leabb : a <= b),
2603 UC_integral (fun x => (f x) + (g x)) a b
2604 modS sCont leab
2605 == UC_integral f a b modF fCont leabb
2606 + UC_integral g a b modG gCont leabb.
2607 Proof.
2608 intros.
2609 unfold UC_integral.
2610 destruct (CR_complete R
2611 (fun last : nat =>
2612 IntegralFiniteSum f (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2613 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
2614 (UC_integral_cauchy f a b modF fCont leabb)).
2615 destruct (CR_complete R
2616 (fun last : nat =>
2617 IntegralFiniteSum g (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2618 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
2619 (UC_integral_cauchy g a b modG gCont leabb)).
2620 destruct (CR_complete R
2621 (fun last : nat =>
2622 IntegralFiniteSum (fun x1 : CRcarrier R => f x1 + g x1)
2623 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2624 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))) last)
2625 (UC_integral_cauchy (fun x1 : CRcarrier R => f x1 + g x1) a b modS sCont leab)).
2626 apply (CR_cv_unique _ _ _ c1).
2627 apply (CR_cv_eq
2628 _ (fun last : nat =>
2629 (IntegralFiniteSum f
2630 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))))
2631 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))) last)
2632 + (IntegralFiniteSum g
2633 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))))
2634 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))) last))).
2635 intro n. unfold IntegralFiniteSum. rewrite <- sum_plus.
2636 apply CRsum_eq.
2637 2: apply CR_cv_plus; assumption.
2638 intros.
2639 generalize (f (a + (b - a) * CR_of_Q R (Z.of_nat i # Pos.of_nat (S n)))),
2640 (g (a + (b - a) * CR_of_Q R (Z.of_nat i # Pos.of_nat (S n)))).
2641 intros.
2642 setoid_replace (a + (b - a) * CR_of_Q R (Z.of_nat (S i) # Pos.of_nat (S n)) -
2643 (a + (b - a) * CR_of_Q R (Z.of_nat i # Pos.of_nat (S n))))
2644 with ((b - a) * CR_of_Q R (Z.of_nat (S i) # Pos.of_nat (S n))
2645 - (b - a) * CR_of_Q R (Z.of_nat i # Pos.of_nat (S n))).
2646 rewrite <- CRmult_plus_distr_r. reflexivity.
2647 unfold CRminus. rewrite (CRplus_comm a), CRopp_plus_distr.
2648 rewrite CRplus_assoc, <- (CRplus_assoc a), CRplus_opp_r, CRplus_0_l.
2649 reflexivity.
2650 Qed.
2651
2652 Lemma UC_integral_sum :
2653 forall {R : ConstructiveReals}
2654 (fn : nat -> CRcarrier R -> CRcarrier R) (a b : CRcarrier R) (n : nat)
2655 (modFn : forall (n:nat) (eps:CRcarrier R), 0 < eps -> CRcarrier R)
2656 (modSn : forall (eps:CRcarrier R), 0 < eps -> CRcarrier R)
2657 (fnCont : forall k:nat, UniformCont (fn k) (modFn k))
2658 (sCont : UniformCont (fun x => CRsum (fun k => (fn k x)) n) modSn)
2659 (leab : a <= b),
2660 UC_integral (fun x => CRsum (fun k => (fn k x)) n) a b
2661 modSn sCont leab
2662 == CRsum (fun k => UC_integral (fn k) a b (modFn k) (fnCont k) leab) n.
2663 Proof.
2664 induction n.
2665 - intros. simpl. apply UC_integral_extens. intros. reflexivity.
2666 - intros. simpl.
2667 destruct (UC_sum fn modFn fnCont n) as [modS c].
2668 rewrite <- (IHn _ _ _ c). apply UC_integral_plus.
2669 Qed.
2670
2671 Lemma Rcauchy_complete_eq
2672 : forall {R : ConstructiveReals} (xn : nat -> CRcarrier R)
2673 (cau : CR_cauchy R xn) (a : CRcarrier R),
2674 CR_cv R xn a
2675 -> (let (l,_) := CR_complete R xn cau in l) == a.
2676 Proof.
2677 intros. destruct (CR_complete R xn cau).
2678 apply (CR_cv_unique xn); assumption.
2679 Qed.
2680
2681 (* The partial integral sum equals a^2 * n/(2*(n+1))
2682 which converges to a^2/2. *)
2683 Lemma x_RiemannInt : forall {R : ConstructiveReals} (a b : CRcarrier R) (leab : a <= b),
2684 UC_integral (fun x=> x) a b _ UC_x leab
2685 == (b*b - a*a) * CR_of_Q R (1#2).
2686 Proof.
2687 intros. unfold UC_integral.
2688 apply Rcauchy_complete_eq.
2689 apply (CR_cv_eq _ (fun n => a*(b-a) + (CR_of_Q R (Z.of_nat n # Pos.of_nat (S n)))
2690 * ((b-a) * (b-a) * CR_of_Q R (1#2)))).
2691 - intros. unfold IntegralFiniteSum.
2692 rewrite (CRsum_eq _ (fun k => a*(b-a) * CR_of_Q R (1# Pos.of_nat (S n))
2693 + INR k * ((b-a)*(b-a) * CR_of_Q R (1# Pos.of_nat (S n * S n))))).
2694 + symmetry. rewrite sum_plus, sum_const.
2695 rewrite sum_scale, (CRmult_comm (CRsum (fun n0 => INR n0) n)).
2696 rewrite sum_INR.
2697 rewrite CRmult_assoc.
2698 setoid_replace (CR_of_Q R (1 # Pos.of_nat (S n)) * INR (S n))
2699 with (CR_of_Q R 1).
2700 rewrite CRmult_1_r. apply CRplus_morph. reflexivity.
2701 rewrite <- (CRmult_comm ((b - a) * (b - a) * CR_of_Q R (1 # 2))).
2702 rewrite CRmult_assoc. rewrite (CRmult_assoc ((b-a)*(b-a))).
2703 apply CRmult_morph. reflexivity.
2704 rewrite CRmult_comm, (CRmult_comm ((INR n)*(INR (S n)))).
2705 rewrite (CRmult_assoc (CR_of_Q R (1#2))).
2706 apply CRmult_morph. reflexivity.
2707 unfold INR, CRealConstructive, CR_of_Q.
2708 do 2 rewrite <- CR_of_Q_mult. apply CR_of_Q_morph.
2709 rewrite Nat2Pos.inj_mul. unfold Qmult, Qeq, Qnum, Qden.
2710 rewrite Z.mul_1_r, Pos.mul_1_l.
2711 rewrite <- Z.mul_assoc. apply f_equal2. reflexivity.
2712 rewrite Pos2Z.inj_mul. apply f_equal2. 2: reflexivity.
2713 rewrite <- positive_nat_Z. rewrite Nat2Pos.id. reflexivity.
2714 discriminate. discriminate. discriminate.
2715 unfold INR. rewrite <- CR_of_Q_mult. apply CR_of_Q_morph.
2716 unfold Qmult, Qeq, Qnum, Qden. rewrite Pos.mul_1_r.
2717 rewrite Z.mul_1_l, Z.mul_1_l, Z.mul_1_r.
2718 rewrite <- positive_nat_Z. rewrite Nat2Pos.id. reflexivity.
2719 discriminate.
2720 + intros.
2721 setoid_replace (a + (b - a) * CR_of_Q R (Z.of_nat (S i) # Pos.of_nat (S n)) -
2722 (a + (b - a) * CR_of_Q R (Z.of_nat i # Pos.of_nat (S n))))
2723 with ((b - a) * CR_of_Q R (1 # Pos.of_nat (S n))).
2724 rewrite CRmult_plus_distr_r. apply CRplus_morph.
2725 rewrite CRmult_assoc. reflexivity.
2726 unfold INR. rewrite Nat2Pos.inj_mul.
2727 setoid_replace (1 # Pos.of_nat (S n) * Pos.of_nat (S n))%Q
2728 with ((1 # Pos.of_nat (S n)) * (1 # Pos.of_nat (S n)))%Q.
2729 2: reflexivity. rewrite CR_of_Q_mult.
2730 setoid_replace (Z.of_nat i # Pos.of_nat (S n))%Q
2731 with ((Z.of_nat i # 1) * (1# Pos.of_nat (S n)))%Q.
2732 rewrite CR_of_Q_mult.
2733 do 4 rewrite <- CRmult_assoc. apply CRmult_morph.
2734 2: reflexivity. rewrite (CRmult_comm (b-a)).
2735 rewrite <- CRmult_assoc.
2736 do 2 rewrite (CRmult_assoc (CR_of_Q R (Z.of_nat i # 1) * (b - a))).
2737 apply CRmult_morph. reflexivity. apply CRmult_comm.
2738 unfold Qmult, Qeq, Qnum, Qden. rewrite Z.mul_1_r. reflexivity.
2739 discriminate. discriminate.
2740 setoid_replace (Z.of_nat (S i) # Pos.of_nat (S n))%Q
2741 with ((1#Pos.of_nat (S n)) + (Z.of_nat i # Pos.of_nat (S n)))%Q.
2742 rewrite CR_of_Q_plus. unfold CRminus. rewrite CRopp_plus_distr.
2743 rewrite <- CRplus_assoc, (CRplus_comm a).
2744 do 2 rewrite CRplus_assoc. rewrite <- (CRplus_assoc a).
2745 rewrite CRplus_opp_r, CRplus_0_l, CRopp_mult_distr_r.
2746 rewrite <- CRmult_plus_distr_l. apply CRmult_morph. reflexivity.
2747 rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r. reflexivity.
2748 rewrite Qinv_plus_distr. fold (1 + i)%nat.
2749 rewrite Nat2Z.inj_add. reflexivity.
2750 - apply (CR_cv_proper
2751 _ (a*(b-a) + 1 * ((b-a) * (b-a) * CR_of_Q R (1#2)))).
2752 apply (CR_cv_plus _ _ (a*(b-a))).
2753 apply CR_cv_const. apply CR_cv_scale.
2754 intros n. exists (Pos.to_nat n). intros.
2755 rewrite CRabs_minus_sym.
2756 setoid_replace (1 - CR_of_Q R (Z.of_nat i # Pos.of_nat (S i)))
2757 with (CR_of_Q R (1# Pos.of_nat (S i))).
2758 rewrite CRabs_right. apply CR_of_Q_le.
2759 unfold Qle,Qnum,Qden. do 2 rewrite Z.mul_1_l.
2760 apply Pos2Z.pos_le_pos. apply Pos2Nat.inj_le.
2761 rewrite Nat2Pos.id. apply le_S,H. discriminate.
2762 apply CR_of_Q_le; discriminate.
2763 unfold CRminus. rewrite <- CR_of_Q_opp, <- CR_of_Q_plus.
2764 apply CR_of_Q_morph. unfold Qopp,Qplus,Qeq,Qnum,Qden.
2765 apply f_equal2. 2: reflexivity.
2766 rewrite Z.mul_1_l, Z.mul_1_r.
2767 rewrite <- positive_nat_Z, Nat2Pos.id. 2: discriminate.
2768 fold (1+i)%nat. rewrite Nat2Z.inj_add. ring.
2769 rewrite CRmult_1_l.
2770 rewrite (CRmult_comm a), CRmult_assoc, <- CRmult_plus_distr_l.
2771 setoid_replace (a + (b - a) * CR_of_Q R (1 # 2))
2772 with ((a+b) * CR_of_Q R (1#2)).
2773 rewrite <- CRmult_assoc. apply CRmult_morph. 2: reflexivity.
2774 unfold CRminus. rewrite CRmult_plus_distr_r, CRmult_plus_distr_l.
2775 rewrite CRmult_plus_distr_l, (CRplus_comm (b*a)), CRplus_assoc.
2776 apply CRplus_morph. reflexivity. rewrite CRplus_comm.
2777 rewrite <- (CRopp_mult_distr_l a b), (CRmult_comm a b).
2778 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
2779 rewrite <- CRopp_mult_distr_l. reflexivity.
2780 apply (CRmult_eq_reg_r (CR_of_Q R 2)).
2781 left. apply CR_of_Q_lt; reflexivity.
2782 rewrite CRmult_plus_distr_r.
2783 rewrite CRmult_assoc, CRmult_assoc, <- CR_of_Q_mult.
2784 setoid_replace ((1#2)*2)%Q with 1%Q. 2: reflexivity.
2785 rewrite (CR_of_Q_plus R 1 1), CRmult_1_r, CRmult_1_r.
2786 rewrite CRmult_plus_distr_l. rewrite CRmult_1_r. rewrite CRplus_assoc.
2787 apply CRplus_morph. reflexivity. unfold CRminus.
2788 rewrite CRplus_comm, CRplus_assoc, CRplus_opp_l.
2789 apply CRplus_0_r.
2790 Qed.
2791
2792 Lemma UC_integral_scale :
2793 forall {R : ConstructiveReals} (f : CRcarrier R -> CRcarrier R)
2794 (a b l : CRcarrier R)
2795 (modF : forall eps:CRcarrier R, 0 < eps -> CRcarrier R)
2796 (fCont : UniformCont f modF) (leab : a <= b),
2797 UC_integral (fun x => l * (f x)) a b
2798 _ (UC_scale f modF l fCont) leab
2799 == l * (UC_integral f a b modF fCont leab).
2800 Proof.
2801 intros.
2802 unfold UC_integral.
2803 destruct (CR_complete R
2804 (fun last : nat =>
2805 IntegralFiniteSum f
2806 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2807 (fun n : nat => a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))
2808 last) (UC_integral_cauchy f a b modF fCont leab)).
2809 apply Rcauchy_complete_eq.
2810 apply (CR_cv_eq
2811 _ (fun last : nat =>
2812 (IntegralFiniteSum f
2813 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last))))
2814 (fun n : nat => (a + (b - a) * CR_of_Q R (Z.of_nat n # Pos.of_nat (S last)))) last) * l)).
2815 2: rewrite CRmult_comm; apply CR_cv_scale, c.
2816 intro n. unfold IntegralFiniteSum.
2817 rewrite <- sum_scale. apply CRsum_eq.
2818 intros.
2819 rewrite (CRmult_comm l). do 2 rewrite CRmult_assoc. apply CRmult_morph.
2820 reflexivity. apply CRmult_comm.
2821 Qed.
2822
2823 Lemma TrapezeLe : forall {R : ConstructiveReals} (a b eta : CRcarrier R)
2824 (etaPos : 0 < eta),
2825 a <= b -> a-eta <= b+eta.
2826 Proof.
2827 intros. apply (CRle_trans _ (a-0)).
2828 apply CRplus_le_compat_l, CRopp_ge_le_contravar, CRlt_asym, etaPos.
2829 unfold CRminus. rewrite CRopp_0. apply CRplus_le_compat.
2830 exact H. apply CRlt_asym, etaPos.
2831 Qed.
2832
2833 Lemma CSUCUnitTrapezeInt
2834 : forall {R : ConstructiveReals}
2835 (a b eta : CRcarrier R) (etaPos : 0 < eta) (leab : a <= b),
2836 UC_integral (CSUCUnitTrapeze a b eta etaPos)
2837 (a-eta) (b+eta)
2838 _ (CSUCUnitTrapeze_cont a b eta etaPos leab)
2839 (TrapezeLe a b eta etaPos leab)
2840 == eta + b - a.
2841 Proof.
2842 intros.
2843 assert (a-eta <= a).
2844 { apply (CRle_trans _ (a-0)).
2845 apply CRplus_le_compat_l, CRopp_ge_le_contravar, CRlt_asym, etaPos.
2846 unfold CRminus. rewrite CRopp_0, CRplus_0_r. apply CRle_refl. }
2847 assert (b <= b+eta) as H1.
2848 { apply (CRplus_le_reg_l (-b)).
2849 rewrite CRplus_opp_l, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
2850 apply CRlt_asym, etaPos. }
2851 assert (a <= b+eta).
2852 { apply (CRle_trans _ b _ leab). exact H1. }
2853 rewrite (UC_integral_chasles
2854 (a-eta) a (b+eta)
2855 (CSUCUnitTrapeze a b eta etaPos)
2856 _ _ H H0).
2857 rewrite (UC_integral_chasles
2858 a b (b+eta)
2859 (CSUCUnitTrapeze a b eta etaPos)
2860 _ _ leab H1).
2861 assert (forall t:CRcarrier R, UniformCont (fun x => x + t) (fun eps epsPos => eps)) as H2.
2862 { intro t. apply (UC_translate_horizontal (fun x=>x) t). apply UC_x. }
2863 rewrite (UC_integral_extens
2864 _ (fun x:CRcarrier R => CRinv R eta (inr etaPos) * (x + (eta - a)))
2865 (a - eta) a
2866 _ _ _ (UC_scale _ _ _ (H2 _)) H H).
2867 rewrite (UC_integral_extens
2868 _ (fun x:CRcarrier R => 1) a b
2869 _ (fun eps epsPos => 1) _ (UC_constant _) leab leab).
2870 rewrite (UC_integral_extens
2871 _ (fun x:CRcarrier R => (-CRinv R eta (inr etaPos))
2872 * (x + (- b - eta)))
2873 b (b+eta) _ _
2874 _ (UC_scale _ _ (-CRinv R eta (inr etaPos)) (H2 _)) H1 H1).
2875 - rewrite (UC_integral_scale
2876 _ (a-eta) a
2877 (CRinv R eta (inr etaPos))
2878 (fun (eps : CRcarrier R) (_ : 0 < eps) => eps)).
2879 rewrite (UC_integral_plus _ _ (a-eta) a
2880 _ _ _ UC_x (UC_constant (eta-a)) _ _ H).
2881 rewrite (UC_integral_scale
2882 _ b (b+eta) _
2883 (fun eps epsPos => eps)).
2884 rewrite (UC_integral_plus _ _ b (b+eta)
2885 _ _ _ UC_x (UC_constant (-b -eta)) _ _ H1).
2886 rewrite (UC_integral_constant _ a b 1).
2887 2: intros; reflexivity. rewrite CRmult_1_r.
2888 rewrite x_RiemannInt.
2889 rewrite (UC_integral_constant _ (a-eta) a (eta-a)).
2890 rewrite x_RiemannInt.
2891 rewrite (UC_integral_constant _ b (b+eta) (-b-eta)).
2892 unfold CRminus. rewrite (CRplus_assoc eta).
2893 rewrite CRplus_comm, CRplus_assoc, (CRplus_comm eta (b+-a)).
2894 apply CRplus_morph. reflexivity. rewrite <- CRopp_mult_distr_l, CRopp_mult_distr_r.
2895 rewrite <- CRmult_plus_distr_l.
2896 apply (CRmult_eq_reg_l eta). right. exact etaPos.
2897 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l.
2898 setoid_replace (b + eta + - b) with eta.
2899 setoid_replace (a + - (a + - eta)) with eta.
2900 rewrite CRopp_plus_distr. rewrite (CRopp_mult_distr_r eta).
2901 rewrite CRopp_plus_distr, CRopp_involutive, CRopp_involutive.
2902 rewrite CRopp_mult_distr_l, CRopp_plus_distr, CRopp_involutive.
2903 setoid_replace (a * a + - ((a + - eta) * (a + - eta)))
2904 with (CR_of_Q R 2*a*eta - eta*eta).
2905 setoid_replace (- ((b + eta) * (b + eta)) + b * b)
2906 with (-CR_of_Q R 2*b*eta - eta*eta).
2907 setoid_replace ((- CR_of_Q R 2 * b * eta - eta * eta) * CR_of_Q R (1 # 2))
2908 with (- eta*eta *CR_of_Q R (1#2) + -(eta*b)).
2909 setoid_replace ((CR_of_Q R 2 * a * eta - eta * eta) * CR_of_Q R (1 # 2))
2910 with ( - eta*eta *CR_of_Q R (1#2) + eta*a).
2911 do 2 rewrite CRplus_assoc. rewrite CRmult_plus_distr_l.
2912 do 2 rewrite <- (CRplus_assoc (-(eta*b))). rewrite CRplus_opp_l, CRplus_0_l.
2913 rewrite (CRplus_comm (eta) (-a)), CRmult_plus_distr_l.
2914 rewrite CRplus_assoc, <- (CRplus_assoc (eta*a)).
2915 rewrite <- (CRopp_mult_distr_r eta a), CRplus_opp_r, CRplus_0_l.
2916 rewrite (CRplus_comm (eta*eta)), <- CRplus_assoc, <- CRplus_assoc.
2917 rewrite <- CRmult_plus_distr_l, <- CR_of_Q_plus, Qinv_plus_distr.
2918 setoid_replace (1+1#2)%Q with 1%Q. 2: reflexivity.
2919 rewrite CRmult_1_r, <- CRopp_mult_distr_l.
2920 rewrite CRplus_opp_l, CRplus_0_l. reflexivity.
2921 unfold CRminus. rewrite CRmult_comm, CRmult_plus_distr_l.
2922 rewrite <- CRmult_assoc, <- CRmult_assoc, <- CR_of_Q_mult.
2923 setoid_replace ((1#2)*2)%Q with 1%Q. rewrite CRmult_1_l.
2924 rewrite CRplus_comm, CRmult_comm, CRopp_mult_distr_l, (CRmult_comm a eta).
2925 reflexivity. reflexivity.
2926 unfold CRminus. rewrite CRmult_comm, CRmult_plus_distr_l.
2927 rewrite <- CR_of_Q_opp, <- CRmult_assoc, <- CRmult_assoc, <- CR_of_Q_mult.
2928 setoid_replace ((1#2)*-(2))%Q with (-(1))%Q.
2929 rewrite CR_of_Q_opp, <- CRopp_mult_distr_l, CRmult_1_l.
2930 rewrite CRplus_comm, CRmult_comm, CRopp_mult_distr_l.
2931 rewrite (CRopp_mult_distr_r eta b), (CRmult_comm eta (-b)).
2932 reflexivity. reflexivity.
2933 rewrite CRmult_plus_distr_l, CRmult_plus_distr_r.
2934 rewrite CRplus_comm, CRopp_plus_distr, CRopp_plus_distr, <- CRplus_assoc.
2935 rewrite <- CRplus_assoc, CRplus_opp_r, CRplus_0_l.
2936 rewrite CRmult_plus_distr_r, CRopp_plus_distr, <- CRplus_assoc.
2937 apply CRplus_morph. 2: reflexivity.
2938 rewrite (CR_of_Q_plus R 1 1).
2939 rewrite <- (CRopp_mult_distr_l), CRmult_plus_distr_r, CRmult_1_l.
2940 rewrite <- (CRopp_mult_distr_l), CRmult_plus_distr_r.
2941 rewrite CRopp_plus_distr, (CRmult_comm eta). reflexivity.
2942 rewrite CRmult_plus_distr_l, CRmult_plus_distr_r.
2943 rewrite CRopp_plus_distr, CRopp_plus_distr.
2944 rewrite <- CRplus_assoc, <- CRplus_assoc, CRplus_opp_r, CRplus_0_l.
2945 rewrite CRmult_plus_distr_r, CRopp_plus_distr.
2946 rewrite CRopp_mult_distr_l, CRopp_involutive.
2947 rewrite CRopp_mult_distr_r, CRopp_involutive.
2948 rewrite CRopp_mult_distr_l, CRopp_involutive, <- CRplus_assoc.
2949 apply CRplus_morph. rewrite (CR_of_Q_plus R 1 1).
2950 rewrite CRmult_plus_distr_r, CRmult_1_l, CRmult_plus_distr_r.
2951 rewrite (CRmult_comm eta a). reflexivity.
2952 rewrite CRopp_mult_distr_r. reflexivity.
2953 rewrite CRopp_plus_distr, CRopp_involutive, <- CRplus_assoc.
2954 rewrite CRplus_opp_r, CRplus_0_l. reflexivity.
2955 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
2956 intro. reflexivity. intros. reflexivity.
2957 - intros. unfold CSUCUnitTrapeze. rewrite UCHeavisideIn. unfold UCUnitHeaviside.
2958 rewrite (CRinv_morph (b + eta - b) eta _ (inr etaPos)).
2959 rewrite CRmax_right. rewrite CRmin_right.
2960 apply (CRmult_eq_reg_l eta).
2961 right. apply etaPos.
2962 rewrite <- CRmult_assoc, <- CRopp_mult_distr_r, CRinv_r.
2963 unfold CRminus.
2964 rewrite (CRmult_plus_distr_l eta), CRmult_1_r.
2965 rewrite <- CRopp_mult_distr_r, <- CRmult_assoc, CRmult_comm, <- CRmult_assoc.
2966 rewrite CRinv_l, CRmult_1_l.
2967 rewrite <- CRopp_mult_distr_l, CRmult_1_l, CRopp_plus_distr, CRopp_plus_distr.
2968 rewrite CRopp_plus_distr, CRopp_involutive, CRopp_involutive.
2969 rewrite CRplus_comm, CRplus_assoc. reflexivity.
2970 apply (CRmult_le_reg_r eta). exact etaPos.
2971 rewrite CRmult_1_l, CRmult_assoc, CRinv_l, CRmult_1_r.
2972 apply (CRplus_le_reg_r b).
2973 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
2974 rewrite CRplus_comm. apply H3.
2975 apply CRmin_glb. apply CRlt_asym, CRzero_lt_one.
2976 apply (CRmult_le_reg_r eta). exact etaPos.
2977 rewrite CRmult_0_l, CRmult_assoc, CRinv_l, CRmult_1_r.
2978 rewrite <- (CRplus_opp_r b). apply CRplus_le_compat_r.
2979 apply H3. unfold CRminus.
2980 rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
2981 apply (CRle_trans _ b _ leab). apply H3.
2982 - intros. rewrite CSUCTrapezePlateau. reflexivity. exact H3.
2983 - intros. unfold CSUCUnitTrapeze, UCUnitHeaviside.
2984 rewrite (CRinv_morph (a - (a- eta)) eta _ (inr etaPos)).
2985 rewrite (CRinv_morph (b + eta - b) eta _ (inr etaPos)).
2986 rewrite CRmax_right, CRmin_right.
2987 rewrite CRmax_left. unfold CRminus. rewrite CRopp_0, CRplus_0_r.
2988 rewrite CRmult_comm. apply CRmult_morph. reflexivity.
2989 apply CRplus_morph. reflexivity.
2990 rewrite CRplus_comm.
2991 rewrite CRopp_plus_distr, CRopp_involutive. reflexivity.
2992 apply (CRle_trans _ _ _ (CRmin_r _ _)).
2993 apply (CRmult_le_reg_r eta). exact etaPos.
2994 rewrite CRmult_0_l, CRmult_assoc, CRinv_l, CRmult_1_r.
2995 apply (CRplus_le_reg_r b).
2996 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
2997 rewrite CRplus_0_l.
2998 apply (CRle_trans _ a). apply H3. exact leab.
2999 apply (CRmult_le_reg_r eta). exact etaPos.
3000 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_1_l.
3001 apply (CRplus_le_reg_r (a - eta)).
3002 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
3003 rewrite CRplus_comm. unfold CRminus.
3004 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
3005 apply H3. apply CRmin_glb. apply CRlt_asym, CRzero_lt_one.
3006 apply (CRmult_le_reg_r eta). exact etaPos.
3007 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_0_l.
3008 apply (CRplus_le_reg_r (a - eta)).
3009 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
3010 rewrite CRplus_0_l. unfold CRminus.
3011 apply H3. unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc.
3012 rewrite CRplus_opp_l. apply CRplus_0_l.
3013 unfold CRminus. rewrite CRopp_plus_distr, <- CRplus_assoc.
3014 rewrite CRplus_opp_r, CRopp_involutive. apply CRplus_0_l.
3015 Qed.