Debian Codegraph @

reals/stdlib/CMTprofile.v

raw
1 (*
2 Copyright © 2020 Vincent Semeria
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
5
6 The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
7
8 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
9 *)
10
11
12 (** Proof that for an integrable function f, the inverse image of
13 of most intervals [t, +\infty[ are integrable, when 0 < t.
14 As a quick justification : if those inverse images has infinite
15 measure, it would be an infinite-area rectangle lower bounding
16 the integral of f.
17
18 The difficulty is making this argument constructive. First, we
19 approximate the indicator function of [t, +\infty[ by a
20 piecewise-linear function that continuously increases from 0 to 1,
21 between s < t and t. This means considering the integrable functions
22 (min(f,t) - min(f,s)) / (t-s)
23 and using the monotone convergence theorem in the limit where s tends
24 to t from below. The last, and main, difficulty is to constructively
25 prove that this non-increasing limit of integrals exists.
26 *)
27
28 From Coq Require Import ZArith QArith_base Qabs.
29 From Coq Require Import ConstructiveReals.
30 From Coq Require Import ConstructiveSum.
31 From Coq Require Import ConstructivePower.
32 From Coq Require Import ConstructiveAbs.
33 From Coq Require Import ConstructiveMinMax.
34 From Coq Require Import ConstructiveLimits.
35 Require Import ConstructiveUniformCont.
36 Require Import ConstructivePartialFunctions.
37 Require Import ConstructiveDiagonal.
38 Require Import CMTbase.
39 Require Import CMTIntegrableFunctions.
40 Require Import CMTIntegrableSets.
41 Require Import CMTFullSets.
42 Require Import CMTReals.
43 From Coq Require Import Lia.
44
45 Local Open Scope ConstructiveReals.
46
47 Lemma RealSequenceCoverMeasure
48 : forall {R : ConstructiveReals}
49 (un : nat -> CRcarrier R) (N : nat),
50 { coverInt : @IntegrableSet IntSpaceCSUCFunctions
51 (fun x => exists n:nat,
52 CRltProp R (un n - CRpow (CR_of_Q R (1#2)) (2 + N + n)) x /\
53 CRltProp R x (un n + CRpow (CR_of_Q R (1#2)) (2 + N + n)))
54 & MeasureSet coverInt <= CRpow (CR_of_Q R (1#2)) N }.
55 Proof.
56 intros.
57 assert (forall n:nat, un n - CRpow (CR_of_Q R (1#2)) (2 + N + n)
58 < un n + CRpow (CR_of_Q R (1#2)) (2 + N + n)).
59 { intro n. apply CRplus_lt_compat_l.
60 apply (CRle_lt_trans _ 0). rewrite <- CRopp_0. apply CRopp_ge_le_contravar.
61 apply CRpow_ge_zero, CRlt_asym, CR_of_Q_pos. reflexivity.
62 apply CRpow_gt_zero, CR_of_Q_pos. reflexivity. }
63 pose (fun n:nat => OpenIntervalIntegrable _ _ (H n)) as openInt.
64 destruct (@IntegrableSetCountableUnionLe
65 IntSpaceCSUCFunctions
66 (fun n x =>
67 CRltProp R (un n - CRpow (CR_of_Q _ (1#2)) (2 + N + n)) x
68 /\ CRltProp R x (un n + CRpow (CR_of_Q _ (1#2)) (2 + N + n)))
69 (fun n => let (i,_) := openInt n in i)
70 (CRpow (CR_of_Q R (1#2)) N)).
71 - apply (series_cv_eq (fun n => CRpow (CR_of_Q R (1#2)) n
72 * CRpow (CR_of_Q R (1#2)) (S N))).
73 intro n. destruct (openInt n). rewrite c.
74 unfold CRminus. rewrite CRopp_plus_distr, CRopp_involutive.
75 rewrite (CRplus_comm (un n)), CRplus_assoc, <- (CRplus_assoc (un n)).
76 rewrite CRplus_opp_r, CRplus_0_l.
77 rewrite CRpow_plus_distr, Nat.add_comm. simpl.
78 rewrite <- CRmult_plus_distr_r, <- CR_of_Q_plus, Qinv_plus_distr.
79 setoid_replace (1 + 1 # 2)%Q with 1%Q. 2: reflexivity.
80 rewrite CRmult_1_l. reflexivity.
81 apply (CR_cv_proper _ (CR_of_Q R 2 * CRpow (CR_of_Q R (1 # 2)) (S N))).
82 apply series_cv_scale. apply GeoHalfTwo. simpl.
83 rewrite <- CRmult_assoc, <- CR_of_Q_mult.
84 setoid_replace (2 * (1 # 2))%Q with 1%Q. 2: reflexivity.
85 rewrite CRmult_1_l. reflexivity.
86 - exists x. exact c.
87 Qed.
88
89 (* Constructive proof that the computable Cauchy reals are uncountable.
90 We prove the even stronger contrapositive : an automatic extraction
91 of a real number appart from the image of any real sequence. *)
92 Lemma CRuncountable
93 : forall {R : ConstructiveReals}
94 (un : nat -> CRcarrier R) (a b : CRcarrier R),
95 a < b
96 -> { x : CRcarrier R
97 & prod (a < x < b)
98 (forall n:nat, CRapart R x (un n)) }.
99 Proof.
100 intros. pose proof (CRlt_minus a b H).
101 destruct (CR_cv_open_above (fun n:nat => CRpow (CR_of_Q R (1#2)) n) (b-a) 0)
102 as [n nmaj].
103 apply GeoCvZero. exact H0.
104 destruct (fun n:nat => OpenIntervalIntegrable a b H)
105 as [intervInt intervMes].
106 destruct (RealSequenceCoverMeasure un n) as [coverInt coverMes].
107 specialize (nmaj n (Nat.le_refl n)).
108 assert (0 < MeasureSet (IntegrableSetDifference _ _ intervInt coverInt)).
109 { rewrite MeasureDifference. apply CRlt_minus.
110 apply (CRle_lt_trans _ (MeasureSet coverInt)).
111 apply IntegralNonDecreasing. intros x xdf xdg. simpl.
112 destruct xdf, xdg. apply CRle_refl. 3: apply CRle_refl.
113 2: apply CRlt_asym, CRzero_lt_one. destruct a0. contradiction.
114 apply (CRle_lt_trans _ _ _ coverMes).
115 apply (CRlt_le_trans _ _ _ nmaj). rewrite intervMes. apply CRle_refl. }
116 apply PositiveMeasureInhabited in H1. destruct H1 as [x xcv].
117 exists x. destruct xcv, H1. split. split.
118 apply CRltEpsilon, H1. apply CRltEpsilon, H3.
119 intro k. destruct (CRltLinear R).
120 destruct (s (un k - CRpow (CR_of_Q R (1 # 2)) (2 + n + k)) x (un k-0)).
121 - apply CRplus_lt_compat_l, CRopp_gt_lt_contravar.
122 apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
123 - destruct (s (un k) x (un k + CRpow (CR_of_Q R (1 # 2)) (2 + n + k))).
124 + apply (CRle_lt_trans _ (un k + 0)). rewrite CRplus_0_r. apply CRle_refl.
125 apply CRplus_lt_compat_l. apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
126 + right. exact c0.
127 + exfalso. apply H2. exists k. split.
128 apply CRltForget. exact c. apply CRltForget. exact c0.
129 - left. apply (CRlt_le_trans _ _ _ c).
130 unfold CRminus. rewrite CRopp_0, CRplus_0_r. apply CRle_refl.
131 Qed.
132
133 Lemma CRuncountableDiag
134 : forall {R : ConstructiveReals}
135 (un : nat -> nat -> CRcarrier R) (a b : CRcarrier R),
136 a < b
137 -> { x : CRcarrier R
138 & prod (a < x < b)
139 (forall n k:nat, CRapart R x (un n k)) }.
140 Proof.
141 intros.
142 destruct (CRuncountable (fun p:nat => let (n, k) := diagPlaneInv p in un n k)
143 a b H).
144 exists x. split. exact (fst p). intros n k.
145 destruct p. specialize (c (diagPlane n k)).
146 rewrite diagPlaneInject in c. exact c.
147 Qed.
148
149 Lemma CRuncountableDiag3
150 : forall {R : ConstructiveReals}
151 (un : nat -> nat -> nat -> CRcarrier R) (a b : CRcarrier R),
152 a < b
153 -> { x : CRcarrier R
154 & prod (a < x < b)
155 (forall n k i:nat, CRapart R x (un n k i)) }.
156 Proof.
157 intros.
158 destruct (CRuncountableDiag
159 (fun p i:nat => let (n, k) := diagPlaneInv p in un n k i)
160 a b H).
161 exists x. split. exact (fst p). intros n k i.
162 destruct p. specialize (c (diagPlane n k) i).
163 rewrite diagPlaneInject in c. exact c.
164 Qed.
165
166
167
168 Definition StepApprox {R : ConstructiveReals} {X : Set}
169 (f : PartialFunction X)
170 (s t : CRcarrier R) (ltst : s < t) : PartialFunction X
171 := Xscale (CRinv R (t - s) (inr (CRlt_minus s t ltst)))
172 (Xminus (XminConst f t) (XminConst f s)).
173
174 Definition StepApproxIntegrable {IS : IntegrationSpace}
175 (f : PartialFunction (X (ElemFunc IS)))
176 (s t : CRcarrier (RealT (ElemFunc IS))) (ltst : 0 < s < t)
177 : IntegrableFunction f
178 -> IntegrableFunction (StepApprox f s t (snd ltst))
179 := fun fInt => IntegrableScale _ _
180 (IntegrableMinus
181 (IntegrableMinConst f t fInt (CRlt_trans 0 s t (fst ltst) (snd ltst)))
182 (IntegrableMinConst f s fInt (fst ltst))).
183
184 Lemma StepApproxBetween : forall {R : ConstructiveReals}
185 (t : CRcarrier R) (tPos : 0 < t) (n : nat),
186 0 < t*CR_of_Q _ (1-(1#Pos.of_nat (2*S n))) < t.
187 Proof.
188 split.
189 - apply CRmult_lt_0_compat. exact tPos. apply CR_of_Q_pos.
190 unfold Qminus.
191 rewrite <- (Qplus_opp_r (1 # Pos.of_nat (2 * S n))), Qplus_lt_l.
192 unfold Qlt, Qnum, Qden. do 2 rewrite Z.mul_1_l.
193 apply Pos2Z.pos_lt_pos. rewrite Pos2Nat.inj_lt, Nat2Pos.id.
194 simpl. apply le_n_S. rewrite Nat.add_comm. apply le_n_S, Nat.le_0_l.
195 discriminate.
196 - apply (CRlt_le_trans _ (t* CR_of_Q _ 1)).
197 2: rewrite CRmult_1_r; apply CRle_refl.
198 apply CRmult_lt_compat_l. exact tPos. apply CR_of_Q_lt.
199 apply (Qplus_lt_l _ _ ((1 # Pos.of_nat (2 * S n))-1)).
200 ring_simplify. reflexivity.
201 Qed.
202
203 Lemma StepApproxCv : forall {R : ConstructiveReals} (t : CRcarrier R),
204 CR_cv R (fun n => t*CR_of_Q _ (1-(1#Pos.of_nat (2*S n)))) t.
205 Proof.
206 intros. apply (CR_cv_proper _ (1*t)). 2: apply CRmult_1_l.
207 apply (CR_cv_eq _ (fun n : nat => CR_of_Q R (1 - (1 # Pos.of_nat (2 * S n))) * t)).
208 intro n. apply CRmult_comm.
209 apply CR_cv_scale. intro p. exists (Pos.to_nat p).
210 intros.
211 setoid_replace (CR_of_Q R (1 - (1 # Pos.of_nat (2 * S i))) - 1)
212 with (-CR_of_Q R (1 # Pos.of_nat (2 * S i))).
213 - rewrite CRabs_opp, CRabs_right. apply CR_of_Q_le.
214 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
215 apply Pos2Z.pos_le_pos. rewrite Pos2Nat.inj_le, Nat2Pos.id.
216 2: discriminate. apply (Nat.le_trans _ _ _ H). simpl.
217 apply le_S. apply (Nat.le_trans _ (i+0)).
218 rewrite Nat.add_comm. apply Nat.le_refl.
219 apply Nat.add_le_mono_l, Nat.le_0_l.
220 apply CR_of_Q_le. discriminate.
221 - unfold Qminus. rewrite CR_of_Q_plus, CR_of_Q_opp.
222 unfold CRminus. rewrite CRplus_comm, <- CRplus_assoc, CRplus_opp_l.
223 rewrite CRplus_0_l. reflexivity.
224 Qed.
225
226 Lemma StepApproxAbove :
227 forall {R : ConstructiveReals} {X : Set}
228 (f : PartialFunction X)
229 (t : CRcarrier R) (tPos : 0 < t) (x : X)
230 (xnD : nat -> Domain f x * Domain f x)
231 (l : CRcarrier R),
232 0 < l
233 -> CR_cv R
234 (fun n : nat =>
235 partialApply
236 (StepApprox f (t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S n)))) t
237 (snd (StepApproxBetween t tPos n))) x (xnD n)) l
238 -> t <= partialApply f x (fst (xnD O)).
239 Proof.
240 intros. intro abs.
241 destruct (CR_cv_open_below _ _ _ (StepApproxCv t) abs) as [n nmaj].
242 assert (CR_cv R
243 (fun n : nat =>
244 partialApply
245 (StepApprox f (t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S n)))) t
246 (snd (StepApproxBetween t tPos n))) x (xnD n)) 0).
247 intro p. exists n. intros. unfold StepApprox.
248 rewrite applyXscale.
249 setoid_replace (partialApply
250 (Xminus (XminConst f t) (XminConst f (t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S i)))))) x
251 (xnD i)) with (CR_of_Q R 0).
252 rewrite CRmult_0_r. unfold CRminus. rewrite CRplus_opp_r, CRabs_right.
253 apply CR_of_Q_le. discriminate. apply CRle_refl.
254 destruct (xnD i).
255 rewrite (applyXminus (XminConst f t)
256 (XminConst f (t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S i))))) x).
257 rewrite applyXminConst, applyXminConst.
258 rewrite CRmin_left, CRmin_left.
259 unfold CRminus. rewrite (DomainProp f x d d0), CRplus_opp_r. reflexivity.
260 specialize (nmaj i H1). rewrite (DomainProp f x d0 (fst (xnD 0%nat))).
261 apply CRlt_asym, nmaj.
262 specialize (nmaj i H1). rewrite (DomainProp f x d (fst (xnD 0%nat))).
263 apply CRlt_asym, (CRlt_trans _ _ _ nmaj). apply StepApproxBetween, tPos.
264 rewrite <- (CR_cv_unique _ _ _ H1 H0) in H. exact (CRlt_asym 0 0 H H).
265 Qed.
266
267 Lemma StepApproxBelow :
268 forall {R : ConstructiveReals} {X : Set}
269 (f : PartialFunction X)
270 (t : CRcarrier R) (tPos : 0 < t) (x : X)
271 (xnD : nat -> Domain f x * Domain f x)
272 (l : CRcarrier R),
273 l < 1
274 -> CR_cv R
275 (fun n : nat =>
276 partialApply
277 (StepApprox f (t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S n)))) t
278 (snd (StepApproxBetween t tPos n))) x (xnD n)) l
279 -> partialApply f x (fst (xnD O)) < t.
280 Proof.
281 intros.
282 destruct (CR_cv_open_above _ _ _ H0 H) as [k kmaj].
283 specialize (kmaj k (Nat.le_refl k)).
284 unfold StepApprox in kmaj. rewrite applyXscale in kmaj.
285 apply (CRmult_lt_compat_l (t - t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S k)))))
286 in kmaj.
287 2: apply CRlt_minus, StepApproxBetween, tPos.
288 destruct (xnD k) as [d d0].
289 assert (partialApply (XminConst f t) x d < t) as H1.
290 { apply (CRplus_lt_reg_r
291 (- partialApply (XminConst f (t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S k))))) x d0)).
292 apply (CRle_lt_trans
293 (partialApply (XminConst f t) x d +
294 - partialApply (XminConst f (t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S k))))) x d0 ))
295 in kmaj.
296 apply (CRlt_le_trans _ _ _ kmaj).
297 rewrite CRmult_1_r.
298 apply CRplus_le_compat_l, CRopp_ge_le_contravar. apply CRmin_r.
299 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l.
300 rewrite (applyXminus
301 (XminConst f t)
302 (XminConst f (t * CR_of_Q R (1 - (1 # Pos.of_nat (2 * S k)))))).
303 apply CRle_refl. }
304 clear kmaj.
305 apply (CRle_lt_trans _ (partialApply (XminConst f t) x d)).
306 2: exact H1. apply CRmin_lt_r in H1. rewrite H1.
307 rewrite (DomainProp f x _ d). apply CRle_refl.
308 Qed.
309
310 Lemma AffineLe
311 : forall {R : ConstructiveReals}
312 (a b c d x low up : CRcarrier R),
313 a * low + b <= c * low + d
314 -> a * up + b <= c * up + d
315 -> low <= x <= up
316 -> a * x + b <= c * x + d.
317 Proof.
318 intro R.
319 assert (forall (a b x low up : CRcarrier R),
320 0 <= a * low + b
321 -> 0 <= a * up + b
322 -> low <= x <= up
323 -> 0 <= a * x + b).
324 { intros.
325 apply (CRle_trans _ (CRmin (a*low+b) (a*up+b))).
326 apply CRmin_glb; assumption.
327 rewrite CRplus_comm, (CRplus_comm (a*up)), <- CRmin_plus, CRplus_comm.
328 apply CRplus_le_compat_r.
329 intro abs. apply CRlt_min in abs. destruct abs.
330 clear H H0. apply CRlt_minus in c.
331 pose proof (CRmult_pos_appart_zero a (low-x)). destruct H.
332 apply (CRlt_le_trans _ _ _ c). unfold CRminus.
333 rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l.
334 apply CRle_refl.
335 + contradict c. apply (CRle_trans _ (a * (low - x))).
336 unfold CRminus. rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l.
337 apply CRle_refl. rewrite <- (CRmult_0_r a). apply CRmult_le_compat_l.
338 apply CRlt_asym, c1.
339 rewrite <- (CRplus_opp_r x). apply CRplus_le_compat_r.
340 exact (proj1 H1).
341 + apply CRopp_gt_lt_contravar in c0. contradict c0.
342 fold (-(a*x) <= -(a*up)).
343 do 2 rewrite CRopp_mult_distr_l. apply CRmult_le_compat_l.
344 rewrite <- CRopp_0. apply CRopp_ge_le_contravar, CRlt_asym, c1.
345 exact (proj2 H1). }
346 intros. apply (CRplus_le_reg_r (-(a*x+b))).
347 rewrite CRplus_opp_r, CRopp_plus_distr, CRplus_assoc.
348 rewrite (CRplus_comm d), <- CRplus_assoc, <- CRplus_assoc.
349 rewrite CRopp_mult_distr_l, <- CRmult_plus_distr_r.
350 rewrite CRplus_assoc. apply (H (c-a) (-b+d) x low up).
351 3: exact H2.
352 rewrite (CRplus_comm (-b)), <- CRplus_assoc.
353 apply (CRplus_le_reg_r b).
354 rewrite CRplus_0_l, CRplus_assoc, CRplus_opp_l, CRplus_0_r.
355 unfold CRminus. rewrite CRmult_plus_distr_r, CRplus_comm, <- CRplus_assoc.
356 apply (CRplus_le_reg_r (a*low)).
357 rewrite CRplus_assoc, <- CRopp_mult_distr_l, CRplus_opp_l, CRplus_0_r.
358 rewrite CRplus_comm, (CRplus_comm d). exact H0.
359 rewrite (CRplus_comm (-b)), <- CRplus_assoc.
360 apply (CRplus_le_reg_r b).
361 rewrite CRplus_0_l, CRplus_assoc, CRplus_opp_l, CRplus_0_r.
362 unfold CRminus. rewrite CRmult_plus_distr_r, CRplus_comm, <- CRplus_assoc.
363 apply (CRplus_le_reg_r (a*up)).
364 rewrite CRplus_assoc, <- CRopp_mult_distr_l, CRplus_opp_l, CRplus_0_r.
365 rewrite CRplus_comm, (CRplus_comm d). exact H1.
366 Qed.
367
368 Lemma StepApproxLe
369 : forall {R : ConstructiveReals}
370 (c s1 t1 s2 t2 : CRcarrier R)
371 (ltst1 : s1 < t1) (ltst2 : s2 < t2),
372 s1 <= s2
373 -> t1 <= t2
374 -> CRinv R (t2 - s2) (inr (CRlt_minus s2 t2 ltst2)) *
375 (CRmin c t2 + - CRmin c s2) <=
376 CRinv R (t1 - s1) (inr (CRlt_minus s1 t1 ltst1)) *
377 (CRmin c t1 + - CRmin c s1).
378 Proof.
379 intros. destruct (CRltLinear R) as [_ s].
380 destruct (s s2 c t2 ltst2).
381 - rewrite (CRmin_right c s2), (CRmin_right c s1).
382 2: apply (CRle_trans _ _ _ H), CRlt_asym, c0.
383 2: apply CRlt_asym, c0.
384 apply (CRmult_le_reg_l (t1-s1)). apply CRlt_minus, ltst1.
385 rewrite <- CRmult_assoc, <- CRmult_assoc, CRinv_r, CRmult_1_l, CRmult_comm.
386 apply (CRplus_le_reg_r s1). rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
387 apply CRmin_glb.
388 + apply (CRplus_le_reg_r (-s1)).
389 rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r.
390 apply (CRmult_le_reg_r (t2-s2)). apply CRlt_minus, ltst2.
391 rewrite CRmult_assoc, CRmult_assoc, CRinv_l, CRmult_1_r.
392 rewrite CRplus_comm, CRmin_plus, CRmult_comm, <- CRmin_mult.
393 2: apply CRlt_asym, CRlt_minus, ltst1.
394 intro abs. apply CRlt_min in abs. destruct abs.
395 rewrite (CRplus_comm (-s2)) in c2. apply CRmult_lt_reg_r in c2.
396 2: apply CRlt_minus, ltst2. apply CRplus_lt_reg_r in c2.
397 assert ((t1 - s1) * (- s2 + c) <= (c + - s1) * (t2 - s2)).
398 { clear c1.
399 rewrite CRplus_comm, CRmult_plus_distr_l.
400 rewrite (CRmult_comm (c+-s1)), CRmult_plus_distr_l.
401 apply (AffineLe _ _ _ _ _ s2 t1).
402 do 2 rewrite <- CRmult_plus_distr_l.
403 rewrite CRplus_opp_r, CRmult_0_r.
404 apply CRmult_le_0_compat. apply CRlt_asym, CRlt_minus, ltst2.
405 rewrite <- (CRplus_opp_r s1). apply CRplus_le_compat_r, H.
406 do 2 rewrite <- CRmult_plus_distr_l.
407 rewrite CRmult_comm. apply CRmult_le_compat_r.
408 apply CRlt_asym, CRlt_minus, ltst1.
409 apply CRplus_le_compat_r, H0.
410 split; apply CRlt_asym; assumption. }
411 contradiction.
412 + apply (CRplus_le_reg_r (-s1)). rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r.
413 apply (CRmult_le_reg_r (t2-s2)). apply CRlt_minus, ltst2.
414 rewrite CRmult_assoc, CRmult_assoc, CRinv_l, CRmult_1_r.
415 rewrite CRmult_comm. apply CRmult_le_compat_l.
416 apply CRlt_asym, CRlt_minus, ltst1.
417 apply CRplus_le_compat_r, CRmin_r.
418 - rewrite CRmin_left. 2: apply CRlt_asym, c0.
419 destruct (s s1 c t1 ltst1).
420 + rewrite (CRmin_right c s1). 2: apply CRlt_asym, c1.
421 apply (CRmult_le_reg_l (t1-s1)). apply CRlt_minus, ltst1.
422 rewrite <- CRmult_assoc, <- CRmult_assoc, CRinv_r, CRmult_1_l.
423 apply (CRplus_le_reg_r s1). rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
424 apply CRmin_glb.
425 apply (CRplus_le_reg_r (-s1)). rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r.
426 rewrite CRmult_comm.
427 apply (CRmult_le_reg_r (t2-s2)). apply CRlt_minus, ltst2.
428 rewrite CRmult_assoc, CRmult_assoc, CRinv_l, CRmult_1_r.
429 setoid_replace (- CRmin c s2) with (-(1) * CRmin c s2).
430 rewrite <- CRmax_min_mult_neg. do 2 rewrite <- CRopp_mult_distr_l, CRmult_1_l.
431 rewrite CRmax_plus, CRmult_comm, <- CRmax_mult. apply CRmax_lub.
432 rewrite CRplus_opp_r, CRmult_0_r. rewrite <- (CRmult_0_r (c-s1)).
433 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, c1.
434 apply CRlt_asym, CRlt_minus, ltst2.
435 rewrite CRmult_plus_distr_l, (CRmult_comm (c+-s1)), CRmult_plus_distr_l.
436 apply (AffineLe _ _ _ _ _ s1 t2).
437 do 2 rewrite <- CRmult_plus_distr_l. rewrite CRplus_opp_r, CRmult_0_r.
438 rewrite <- (CRmult_0_r (t1-s1)). apply CRmult_le_compat_l.
439 apply CRlt_asym, CRlt_minus, ltst1.
440 rewrite <- (CRplus_opp_r s2). apply CRplus_le_compat_r, H.
441 do 2 rewrite <- CRmult_plus_distr_l. rewrite CRmult_comm.
442 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltst2.
443 apply CRplus_le_compat_r, H0.
444 split; apply CRlt_asym; assumption.
445 apply CRlt_asym, CRlt_minus, ltst1.
446 apply (CRplus_le_reg_l 1). rewrite CRplus_opp_r, CRplus_0_r.
447 apply CRlt_asym, CRzero_lt_one.
448 rewrite <- CRopp_mult_distr_l, CRmult_1_l. reflexivity.
449 apply (CRplus_le_reg_r (-s1)). rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r.
450 rewrite <- (CRmult_1_r (t1 + - s1)), CRmult_assoc.
451 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltst1.
452 apply (CRmult_le_reg_l (t2-s2)). apply CRlt_minus, ltst2.
453 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l, CRmult_1_r.
454 apply (CRplus_le_reg_r (CRmin c s2)).
455 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
456 rewrite CRmin_plus. apply CRmin_glb.
457 apply (CRplus_le_reg_l s2). rewrite <- CRplus_assoc. apply CRplus_le_compat_r.
458 rewrite CRplus_comm. unfold CRminus.
459 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
460 apply CRlt_asym, ltst2. unfold CRminus.
461 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
462 apply CRlt_asym, c0.
463 + clear c0. rewrite (CRmin_left c t1). 2: apply CRlt_asym, c1.
464 apply (CRmult_le_reg_l (t2-s2)). apply CRlt_minus, ltst2.
465 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l.
466 apply (CRplus_le_reg_l (-c)).
467 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
468 setoid_replace (- CRmin c s2) with (-(1) * CRmin c s2).
469 2: rewrite <- CRopp_mult_distr_l, CRmult_1_l; reflexivity.
470 rewrite <- CRmax_min_mult_neg. apply CRmax_lub.
471 rewrite <- CRopp_mult_distr_l, CRmult_1_l.
472 apply (CRle_trans _ (-c +0)). rewrite CRplus_0_r; apply CRle_refl.
473 apply CRplus_le_compat_l. apply (CRle_trans _ ((t2-s2)*0)).
474 rewrite CRmult_0_r; apply CRle_refl. apply CRmult_le_compat_l.
475 apply CRlt_asym, CRlt_minus, ltst2.
476 apply (CRmult_le_reg_l (t1-s1)). apply CRlt_minus, ltst1.
477 rewrite CRmult_0_r, <- CRmult_assoc, CRinv_r, CRmult_1_l.
478 rewrite <- (CRplus_opp_r (CRmin c s1)). apply CRplus_le_compat_r, CRmin_l.
479 rewrite <- CRopp_mult_distr_l, CRmult_1_l.
480 apply (CRplus_le_reg_l c).
481 rewrite <- CRplus_assoc, CRplus_opp_r, CRplus_0_l, CRmult_comm.
482 apply (CRmult_le_reg_l (t1-s1)). apply CRlt_minus, ltst1.
483 rewrite <- CRmult_assoc, <- CRmult_assoc, CRinv_r, CRmult_1_l.
484 rewrite CRmult_plus_distr_r.
485 apply (CRplus_le_reg_l (-(c*(t2-s2)))).
486 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
487 rewrite (CRmult_comm (-CRmin c s1)), <- CRopp_mult_distr_r.
488 rewrite <- CRmin_mult. 2: apply CRlt_asym, CRlt_minus, ltst2.
489 rewrite <- CRopp_involutive, CRopp_plus_distr, CRopp_involutive.
490 apply CRopp_ge_le_contravar.
491 intro abs. apply CRlt_min in abs. destruct abs.
492 rewrite <- (CRplus_0_r ((t2-s2)*c)), (CRmult_comm (t2-s2)) in c0.
493 apply CRplus_lt_reg_l in c0.
494 apply (CRplus_lt_compat_l R ((t1 - s1) * (c + - s2))) in c0.
495 rewrite CRplus_opp_r, CRplus_0_r in c0.
496 rewrite <- (CRmult_0_r (t1-s1)) in c0. apply CRmult_lt_reg_l in c0.
497 2: apply CRlt_minus, ltst1. rewrite <- (CRplus_opp_r s2) in c0.
498 apply CRplus_lt_reg_r in c0.
499 assert ((t2-s2)*s1 <= c * (t2 - s2) + - ((t1 - s1) * (c + - s2))).
500 { apply (CRplus_le_reg_r ((t1 - s1) * (c + - s2))).
501 rewrite CRplus_assoc, CRplus_opp_l, CRplus_comm.
502 rewrite CRmult_plus_distr_l, CRplus_assoc, (CRmult_comm c).
503 apply (AffineLe _ _ _ _ _ s2 t1).
504 3: split; apply CRlt_asym; assumption.
505 rewrite CRplus_0_r, <- CRplus_assoc, <- CRopp_mult_distr_r.
506 rewrite CRplus_opp_r, CRplus_0_l. apply CRmult_le_compat_l.
507 apply CRlt_asym, CRlt_minus, ltst2. exact H.
508 rewrite CRplus_0_r, <- CRplus_assoc, <- CRmult_plus_distr_l.
509 apply (CRplus_le_reg_r (-((t2-s2)*s1))).
510 rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r, CRopp_mult_distr_r.
511 rewrite <- CRmult_plus_distr_l, CRmult_comm.
512 apply CRmult_le_compat_r. apply CRlt_asym, CRlt_minus, ltst1.
513 apply CRplus_le_compat_r, H0. }
514 contradiction. apply (CRplus_le_reg_l 1).
515 rewrite CRplus_opp_r, CRplus_0_r. apply CRlt_asym, CRzero_lt_one.
516 Qed.
517
518 Definition InverseImageIntegrableGivenLimit
519 {IS : IntegrationSpace}
520 (f : PartialFunction (X (ElemFunc IS)))
521 (fInt : IntegrableFunction f)
522 (t : CRcarrier (RealT (ElemFunc IS))) (tPos : 0 < t)
523 : CR_cauchy _ (fun n:nat => Integral (StepApproxIntegrable
524 f _ t (StepApproxBetween t tPos n) fInt))
525 -> { limInt : IntegrableSet (fun x => exists xD:Domain f x, t <= partialApply f x xD)
526 & CR_cv _ (fun n:nat => Integral (StepApproxIntegrable
527 f _ t (StepApproxBetween t tPos n) fInt))
528 (MeasureSet limInt) }.
529 Proof.
530 intro cv. apply CR_complete in cv. destruct cv as [a cv].
531 destruct (IntegralMonotoneConvergenceDecr
532 IS _ (fun n => StepApproxIntegrable
533 f _ _ (StepApproxBetween t tPos n) fInt) a)
534 as [limInt c].
535 - intros n x xdf xdg. destruct xdf, xdg. unfold StepApprox.
536 rewrite applyXscale, applyXscale.
537 rewrite (applyXminus
538 (XminConst f t)
539 (XminConst f (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S (S n))))))).
540 rewrite (applyXminus
541 (XminConst f t)
542 (XminConst f (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S n)))))).
543 do 4 rewrite applyXminConst.
544 rewrite (DomainProp f x d2 d), (DomainProp f x d1 d), (DomainProp f x d0 d).
545 apply StepApproxLe. 2: apply CRle_refl.
546 apply CRmult_le_compat_l. apply CRlt_asym, tPos.
547 apply CR_of_Q_le. apply Qplus_le_r, Qopp_le_compat.
548 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
549 apply Pos2Z.pos_le_pos. rewrite Pos2Nat.inj_le, Nat2Pos.id, Nat2Pos.id.
550 2: discriminate. 2: discriminate.
551 simpl. apply le_n_S, le_S. apply Nat.add_le_mono_l.
552 apply le_S, Nat.le_refl.
553 - exact cv.
554 - assert (PartialRestriction
555 (XpointwiseLimit
556 (fun n : nat =>
557 StepApprox f (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S n)))) t
558 (snd (StepApproxBetween t tPos n))))
559 (CharacFunc (fun x => exists xD:Domain f x, t <= partialApply f x xD))) as res.
560 { clear c limInt cv a. split.
561 + intros x [xnD xnlim]. simpl in xnD.
562 apply CR_complete in xnlim. destruct xnlim as [l xnlim].
563 destruct (CRltLinear (RealT (ElemFunc IS))).
564 destruct (s 0 l 1 (CRzero_lt_one _)).
565 left. exists (fst (xnD O)).
566 exact (StepApproxAbove f t tPos x xnD l c xnlim).
567 right. intros [xD abs]. apply abs. clear abs.
568 rewrite (DomainProp f x xD (fst (xnD O))).
569 exact (StepApproxBelow f t tPos x xnD l c xnlim).
570 + intros. apply applyPointwiseLimit. destruct xG.
571 apply (CR_cv_eq _ (fun _ => 1)). 2: apply CR_cv_const.
572 intro n. destruct xD as [xnD H].
573 unfold StepApprox. rewrite applyXscale.
574 setoid_replace (partialApply
575 (Xminus (XminConst f t)
576 (XminConst f (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S n)))))) x
577 (xnD n))
578 with (t - t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S n)))).
579 rewrite CRinv_l. reflexivity. destruct (xnD n).
580 apply CRplus_morph. rewrite applyXminConst.
581 rewrite CRmin_right. reflexivity.
582 destruct e. rewrite (DomainProp f x d x0). exact H0.
583 rewrite applyXscale. rewrite applyXminConst, CRmin_right.
584 rewrite <- CRopp_mult_distr_l, CRmult_1_l. reflexivity.
585 destruct e. rewrite (DomainProp f x d0 x0).
586 apply (CRle_trans _ t). 2: exact H0.
587 apply CRlt_asym, StepApproxBetween, tPos.
588 destruct xD as [xnD H]. simpl in xnD.
589 apply CR_complete in H. destruct H as [l lcv].
590 destruct (CRltLinear (RealT (ElemFunc IS))).
591 destruct (s 0 l 1 (CRzero_lt_one _)).
592 exfalso. apply n. exists (fst (xnD O)).
593 exact (StepApproxAbove f t tPos x xnD l c lcv).
594 pose proof (StepApproxBelow f t tPos x xnD l c lcv).
595 destruct (CR_cv_open_below _ _ _ (StepApproxCv t) H) as [k kmaj].
596 intro i. exists k. intros.
597 setoid_replace (partialApply
598 (StepApprox f
599 (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S i0)))) t
600 (snd (StepApproxBetween t tPos i0))) x (xnD i0))
601 with (CR_of_Q (RealT (ElemFunc IS)) 0).
602 simpl. unfold CRminus. rewrite CRplus_opp_r, CRabs_right.
603 apply CR_of_Q_le. discriminate.
604 apply CRle_refl. unfold StepApprox. rewrite applyXscale.
605 setoid_replace (partialApply
606 (Xminus (XminConst f t)
607 (XminConst f
608 (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S i0)))))) x
609 (xnD i0) ) with (CR_of_Q (RealT (ElemFunc IS)) 0).
610 rewrite CRmult_0_r. reflexivity. destruct (xnD i0).
611 rewrite (applyXminus (XminConst f t)
612 (XminConst f (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S i0))))) ).
613 rewrite applyXminConst, applyXminConst, CRmin_left, CRmin_left.
614 unfold CRminus; rewrite (DomainProp f x d0 d), CRplus_opp_r; reflexivity.
615 rewrite (DomainProp f x d0 (fst (xnD O))).
616 apply CRlt_asym, kmaj, H0.
617 rewrite (DomainProp f x d (fst (xnD O))).
618 apply CRlt_asym, H. }
619 exists (IntegrableFunctionExtensional _ _ res limInt).
620 unfold MeasureSet. rewrite IntegralRestrict.
621 exact (CR_cv_proper _ _ _ cv (CReq_sym _ _ c)).
622 Qed.
623
624 (*
625 To prove that the inverse image {t <= f} is integrable, we have reduced
626 the problem of giving a sequence of representative L-functions to the
627 problem of the convergence of a non-increasing and bounded sequence :
628 lim_{s -> t} Integral (StepApproxIntegrable f s t).
629
630 Classically this convergence is automatic at each t, which gives a
631 non-increasing function of t that is caglad. It is well-known classically
632 that those functions are almost everywhere continuous,
633 with at most a countable infinity of jump points.
634
635 Constructively this convergence is not automatic, so we are left with
636 studying the function of 2 variables
637 fun s t => Integral (StepApproxIntegrable f s t) with 0 < s < t.
638 We will define constructively what t's are jump points of the intended
639 limit function, prove that they are at most countable, and prove that
640 outside of them the limit exists constructively. Besides at those
641 continuity points t we will also have equal measures for the subsets
642 {t <= f} and {t < f}.
643 *)
644
645
646 (* The monotone property extended constructively in 2 variables. *)
647 Lemma StepApproxIntegralIncr
648 : forall {IS : IntegrationSpace}
649 (f : PartialFunction (X (ElemFunc IS)))
650 (fInt : IntegrableFunction f)
651 (s1 t1 s2 t2 : CRcarrier (RealT (ElemFunc IS)))
652 (ltst1 : 0 < s1 < t1) (ltst2 : 0 < s2 < t2),
653 s1 <= s2
654 -> t1 <= t2
655 -> Integral (StepApproxIntegrable f s2 t2 ltst2 fInt)
656 <= Integral (StepApproxIntegrable f s1 t1 ltst1 fInt).
657 Proof.
658 intros. apply IntegralNonDecreasing.
659 intros x xdf xdg. simpl. destruct xdf, xdg.
660 rewrite (DomainProp f x d2 d), (DomainProp f x d1 d), (DomainProp f x d0 d).
661 generalize (partialApply f x d). intro c.
662 rewrite <- CRopp_mult_distr_l, CRmult_1_l.
663 rewrite <- CRopp_mult_distr_l, CRmult_1_l.
664 apply StepApproxLe; assumption.
665 Qed.
666
667 Record IntervalExtension {R : ConstructiveReals} {x y : CRcarrier R} : Set
668 := {
669 ext_eta : CRcarrier R;
670 left_ordered : 0 < x - ext_eta < x;
671 right_ordered : y < y + ext_eta;
672 }.
673
674 Lemma IntExtRightPos : forall {R : ConstructiveReals} {x y : CRcarrier R}
675 (IntExt : @IntervalExtension R x y),
676 x <= y -> 0 < y.
677 Proof.
678 intros. apply (CRlt_le_trans _ x).
679 apply (CRlt_trans _ _ _ (fst (left_ordered IntExt)) (snd (left_ordered IntExt))).
680 exact H.
681 Qed.
682
683 (* Now for t1 <= t2 we bound the difference of measures of
684 { t1 <= f } and { t2 <= f }, left limit at t1 and right
685 limit at t2, ie including both jumps at the extreme points t1 and t2. *)
686 Definition StepApproxBound
687 {IS : IntegrationSpace}
688 (f : PartialFunction (X (ElemFunc IS)))
689 (fInt : IntegrableFunction f)
690 (t1 t2 b : CRcarrier (RealT (ElemFunc IS)))
691 (let1t2 : t1 <= t2)
692 : Set
693 := { ext : @IntervalExtension _ t1 t2
694 & Integral (StepApproxIntegrable
695 f (t1 - ext_eta ext) t1
696 (left_ordered ext) fInt)
697 - Integral (StepApproxIntegrable
698 f t2 (t2 + ext_eta ext)
699 (pair (IntExtRightPos ext let1t2)
700 (right_ordered ext)) fInt)
701 < b }.
702
703 (* Exlude jumps at extreme points t1, t2 for open intervals ]t1,t2[. *)
704 Definition StepApproxBoundOpen
705 {IS : IntegrationSpace}
706 (f : PartialFunction (X (ElemFunc IS)))
707 (fInt : IntegrableFunction f)
708 (t1 t2 b : CRcarrier (RealT (ElemFunc IS)))
709 : Prop
710 := forall x y u v (ltxy : 0 < x < y) (ltuv : 0 < u < v),
711 t1 < x
712 -> y <= u
713 -> v < t2
714 -> Integral (StepApproxIntegrable f x y ltxy fInt)
715 - Integral (StepApproxIntegrable f u v ltuv fInt)
716 <= b.
717
718 Lemma StepApproxBoundPos
719 : forall {IS : IntegrationSpace}
720 (f : PartialFunction (X (ElemFunc IS)))
721 (fInt : IntegrableFunction f)
722 (t1 t2 b : CRcarrier (RealT (ElemFunc IS))) (let1t2 : t1 <= t2),
723 StepApproxBound f fInt t1 t2 b let1t2 -> 0 < b.
724 Proof.
725 intros. destruct H.
726 apply (CRle_lt_trans _ (Integral (StepApproxIntegrable f (t1 - ext_eta x) t1 (left_ordered x) fInt) -
727 Integral
728 (StepApproxIntegrable f t2 (t2 + ext_eta x) (IntExtRightPos x let1t2, right_ordered x) fInt))).
729 2: exact c.
730 apply (CRplus_le_reg_r (Integral (StepApproxIntegrable f t2 (t2 + ext_eta x) (IntExtRightPos x let1t2, right_ordered x) fInt))).
731 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_0_l.
732 clear c. apply StepApproxIntegralIncr. destruct x. simpl.
733 apply (CRle_trans _ t1). apply CRlt_asym, left_ordered0.
734 exact let1t2. destruct x. simpl.
735 apply (CRle_trans _ t2). exact let1t2.
736 apply CRlt_asym, right_ordered0.
737 Qed.
738
739 (* It is easier to detect that a monotone sequence converges. *)
740 Lemma StepApproxBoundCv
741 : forall {IS : IntegrationSpace}
742 (f : PartialFunction (X (ElemFunc IS)))
743 (fInt : IntegrableFunction f)
744 (t : CRcarrier (RealT (ElemFunc IS))) (tPos : 0 < t),
745 (forall b : CRcarrier (RealT (ElemFunc IS)),
746 0 < b -> StepApproxBound f fInt t t b (CRle_refl t))
747 -> CR_cauchy _ (fun n:nat => Integral (StepApproxIntegrable
748 f _ t (StepApproxBetween t tPos n) fInt)).
749 Proof.
750 intros. intro p.
751 destruct (H (CR_of_Q _ (1 # p))) as [ext extmaj].
752 apply CR_of_Q_pos. reflexivity.
753 assert (0 < ext_eta ext).
754 { destruct ext; clear extmaj. simpl.
755 apply (CRplus_lt_reg_l _ t). rewrite CRplus_0_r. exact right_ordered0. }
756 destruct (CR_cv_open_below _ (t-ext_eta ext) t (StepApproxCv t)) as [n nmaj].
757 apply ext. exists n. intros. destruct (le_lt_dec i j).
758 - rewrite CRabs_right.
759 apply (CRle_trans _ (Integral (StepApproxIntegrable f (t - ext_eta ext) t (left_ordered ext) fInt) -
760 Integral
761 (StepApproxIntegrable f t (t + ext_eta ext)
762 (IntExtRightPos ext (CRle_refl t), right_ordered ext) fInt))).
763 2: apply CRlt_asym; exact extmaj. apply CRplus_le_compat.
764 apply StepApproxIntegralIncr. apply CRlt_asym, nmaj, H1.
765 apply CRle_refl. apply CRopp_ge_le_contravar.
766 apply StepApproxIntegralIncr. apply CRlt_asym, StepApproxBetween, tPos.
767 apply CRlt_asym, ext.
768 apply (CRplus_le_reg_r (Integral
769 (StepApproxIntegrable f (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S j)))) t
770 (StepApproxBetween t tPos j) fInt))).
771 unfold CRminus. rewrite CRplus_0_l, CRplus_assoc, CRplus_opp_l, CRplus_0_r.
772 apply StepApproxIntegralIncr. 2: apply CRle_refl.
773 apply CRmult_le_compat_l. apply CRlt_asym, tPos.
774 apply CR_of_Q_le, Qplus_le_r, Qopp_le_compat.
775 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
776 apply Pos2Z.pos_le_pos. rewrite Pos2Nat.inj_le, Nat2Pos.id, Nat2Pos.id.
777 apply Nat.mul_le_mono_nonneg_l. auto. apply le_n_S, l.
778 discriminate. discriminate.
779 - rewrite CRabs_minus_sym. rewrite CRabs_right.
780 apply (CRle_trans _ (Integral (StepApproxIntegrable f (t - ext_eta ext) t (left_ordered ext) fInt) -
781 Integral
782 (StepApproxIntegrable f t (t + ext_eta ext)
783 (IntExtRightPos ext (CRle_refl t), right_ordered ext) fInt))).
784 2: apply CRlt_asym; exact extmaj. apply CRplus_le_compat.
785 apply StepApproxIntegralIncr. apply CRlt_asym, nmaj, H2.
786 apply CRle_refl. apply CRopp_ge_le_contravar.
787 apply StepApproxIntegralIncr. apply CRlt_asym, StepApproxBetween, tPos.
788 apply CRlt_asym, ext.
789 apply (CRplus_le_reg_r (Integral
790 (StepApproxIntegrable f (t * CR_of_Q (RealT (ElemFunc IS)) (1 - (1 # Pos.of_nat (2 * S i)))) t
791 (StepApproxBetween t tPos i) fInt))).
792 unfold CRminus. rewrite CRplus_0_l, CRplus_assoc, CRplus_opp_l, CRplus_0_r.
793 apply StepApproxIntegralIncr. 2: apply CRle_refl.
794 apply CRmult_le_compat_l. apply CRlt_asym, tPos.
795 apply CR_of_Q_le, Qplus_le_r, Qopp_le_compat.
796 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
797 apply Pos2Z.pos_le_pos. rewrite Pos2Nat.inj_le, Nat2Pos.id, Nat2Pos.id.
798 apply Nat.mul_le_mono_nonneg_l. auto. apply le_S, l.
799 discriminate. discriminate.
800 Qed.
801
802 Definition BinarySubdiv {R : ConstructiveReals} (a b : CRcarrier R) (n i : nat)
803 : CRcarrier R
804 := a + CR_of_Q R (Z.of_nat i # 1) * (b-a) * CRpow (CR_of_Q R ((/2))) n.
805
806 Lemma BinarySubdivIncr
807 : forall {R : ConstructiveReals} (a b : CRcarrier R) (n i : nat),
808 0 < a < b
809 -> 0 < BinarySubdiv a b n i < BinarySubdiv a b n (S i).
810 Proof.
811 intros. assert (0 < (b - a) * CRpow (CR_of_Q R (/ 2)) n).
812 { apply CRmult_lt_0_compat. apply CRlt_minus. exact (snd H).
813 apply CRpow_gt_zero. apply CR_of_Q_pos. reflexivity. }
814 split.
815 - unfold BinarySubdiv. apply (CRlt_le_trans _ (a + 0)).
816 rewrite CRplus_0_r. exact (fst H).
817 apply CRplus_le_compat_l. rewrite CRmult_assoc.
818 apply CRmult_le_0_compat.
819 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
820 do 2 rewrite Z.mul_1_r. apply Zle_0_nat. apply CRlt_asym, H0.
821 - apply CRplus_lt_compat_l.
822 apply CRmult_lt_compat_r. apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
823 apply CRmult_lt_compat_r. apply CRlt_minus. exact (snd H).
824 apply CR_of_Q_lt.
825 unfold Qlt, Qnum, Qden. do 2 rewrite Z.mul_1_r. apply inj_lt, Nat.le_refl.
826 Qed.
827
828 Lemma BinarySubdivNext
829 : forall {R : ConstructiveReals} (a b : CRcarrier R) (n i:nat),
830 BinarySubdiv a b n i + CRpow (CR_of_Q R (1 # 2)) n * (b - a)
831 == BinarySubdiv a b n (S i).
832 Proof.
833 intros. unfold BinarySubdiv.
834 rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
835 rewrite CRmult_assoc, <- (CRmult_comm (b-a)).
836 rewrite <- (CRmult_1_l ((b - a) * CRpow (CR_of_Q R (1 # 2)) n)).
837 rewrite (CRpow_proper (CR_of_Q R (/ 2)) (CR_of_Q R (1#2))).
838 2: apply CR_of_Q_morph; reflexivity.
839 rewrite <- CRmult_plus_distr_r.
840 rewrite CRmult_assoc. apply CRmult_morph. 2: reflexivity.
841 rewrite <- CR_of_Q_plus.
842 apply CR_of_Q_morph. rewrite Qinv_plus_distr.
843 unfold Qeq, Qnum, Qden. do 2 rewrite Z.mul_1_r.
844 replace 1%Z with (Z.of_nat 1).
845 rewrite <- Nat2Z.inj_add. rewrite Nat.add_comm. reflexivity. reflexivity.
846 Qed.
847
848 Lemma pow_nat : forall {R : ConstructiveReals} (a n : nat),
849 CR_of_Q R (Z.of_nat (a ^ n) # 1) == CRpow (CR_of_Q R (Z.of_nat a # 1)) n.
850 Proof.
851 induction n.
852 - reflexivity.
853 - simpl.
854 setoid_replace (Z.of_nat (a * a ^ n) # 1)
855 with ((Z.of_nat a # 1) * (Z.of_nat (a ^ n) # 1))%Q.
856 rewrite CR_of_Q_mult. apply CRmult_morph. reflexivity.
857 exact IHn. rewrite Nat2Z.inj_mul. reflexivity.
858 Qed.
859
860 Lemma BinarySubdivInside
861 : forall {R : ConstructiveReals} (a b : CRcarrier R) (n i : nat),
862 a <= b
863 -> le i (2 ^ n)
864 -> a <= BinarySubdiv a b n i <= b.
865 Proof.
866 split.
867 - apply (CRle_trans _ (a+0)). rewrite CRplus_0_r. apply CRle_refl.
868 apply CRplus_le_compat_l. apply CRmult_le_0_compat.
869 apply CRmult_le_0_compat.
870 apply CR_of_Q_le. destruct i; discriminate.
871 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat_r, H.
872 apply CRpow_ge_zero. apply CR_of_Q_le. discriminate.
873 - unfold BinarySubdiv. apply (CRplus_le_reg_l (-a)).
874 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
875 rewrite (CRplus_comm (-a)), <- (CRmult_comm (b-a)), <- (CRmult_1_r (b+-a)).
876 rewrite CRmult_assoc. apply CRmult_le_compat_l.
877 rewrite <- (CRplus_opp_r a). apply CRplus_le_compat_r, H.
878 apply (CRmult_le_reg_r (CRpow (CR_of_Q R 2) n)).
879 apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
880 rewrite CRmult_assoc, CRpow_mult.
881 rewrite (CRpow_proper (CR_of_Q R (/ 2) * CR_of_Q R 2) 1).
882 rewrite CRpow_one, CRmult_1_r, CRmult_1_l.
883 apply (CRle_trans _ (CR_of_Q R (Z.of_nat (2^n)#1))).
884 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
885 rewrite Z.mul_1_r, Z.mul_1_r. apply Nat2Z.inj_le, H0.
886 rewrite <- (pow_nat 2). apply CRle_refl.
887 rewrite <- CR_of_Q_mult. apply CR_of_Q_morph. reflexivity.
888 Qed.
889
890 Lemma BinarySubdivRight
891 : forall {R : ConstructiveReals} (a b : CRcarrier R) (n : nat),
892 a <= b
893 -> BinarySubdiv a b n (2 ^ n) == b.
894 Proof.
895 intros. unfold BinarySubdiv.
896 apply (CRplus_eq_reg_l (-a)).
897 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l, (CRplus_comm (-a)).
898 rewrite <- (CRmult_comm (b-a)), <- (CRmult_1_r (b+-a)).
899 rewrite CRmult_assoc. apply CRmult_morph. reflexivity.
900 apply (CRmult_eq_reg_r (CRpow (CR_of_Q R 2) n)).
901 left. apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
902 rewrite CRmult_assoc, CRmult_1_l, CRpow_mult.
903 rewrite (CRpow_proper (CR_of_Q R (/ 2) * CR_of_Q R 2) 1).
904 rewrite CRpow_one, CRmult_1_r.
905 apply (pow_nat 2).
906 rewrite <- CR_of_Q_mult. apply CR_of_Q_morph. reflexivity.
907 Qed.
908
909 Fixpoint FindCrossingPoint {R : ConstructiveReals}
910 (un : nat -> CRcarrier R) (N : nat) (alpha : CRcarrier R) { struct N }
911 : (forall n:nat, un (S n) <= un n)
912 -> (forall n:nat, CRapart R alpha (un n))
913 -> alpha < un O
914 -> { k : nat & (le k N)
915 * (sum (k = N) (un (S k) < alpha))
916 * (alpha < un k) }%type. (* besides k is unique *)
917 Proof.
918 intros. destruct N.
919 - exists O. split. split. exact (Nat.le_refl O). left. reflexivity. exact H1.
920 - destruct (H0 (S N)).
921 + exists (S N). split. split. exact (Nat.le_refl (S N)).
922 left. reflexivity. exact c.
923 + destruct (FindCrossingPoint R un N alpha H H0 H1) as [k kmaj].
924 exists k. split. split. apply le_S, (fst kmaj). right.
925 destruct kmaj, p, s. subst k. exact c. exact c1. exact (snd kmaj).
926 Qed.
927
928 (* Search the jump points in the binary discretization of interval [a,b].
929 Allows to build incrementally better approximations of them.
930 Also, being countable, we can use a jump size epsilon that is
931 appart of them all. *)
932 Definition StepApproxDiscretize
933 {IS : IntegrationSpace}
934 (f : PartialFunction (X (ElemFunc IS)))
935 (fInt : IntegrableFunction f)
936 (a b eta : CRcarrier (RealT (ElemFunc IS)))
937 (aPos : 0 < a) (ltab : a < b)
938 (aeta : 0 < a - eta < a) (beta : 0 < b < b + eta)
939 (n i : nat) (* Cut [a,b] into 2^n pieces *)
940 : CRcarrier (RealT (ElemFunc IS))
941 := match i with
942 | O => Integral (StepApproxIntegrable f (a - eta) a aeta fInt)
943 | S j => if le_lt_dec (S (2 ^ n)) i
944 then Integral (StepApproxIntegrable f b (b + eta) beta fInt)
945 else Integral (StepApproxIntegrable
946 f (BinarySubdiv a b n j)
947 (BinarySubdiv a b n (S j))
948 (BinarySubdivIncr a b n j (pair aPos ltab)) fInt)
949 end.
950
951 Lemma StepApproxDiscretizeDecr
952 : forall {IS : IntegrationSpace}
953 (f : PartialFunction (X (ElemFunc IS)))
954 (fInt : IntegrableFunction f)
955 (a b eta : CRcarrier (RealT (ElemFunc IS)))
956 (aPos : 0 < a) (ltab : a < b)
957 (aeta : 0 < a - eta < a) (beta : 0 < b < b + eta)
958 (n i j : nat),
959 le i j
960 -> StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n j
961 <= StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n i.
962 Proof.
963 induction j.
964 - intros. inversion H. apply CRle_refl.
965 - intros. apply Nat.le_succ_r in H. destruct H.
966 2: subst i; apply CRle_refl.
967 apply (CRle_trans _ (StepApproxDiscretize
968 f fInt a b eta aPos ltab aeta beta n j)).
969 2: exact (IHj H). destruct j.
970 + unfold StepApproxDiscretize.
971 destruct (le_lt_dec (S (2 ^ n)) 1). exfalso.
972 apply le_S_n in l. inversion l.
973 pose proof (Nat.pow_gt_lin_r 2 n (Nat.le_refl _)). rewrite H1 in H0.
974 inversion H0. apply StepApproxIntegralIncr.
975 apply (CRle_trans _ a). apply CRlt_asym, (snd aeta).
976 apply BinarySubdivInside. apply CRlt_asym, ltab. apply Nat.le_0_l.
977 apply BinarySubdivInside. apply CRlt_asym, ltab. apply le_S_n, l.
978 + unfold StepApproxDiscretize.
979 destruct (le_lt_dec (S (2 ^ n)) (S (S j))), (le_lt_dec (S (2 ^ n)) (S j)).
980 apply CRle_refl.
981 apply StepApproxIntegralIncr.
982 apply BinarySubdivInside. apply CRlt_asym, ltab.
983 apply le_S_n in l0. apply (Nat.le_trans _ (S j)).
984 apply le_S, Nat.le_refl. exact l0.
985 apply (CRle_trans _ b). apply BinarySubdivInside.
986 apply CRlt_asym, ltab. apply le_S_n, l0. apply CRlt_asym, (snd beta).
987 exfalso. pose proof (Nat.lt_le_trans _ _ _ l l0).
988 apply (proj1 (Nat.lt_nge _ _) H0). apply le_S, Nat.le_refl.
989 apply StepApproxIntegralIncr.
990 apply CRlt_asym, BinarySubdivIncr. exact (pair aPos ltab).
991 apply CRlt_asym, BinarySubdivIncr. exact (pair aPos ltab).
992 Qed.
993
994 Lemma StepApproxDiscretizeRefineDecr
995 : forall {IS : IntegrationSpace}
996 (f : PartialFunction (X (ElemFunc IS)))
997 (fInt : IntegrableFunction f)
998 (a b eta : CRcarrier (RealT (ElemFunc IS)))
999 (aPos : 0 < a) (ltab : a < b)
1000 (aeta : 0 < a - eta < a) (beta : 0 < b < b + eta)
1001 (n i j : nat),
1002 le (2*j) i
1003 -> StepApproxDiscretize
1004 f fInt a b eta aPos ltab aeta beta (S n) i
1005 <= StepApproxDiscretize
1006 f fInt a b eta aPos ltab aeta beta n j.
1007 (* Integral between a + (b-a)*(j-1)/2^n and a + (b-a)*j/2^n *)
1008 Proof.
1009 intros. unfold StepApproxDiscretize. destruct j,i.
1010 - apply CRle_refl.
1011 - clear H. destruct (le_lt_dec (S (2 ^ S n)) (S i)).
1012 apply StepApproxIntegralIncr.
1013 apply (CRle_trans _ a). apply CRlt_asym, (snd aeta). apply CRlt_asym, ltab.
1014 apply (CRle_trans _ b). apply CRlt_asym, ltab. apply CRlt_asym, (snd beta).
1015 apply StepApproxIntegralIncr.
1016 apply (CRle_trans _ a). apply CRlt_asym, (snd aeta).
1017 apply BinarySubdivInside. apply CRlt_asym, ltab.
1018 apply le_S_n in l. apply (Nat.le_trans _ (S i)). apply le_S, Nat.le_refl.
1019 exact l. apply BinarySubdivInside. apply CRlt_asym, ltab.
1020 apply le_S_n, l.
1021 - exfalso. inversion H.
1022 - destruct (le_lt_dec (S (2 ^ n)) (S j)), (le_lt_dec (S (2 ^ S n)) (S i)).
1023 + apply CRle_refl.
1024 + exfalso. apply le_S_n in l0.
1025 apply (Nat.le_trans _ _ _ H) in l0. clear H.
1026 apply (Nat.mul_le_mono_pos_l _ _ 2) in l0.
1027 apply (Nat.le_trans _ _ _ l) in l0. apply (proj1 (Nat.le_ngt _ _) l0 (Nat.le_refl _)).
1028 apply le_n_S, Nat.le_0_l.
1029 + apply StepApproxIntegralIncr.
1030 apply BinarySubdivInside. apply CRlt_asym, ltab.
1031 apply le_S_n in l. apply (Nat.le_trans _ (S j)).
1032 apply le_S, Nat.le_refl. exact l. apply (CRle_trans _ b).
1033 apply BinarySubdivInside. apply CRlt_asym, ltab.
1034 apply le_S_n, l. apply CRlt_asym, (snd beta).
1035 + apply StepApproxIntegralIncr.
1036 apply CRplus_le_compat_l.
1037 do 2 rewrite <- (CRmult_comm (b-a)), CRmult_assoc.
1038 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltab.
1039 simpl (CRpow (CR_of_Q (RealT (ElemFunc IS)) (/ 2)) (S n)).
1040 rewrite <- CRmult_assoc. apply CRmult_le_compat_r.
1041 apply CRpow_ge_zero. apply CR_of_Q_le. discriminate.
1042 rewrite <- CR_of_Q_mult. apply CR_of_Q_le.
1043 apply Qle_shift_div_l. reflexivity.
1044 unfold Qmult, Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
1045 replace 2%Z with (Z.of_nat 2). 2: reflexivity.
1046 rewrite <- Nat2Z.inj_mul. apply Nat2Z.inj_le.
1047 apply le_S_n. apply (Nat.le_trans _ (2*S j)). 2: exact H.
1048 rewrite Nat.mul_comm.
1049 simpl. rewrite Nat.add_0_r, Nat.add_succ_r. apply le_S, Nat.le_refl.
1050 apply CRplus_le_compat_l.
1051 do 2 rewrite <- (CRmult_comm (b-a)), CRmult_assoc.
1052 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltab.
1053 simpl (CRpow (CR_of_Q (RealT (ElemFunc IS)) (/ 2)) (S n)).
1054 rewrite <- CRmult_assoc. apply CRmult_le_compat_r.
1055 apply CRpow_ge_zero. apply CR_of_Q_le. discriminate.
1056 rewrite <- CR_of_Q_mult. apply CR_of_Q_le.
1057 apply Qle_shift_div_l. reflexivity.
1058 unfold Qmult, Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
1059 replace 2%Z with (Z.of_nat 2). 2: reflexivity.
1060 rewrite <- Nat2Z.inj_mul. apply Nat2Z.inj_le.
1061 apply (Nat.le_trans _ (2*S j)). 2: exact H.
1062 rewrite Nat.mul_comm. apply Nat.le_refl.
1063 Qed.
1064
1065 Lemma StepApproxDiscretizeRefineIncr
1066 : forall {IS : IntegrationSpace}
1067 (f : PartialFunction (X (ElemFunc IS)))
1068 (fInt : IntegrableFunction f)
1069 (a b eta : CRcarrier (RealT (ElemFunc IS)))
1070 (aPos : 0 < a) (ltab : a < b)
1071 (aeta : 0 < a - eta < a) (beta : 0 < b < b + eta)
1072 (n i j : nat),
1073 le (S i) (2*j)
1074 -> StepApproxDiscretize
1075 f fInt a b eta aPos ltab aeta beta n j
1076 (* Integral between a + (b-a)*(j-1)/2^n and a + (b-a)*j/2^n *)
1077 <= StepApproxDiscretize
1078 f fInt a b eta aPos ltab aeta beta (S n) i.
1079 Proof.
1080 intros. unfold StepApproxDiscretize.
1081 destruct j. exfalso; inversion H. destruct i.
1082 - destruct (le_lt_dec (S (2 ^ n)) (S j)).
1083 apply StepApproxIntegralIncr.
1084 apply (CRle_trans _ a). apply CRlt_asym, aeta. apply CRlt_asym, ltab.
1085 apply (CRle_trans _ b). apply CRlt_asym, ltab. apply CRlt_asym, beta.
1086 apply StepApproxIntegralIncr. apply (CRle_trans _ a).
1087 apply CRlt_asym, aeta.
1088 apply BinarySubdivInside. apply CRlt_asym, ltab.
1089 apply le_S_n in l. apply (Nat.le_trans _ (S j)). apply le_S, Nat.le_refl.
1090 exact l. apply BinarySubdivInside. apply CRlt_asym, ltab.
1091 apply le_S_n, l.
1092 - destruct (le_lt_dec (S (2 ^ n)) (S j)), (le_lt_dec (S (2 ^ S n)) (S i)).
1093 + apply CRle_refl.
1094 + apply StepApproxIntegralIncr.
1095 apply BinarySubdivInside. apply CRlt_asym, ltab.
1096 apply le_S_n in l0. apply (Nat.le_trans _ (S i)). apply le_S, Nat.le_refl.
1097 exact l0. apply (CRle_trans _ b).
1098 apply BinarySubdivInside. apply CRlt_asym, ltab.
1099 apply le_S_n, l0. apply CRlt_asym, (snd beta).
1100 + exfalso. apply le_S_n in l0. apply le_S_n in l.
1101 apply (Nat.le_trans _ _ (2^S n)) in H.
1102 apply (Nat.le_trans _ _ _ H) in l0. apply (proj1 (Nat.le_ngt _ _) l0).
1103 apply le_S, Nat.le_refl. apply Nat.mul_le_mono_nonneg_l.
1104 apply Nat.le_0_l. exact l.
1105 + clear l l0.
1106 replace (2 * S j)%nat with (S (S (2 * j))) in H.
1107 2: simpl; rewrite Nat.add_0_r, Nat.add_succ_r; reflexivity.
1108 apply le_S_n, le_S_n in H.
1109 apply StepApproxIntegralIncr.
1110 apply CRplus_le_compat_l.
1111 do 2 rewrite <- (CRmult_comm (b-a)), CRmult_assoc.
1112 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltab.
1113 simpl (CRpow (CR_of_Q (RealT (ElemFunc IS)) (/ 2)) (S n)).
1114 rewrite <- CRmult_assoc. apply CRmult_le_compat_r.
1115 apply CRpow_ge_zero. apply CR_of_Q_le. discriminate.
1116 rewrite <- CR_of_Q_mult. apply CR_of_Q_le.
1117 apply Qle_shift_div_r. reflexivity.
1118 unfold Qmult, Qle, Qnum, Qden. rewrite Z.mul_1_r, Z.mul_1_r.
1119 replace 2%Z with (Z.of_nat 2). 2: reflexivity.
1120 rewrite <- (Nat2Z.inj_mul j 2). apply Nat2Z.inj_le.
1121 rewrite Nat.mul_comm. exact H.
1122 apply CRplus_le_compat_l.
1123 do 2 rewrite <- (CRmult_comm (b-a)), CRmult_assoc.
1124 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltab.
1125 simpl (CRpow (CR_of_Q (RealT (ElemFunc IS)) (/ 2)) (S n)).
1126 rewrite <- CRmult_assoc. apply CRmult_le_compat_r.
1127 apply CRpow_ge_zero. apply CR_of_Q_le. discriminate.
1128 rewrite <- CR_of_Q_mult. apply CR_of_Q_le.
1129 apply Qle_shift_div_r. reflexivity.
1130 unfold Qmult, Qle, Qnum, Qden. rewrite Z.mul_1_r, Z.mul_1_r.
1131 replace 2%Z with (Z.of_nat 2). 2: reflexivity.
1132 rewrite <- (Nat2Z.inj_mul (S j) 2). apply Nat2Z.inj_le.
1133 replace (S j * 2)%nat with (S (S (2*j))). apply le_n_S.
1134 apply (Nat.le_trans _ _ _ H). apply le_S, Nat.le_refl.
1135 rewrite (Nat.mul_comm (S j)). simpl.
1136 rewrite Nat.add_0_r, Nat.add_succ_r. reflexivity.
1137 Qed.
1138
1139 (* More points to approximate, so better approximation. *)
1140 Lemma FindCrossingPointIncr
1141 : forall {IS : IntegrationSpace}
1142 (f : PartialFunction (X (ElemFunc IS)))
1143 (fInt : IntegrableFunction f)
1144 (a b eta alpha : CRcarrier (RealT (ElemFunc IS)))
1145 (aPos : 0 < a) (ltab : a < b)
1146 (aeta : 0 < a - eta < a) (beta : 0 < b < b + eta)
1147 (n i j : nat),
1148 ((i <= 2 ^ n)%nat *
1149 ((i = (2 ^ n)%nat) +
1150 (StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n (S i) < alpha)) *
1151 (alpha < StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n i))
1152 -> ((j <= 2 ^ S n)%nat *
1153 ((j = (2 ^ S n)%nat) +
1154 (StepApproxDiscretize
1155 f fInt a b eta aPos ltab aeta beta (S n) (S j) < alpha)) *
1156 (alpha < StepApproxDiscretize f fInt a b eta aPos ltab aeta beta (S n) j))
1157 -> BinarySubdiv a b n i
1158 <= BinarySubdiv a b (S n) j + (b-a) * CRpow (CR_of_Q _ (1#2)) (S n).
1159 Proof.
1160 intros.
1161 destruct H,H0,p,p0. destruct s0.
1162 - subst j. rewrite BinarySubdivRight.
1163 apply (CRle_trans _ (b+0)). rewrite CRplus_0_r.
1164 apply BinarySubdivInside. apply CRlt_asym, ltab. exact l.
1165 apply CRplus_le_compat_l. apply CRmult_le_0_compat.
1166 apply CRlt_asym, CRlt_minus, ltab. apply CRpow_ge_zero.
1167 apply CR_of_Q_le. discriminate.
1168 apply CRlt_asym, ltab.
1169 - destruct s. subst i. rewrite BinarySubdivRight. 2: apply CRlt_asym, ltab.
1170 destruct (le_lt_dec (2^S n) (S j)).
1171 + unfold BinarySubdiv.
1172 apply (CRplus_le_reg_l (-a)).
1173 rewrite <- CRplus_assoc, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
1174 rewrite <- (CRmult_comm (b-a)), <- (CRmult_1_r (-a+b)).
1175 rewrite CRmult_assoc, <- CRmult_plus_distr_l, CRplus_comm.
1176 apply CRmult_le_compat_l.
1177 apply CRlt_asym, CRlt_minus, ltab.
1178 rewrite <- (CRmult_1_l (CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) (S n))).
1179 rewrite <- CRmult_plus_distr_r.
1180 apply (CRmult_le_reg_r (CRpow (CR_of_Q _ (Z.of_nat 2 # 1)) (S n))).
1181 apply CRpow_gt_zero. apply CR_of_Q_pos. reflexivity.
1182 rewrite CRmult_1_l, CRmult_assoc, CRpow_mult.
1183 rewrite (CRpow_proper (CR_of_Q (RealT (ElemFunc IS)) (/ 2) *
1184 CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat 2 # 1)) 1).
1185 rewrite CRpow_one, <- pow_nat, CRmult_1_r.
1186 rewrite <- CR_of_Q_plus. apply CR_of_Q_le.
1187 unfold Qplus, Qle, Qnum, Qden. do 4 rewrite Z.mul_1_r.
1188 replace 1%Z with (Z.of_nat 1). rewrite <- Nat2Z.inj_add.
1189 apply Nat2Z.inj_le. rewrite Nat.add_comm. exact l1.
1190 reflexivity.
1191 rewrite <- CR_of_Q_mult. apply CR_of_Q_morph. reflexivity.
1192 + exfalso. pose proof (CRlt_trans _ _ _ c1 c).
1193 apply (StepApproxDiscretizeRefineIncr
1194 f fInt a b eta aPos ltab aeta beta n (S j) (2^n)).
1195 2: exact H. unfold lt in l1.
1196 replace (2*2^n)%nat with (2 ^ S n)%nat.
1197 exact l1. reflexivity.
1198 + pose proof (CRlt_trans _ _ _ c1 c) as H.
1199 (* Integral on [BinarySubdiv a b (S n) j, BinarySubdiv a b (S n) (S j)]
1200 lower than integral on
1201 [BinarySubdiv a b n (i-1), BinarySubdiv a b n i] *)
1202 destruct (le_lt_dec (S (S j)) (2*i)).
1203 * exfalso.
1204 exact (StepApproxDiscretizeRefineIncr
1205 f fInt a b eta aPos ltab aeta beta n (S j) i l1 H).
1206 * apply le_S_n in l1. unfold BinarySubdiv. rewrite CRplus_assoc.
1207 apply CRplus_le_compat_l.
1208 do 2 rewrite <- (CRmult_comm (b-a)), CRmult_assoc.
1209 rewrite <- CRmult_plus_distr_l.
1210 rewrite <- (CRmult_1_l (CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) (S n))).
1211 rewrite <- CRmult_plus_distr_r.
1212 simpl (CRpow (CR_of_Q (RealT (ElemFunc IS)) (/ 2)) (S n)).
1213 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltab.
1214 rewrite <- CRmult_assoc. apply CRmult_le_compat_r.
1215 apply CRpow_ge_zero. apply CR_of_Q_le. discriminate.
1216 rewrite <- CR_of_Q_plus, <- CR_of_Q_mult. apply CR_of_Q_le.
1217 apply Qle_shift_div_l. reflexivity.
1218 unfold Qplus, Qmult, Qle, Qnum, Qden.
1219 do 4 rewrite Z.mul_1_r.
1220 replace 2%Z with (Z.of_nat 2). rewrite <- Nat2Z.inj_mul.
1221 replace 1%Z with (Z.of_nat 1). rewrite <- Nat2Z.inj_add.
1222 apply Nat2Z.inj_le. rewrite Nat.add_comm, Nat.mul_comm. exact l1.
1223 reflexivity. reflexivity.
1224 Qed.
1225
1226 Lemma FindCrossingPointDecr
1227 : forall {IS : IntegrationSpace}
1228 (f : PartialFunction (X (ElemFunc IS)))
1229 (fInt : IntegrableFunction f)
1230 (a b eta alpha : CRcarrier (RealT (ElemFunc IS)))
1231 (aPos : 0 < a) (ltab : a < b)
1232 (aeta : 0 < a - eta < a) (beta : 0 < b < b + eta)
1233 (n i j : nat),
1234 ((i <= 2 ^ n)%nat *
1235 ((i = (2 ^ n)%nat) +
1236 (StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n (S i) < alpha)) *
1237 (alpha < StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n i))
1238 -> ((j <= 2 ^ S n)%nat *
1239 ((j = (2 ^ S n)%nat) +
1240 (StepApproxDiscretize
1241 f fInt a b eta aPos ltab aeta beta (S n) (S j) < alpha)) *
1242 (alpha < StepApproxDiscretize f fInt a b eta aPos ltab aeta beta (S n) j))
1243 -> BinarySubdiv a b (S n) j
1244 <= BinarySubdiv a b n i + (b-a) * CRpow (CR_of_Q _ (1#2)) n.
1245 Proof.
1246 intros. destruct H,H0,p,p0. destruct s.
1247 - subst i. rewrite BinarySubdivRight.
1248 apply (CRle_trans _ (b+0)). rewrite CRplus_0_r.
1249 apply BinarySubdivInside. apply CRlt_asym, ltab. exact l0.
1250 apply CRplus_le_compat_l. apply CRmult_le_0_compat.
1251 apply CRlt_asym, CRlt_minus, ltab. apply CRpow_ge_zero.
1252 apply CR_of_Q_le. discriminate. apply CRlt_asym, ltab.
1253 - destruct s0.
1254 subst j. rewrite BinarySubdivRight. 2: apply CRlt_asym, ltab.
1255 destruct (le_lt_dec (2^n) i).
1256 + unfold BinarySubdiv.
1257 apply (CRplus_le_reg_l (-a)).
1258 rewrite <- CRplus_assoc, <- CRplus_assoc, CRplus_opp_l, CRplus_0_l.
1259 rewrite <- (CRmult_comm (b-a)), <- (CRmult_1_r (-a+b)).
1260 rewrite CRmult_assoc, <- CRmult_plus_distr_l, CRplus_comm.
1261 apply CRmult_le_compat_l.
1262 apply CRlt_asym, CRlt_minus, ltab.
1263 rewrite <- (CRmult_1_l (CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) n)).
1264 rewrite <- CRmult_plus_distr_r.
1265 apply (CRmult_le_reg_r (CRpow (CR_of_Q _ (Z.of_nat 2 # 1)) n)).
1266 apply CRpow_gt_zero. apply CR_of_Q_pos. reflexivity.
1267 rewrite CRmult_1_l, CRmult_assoc, CRpow_mult.
1268 rewrite (CRpow_proper (CR_of_Q (RealT (ElemFunc IS)) (/ 2) *
1269 CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat 2 # 1)) 1).
1270 rewrite CRpow_one, <- pow_nat, CRmult_1_r.
1271 rewrite <- CR_of_Q_plus. apply CR_of_Q_le.
1272 unfold Qplus, Qle, Qnum, Qden. do 4 rewrite Z.mul_1_r.
1273 replace 1%Z with (Z.of_nat 1). rewrite <- Nat2Z.inj_add.
1274 apply Nat2Z.inj_le. apply (Nat.le_trans _ i _ l1).
1275 rewrite Nat.add_comm. apply le_S, Nat.le_refl.
1276 reflexivity.
1277 rewrite <- CR_of_Q_mult. apply CR_of_Q_morph. reflexivity.
1278 + exfalso. pose proof (CRlt_trans _ _ _ c1 c0).
1279 apply (StepApproxDiscretizeRefineDecr
1280 f fInt a b eta aPos ltab aeta beta n (2^S n) (S i)).
1281 2: exact H. unfold lt in l1. apply Nat.mul_le_mono_nonneg_l.
1282 apply Nat.le_0_l. exact l1.
1283 + pose proof (CRlt_trans _ _ _ c1 c0) as H.
1284 (* Integral on [BinarySubdiv a b (S n) j, BinarySubdiv a b (S n) (S j)]
1285 lower than integral on
1286 [BinarySubdiv a b n (i-1), BinarySubdiv a b n i] *)
1287 destruct (le_lt_dec (2*S i) j).
1288 * exfalso.
1289 exact (StepApproxDiscretizeRefineDecr
1290 f fInt a b eta aPos ltab aeta beta n j (S i) l1 H).
1291 * unfold BinarySubdiv. rewrite CRplus_assoc.
1292 apply CRplus_le_compat_l.
1293 do 2 rewrite <- (CRmult_comm (b-a)), CRmult_assoc.
1294 rewrite <- CRmult_plus_distr_l.
1295 rewrite <- (CRmult_1_l (CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) n)).
1296 rewrite <- CRmult_plus_distr_r.
1297 simpl (CRpow (CR_of_Q (RealT (ElemFunc IS)) (/ 2)) (S n)).
1298 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltab.
1299 rewrite <- CRmult_assoc. apply CRmult_le_compat_r.
1300 apply CRpow_ge_zero. apply CR_of_Q_le. discriminate.
1301 rewrite <- CR_of_Q_plus, <- CR_of_Q_mult. apply CR_of_Q_le.
1302 apply Qle_shift_div_r. reflexivity.
1303 unfold Qplus, Qmult, Qle, Qnum, Qden.
1304 do 4 rewrite Z.mul_1_r.
1305 replace 1%Z with (Z.of_nat 1). rewrite <- Nat2Z.inj_add. 2: reflexivity.
1306 replace 2%Z with (Z.of_nat 2). rewrite <- Nat2Z.inj_mul. 2: reflexivity.
1307 apply Nat2Z.inj_le. apply le_S_n.
1308 apply (Nat.le_trans _ _ _ l1).
1309 rewrite (Nat.mul_comm (i+1)). apply le_S. rewrite Nat.add_comm.
1310 apply Nat.le_refl.
1311 Qed.
1312
1313 Lemma FindCrossingPointThreasholdDecr
1314 : forall {IS : IntegrationSpace}
1315 (f : PartialFunction (X (ElemFunc IS)))
1316 (fInt : IntegrableFunction f)
1317 (a b eta alpha gamma : CRcarrier (RealT (ElemFunc IS)))
1318 (aPos : 0 < a) (ltab : a < b)
1319 (aeta : 0 < a - eta < a) (beta : 0 < b < b + eta)
1320 (n i j : nat),
1321 alpha <= gamma
1322 -> ((i <= 2 ^ n)%nat *
1323 ((i = (2 ^ n)%nat) +
1324 (StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n (S i) < alpha)) *
1325 (alpha < StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n i))
1326 -> ((j <= 2 ^ n)%nat *
1327 ((j = (2 ^ n)%nat) +
1328 (StepApproxDiscretize
1329 f fInt a b eta aPos ltab aeta beta n (S j) < gamma)) *
1330 (gamma < StepApproxDiscretize f fInt a b eta aPos ltab aeta beta n j))
1331 -> le j i.
1332 Proof.
1333 intros. destruct H0, H1, p, p0.
1334 destruct s, s0.
1335 - subst i. rewrite e0. apply Nat.le_refl.
1336 - subst i. exact l0.
1337 - subst j. clear l0.
1338 apply (CRlt_le_trans _ _ _ c1) in H.
1339 apply (CRlt_trans _ _ _ H) in c0. clear H c1 c.
1340 unfold StepApproxDiscretize in c0.
1341 destruct (2^n)%nat eqn:des. apply Nat.le_0_l. rewrite <- des.
1342 destruct (le_lt_dec (S (S n0)) (S n0)). exfalso.
1343 lia.
1344 destruct (le_lt_dec (S (S n0)) (S i)).
1345 + apply le_S_n in l1. pose proof (Nat.le_antisymm _ _ l l1).
1346 subst i. rewrite <- des. apply Nat.le_refl.
1347 + clear l0. apply le_S_n, le_S_n in l1. clear l. exfalso.
1348 apply (StepApproxIntegralIncr
1349 f fInt
1350 (BinarySubdiv a b n i) (BinarySubdiv a b n (S i))
1351 (BinarySubdiv a b n n0) (BinarySubdiv a b n (S n0))
1352 (BinarySubdivIncr a b n i (aPos, ltab))
1353 (BinarySubdivIncr a b n n0 (aPos, ltab))).
1354 3: exact c0. clear c0.
1355 apply CRplus_le_compat_l. do 2 rewrite CRmult_assoc.
1356 apply CRmult_le_compat_r. apply CRlt_asym, CRmult_lt_0_compat.
1357 apply CRlt_minus, ltab. apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
1358 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
1359 do 2 rewrite Z.mul_1_r. apply Nat2Z.inj_le, l1.
1360 apply CRplus_le_compat_l. do 2 rewrite CRmult_assoc.
1361 apply CRmult_le_compat_r. apply CRlt_asym, CRmult_lt_0_compat.
1362 apply CRlt_minus, ltab. apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
1363 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
1364 do 2 rewrite Z.mul_1_r. apply Nat2Z.inj_le, le_n_S, l1.
1365 - apply (CRlt_le_trans _ _ _ c1) in H.
1366 apply (CRlt_trans _ _ _ H) in c0. unfold StepApproxDiscretize in c0.
1367 destruct j. apply Nat.le_0_l.
1368 destruct (le_lt_dec (S (2 ^ n)) (S j)).
1369 exfalso. apply le_S_n in l1. lia.
1370 destruct (le_lt_dec (S (2 ^ n)) (S i)).
1371 apply le_S_n in l1. apply le_S_n in l2. exact (Nat.le_trans _ _ _ l1 l2).
1372 destruct (le_lt_dec (S j) i). exact l3. exfalso.
1373 apply (StepApproxIntegralIncr
1374 f fInt
1375 (BinarySubdiv a b n i) (BinarySubdiv a b n (S i))
1376 (BinarySubdiv a b n j) (BinarySubdiv a b n (S j))
1377 (BinarySubdivIncr a b n i (aPos, ltab))
1378 (BinarySubdivIncr a b n j (aPos, ltab))).
1379 3: exact c0. apply le_S_n in l3.
1380 apply CRplus_le_compat_l. do 2 rewrite CRmult_assoc.
1381 apply CRmult_le_compat_r. apply CRlt_asym, CRmult_lt_0_compat.
1382 apply CRlt_minus, ltab. apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
1383 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
1384 do 2 rewrite Z.mul_1_r. apply Nat2Z.inj_le, l3.
1385 apply CRplus_le_compat_l. do 2 rewrite CRmult_assoc.
1386 apply CRmult_le_compat_r. apply CRlt_asym, CRmult_lt_0_compat.
1387 apply CRlt_minus, ltab. apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
1388 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
1389 do 2 rewrite Z.mul_1_r. apply Nat2Z.inj_le, l3.
1390 Qed.
1391
1392 Lemma diff_series_cv_maj
1393 : forall {R : ConstructiveReals}
1394 (un vn : nat -> CRcarrier R) (s : CRcarrier R),
1395 (* skip 0 *)
1396 (forall n:nat, CRabs R (un (S n) - un n) <= vn n)
1397 -> series_cv vn s
1398 -> { l : CRcarrier R & prod (CR_cv R un l) (l <= s + CRabs R (un O)) }.
1399 Proof.
1400 intros.
1401 destruct (series_cv_maj (fun n:nat => match n with
1402 | O => un O
1403 | S p => un n - un p end)
1404 (fun n:nat => match n with
1405 | O => CRabs R (un O)
1406 | S p => vn p end)
1407 (s + CRabs R (un O))) as [l lcv].
1408 - intro n. destruct n. apply CRle_refl. apply H.
1409 - intro p. specialize (H0 p) as [n ncv].
1410 exists (S n). intros. destruct i. exfalso; inversion H0.
1411 rewrite decomp_sum. simpl. unfold CRminus.
1412 rewrite CRplus_comm, CRopp_plus_distr, CRplus_assoc.
1413 rewrite <- (CRplus_assoc (-CRabs R (un O))), CRplus_opp_l, CRplus_0_l.
1414 rewrite CRplus_comm. apply ncv. apply le_S_n, H0.
1415 apply le_n_S, Nat.le_0_l.
1416 - exists l. split. 2: exact (snd lcv).
1417 apply (CR_cv_eq _ (CRsum (fun n : nat => match n with
1418 | 0%nat => un 0%nat
1419 | S p => un n - un p
1420 end))).
1421 + induction n. reflexivity. simpl. rewrite IHn.
1422 rewrite CRplus_comm. unfold CRminus.
1423 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r. reflexivity.
1424 + exact (fst lcv).
1425 Qed.
1426
1427 Lemma StepApproxProofIrrel
1428 : forall {IS : IntegrationSpace}
1429 (f : PartialFunction (X (ElemFunc IS)))
1430 (fInt : IntegrableFunction f)
1431 (s t : CRcarrier (RealT (ElemFunc IS))) (ltst ltst2 : 0 < s < t),
1432 Integral (StepApproxIntegrable f s t ltst fInt)
1433 == Integral (StepApproxIntegrable f s t ltst2 fInt).
1434 Proof.
1435 intros. apply IntegralExtensional.
1436 intros. simpl. destruct xdf, xdg.
1437 apply (CRmult_eq_reg_l (t-s)). right. apply CRlt_minus, ltst.
1438 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l, (CRmult_comm (t-s)).
1439 apply (CRmult_eq_reg_l (t-s)). right. apply CRlt_minus, ltst.
1440 rewrite <- CRmult_assoc, <- CRmult_assoc, CRinv_r, CRmult_1_l.
1441 rewrite CRmult_comm. rewrite (DomainProp f x d2 d), (DomainProp f x d1 d).
1442 rewrite (DomainProp f x d0 d). reflexivity.
1443 Qed.
1444
1445 (* There are at most q+1 points with jumps bigger than epsilon,
1446 s0, ..., sq.
1447 To search jump points, we throw missiles from a to b with increasing speeds
1448 epsilon * (k / q), k=0..q
1449 Jump points are barriers that take down some of the missile speed,
1450 it will continue going towards b as long as it has positive speed.
1451 When there are no jump points (f = 0), all points sk's will be equal to b. *)
1452 Lemma FindJumpPointsFinite
1453 : forall {IS : IntegrationSpace}
1454 (f : PartialFunction (X (ElemFunc IS)))
1455 (fInt : IntegrableFunction f)
1456 (a b alpha epsilon : CRcarrier (RealT (ElemFunc IS)))
1457 (aPos : 0 < a) (ltab : a < b) (epsPos : 0 < epsilon) (q : nat),
1458 alpha <= CR_of_Q _ (Z.of_nat q # 1) * epsilon
1459 -> q <> O
1460 -> StepApproxBound f fInt a b alpha (CRlt_asym a b ltab)
1461 -> { s : nat -> CRcarrier (RealT (ElemFunc IS))
1462 | (s O == a) /\ (forall k:nat, le q k -> s k == b)
1463 /\ (forall k:nat, s k <= s (S k))
1464 /\ (forall k:nat, StepApproxBoundOpen f fInt (s k) (s (S k)) epsilon) }.
1465 Proof.
1466 intros IS f fInt a b alpha epsilon aPos ltab epsPos q H qnz H0.
1467 destruct H0 as [ext c].
1468 pose (StepApproxDiscretize
1469 f fInt a b (ext_eta ext) aPos ltab
1470 (left_ordered ext) (pair (CRlt_trans _ _ _ aPos ltab) (right_ordered ext)))
1471 as Fni.
1472
1473 (* We define the q numbers sk as limits of sequences. *)
1474 (* Define the non-negative sequence of jumps *)
1475 (* pose (fun n i : nat => Fni n O - Fni n i) as Sni. *)
1476 destruct (CRuncountableDiag3
1477 (fun n i k => (Fni n O - Fni n i)
1478 * CR_of_Q _ (Z.of_nat q # Pos.of_nat (S k)))
1479 _ alpha c)
1480 as [epsilonPrime H0]. destruct H0.
1481 assert (0 < epsilonPrime) as epsilonPrimePos.
1482 { apply (CRle_lt_trans _ (Integral (StepApproxIntegrable f (a - ext_eta ext) a (left_ordered ext) fInt) - Integral
1483 (StepApproxIntegrable f b (b + ext_eta ext)
1484 (IntExtRightPos ext (CRlt_asym a b ltab), right_ordered ext) fInt))).
1485 2: apply p.
1486 apply (CRplus_le_reg_r ( Integral
1487 (StepApproxIntegrable f b (b + ext_eta ext)
1488 (IntExtRightPos ext (CRlt_asym a b ltab), right_ordered ext) fInt))).
1489 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_0_l.
1490 apply StepApproxIntegralIncr.
1491 apply (CRle_trans _ a). apply CRlt_asym, ext. apply CRlt_asym, ltab.
1492 apply (CRle_trans _ b). apply CRlt_asym, ltab. apply CRlt_asym, ext. }
1493 assert (forall n k:nat,
1494 Fni n O - CR_of_Q _ (Z.of_nat (S k) # Pos.of_nat q) * epsilonPrime
1495 < Fni n O) as H0.
1496 { intros. apply (CRlt_le_trans _ (Fni n 0%nat - 0)).
1497 apply CRplus_lt_compat_l, CRopp_gt_lt_contravar.
1498 apply CRmult_lt_0_compat. apply CR_of_Q_pos. reflexivity.
1499 exact epsilonPrimePos. unfold CRminus.
1500 rewrite CRopp_0, CRplus_0_r. apply CRle_refl. }
1501 assert (forall n k i : nat,
1502 (Fni n 0%nat -
1503 CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat (S k) # Pos.of_nat q) * epsilonPrime)
1504 ≶ (Fni n i)).
1505 { intros.
1506 apply (CRplus_appart_reg_r (CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat (S k) # Pos.of_nat q) * epsilonPrime)).
1507 unfold CRminus.
1508 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1509 apply (CRplus_appart_reg_l (-(Fni n i))).
1510 apply (CRapart_morph _ _ (CReq_refl _)
1511 _ (CR_of_Q _ (Z.of_nat (S k) # Pos.of_nat q) * epsilonPrime)).
1512 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
1513 rewrite CRplus_comm. specialize (c0 n i k).
1514 apply (CRmult_appart_reg_l
1515 (CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat q # Pos.of_nat (S k)))).
1516 apply CR_of_Q_pos. destruct q. exfalso; exact (qnz (eq_refl O)).
1517 reflexivity.
1518 apply (CRapart_morph _ _ (CReq_refl _) _ epsilonPrime).
1519 rewrite <- CRmult_assoc, <- CR_of_Q_mult.
1520 setoid_replace
1521 ((Z.of_nat q # Pos.of_nat (S k)) * (Z.of_nat (S k) # Pos.of_nat q))%Q
1522 with 1%Q.
1523 rewrite CRmult_1_l. reflexivity.
1524 unfold Qmult, Qeq, Qnum, Qden.
1525 rewrite Z.mul_1_l, Z.mul_1_r, Z.mul_comm.
1526 rewrite Pos2Z.inj_mul. apply f_equal2.
1527 simpl (Z.of_nat (S k)). apply f_equal.
1528 rewrite Pos.of_nat_succ. reflexivity.
1529 destruct q. exfalso; exact (qnz (eq_refl O)).
1530 simpl (Z.of_nat (S q)). apply f_equal.
1531 rewrite Pos.of_nat_succ. reflexivity.
1532 rewrite CRmult_comm.
1533 destruct c0. right. exact c0. left. exact c0. }
1534 pose proof (fun (n k:nat)
1535 => FindCrossingPoint
1536 (Fni n) (2 ^ n) (* gives 2^n + 1 possible indices,
1537 as many as the numbers of points in the
1538 nth binary subdivision of [a,b] *)
1539 (Fni n O - CR_of_Q _ (Z.of_nat (S k) # Pos.of_nat q) * epsilonPrime)
1540 (fun i:nat => StepApproxDiscretizeDecr
1541 f fInt a b (ext_eta ext) aPos ltab (left_ordered ext)
1542 (pair (CRlt_trans _ _ _ aPos ltab) (right_ordered ext))
1543 n i (S i) (le_S i i (Nat.le_refl i)))
1544 (H1 n k) (H0 n k)) as H2.
1545 clear H1. clear H0.
1546 pose (fun (n k:nat) => let (i,_) := H2 n k in BinarySubdiv a b n i) as snk.
1547 assert (forall n k:nat, CRabs _ (snk (S n) k - snk n k)
1548 <= (b-a) * CRpow (CR_of_Q _ (1#2)) n).
1549 { intros n k. unfold snk.
1550 destruct (H2 n k), (H2 (S n) k). apply CRabs_le. split.
1551 - pose proof (FindCrossingPointIncr
1552 f fInt a b (ext_eta ext)
1553 (Fni n O - CR_of_Q _ (Z.of_nat (S k) # Pos.of_nat q) * epsilonPrime)
1554 aPos ltab (left_ordered ext)
1555 (pair (CRlt_trans _ _ _ aPos ltab) (right_ordered ext))
1556 _ _ _ p0 p1).
1557 apply (CRplus_le_reg_r (BinarySubdiv a b n x)). unfold CRminus.
1558 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1559 apply (CRplus_le_reg_l
1560 ((b - a) * CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) n)).
1561 rewrite <- CRplus_assoc, CRplus_opp_r, CRplus_0_l, CRplus_comm.
1562 apply (CRle_trans _ _ _ H0). apply CRplus_le_compat_l.
1563 apply CRmult_le_compat_l. apply CRlt_asym, CRlt_minus, ltab.
1564 rewrite <- (CRmult_1_l (CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) n)).
1565 simpl. apply CRmult_le_compat_r.
1566 apply CRpow_ge_zero, CRlt_asym, CR_of_Q_pos.
1567 reflexivity. apply CR_of_Q_le. discriminate.
1568 - pose proof (FindCrossingPointDecr
1569 f fInt a b (ext_eta ext)
1570 (Fni n O - CR_of_Q _ (Z.of_nat (S k) # Pos.of_nat q) * epsilonPrime)
1571 aPos ltab (left_ordered ext)
1572 (pair (CRlt_trans _ _ _ aPos ltab) (right_ordered ext))
1573 _ _ _ p0 p1).
1574 apply (CRplus_le_reg_r (BinarySubdiv a b n x)).
1575 unfold CRminus.
1576 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r, CRplus_comm.
1577 exact H0. }
1578 assert (series_cv
1579 (fun n : nat => (b - a) * CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) n)
1580 (CR_of_Q _ 2 * (b-a))).
1581 { apply (series_cv_eq
1582 (fun n : nat => CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) n * (b-a))).
1583 intro n. apply CRmult_comm. apply series_cv_scale. apply GeoHalfTwo. }
1584 pose proof (fun (k:nat) => diff_series_cv_maj
1585 (fun n => snk n k)
1586 (fun n => (b - a) * CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) n)
1587 (CR_of_Q _ 2 * (b-a)) (fun n => H0 n k) H1).
1588 pose (fun k:nat => match k with
1589 | O => a (* necessary special case at a, because all missiles
1590 go to b when f=0 *)
1591 | S i => let (l,_) := H3 i in l
1592 end) as sk.
1593 exists sk.
1594 assert (forall k:nat, le q k -> sk k == b) as lastB.
1595 { intros. unfold sk. destruct k.
1596 exfalso. inversion H4. rewrite H5 in qnz.
1597 exact (qnz (eq_refl _)).
1598 destruct (H3 k) as [x p0]. destruct p0. clear c2.
1599 apply (CR_cv_unique (fun n : nat => snk n k) _ _ c1). clear c1 x.
1600 apply (CR_cv_eq _ (fun _ : nat => b)). 2: apply CR_cv_const.
1601 intro n. unfold snk.
1602 destruct (H2 n k). destruct p0, p0.
1603 destruct s.
1604 - rewrite e.
1605 rewrite BinarySubdivRight. reflexivity. apply CRlt_asym, ltab.
1606 - exfalso. clear c1. contradict c2.
1607 apply (CRle_trans _ (Fni n (S (2^n)))).
1608 2: apply StepApproxDiscretizeDecr, le_n_S, l.
1609 apply (CRle_trans _ ( Fni n 0%nat - 1 * epsilonPrime)).
1610 apply CRplus_le_compat_l, CRopp_ge_le_contravar.
1611 apply CRmult_le_compat_r. apply CRlt_asym, epsilonPrimePos.
1612 apply CR_of_Q_le.
1613 unfold Qle, Qnum, Qden. rewrite Z.mul_1_r, Z.mul_1_l.
1614 simpl (Z.of_nat (S k)). apply Pos2Z.pos_le_pos.
1615 rewrite Pos.of_nat_succ. apply Pos2Nat.inj_le.
1616 rewrite Nat2Pos.id, Nat2Pos.id. exact H4.
1617 discriminate. exact qnz. rewrite CRmult_1_l.
1618 apply (CRplus_le_reg_r epsilonPrime).
1619 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1620 apply (CRplus_le_reg_l (-Fni n (S (2^n)))).
1621 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l, CRplus_comm.
1622 destruct p. unfold Fni, StepApproxDiscretize.
1623 destruct (le_lt_dec (S (2 ^ n)) (S (2 ^ n))).
1624 rewrite (StepApproxProofIrrel
1625 f fInt _ _
1626 (CRlt_trans 0 a b aPos ltab, right_ordered ext)
1627 (IntExtRightPos ext (CRlt_asym a b ltab), right_ordered ext) ).
1628 apply CRlt_asym, c1.
1629 exfalso; exact (proj1 (Nat.lt_nge _ _) l0 (Nat.le_refl _)). }
1630 assert (forall k : nat, sk k <= sk (S k)) as skIncr.
1631 { unfold sk. intros k. destruct k.
1632 - destruct (H3 O).
1633 apply (CR_cv_bound_down (fun n : nat => snk n 0%nat) _ _ O).
1634 intros. unfold snk. destruct (H2 n O).
1635 apply BinarySubdivInside. apply CRlt_asym, ltab.
1636 apply (fst p1). exact (fst p0).
1637 - destruct (H3 k), (H3 (S k)).
1638 apply (CR_cv_le (fun n : nat => snk n k) (fun n : nat => snk n (S k))).
1639 2: exact (fst p0). 2: exact (fst p1). intro n.
1640 unfold snk. destruct (H2 n k), (H2 n (S k)).
1641 apply CRplus_le_compat_l. rewrite CRmult_assoc, CRmult_assoc.
1642 apply CRmult_le_compat_r. apply CRmult_le_0_compat.
1643 apply CRlt_asym, CRlt_minus, ltab. apply CRpow_ge_zero.
1644 apply CRlt_asym, CR_of_Q_pos. reflexivity. apply CR_of_Q_le.
1645 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r. apply Nat2Z.inj_le.
1646 apply (FindCrossingPointThreasholdDecr
1647 f fInt a b (ext_eta ext)
1648 (Fni n 0%nat -
1649 CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat (S (S k)) # Pos.of_nat q) *
1650 epsilonPrime)
1651 (Fni n 0%nat -
1652 CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat (S k) # Pos.of_nat q) * epsilonPrime)
1653 aPos ltab (left_ordered ext)
1654 (CRlt_trans 0 a b aPos ltab, right_ordered ext) n).
1655 2: exact p3. 2: exact p2.
1656 apply CRplus_le_compat_l, CRopp_ge_le_contravar.
1657 apply CRmult_le_compat_r. apply CRlt_asym, epsilonPrimePos.
1658 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
1659 apply Z.mul_le_mono_nonneg_r. discriminate. apply Nat2Z.inj_le.
1660 apply le_S, Nat.le_refl. }
1661 split. 2: split. 3: split.
1662 - reflexivity.
1663 - exact lastB.
1664 - exact skIncr.
1665 - (* No jumps between jump points. *)
1666 intros k x y u v ltxy ltuv H4 H5 H6.
1667 destruct (le_lt_dec q k) as [l | ltkq].
1668 contradict H6.
1669 apply (CRle_trans _ b). apply lastB. apply le_S, l.
1670 apply (CRle_trans _ u). 2: apply CRlt_asym, (snd ltuv).
1671 apply (CRle_trans _ y). 2: exact H5.
1672 apply (CRle_trans _ x). 2: apply CRlt_asym, (snd ltxy).
1673 rewrite <- (lastB k). apply CRlt_asym, H4. exact l.
1674 assert (CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat 1 # Pos.of_nat q) * epsilonPrime
1675 < epsilon).
1676 { apply (CRmult_lt_reg_l (CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat q # 1))).
1677 apply CR_of_Q_pos. destruct q. exfalso; exact (qnz (eq_refl _)).
1678 reflexivity. apply (CRlt_le_trans _ alpha). 2: exact H.
1679 apply (CRle_lt_trans _ epsilonPrime). 2: exact (snd p).
1680 rewrite <- CRmult_assoc, <- CR_of_Q_mult.
1681 setoid_replace ((Z.of_nat q # 1) * (Z.of_nat 1 # Pos.of_nat q))%Q with 1%Q.
1682 rewrite CRmult_1_l. apply CRle_refl.
1683 unfold Qmult, Qeq, Qnum, Qden. simpl. do 2 rewrite Z.mul_1_r.
1684 destruct q. exfalso; exact (qnz (eq_refl _)). simpl (Z.of_nat (S q)).
1685 apply f_equal. apply (Pos.of_nat_succ). }
1686 destruct (CR_cv_open_below
1687 (fun n => snk n k + (CRpow (CR_of_Q _ (1#2)) n)*(-(b-a)))
1688 v (sk (S k))) as [m mcv].
1689 apply (CR_cv_proper _ (sk (S k) + 0)). 2: apply CRplus_0_r.
1690 apply CR_cv_plus. unfold sk.
1691 destruct (H3 k). exact (fst p0).
1692 apply (CR_cv_proper _ (0 * (-(b-a)))). apply CR_cv_scale.
1693 apply GeoCvZero. apply CRmult_0_l. exact H6.
1694 destruct k.
1695 + (* First segment, starting at a *)
1696 apply (CRle_trans _ (Fni m O - Fni m (let (i, _) := H2 m O in i))).
1697 unfold sk in H4.
1698 apply CRplus_le_compat. apply StepApproxIntegralIncr.
1699 apply (CRle_trans _ a). apply CRlt_asym, (snd (left_ordered ext)).
1700 apply CRlt_asym, H4. apply (CRle_trans _ x).
1701 apply CRlt_asym, H4. apply CRlt_asym, (snd ltxy).
1702 apply CRopp_ge_le_contravar. unfold Fni.
1703 specialize (mcv m (Nat.le_refl m)). unfold snk in mcv.
1704 destruct (H2 m O), p0, p0. unfold StepApproxDiscretize. destruct x0.
1705 exfalso. contradict mcv. apply (CRle_trans _ (a+0)).
1706 unfold BinarySubdiv.
1707 rewrite CRmult_0_l, CRmult_0_l, CRplus_assoc.
1708 apply CRplus_le_compat_l.
1709 rewrite CRplus_0_l, <- CRopp_mult_distr_r, <- CRopp_0.
1710 apply CRopp_ge_le_contravar, CRmult_le_0_compat.
1711 apply CRpow_ge_zero. apply CRlt_asym, CR_of_Q_pos. reflexivity.
1712 apply CRlt_asym, CRlt_minus, ltab.
1713 rewrite CRplus_0_r. apply CRlt_asym.
1714 apply (CRlt_trans _ _ _ H4), (CRlt_trans _ _ _ (snd ltxy)).
1715 apply (CRle_lt_trans _ _ _ H5), (snd ltuv).
1716 destruct (le_lt_dec (S (2 ^ m)) (S x0)).
1717 exfalso. apply le_S_n in l0. exact (proj1 (Nat.lt_nge _ _) l l0).
1718 assert (v <= BinarySubdiv a b m x0).
1719 { apply (CRle_trans _ (BinarySubdiv a b m (S x0) +
1720 CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) m * - (b - a))).
1721 apply CRlt_asym, mcv. rewrite <- BinarySubdivNext.
1722 rewrite <- CRopp_mult_distr_r, CRplus_assoc, CRplus_opp_r.
1723 rewrite CRplus_0_r. apply CRle_refl. }
1724 apply StepApproxIntegralIncr. clear l0 c1 s.
1725 apply (CRle_trans _ v). apply CRlt_asym, (snd ltuv). exact H8.
1726 apply (CRle_trans _ _ _ H8). apply CRplus_le_compat_l.
1727 rewrite CRmult_assoc, CRmult_assoc. apply CRmult_le_compat_r.
1728 apply CRmult_le_0_compat.
1729 apply CRlt_asym, CRlt_minus, ltab.
1730 apply CRpow_ge_zero. apply CRlt_asym, CR_of_Q_pos. reflexivity.
1731 apply CR_of_Q_le. unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
1732 apply Nat2Z.inj_le, le_S, Nat.le_refl.
1733 destruct (H2 m O), p0, p0.
1734 apply (CRplus_le_reg_r (Fni m x0)). unfold CRminus.
1735 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1736 apply (CRplus_le_reg_r (-
1737 (CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat 1 # Pos.of_nat q) * epsilonPrime))).
1738 apply (CRle_trans _ (Fni m x0) _ (CRlt_asym _ _ c1)).
1739 rewrite (CRplus_comm epsilon), <- (CRplus_0_r (Fni m x0)).
1740 rewrite CRplus_assoc, CRplus_assoc.
1741 apply CRplus_le_compat_l. rewrite CRplus_0_l.
1742 apply CRlt_asym, CRlt_minus, H7.
1743 + destruct (CR_cv_open_above
1744 (fun n => snk n k + (CRpow (CR_of_Q _ (1#2)) n)*(b-a))
1745 x (sk (S k))) as [n ncv].
1746 2: exact H4.
1747 apply (CR_cv_proper _ (sk (S k) + 0)). 2: apply CRplus_0_r.
1748 apply CR_cv_plus. unfold sk.
1749 destruct (H3 k), p0. exact c1.
1750 apply (CR_cv_proper _ (0 * (b-a))). apply CR_cv_scale.
1751 apply GeoCvZero. apply CRmult_0_l.
1752 specialize (ncv (max n m) (Nat.le_max_l _ _)).
1753 specialize (mcv (max n m) (Nat.le_max_r _ _)).
1754 rewrite <- CRopp_mult_distr_r in mcv.
1755 apply (CRle_trans
1756 _ (Fni (max n m) (let (i,_) := H2 (max n m) k in S i)
1757 - Fni (max n m) (let (i, _) := H2 (max n m) (S k) in i))).
1758 * assert (forall i j:nat, le i j -> sk i <= sk j).
1759 { induction j. intros. inversion H8. apply CRle_refl.
1760 intros. apply Nat.le_succ_r in H8. destruct H8.
1761 apply (CRle_trans _ (sk j)). exact (IHj H8).
1762 apply skIncr. subst i. apply CRle_refl. }
1763 apply CRplus_le_compat.
1764 (* Interval [x,y] *)
1765 clear mcv.
1766 unfold Fni, StepApproxDiscretize. unfold snk in ncv.
1767 destruct (H2 (max n m) k) as [x0 p0].
1768 destruct (le_lt_dec (S (2 ^ max n m)) (S x0)).
1769 destruct p0, p0. apply le_S_n in l.
1770 apply (Nat.le_antisymm _ _ l0) in l. subst x0. (* x0 = 2 ^ max n m *)
1771 clear l0 s c1.
1772 contradict ncv. apply (CRle_trans _ (b+0)).
1773 rewrite CRplus_0_r. apply (CRle_trans _ y _ (CRlt_asym _ _ (snd ltxy))).
1774 apply (CRle_trans _ u _ H5).
1775 apply (CRle_trans _ v _ (CRlt_asym _ _ (snd ltuv))).
1776 apply (CRle_trans _ _ _ (CRlt_asym _ _ H6)).
1777 apply (CRle_trans _ (sk q)).
1778 apply H8. exact ltkq. apply lastB. apply Nat.le_refl.
1779 rewrite BinarySubdivRight. apply CRplus_le_compat_l.
1780 apply CRlt_asym, CRmult_lt_0_compat.
1781 apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
1782 apply CRlt_minus, ltab. apply CRlt_asym, ltab.
1783 rewrite BinarySubdivNext in ncv. apply StepApproxIntegralIncr.
1784 apply le_S_n in l. destruct p0, p0. clear l0.
1785 apply (CRle_trans _ (BinarySubdiv a b (max n m) (S x0))).
1786 apply CRlt_asym, BinarySubdivIncr. exact (pair aPos ltab).
1787 apply CRlt_asym, ncv.
1788 apply (CRle_trans _ x). apply CRlt_asym, ncv.
1789 apply CRlt_asym, (snd ltxy).
1790 (* Interval [u,v] *)
1791 clear ncv. apply CRopp_ge_le_contravar.
1792 unfold Fni, StepApproxDiscretize. unfold snk in mcv.
1793 destruct (H2 (max n m) (S k)), p0, p0. destruct x0.
1794 clear l c1. contradict mcv.
1795 apply (CRle_trans _ (a-0)). unfold BinarySubdiv, CRminus.
1796 rewrite CRplus_assoc. apply CRplus_le_compat_l.
1797 rewrite CRmult_0_l, CRmult_0_l, CRplus_0_l.
1798 apply CRopp_ge_le_contravar.
1799 apply CRlt_asym, CRmult_lt_0_compat.
1800 apply CRpow_gt_zero, CR_of_Q_pos. reflexivity.
1801 apply CRlt_minus, ltab. unfold CRminus. rewrite CRopp_0, CRplus_0_r.
1802 apply (CRle_trans _ (sk (S k))). apply (H8 O (S k)), Nat.le_0_l.
1803 apply (CRle_trans _ x _ (CRlt_asym _ _ H4)).
1804 apply (CRle_trans _ y _ (CRlt_asym _ _ (snd ltxy))).
1805 apply (CRle_trans _ u _ H5).
1806 apply CRlt_asym, (snd ltuv).
1807 destruct (le_lt_dec (S (2 ^ max n m)) (S x0)).
1808 apply le_S_n in l0.
1809 exfalso. exact (proj1 (Nat.lt_nge _ _) l l0).
1810 apply CRlt_asym in mcv.
1811 rewrite <- BinarySubdivNext, CRplus_assoc, CRplus_opp_r, CRplus_0_r in mcv.
1812 apply StepApproxIntegralIncr.
1813 apply (CRle_trans _ v _ (CRlt_asym _ _ (snd ltuv)) mcv).
1814 apply (CRle_trans _ _ _ mcv). apply CRlt_asym, BinarySubdivIncr.
1815 exact (pair aPos ltab).
1816 * destruct (H2 (max n m) k) as [x0 p0], (H2 (max n m) (S k)) as [x1 p1].
1817 destruct p0, p1, p0, p1. destruct s. subst x0.
1818 apply (CRplus_le_reg_r (Fni (max n m) x1)).
1819 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1820 apply (CRle_trans _ (0 + Fni (max n m) x1)).
1821 rewrite CRplus_0_l.
1822 apply StepApproxDiscretizeDecr. apply le_S, l0.
1823 apply CRplus_le_compat_r. apply CRlt_asym, epsPos.
1824 apply (CRle_trans
1825 _ (Fni (Init.Nat.max n m) 0%nat -
1826 CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat (S k) # Pos.of_nat q)
1827 * epsilonPrime
1828 - (Fni (Init.Nat.max n m) 0%nat -
1829 CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat (S (S k)) # Pos.of_nat q) * epsilonPrime))).
1830 apply CRplus_le_compat. apply CRlt_asym, c3.
1831 apply CRopp_ge_le_contravar. apply CRlt_asym, c2.
1832 unfold CRminus.
1833 rewrite (CRplus_comm (Fni (max n m) O)), CRplus_assoc, CRopp_plus_distr.
1834 rewrite <- (CRplus_assoc (Fni (max n m) O)), CRplus_opp_r, CRplus_0_l.
1835 rewrite CRopp_involutive, CRopp_mult_distr_l.
1836 rewrite <- CRmult_plus_distr_r.
1837 apply (CRle_trans _ ((CR_of_Q _ (1 # Pos.of_nat q)) * epsilonPrime)).
1838 apply CRmult_le_compat_r. apply CRlt_asym, epsilonPrimePos.
1839 rewrite <- CR_of_Q_opp, <- CR_of_Q_plus. apply CR_of_Q_le.
1840 rewrite Qplus_comm, Qinv_minus_distr.
1841 unfold Qle, Qnum, Qden. apply Z.mul_le_mono_nonneg_r. discriminate.
1842 destruct k. discriminate.
1843 2: apply CRlt_asym, H7.
1844 rewrite (Z.add_le_mono_r _ _ (Z.of_nat (S (S k)))).
1845 ring_simplify. replace 1%Z with (Z.of_nat 1).
1846 rewrite <- Nat2Z.inj_add, Nat.add_comm. apply Z.le_refl.
1847 reflexivity.
1848 Qed.
1849
1850 Lemma FindInterval {R : ConstructiveReals} (un : nat -> CRcarrier R)
1851 (x : CRcarrier R) (i j : nat)
1852 : (forall n:nat, un n <= un (S n))
1853 -> (forall n:nat, CRapart R x (un n))
1854 -> un i < x < un j
1855 -> { k : nat & un k < x < un (S k) }.
1856 Proof.
1857 intro uIncr.
1858 assert (forall b : nat, un O <= un b).
1859 { induction b. apply CRle_refl.
1860 apply (CRle_trans _ (un b) _ IHb). apply uIncr. }
1861 induction j.
1862 - intros. pose proof (CRlt_trans _ _ _ (fst H1) (snd H1)) as H3.
1863 contradict H3. apply H.
1864 - intros. specialize (IHj H0).
1865 destruct (H0 j). exact (IHj (pair (fst H1) c)).
1866 exists j. exact (pair c (snd H1)).
1867 Qed.
1868
1869 Lemma IntervalOpenEta : forall {R : ConstructiveReals} (a b x : CRcarrier R),
1870 a < x < b
1871 -> { eta : CRcarrier R & prod (a < x-eta < x) (x < x+eta < b) }.
1872 Proof.
1873 intros. exists (CRmin (x-a) (b-x) * CR_of_Q R (1#2)).
1874 split. split.
1875 apply (CRplus_lt_reg_r (CRmin (x - a) (b - x) * CR_of_Q R (1 # 2))).
1876 apply (CRlt_le_trans _ x).
1877 2: unfold CRminus; rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r; apply CRle_refl.
1878 apply (CRplus_lt_reg_l R (-a)).
1879 apply (CRle_lt_trans _ (CRmin (x - a) (b - x) * CR_of_Q R (1 # 2))).
1880 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. apply CRle_refl.
1881 apply (CRlt_le_trans _ (CRmin (x + - a) (b + - x) * 1)).
1882 2: rewrite CRmult_1_r, CRplus_comm; apply CRmin_l.
1883 apply CRmult_lt_compat_l. apply CRmin_lt. apply CRlt_minus, (fst H).
1884 apply CRlt_minus, (snd H).
1885 apply CR_of_Q_lt. reflexivity.
1886 apply (CRlt_le_trans _ (x+0)). apply CRplus_lt_compat_l.
1887 rewrite <- CRopp_0. apply CRopp_gt_lt_contravar.
1888 apply CRmult_lt_0_compat. apply CRmin_lt.
1889 apply CRlt_minus. exact (fst H). apply CRlt_minus. exact (snd H).
1890 apply CR_of_Q_pos. reflexivity. rewrite CRplus_0_r. apply CRle_refl.
1891 split. apply (CRle_lt_trans _ (x+0)). rewrite CRplus_0_r.
1892 apply CRle_refl. apply CRplus_lt_compat_l. apply CRmult_lt_0_compat.
1893 apply CRmin_lt. apply CRlt_minus. exact (fst H).
1894 apply CRlt_minus. exact (snd H). apply CR_of_Q_pos. reflexivity.
1895 apply (CRplus_lt_reg_l R (-x)).
1896 apply (CRle_lt_trans _ (CRmin (x - a) (b - x) * CR_of_Q R (1 # 2))).
1897 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. apply CRle_refl.
1898 apply (CRle_lt_trans _ ((b - x) * CR_of_Q R (1 # 2))).
1899 apply CRmult_le_compat_r.
1900 apply CR_of_Q_le. discriminate. apply CRmin_r.
1901 apply (CRlt_le_trans _ ((b-x)*CR_of_Q _ 1)).
1902 apply CRmult_lt_compat_l. apply CRlt_minus. exact (snd H).
1903 apply CR_of_Q_lt. reflexivity.
1904 rewrite CRplus_comm, <- (CRmult_1_r (b + - x)).
1905 apply CRle_refl.
1906 Qed.
1907
1908 Lemma FindJumpPointsCountable
1909 : forall {IS : IntegrationSpace}
1910 (f : PartialFunction (X (ElemFunc IS)))
1911 (fInt : IntegrableFunction f),
1912 { s : nat -> CRcarrier (RealT (ElemFunc IS))
1913 & forall x, 0 < x
1914 -> (forall n:nat, CRapart _ x (s n))
1915 -> (forall eps, 0 < eps -> StepApproxBound f fInt x x eps (CRle_refl x)) }.
1916 Proof.
1917 intros.
1918 pose (fun (n:nat) => CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S n))) as an.
1919 pose (fun (n:nat) => CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat (2+n) # 1)) as bn.
1920 assert (forall n:nat, an n < bn n) as ltabn.
1921 { intro n. unfold an, bn.
1922 apply (CRle_lt_trans _ (CR_of_Q _ 1)).
1923 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
1924 do 2 rewrite Z.mul_1_l. apply Pos2Z.pos_le_pos. apply Pos.le_1_l.
1925 apply CR_of_Q_lt. unfold Qlt, Qnum, Qden.
1926 do 2 rewrite Z.mul_1_r. apply (Nat2Z.inj_lt 1 (2+n)).
1927 apply le_n_S, le_n_S, Nat.le_0_l. }
1928 assert (forall n:nat, 0 < an n) as anPos.
1929 { intro n. apply CR_of_Q_pos. reflexivity. }
1930 assert (forall n:nat, 0 < an n - an n * CR_of_Q _ (1#2) < an n) as orderBefore.
1931 { split. apply (CRlt_le_trans _ (an n * CR_of_Q _ (1#2))).
1932 apply CRmult_lt_0_compat. exact (anPos n).
1933 apply CR_of_Q_pos. reflexivity.
1934 apply (CRplus_le_reg_r (an n * CR_of_Q (RealT (ElemFunc IS)) (1 # 2))).
1935 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1936 rewrite <- CRmult_plus_distr_l, <- CR_of_Q_plus.
1937 setoid_replace ((1 # 2) + (1 # 2))%Q with 1%Q.
1938 rewrite CRmult_1_r. apply CRle_refl. reflexivity.
1939 apply (CRle_lt_trans _ (an n * CR_of_Q _ (1#2))).
1940 apply (CRplus_le_reg_r (an n * CR_of_Q (RealT (ElemFunc IS)) (1 # 2))).
1941 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
1942 rewrite <- CRmult_plus_distr_l, <- CR_of_Q_plus.
1943 setoid_replace ((1 # 2) + (1 # 2))%Q with 1%Q.
1944 rewrite CRmult_1_r. apply CRle_refl. reflexivity.
1945 rewrite <- (CRmult_1_r (an n)), CRmult_assoc.
1946 apply CRmult_lt_compat_l. exact (anPos n).
1947 rewrite CRmult_1_l. apply CR_of_Q_lt. reflexivity. }
1948 assert (forall n:nat, 0 < bn n < bn n + an n*CR_of_Q _ (1#2)) as orderAfter.
1949 { split. exact (CRlt_trans _ (an n) _ (anPos n) (ltabn n)).
1950 apply (CRle_lt_trans _ (bn n + 0)).
1951 rewrite CRplus_0_r. apply CRle_refl.
1952 apply CRplus_lt_compat_l. apply CRmult_lt_0_compat.
1953 exact (anPos n). apply CR_of_Q_pos. reflexivity. }
1954 pose (fun n:nat => Integral (StepApproxIntegrable
1955 f (an n - an n*CR_of_Q _ (1#2)) (an n)
1956 (orderBefore n) fInt))
1957 as intBefore.
1958 pose (fun n:nat => Integral (StepApproxIntegrable
1959 f (bn n) (bn n + an n*CR_of_Q _ (1#2))
1960 (orderAfter n) fInt))
1961 as intAfter.
1962 pose (fun (n:nat) => let (k,_) := CRup_nat ((1+ intBefore n - intAfter n)
1963 * CRinv _ (CR_of_Q _ (1 # Pos.of_nat n))
1964 (inr (CR_of_Q_pos (1 # Pos.of_nat n) (eq_refl _))))
1965 in k) as qn.
1966 assert (forall n:nat, 1 + intBefore n - intAfter n <=
1967 CR_of_Q _ (Z.of_nat (qn n) # 1) * CR_of_Q _ (1 # Pos.of_nat n)).
1968 { intro n. unfold qn.
1969 destruct ( CRup_nat
1970 ((1 + intBefore n - intAfter n) *
1971 CRinv (RealT (ElemFunc IS))
1972 (CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat n))
1973 (inr (CR_of_Q_pos (1 # Pos.of_nat n) eq_refl)))).
1974 apply CRlt_asym in c.
1975 apply (CRmult_le_compat_r (CR_of_Q _ (1 # Pos.of_nat n))) in c.
1976 rewrite CRmult_assoc, CRinv_l, CRmult_1_r in c. exact c.
1977 apply CR_of_Q_le. discriminate. }
1978 assert (forall n:nat, intAfter n <= intBefore n) as orderInt.
1979 { intro n.
1980 apply (StepApproxIntegralIncr
1981 f fInt (an n - an n * CR_of_Q _ (1 # 2)) (an n)
1982 (bn n) (bn n + an n * CR_of_Q _ (1 # 2))
1983 (orderBefore n) (orderAfter n)).
1984 apply (CRle_trans _ (an n)). apply CRlt_asym, orderBefore.
1985 apply CRlt_asym, ltabn. apply (CRle_trans _ (bn n + 0)).
1986 rewrite CRplus_0_r. apply CRlt_asym, ltabn.
1987 apply CRplus_le_compat_l. apply CRlt_asym, CRmult_lt_0_compat.
1988 exact (anPos n). apply CR_of_Q_pos. reflexivity. }
1989 assert (forall n:nat, qn n <> O) as qnz.
1990 { intro n. unfold qn.
1991 destruct ( CRup_nat
1992 ((1 + intBefore n - intAfter n) *
1993 CRinv (RealT (ElemFunc IS))
1994 (CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat n))
1995 (inr (CR_of_Q_pos (1 # Pos.of_nat n) eq_refl)))).
1996 apply CRlt_asym in c.
1997 intro abs. rewrite abs in c.
1998 apply (CRmult_le_compat_r (CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat n))) in c.
1999 rewrite CRmult_assoc, CRinv_l, CRmult_1_r, CRmult_0_l in c.
2000 apply (CRplus_le_compat _ _ _ _ (orderInt n)) in c.
2001 rewrite CRplus_comm in c. unfold CRminus in c.
2002 rewrite CRplus_assoc, CRplus_assoc, CRplus_opp_l, CRplus_comm in c.
2003 rewrite CRplus_assoc in c. apply CRplus_le_reg_l in c.
2004 rewrite CRplus_0_l in c. apply c. apply CRzero_lt_one.
2005 apply CR_of_Q_le. discriminate. }
2006 assert (forall n:nat, bn n < bn n + an n*CR_of_Q _ (1#2)).
2007 { intro n. apply (CRle_lt_trans _ (bn n + 0)). rewrite CRplus_0_r.
2008 apply CRle_refl. apply CRplus_lt_compat_l. apply CRmult_lt_0_compat.
2009 exact (anPos n). apply CR_of_Q_pos. reflexivity. }
2010 assert (forall n : nat,
2011 StepApproxBound f fInt (an n) (bn n) (1 + intBefore n - intAfter n)
2012 (CRlt_asym (an n) (bn n) (ltabn n)) ) as intBound.
2013 { intro n.
2014 exists (Build_IntervalExtension _ _ _ _ (orderBefore n) (H0 n)).
2015 simpl. apply (CRle_lt_trans _ (intBefore n - intAfter n)).
2016 apply CRplus_le_compat. unfold intBefore.
2017 apply StepApproxIntegralIncr. apply CRle_refl. apply CRle_refl.
2018 unfold intAfter.
2019 apply CRopp_ge_le_contravar, StepApproxIntegralIncr.
2020 apply CRle_refl. apply CRle_refl.
2021 rewrite <- (CRplus_0_l (intBefore n - intAfter n)).
2022 unfold CRminus. rewrite CRplus_assoc.
2023 apply CRplus_lt_compat_r, CRzero_lt_one. }
2024 pose proof (fun (n:nat) => FindJumpPointsFinite
2025 f fInt (an n) (bn n) (1 + intBefore n - intAfter n)
2026 (CR_of_Q _ (1 # Pos.of_nat n)) (anPos n) (ltabn n)
2027 (CR_of_Q_pos (1 # Pos.of_nat n) (eq_refl _))
2028 (qn n) (H n) (qnz n) (intBound n)).
2029 exists (diagSeq (fun n k => let (s,_) := H1 n in s k)).
2030 intros.
2031 assert (forall n k : nat, CRapart _ x (let (s, _) := H1 n in s k)).
2032 { intros. specialize (H3 (diagPlane n k)). unfold diagSeq in H3.
2033 rewrite diagPlaneInject in H3. exact H3. }
2034 clear H3.
2035 destruct (CRup_nat (CRinv _ eps (inr H4))) as [n nmaj].
2036 (* Locate x in an open interval ]an p, bn p[ with n <= p *)
2037 assert (CR_cv _ an 0) as stepCv.
2038 { unfold an. intro p. exists (Pos.to_nat p). intros. unfold CRminus.
2039 rewrite CRopp_0, CRplus_0_r. rewrite CRabs_right.
2040 apply CR_of_Q_le. unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
2041 apply Pos2Z.pos_le_pos. apply Pos2Nat.inj_le.
2042 rewrite Nat2Pos.id. apply (Nat.le_trans _ _ _ H3).
2043 apply le_S, Nat.le_refl. discriminate.
2044 apply CR_of_Q_le. discriminate. }
2045 destruct (CR_cv_open_above an x 0 stepCv H2) as [i imaj].
2046 destruct (CRup_nat x) as [j jmaj].
2047 specialize (imaj (max n (max i j))
2048 (Nat.le_trans _ _ _ (Nat.le_max_l i j) (Nat.le_max_r _ _))).
2049 specialize (H5 (max n (max i j))).
2050 destruct (H1 (max n (max i j))) as [s a0], a0, H6, H7.
2051 (* Locate x in an open interval ]s k, s (k+1)[ *)
2052 destruct (FindInterval s x O (qn (max n (max i j))) H7 H5) as [k kmaj].
2053 split. rewrite H3. exact imaj. rewrite H6.
2054 apply (CRlt_le_trans _ _ _ jmaj). apply CR_of_Q_le.
2055 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r.
2056 apply Nat2Z.inj_le. apply (Nat.le_trans _ (2+j)).
2057 apply le_S, le_S, Nat.le_refl. apply le_n_S, le_n_S.
2058 exact (Nat.le_trans _ _ _ (Nat.le_max_r i _) (Nat.le_max_r _ _)).
2059 apply Nat.le_refl.
2060 destruct (IntervalOpenEta (s k) (s (S k)) x kmaj) as [eta etamaj].
2061 destruct etamaj.
2062 assert (0 < x - eta < x).
2063 { split. 2: exact (snd p). apply (CRle_lt_trans _ (s k)).
2064 2: exact (fst p). apply (CRle_trans _ (s O)).
2065 rewrite H3. apply CRlt_asym, anPos.
2066 apply growing_transit. exact H7. apply Nat.le_0_l. }
2067 exists (Build_IntervalExtension _ _ _ _ H9 (fst p0)). simpl.
2068 apply (CRle_lt_trans _ (CR_of_Q _ (1 # Pos.of_nat n))).
2069 specialize (H8 k (x - eta) x x (x + eta) H9).
2070 apply (CRle_trans _ (CR_of_Q (RealT (ElemFunc IS))
2071 (1 # Pos.of_nat (max n (max i j))))).
2072 apply H8. 2: exact (CRle_refl x).
2073 exact (fst p). exact (snd p0). apply CR_of_Q_le. unfold Qle, Qnum, Qden.
2074 do 2 rewrite Z.mul_1_l. apply Pos2Z.pos_le_pos.
2075 rewrite Nat2Pos.inj_max. apply Pos.le_max_l.
2076 apply (CRmult_lt_compat_l eps) in nmaj. rewrite CRinv_r in nmaj.
2077 destruct n. exfalso. rewrite CRmult_0_r in nmaj.
2078 contradict nmaj. apply CRlt_asym, CRzero_lt_one.
2079 apply (CRmult_lt_reg_r (CR_of_Q (RealT (ElemFunc IS)) (Z.of_nat (S n) # 1))).
2080 apply CR_of_Q_pos. reflexivity. rewrite <- CR_of_Q_mult.
2081 setoid_replace ((1 # Pos.of_nat (S n)) * (Z.of_nat (S n) # 1))%Q with 1%Q.
2082 exact nmaj. unfold Qmult, Qeq, Qnum, Qden.
2083 rewrite Z.mul_1_l, Z.mul_1_l, Z.mul_1_r, Pos.mul_1_r.
2084 simpl (Z.of_nat (S n)). apply f_equal. rewrite Pos.of_nat_succ.
2085 reflexivity. exact H4.
2086 Qed.
2087
2088 (* The main theorem of profiles : inverse images are integrable
2089 except possibly on a countable set of points. *)
2090 Lemma InverseImageIntegrableAE
2091 : forall {IS : IntegrationSpace}
2092 (f : PartialFunction (X (ElemFunc IS)))
2093 (fInt : IntegrableFunction f),
2094 { s : nat -> CRcarrier (RealT (ElemFunc IS))
2095 & forall t (tPos : 0 < t),
2096 (forall n:nat, CRapart _ t (s n))
2097 -> { limInt : IntegrableSet (fun x => exists xD:Domain f x, t <= partialApply f x xD)
2098 & CR_cv _ (fun n:nat => Integral (StepApproxIntegrable
2099 f _ t (StepApproxBetween t tPos n) fInt))
2100 (MeasureSet limInt) } }.
2101 Proof.
2102 intros.
2103 destruct (FindJumpPointsCountable f fInt).
2104 exists x. intros.
2105 apply (InverseImageIntegrableGivenLimit f fInt t tPos).
2106 apply StepApproxBoundCv. apply (s t tPos H).
2107 Qed.
2108
2109 (* In any integration space, construct a subset of positive measure. *)
2110 Lemma IoneValSplit
2111 : forall {IS : IntegrationSpace},
2112 { nk : prod nat nat
2113 & I IS (XminConst (Xabs (Ione IS)) (CR_of_Q _ (1# Pos.of_nat (S (snd nk)))))
2114 (LminConstStable (CR_of_Q _ (1# Pos.of_nat (S (snd nk))))
2115 (Xabs (Ione IS))
2116 (invSuccRealPositive (snd nk))
2117 (LabsStable (ElemFunc IS) (Ione IS) (IoneL IS)))
2118 < I IS (XminConst (Xabs (Ione IS)) (INR (2 + (fst nk))))
2119 (LminIntStable (2 + (fst nk)) (Xabs (Ione IS))
2120 (LabsStable _ _ (IoneL IS))) }.
2121 Proof.
2122 intro IS.
2123 assert (0 < I IS (Xabs (Ione IS)) (LabsStable _ _ (IoneL IS))).
2124 { apply (CRlt_le_trans _ 1). apply CRzero_lt_one.
2125 rewrite <- IoneInt. apply INonDecreasing. intros.
2126 simpl. rewrite (DomainProp _ x xF y). apply CRle_abs. }
2127 pose proof (Ilimit IS (Ione IS) (IoneL IS)) as [_ lowInt].
2128 pose proof (CR_cv_open_above _ _ _ lowInt H) as [k kmaj].
2129 specialize (kmaj k (Nat.le_refl k)).
2130 pose proof (Ilimit IS (Xabs (Ione IS)) (LabsStable _ _ (IoneL IS)))
2131 as [highInt _].
2132 pose proof (CR_cv_open_below _ _ _ highInt kmaj) as [n nmaj].
2133 exists (pair n k). apply nmaj. unfold fst. apply le_S, le_S, Nat.le_refl.
2134 Qed.
2135
2136 Record PositiveMeasureSubset {IS : IntegrationSpace} :=
2137 { pms_subset : X (ElemFunc IS) -> Prop;
2138 pms_int : IntegrableSet pms_subset;
2139 pms_pos : 0 < MeasureSet pms_int;
2140 }.
2141
2142 Lemma StepApproxMax
2143 : forall {R : ConstructiveReals}
2144 (c s2 t2 : CRcarrier R) (ltst2 : s2 < t2),
2145 s2 <= t2
2146 -> CRinv R (t2 - s2) (inr (CRlt_minus s2 t2 ltst2)) *
2147 (CRmin c t2 + - CRmin c s2) <= 1.
2148 Proof.
2149 intros. apply (CRmult_le_reg_l (t2-s2)).
2150 apply CRlt_minus, ltst2.
2151 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l, CRmult_1_r.
2152 apply (CRle_trans _ _ _ (CRle_abs _)).
2153 rewrite CRmin_sym, (CRmin_sym c s2).
2154 apply (CRle_trans _ _ _ (CRmin_contract _ _ _)).
2155 rewrite CRabs_right. apply CRle_refl.
2156 apply CRlt_asym, CRlt_minus, ltst2.
2157 Qed.
2158
2159 Lemma PositiveMeasureSubsetExists
2160 : forall (IS : IntegrationSpace), @PositiveMeasureSubset IS.
2161 Proof.
2162 intro IS. destruct (@IoneValSplit IS) as [[n k] H].
2163 unfold fst, snd in H.
2164 assert (1 # Pos.of_nat (S k) < Z.of_nat (2 + n) # 1)%Q.
2165 { unfold Qlt, Qnum, Qden. rewrite Z.mul_1_l.
2166 apply (Z.lt_le_trans _ (Z.of_nat (2+n)*1)).
2167 rewrite Z.mul_1_r. replace 1%Z with (Z.of_nat 1).
2168 apply Nat2Z.inj_lt. apply le_n_S, le_n_S, Nat.le_0_l. reflexivity.
2169 apply Z.mul_le_mono_nonneg_l. discriminate.
2170 apply Pos2Z.pos_le_pos. apply Pos.le_1_l. }
2171 pose proof (InverseImageIntegrableAE
2172 (Xabs (Ione IS)) (IntegrableL _ (LabsStable _ _ (IoneL IS))))
2173 as [s sint].
2174 assert (0 < CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S k)) < INR (2 + n)).
2175 { split. apply CR_of_Q_pos. reflexivity. apply CR_of_Q_lt. exact H0. }
2176 destruct (CRuncountable s 0 (CR_of_Q _ (1 # Pos.of_nat (S k))) (fst H1))
2177 as [t tap].
2178 destruct tap. specialize (sint t (fst p) c). destruct sint.
2179 assert (0 < MeasureSet x).
2180 { apply (CRlt_le_trans
2181 _ (Integral (StepApproxIntegrable
2182 (Xabs (Ione IS))
2183 (CR_of_Q _ (1 # Pos.of_nat (S k))) (INR (2 + n)) H1
2184 (IntegrableL _ (LabsStable _ _ (IoneL IS)))))).
2185 unfold StepApproxIntegrable.
2186 rewrite (IntegralScale (Xminus (XminConst (Xabs (Ione IS)) (INR (2 + n)))
2187 (XminConst (Xabs (Ione IS))
2188 (CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S k)))))
2189 _
2190 (CRinv (RealT (ElemFunc IS))
2191 (INR (2 + n) - CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S k)))
2192 (inr
2193 (CRlt_minus (CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S k)))
2194 (INR (2 + n)) (snd H1)))) ).
2195 apply CRmult_lt_0_compat. rewrite IntegralMinus.
2196 apply CRlt_minus.
2197 apply (CRle_lt_trans _ (Integral (IntegrableL _ (LminConstStable (CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S k)))
2198 (Xabs (Ione IS)) (invSuccRealPositive k)
2199 (LabsStable (ElemFunc IS) (Ione IS) (IoneL IS)))))).
2200 apply IntegralNonDecreasing. intros y ydf ydg.
2201 rewrite (DomainProp _ y ydf ydg). apply CRle_refl.
2202 rewrite IntegralLstable.
2203 apply (CRlt_le_trans _ _ _ H).
2204 apply (CRle_trans _ (Integral (IntegrableL _ (LminIntStable (2 + n) (Xabs (Ione IS))
2205 (LabsStable (ElemFunc IS) (Ione IS) (IoneL IS)))))).
2206 rewrite IntegralLstable. apply CRle_refl.
2207 apply IntegralNonDecreasing. intros y ydf ydg.
2208 rewrite (DomainProp _ y ydf ydg). apply CRle_refl.
2209 apply CRinv_0_lt_compat, CRlt_minus, CR_of_Q_lt. exact H0.
2210 apply IntegralNonDecreasing. intros y ydf ydg.
2211 simpl ( partialApply (CharacFunc
2212 (fun x0 : X (ElemFunc IS) =>
2213 exists xD : Domain (Xabs (Ione IS)) x0,
2214 t <= partialApply (Xabs (Ione IS)) x0 xD)) y ydg).
2215 destruct ydg.
2216 - unfold StepApprox. rewrite applyXscale.
2217 destruct ydf.
2218 rewrite (applyXminus _ (XminConst (Xabs (Ione IS))
2219 (CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S k))))).
2220 do 2 rewrite applyXminConst. rewrite (DomainProp (Xabs (Ione IS)) y d0 d).
2221 apply StepApproxMax. apply CRlt_asym, CR_of_Q_lt. exact H0.
2222 - destruct (CRltLinear (RealT (ElemFunc IS))).
2223 destruct ydf.
2224 destruct (s0 t (partialApply (Xabs (Ione IS)) y d0)
2225 (CR_of_Q _ (1 # Pos.of_nat (S k))) (snd p)).
2226 exfalso. apply n0. exists d0. apply CRlt_asym, c1.
2227 unfold StepApprox. rewrite applyXscale.
2228 apply (CRmult_le_reg_l (INR (2 + n) - CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S k)))).
2229 apply CRlt_minus, CR_of_Q_lt. exact H0.
2230 rewrite <- CRmult_assoc, CRinv_r, CRmult_0_r, CRmult_1_l.
2231 rewrite (applyXminus _ (XminConst (Xabs (Ione IS))
2232 (CR_of_Q (RealT (ElemFunc IS)) (1 # Pos.of_nat (S k))))).
2233 do 2 rewrite applyXminConst. rewrite (DomainProp (Xabs (Ione IS)) y d d0).
2234 unfold CRminus.
2235 rewrite CRmin_left, CRmin_left, CRplus_opp_r. apply CRle_refl.
2236 apply CRlt_asym, c1. apply CRlt_asym.
2237 apply (CRlt_trans _ _ _ c1). apply CR_of_Q_lt. exact H0. }
2238 exact (Build_PositiveMeasureSubset IS _ x H2).
2239 Qed.