Debian Codegraph @

reals/stdlib/CMTIntegrableSets.v

raw
1 (*
2 Copyright © 2020 Vincent Semeria
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
5
6 The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
7
8 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
9 *)
10
11
12 (*
13 We now move from functions to integrable sets, ie measures. We will
14 prove the properties of measures up to monotonous continuity.
15
16 Given an integration space IS on a base type X, a subset
17 A : X -> Prop is declared integrable when it is almost everywhere
18 decidable, i.e. when there is an integrable function
19 f : X -> {0, 1} such as A x when f x == 1 and ~A x when f x == 0.
20 The integral of f will be called the measure of A. Because integrable
21 functions are stable under extensions, this definition is
22 equivalent to requiring that the biggest characteristic function
23 with domain { x : X & { A x } + { ~A x } } is integrable.
24
25 This simplifies the theory of Bishop and Cheng, by avoiding the
26 unnecessary concept of complemented set.
27 *)
28
29 From Coq Require Import ConstructiveEpsilon.
30 From Coq Require Import ZArith.
31 From Coq Require Import QArith.
32 From Coq Require Import ConstructiveReals.
33 From Coq Require Import ConstructiveAbs.
34 From Coq Require Import ConstructiveMinMax.
35 From Coq Require Import ConstructiveSum.
36 From Coq Require Import ConstructivePower.
37 From Coq Require Import ConstructiveLimits.
38 Require Import ConstructiveDiagonal.
39 Require Import ConstructivePartialFunctions.
40
41 Require Import CMTbase.
42 Require Import CMTIntegrableFunctions.
43 Require Import CMTFullSets.
44 Require Import CMTPositivity.
45
46 Local Open Scope ConstructiveReals.
47
48
49 Definition CharacFunc {R : ConstructiveReals} {X : Set} (A : X -> Prop)
50 : @PartialFunction R X.
51 Proof.
52 apply (Build_PartialFunctionXY
53 X (CRcarrier R) (CReq R) (fun x:X => { A x } + { ~A x })
54 (fun x dec => if dec then CR_of_Q R 1 else CR_of_Q R 0) ).
55 intros. destruct p,q.
56 reflexivity. contradiction. contradiction. reflexivity.
57 Defined.
58
59 Definition IntegrableSet {IS : IntegrationSpace}
60 (A : (X (ElemFunc IS)) -> Prop) : Type
61 := IntegrableFunction (CharacFunc A).
62
63 Definition MeasureSet {IS : IntegrationSpace}
64 {A : X (ElemFunc IS) -> Prop}
65 : IntegrableSet A -> CRcarrier (RealT (ElemFunc IS))
66 := Integral.
67
68
69 (*********************************************************)
70 (** * Integration of complemented sets *)
71 (*********************************************************)
72
73 Definition PartialFunctionBoolR
74 {X : Set} {R : ConstructiveReals}
75 (f : @PartialFunctionXY X bool eq)
76 : @PartialFunction R X.
77 Proof.
78 apply (Build_PartialFunctionXY
79 X (CRcarrier R) (CReq R) (Domain f)
80 (fun x dec => if partialApply f x dec then CR_of_Q R 1 else CR_of_Q R 0)).
81 intros. rewrite (DomainProp f x p q). reflexivity.
82 Defined.
83
84 (* As announced, we prove that Definition IntegrableSet is equivalent
85 to the more general formulation that the subset is almost everywhere decidable. *)
86 Lemma IntegrableSetAEdecidable
87 : forall {IS : IntegrationSpace}
88 (A : (X (ElemFunc IS)) -> Prop)
89 (f : @PartialFunctionXY (X (ElemFunc IS)) bool eq),
90 IntegrableFunction (PartialFunctionBoolR f)
91 -> (forall (x : X (ElemFunc IS)) (dec : Domain f x),
92 if partialApply f x dec then A x else ~A x)
93 -> IntegrableSet A.
94 Proof.
95 intros IS A f fInt. destruct fInt.
96 exists x. apply (PartialRestriction_trans _ _ (PartialFunctionBoolR f) _ p).
97 split.
98 - intros y yD. simpl in yD. specialize (H y yD).
99 destruct (partialApply f y yD).
100 left. exact H. right. exact H.
101 - intros. simpl. specialize (H x0 xD).
102 destruct (partialApply f x0 xD), xG. reflexivity. 3: reflexivity.
103 contradiction. contradiction.
104 Qed.
105
106 Definition IntegrableSetExtensional
107 {IS : IntegrationSpace}
108 (A B : (X (ElemFunc IS)) -> Prop)
109 : (forall x:X (ElemFunc IS), { A x } + { ~A x } -> (A x <-> B x))
110 -> IntegrableSet A
111 -> IntegrableSet B.
112 Proof.
113 intros H Aint.
114 apply (IntegrableFunctionExtensional (CharacFunc A)).
115 2: exact Aint.
116 split.
117 - intros x xdf. destruct xdf. left. apply H.
118 left. exact a. exact a.
119 right. intro abs. apply H in abs. contradiction.
120 right. exact n.
121 - intros. simpl. destruct xD, xG. reflexivity.
122 apply H in a. contradiction. left. exact a.
123 apply H in b. contradiction. right. exact n. reflexivity.
124 Qed.
125
126 (* ~~A can constructively be bigger than A, but when A is integrable
127 then so is ~~A, with same measure. *)
128 Definition IntegrableSetNotNot
129 {IS : IntegrationSpace}
130 (A : (X (ElemFunc IS)) -> Prop)
131 : IntegrableSet A -> IntegrableSet (fun x => ~~A x).
132 Proof.
133 intro Aint.
134 apply (IntegrableSetExtensional A).
135 split. intros H0 abs. contradiction.
136 intro abs. destruct H. exact a. contradiction. exact Aint.
137 Qed.
138
139 Lemma MeasureExtensional
140 : forall {IS : IntegrationSpace}
141 (A B : (X (ElemFunc IS)) -> Prop)
142 (Aint : IntegrableSet A) (Bint : IntegrableSet B),
143 (forall x:X (ElemFunc IS),
144 { A x } + { ~A x } -> { B x } + { ~B x }
145 -> (A x <-> B x))
146 -> MeasureSet Aint == MeasureSet Bint.
147 Proof.
148 intros. apply IntegralExtensional.
149 intros. simpl. destruct xdf, xdg. reflexivity. 3: reflexivity.
150 exfalso. rewrite H in a. contradiction.
151 left. exact a. right. exact n.
152 exfalso. rewrite <- H in b. contradiction.
153 right. exact n. left. exact b.
154 Qed.
155
156 Lemma MeasureEmptyZero
157 : forall {IS : IntegrationSpace}
158 (A : X (ElemFunc IS) -> Prop)
159 (aInt : IntegrableSet A),
160 (forall x:X (ElemFunc IS), { A x } + { ~A x } -> ~A x)
161 -> MeasureSet aInt == 0.
162 Proof.
163 intros. transitivity (Integral (@IntegrableZero IS)).
164 apply IntegralExtensional.
165 intros. simpl.
166 destruct xdf. 2: reflexivity. exfalso.
167 specialize (H x (left a)). contradiction.
168 apply IntegralZeroIsZero.
169 Qed.
170
171 Lemma MeasureNonNeg : forall {IS : IntegrationSpace}
172 (A : X (ElemFunc IS) -> Prop)
173 (aInt : IntegrableSet A),
174 0 <= MeasureSet aInt.
175 Proof.
176 intros. apply (CRle_trans _ (Integral (@IntegrableZero IS))).
177 rewrite IntegralZeroIsZero. apply CRle_refl.
178 apply IntegralNonDecreasing. intros x xdf xdg.
179 simpl. destruct xdg. apply CRlt_asym, CRzero_lt_one.
180 apply CRle_refl.
181 Qed.
182
183 Lemma MeasureNonDecreasing
184 : forall {IS : IntegrationSpace}
185 (A B : X (ElemFunc IS) -> Prop)
186 (aInt : IntegrableSet A)
187 (bInt : IntegrableSet B),
188 (forall x : X (ElemFunc IS), A x -> B x)
189 -> MeasureSet aInt <= MeasureSet bInt.
190 Proof.
191 intros. apply IntegralNonDecreasing.
192 intros x xdf xdg. simpl. destruct xdf, xdg.
193 apply CRle_refl. exfalso. specialize (H x a). contradiction.
194 apply CRlt_asym, CRzero_lt_one. apply CRle_refl.
195 Qed.
196
197 Lemma MeasureZeroAE
198 : forall {IS : IntegrationSpace}
199 (Z : X (ElemFunc IS) -> Prop)
200 (zInt : IntegrableSet Z),
201 MeasureSet zInt == 0
202 -> almost_everywhere (fun x => ~Z x).
203 Proof.
204 intros.
205 destruct (IntegrableFunctionsComplete
206 IS (fun _:nat => CharacFunc Z) (fun _ => zInt) 0) as [rep [p s]].
207 - apply (CR_cv_eq _ (fun _:nat => 0)). 2: apply CR_cv_const.
208 intro n. rewrite sum_const. unfold MeasureSet in H.
209 rewrite <- (CRmult_0_l (INR (S n))).
210 apply CRmult_morph. 2: reflexivity. rewrite <- H.
211 apply IntegralExtensional. intros. rewrite applyXabs.
212 rewrite (DomainProp _ x xdf xdg). rewrite CRabs_right.
213 reflexivity. simpl. destruct xdg. apply CRlt_asym, CRzero_lt_one.
214 apply CRle_refl.
215 - exists (XinfiniteSumAbs (IntFn rep)). split.
216 + exists rep. apply PartialRestriction_refl.
217 + intros x H0 abs. destruct p. specialize (d x H0) as [xn xncv].
218 apply CR_complete in xncv. destruct xncv as [l lcv].
219 apply (CR_cv_eq (fun n:nat => CR_of_Q _ (Z.of_nat (S n) # 1))) in lcv.
220 specialize (lcv 1%positive) as [n ncv].
221 destruct (CRup_nat (1+l)) as [k kup].
222 specialize (ncv (max n k) (Nat.le_max_l _ _)).
223 apply (CRle_trans _ _ _ (CRle_abs _)) in ncv.
224 apply (CRplus_le_compat_r l) in ncv.
225 unfold CRminus in ncv. rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r in ncv.
226 apply ncv. apply (CRlt_le_trans _ _ _ kup).
227 apply CR_of_Q_le. unfold Qle, Qnum, Qden. rewrite Z.mul_1_r, Z.mul_1_r.
228 apply Nat2Z.inj_le, le_S, Nat.le_max_r.
229 intro n. rewrite <- (CRsum_eq (fun _ => 1)).
230 rewrite sum_const, CRmult_1_l. reflexivity.
231 intros. simpl. destruct (xn i).
232 rewrite CRabs_right. reflexivity. apply CRlt_asym, CRzero_lt_one.
233 contradiction.
234 Qed.
235
236 Lemma domainXinfinitePosNeg
237 : forall {R : ConstructiveReals} {X : Set}
238 (fn : nat -> @PartialFunction R X) (x : X),
239 (Domain (XinfiniteSumAbs (fun n => XposPart (fn n))) x)
240 -> (Domain (XinfiniteSumAbs (fun n => XnegPart (fn n))) x)
241 -> Domain (XinfiniteSumAbs fn) x.
242 Proof.
243 intros. destruct H, H0.
244 exists (fun n => fst (x0 n)).
245 apply CR_complete in c. apply CR_complete in c0. destruct c,c0.
246 apply (Rcv_cauchy_mod _ (x2+x3)).
247 pose proof (series_cv_plus _ _ _ _ c c0).
248 apply (series_cv_eq (fun n : nat =>
249 (fun n0 : nat => CRabs R (partialApply (XposPart (fn n0)) x (x0 n0))) n +
250 (fun n0 : nat => CRabs R (partialApply (XnegPart (fn n0)) x (x1 n0))) n)).
251 intro n. rewrite CRabs_right, CRabs_right.
252 simpl. destruct (x0 n), (x1 n). rewrite <- CRmult_plus_distr_l.
253 rewrite <- CRopp_mult_distr_l, CRmult_1_l, CRplus_comm, CRplus_assoc.
254 rewrite <- (CRplus_assoc (- partialApply (fn n) x d2)).
255 rewrite (DomainProp (fn n) x d2 d), CRplus_opp_l, CRplus_0_l.
256 apply (CRmult_eq_reg_l (CR_of_Q R 2)). right. apply CR_of_Q_pos. reflexivity.
257 rewrite <- CRmult_assoc, <- CR_of_Q_mult.
258 setoid_replace (2 * (1 # 2))%Q with 1%Q. 2: reflexivity.
259 rewrite (CR_of_Q_plus R 1 1), CRmult_1_l.
260 rewrite CRmult_plus_distr_r, CRmult_1_l.
261 rewrite (DomainProp (fn n) x (fst (d,d0)) d0), (DomainProp (fn n) x d1 d0).
262 reflexivity. apply applyXnegPartNonNeg. apply applyXposPartNonNeg.
263 exact H.
264 Qed.
265
266 (* This will provide a very nice proof that the Cauchy reals are uncountable. *)
267 Lemma PositiveMeasureInhabited
268 : forall {IS : IntegrationSpace}
269 (A : X (ElemFunc IS) -> Prop)
270 (aInt : IntegrableSet A),
271 0 < MeasureSet aInt -> { x : X (ElemFunc IS) | A x }.
272 Proof.
273 intros. destruct aInt.
274 destruct (splitIntegralSumPosNeg
275 (IntFn x) (IntFnL x)
276 (IntAbsSum x) (IntAbsSumCv x)), s, p0, p0.
277 assert (series_cv
278 (fun k : nat => Iabs (XposPart (IntFn x k))
279 (LposPartStable (IntFn x k) (IntFnL x k))) x0).
280 { apply (series_cv_eq (fun n0 : nat =>
281 I IS (XposPart (IntFn x n0)) (LposPartStable (IntFn x n0) (IntFnL x n0)))).
282 2: exact s0. intro n. apply IExtensional.
283 intros. rewrite applyXabs, CRabs_right, (DomainProp _ x2 xF y).
284 reflexivity. apply applyXposPartNonNeg. }
285 destruct (IntegrableContinuous
286 (XinfiniteSumAbs (fun n : nat => XposPart (IntFn x n)))
287 (fun n => XnegPart (IntFn x n))
288 (existT _
289 (Build_IntegralRepresentation
290 IS (fun n => XposPart (IntFn x n))
291 (fun n => LposPartStable _ (IntFnL x n)) x0 H0)
292 (pair (fun y yD => yD) (fun x2 xD xG => DomainProp _ x2 xD xG)))
293 (fun n => IntegrableL _ (LnegPartStable (IntFn x n) (IntFnL x n)))).
294 - intro n. apply applyXnegPartNonNeg.
295 - exists x1. split.
296 apply (series_cv_eq (fun n0 : nat =>
297 I IS (XnegPart (IntFn x n0)) (LnegPartStable (IntFn x n0) (IntFnL x n0)))).
298 2: exact s1. intro n. rewrite IntegralLstable. reflexivity.
299 unfold Integral. apply (CRlt_le_trans _ x0).
300 apply (CRplus_lt_reg_r (-x1)). rewrite CRplus_opp_r.
301 pose proof (IntegralCv x).
302 setoid_replace (x0 + - x1) with (IntegralSeries x). exact H.
303 apply (series_cv_unique (fun n : nat => I IS (IntFn x n) (IntFnL x n))).
304 2: exact H1. unfold CRminus in s. exact s.
305 unfold IntegralSeries.
306 destruct (series_cv_maj
307 _ _ x0
308 (fun n : nat =>
309 integralAbsMaj (XposPart (IntFn x n))
310 (LposPartStable (IntFn x n) (IntFnL x n))) H0), p0.
311 setoid_replace x0 with x2. apply CRle_refl.
312 apply (series_cv_unique
313 (fun k : nat => Iabs (XposPart (IntFn x k))
314 (LposPartStable (IntFn x k) (IntFnL x k))) _ _ H0).
315 apply (series_cv_eq (fun n : nat => I IS (XposPart (IntFn x n))
316 (LposPartStable (IntFn x n) (IntFnL x n)))).
317 2: exact s2. intro n. apply IExtensional. intros.
318 rewrite applyXabs, CRabs_right. apply DomainProp.
319 apply applyXposPartNonNeg.
320 - clear H. destruct x2;
321 unfold ConstructivePartialFunctions.cpx,
322 ConstructivePartialFunctions.cpxF,
323 ConstructivePartialFunctions.cpxFn in s2.
324 exists cpx. destruct s2, p0, p.
325 assert (Domain (XinfiniteSumAbs (IntFn x)) cpx).
326 { apply (domainXinfinitePosNeg _ _ cpxF).
327 exists cpxFn. apply (Rcv_cauchy_mod _ x2).
328 apply (series_cv_eq
329 (fun n : nat => partialApply (XnegPart (IntFn x n)) cpx (cpxFn n))).
330 2: exact s2. intro n. rewrite CRabs_right. reflexivity.
331 apply applyXnegPartNonNeg. }
332 pose proof (c0 cpx H (d _ H)).
333 simpl (partialApply (CharacFunc A) cpx (d cpx H)) in H1.
334 destruct (d cpx H). exact a. exfalso. clear n.
335 apply applyInfiniteSumAbs in H1.
336 pose proof (series_cv_unique
337 _ 0 (partialApply (XinfiniteSumAbs
338 (fun n : nat => XposPart (IntFn x n))) cpx cpxF-x2) H1).
339 clear H1. apply CRlt_minus in c. destruct H2. 2: contradiction.
340 destruct cpxF.
341 apply (series_cv_eq
342 (fun n : nat =>
343 partialApply (XposPart (IntFn x n)) cpx (x3 n)
344 - partialApply (XnegPart (IntFn x n)) cpx (cpxFn n))).
345 intro n. apply SplitPosNegParts.
346 apply series_cv_minus. 2: exact s2.
347 apply (series_cv_eq
348 (fun n => partialApply (XposPart (IntFn x n)) cpx
349 (domainInfiniteSumAbsIncReverse
350 _ cpx
351 (existT _ x3 c1) n))).
352 intro n. apply DomainProp.
353 apply applyInfiniteSumAbs. reflexivity.
354 Qed.
355
356 Definition IntegrableSetIntersect
357 {IS : IntegrationSpace}
358 (A B : X (ElemFunc IS) -> Prop)
359 (aInt : IntegrableSet A)
360 (bInt : IntegrableSet B)
361 : IntegrableSet (fun x => A x /\ B x).
362 Proof.
363 apply (IntegrableFunctionExtensional
364 (Xmin (CharacFunc A) (CharacFunc B))).
365 - split.
366 + intros x xdf. simpl. destruct xdf, d0, d0.
367 destruct d. destruct d0.
368 left. split; assumption. right.
369 intros [abs _]. contradiction. right. intros [_ abs]. contradiction.
370 + intros.
371 assert (Domain (@CharacFunc (RealT (ElemFunc IS)) _ A) x) as H.
372 { destruct (CharacFunc A), (CharacFunc B); simpl; apply xD. }
373 assert (Domain (@CharacFunc (RealT (ElemFunc IS)) _ B) x) as H0.
374 { destruct (CharacFunc A), (CharacFunc B); simpl; apply xD. }
375 rewrite (applyXmin _ _ _ H H0).
376 destruct H. destruct H0.
377 (* In intersection *)
378 rewrite CRmin_left. simpl. destruct xG.
379 reflexivity. exfalso. apply n. split; assumption.
380 apply CRle_refl.
381 (* Not in intersection *)
382 destruct xG.
383 exfalso. apply n; apply a0.
384 rewrite CRmin_right. reflexivity. apply CRlt_asym, CRzero_lt_one.
385 destruct H0. destruct xG.
386 exfalso. apply n, a.
387 rewrite CRmin_left. reflexivity. apply CRlt_asym, CRzero_lt_one.
388 rewrite CRmin_left. destruct xG.
389 exfalso. apply n, a.
390 reflexivity. apply CRle_refl.
391 - apply IntegrableMin; assumption.
392 Defined.
393
394 Lemma MeasureIntersectSym
395 : forall {IS : IntegrationSpace}
396 (A B : X (ElemFunc IS) -> Prop)
397 (aInt : IntegrableSet A)
398 (bInt : IntegrableSet B),
399 MeasureSet (IntegrableSetIntersect A B aInt bInt)
400 == MeasureSet (IntegrableSetIntersect B A bInt aInt).
401 Proof.
402 intros. unfold MeasureSet. apply IntegralExtensional. intros.
403 destruct xdf,xdg; simpl. reflexivity.
404 exfalso. apply n. split; apply a.
405 exfalso. apply n. split; apply a.
406 reflexivity.
407 Qed.
408
409 Definition IntegrableSetUnion {IS : IntegrationSpace}
410 (A B : X (ElemFunc IS) -> Prop)
411 (aInt : IntegrableSet A)
412 (bInt : IntegrableSet B)
413 : IntegrableSet (fun x => A x \/ B x).
414 Proof.
415 apply (IntegrableFunctionExtensional
416 (Xmax (CharacFunc A) (CharacFunc B))).
417 - split.
418 + intros x xdf. simpl. destruct xdf, d0, d0.
419 clear d2 d1.
420 destruct d. left. right. exact b.
421 destruct d0. left. left. exact a.
422 right. intro abs. destruct abs; contradiction.
423 + intros.
424 assert (Domain (@CharacFunc (RealT (ElemFunc IS)) _ A) x) as H.
425 { destruct (CharacFunc A), (CharacFunc B); simpl; apply xD. }
426 assert (Domain (@CharacFunc (RealT (ElemFunc IS)) _ B) x) as H0.
427 { destruct (CharacFunc A), (CharacFunc B); simpl; apply xD. }
428 rewrite (applyXmax _ _ _ H H0).
429 destruct xG.
430 (* In union *)
431 destruct H, H0.
432 rewrite CRmax_right. reflexivity. apply CRle_refl.
433 rewrite CRmax_left. reflexivity. apply CRlt_asym, CRzero_lt_one.
434 rewrite CRmax_right. reflexivity. apply CRlt_asym, CRzero_lt_one.
435 exfalso. destruct o; contradiction.
436 (* Not in union *)
437 destruct H. exfalso. apply n. left. exact a.
438 destruct H0. exfalso. apply n. right. exact b.
439 rewrite CRmax_right. reflexivity. apply CRle_refl.
440 - apply IntegrableMax; assumption.
441 Defined.
442
443 Lemma MeasureAdditive
444 : forall {IS : IntegrationSpace}
445 (A B : X (ElemFunc IS) -> Prop)
446 (aInt : IntegrableSet A)
447 (bInt : IntegrableSet B),
448 MeasureSet aInt + MeasureSet bInt
449 == MeasureSet (IntegrableSetUnion A B aInt bInt)
450 + MeasureSet (IntegrableSetIntersect A B aInt bInt).
451 Proof.
452 intros.
453 setoid_replace (MeasureSet aInt + MeasureSet bInt)
454 with (Integral (IntegrablePlus _ _ aInt bInt)).
455 setoid_replace (MeasureSet (IntegrableSetUnion A B aInt bInt)
456 + MeasureSet (IntegrableSetIntersect A B aInt bInt))
457 with (Integral (IntegrablePlus _ _ (IntegrableSetUnion A B aInt bInt)
458 (IntegrableSetIntersect A B aInt bInt))).
459 - apply IntegralExtensional. intros.
460 destruct xdf,xdg; simpl. destruct d.
461 destruct d1. 2: exfalso; apply n; left; exact a.
462 destruct d0.
463 destruct d2. reflexivity. exfalso; apply n; split; assumption.
464 destruct d2. exfalso. destruct a0. contradiction.
465 reflexivity. destruct d0, d1, d2.
466 exfalso. apply n, a. apply CRplus_comm. reflexivity.
467 exfalso. apply n0. right. exact b.
468 exfalso. apply n, a. exfalso. destruct o; contradiction.
469 exfalso. apply n, a. reflexivity.
470 - rewrite IntegralPlus. reflexivity.
471 - rewrite IntegralPlus. reflexivity.
472 Qed.
473
474 Fixpoint UnionIterate {X : Set} (An : nat -> X -> Prop) (n : nat)
475 : X -> Prop
476 := match n with
477 | O => An O
478 | S p => fun x => UnionIterate An p x \/ An n x
479 end.
480
481 Fixpoint IntersectIterate {X : Set} (An : nat -> X -> Prop) (n : nat)
482 : X -> Prop
483 := match n with
484 | O => An O
485 | S p => fun x => IntersectIterate An p x /\ An n x
486 end.
487
488 Lemma applyUnionIterate
489 : forall (X : Set) (An : nat -> X -> Prop)
490 (n : nat)
491 (x : X),
492 UnionIterate An n x
493 <-> exists (p:nat), le p n /\ An p x.
494 Proof.
495 induction n.
496 - split. intros. exists O. split. reflexivity. apply H.
497 intros. simpl. destruct H as [p [pneg pxp]].
498 inversion pneg. subst p. apply pxp.
499 - split.
500 + intros. simpl in H.
501 destruct H.
502 specialize (IHn x) as [H0 _].
503 destruct (H0 H). exists x0. split. apply (Nat.le_trans _ n).
504 apply H1. apply le_S, Nat.le_refl. apply H1.
505 exists (S n). split. apply Nat.le_refl. apply H.
506 + intros. destruct H as [p [pxp H]].
507 apply Nat.le_succ_r in pxp. destruct pxp.
508 (* p <= n *)
509 left. specialize (IHn x) as [_ H3]. apply H3. exists p.
510 split; assumption. subst p. right. exact H.
511 Qed.
512
513 Lemma applyIntersectIterate
514 : forall (X : Set) (An : nat -> X -> Prop)
515 (n : nat)
516 (x : X),
517 IntersectIterate An n x
518 <-> forall (p:nat), le p n -> An p x.
519 Proof.
520 induction n.
521 - split. intros. simpl in H. inversion H0. subst p. exact H.
522 intros. simpl. apply H. apply Nat.le_refl.
523 - split.
524 + intros. apply Nat.le_succ_r in H0. destruct H0.
525 apply IHn. apply H. exact H0. subst p. apply H.
526 + intros. split. apply IHn. intros. apply H.
527 apply (Nat.le_trans _ _ _ H0). apply le_S, Nat.le_refl.
528 apply H. apply Nat.le_refl.
529 Qed.
530
531 Definition IntegrableSetUnionIterate
532 {IS : IntegrationSpace}
533 (An : nat -> X (ElemFunc IS) -> Prop)
534 (aInt : forall n:nat, IntegrableSet (An n))
535 : forall n:nat, IntegrableSet (UnionIterate An n).
536 Proof.
537 induction n.
538 - apply aInt.
539 - simpl. apply IntegrableSetUnion. apply IHn. apply aInt.
540 Defined.
541
542 Definition IntegrableSetIntersectIterate
543 {IS : IntegrationSpace}
544 (An : nat -> X (ElemFunc IS) -> Prop)
545 (aInt : forall n:nat, IntegrableSet (An n))
546 : forall n:nat, IntegrableSet (IntersectIterate An n).
547 Proof.
548 induction n.
549 - apply aInt.
550 - simpl. apply IntegrableSetIntersect. apply IHn. apply aInt.
551 Defined.
552
553 Lemma MeasureIntersectSeqDecr
554 : forall {IS : IntegrationSpace}
555 (An : nat -> X (ElemFunc IS) -> Prop)
556 (AnInt : forall n:nat, IntegrableSet (An n)),
557 (forall (n : nat) (x : X (ElemFunc IS)),
558 An (S n) x -> An n x)
559 -> forall n : nat,
560 MeasureSet (IntegrableSetIntersectIterate An AnInt n)
561 == MeasureSet (AnInt n).
562 Proof.
563 intros IS An AnInt H.
564 (* The characteristic function of the decreasing intersection is
565 equal to the last characteristic function. *)
566 assert (forall (n : nat) (x : X (ElemFunc IS))
567 (xIntersect : Domain (@CharacFunc (RealT (ElemFunc IS)) _ (IntersectIterate An n)) x)
568 (xLast : Domain (CharacFunc (An n)) x),
569 partialApply _ _ xIntersect = partialApply _ _ xLast).
570 { induction n.
571 - intros. simpl. destruct xIntersect, xLast.
572 reflexivity. contradiction. contradiction. reflexivity.
573 - intros. specialize (H n).
574 (* Extract point in dAn *)
575 destruct n.
576 + clear IHn. simpl. destruct xIntersect, xLast.
577 reflexivity. destruct i. contradiction.
578 2: reflexivity. exfalso. apply n. split.
579 apply H, a. exact a.
580 + simpl. simpl in IHn, xIntersect.
581 destruct xIntersect. destruct a.
582 destruct xLast. reflexivity. contradiction.
583 destruct xLast. 2: reflexivity.
584 assert (~ (IntersectIterate An n x /\ An (S n) x)).
585 intro abs. apply n0. split; assumption.
586 specialize (H x a).
587 specialize (IHn x (right H0) (left H)). exact IHn. }
588 intros. apply IntegralExtensional. intros.
589 rewrite (H0 _ _ _ xdg). reflexivity.
590 Qed.
591
592 Definition IntegrableSetDifference
593 {IS : IntegrationSpace}
594 (A B : X (ElemFunc IS) -> Prop)
595 (aInt : IntegrableSet A)
596 (bInt : IntegrableSet B)
597 : IntegrableSet (fun x => A x /\ ~B x).
598 Proof.
599 apply (IntegrableFunctionExtensional
600 (Xminus (CharacFunc A) (CharacFunc (fun x => A x /\ B x)))).
601 - split.
602 + intros x xdf. destruct xdf. simpl.
603 destruct d, d0. right. intro abs. destruct a0, abs; contradiction.
604 left. split. exact a. intro abs. apply n. split; assumption.
605 destruct a; contradiction.
606 right. intro abs. destruct abs; contradiction.
607 + intros. destruct xD.
608 rewrite (applyXminus (CharacFunc A) (CharacFunc (fun x0 : X (ElemFunc IS) => A x0 /\ B x0))).
609 destruct xG; simpl. destruct d0.
610 destruct d. 2: destruct a0; contradiction.
611 destruct a0, a; contradiction. destruct d. unfold CRminus.
612 rewrite CRopp_0, CRplus_0_r. reflexivity.
613 destruct a; contradiction. destruct d0.
614 destruct d. unfold CRminus. rewrite CRplus_opp_r. reflexivity.
615 destruct a; contradiction.
616 destruct d. exfalso. apply n. split.
617 exact a. intro abs. apply n0. split; assumption.
618 unfold CRminus. rewrite CRplus_opp_r. reflexivity.
619 - apply (IntegrableMinus aInt (IntegrableSetIntersect A B aInt bInt)).
620 Defined.
621
622 Lemma MeasureDifference
623 : forall {IS : IntegrationSpace}
624 (A B : X (ElemFunc IS) -> Prop)
625 (aInt : IntegrableSet A)
626 (bInt : IntegrableSet B),
627 MeasureSet (IntegrableSetDifference A B aInt bInt)
628 == MeasureSet aInt
629 - MeasureSet (IntegrableSetIntersect A B aInt bInt).
630 Proof.
631 intros. unfold MeasureSet.
632 rewrite <- IntegralMinus. apply IntegralExtensional. intros.
633 destruct xdg.
634 rewrite (applyXminus (CharacFunc A) (CharacFunc (fun x0 : X (ElemFunc IS) => A x0 /\ B x0))).
635 destruct xdf; simpl. destruct d0.
636 destruct d. destruct a,a0; contradiction. destruct a0; contradiction.
637 destruct d. unfold CRminus. rewrite CRopp_0, CRplus_0_r.
638 reflexivity. destruct a; contradiction.
639 destruct d0. destruct d. unfold CRminus. rewrite CRplus_opp_r.
640 reflexivity. destruct a; contradiction.
641 destruct d. 2: unfold CRminus; rewrite CRplus_opp_r; reflexivity.
642 exfalso. apply n. split. exact a.
643 intro abs. apply n0. split; assumption.
644 Qed.
645
646 Lemma MeasureDifferenceIncluded
647 : forall {IS : IntegrationSpace}
648 (A B : X (ElemFunc IS) -> Prop)
649 (aInt : IntegrableSet A)
650 (bInt : IntegrableSet B),
651 (forall x:X (ElemFunc IS), B x -> A x)
652 -> MeasureSet (IntegrableSetDifference A B aInt bInt)
653 == MeasureSet aInt - MeasureSet bInt.
654 Proof.
655 intros. rewrite MeasureDifference. apply CRplus_morph. reflexivity.
656 apply CRopp_morph. apply IntegralExtensional. intros. simpl.
657 destruct xdf, xdg. reflexivity. 3: reflexivity.
658 destruct a. contradiction. exfalso. apply n. split.
659 apply H, b. exact b.
660 Qed.
661
662 Lemma MeasureDifferenceInvolutive
663 : forall {IS : IntegrationSpace}
664 (A B : X (ElemFunc IS) -> Prop)
665 (aInt : IntegrableSet A)
666 (bInt : IntegrableSet B),
667 MeasureSet (IntegrableSetDifference
668 A _ aInt (IntegrableSetDifference A B aInt bInt))
669 == MeasureSet (IntegrableSetIntersect A B aInt bInt).
670 Proof.
671 intros. apply IntegralExtensional. intros.
672 destruct xdf,xdg; simpl.
673 reflexivity. exfalso. destruct a. apply H0.
674 split. exact H. intro abs. apply n. split; assumption.
675 exfalso. apply n. split. apply a. intro abs.
676 destruct a, abs; contradiction. reflexivity.
677 Qed.
678
679 Lemma CharacFuncStationary
680 : forall {R : ConstructiveReals} (X : Set) (An : nat -> X -> Prop) (x : X)
681 (xn : forall n:nat, Domain (CharacFunc (An n)) x),
682 CR_cauchy R (fun n => partialApply (CharacFunc (An n)) x (xn n))
683 -> { p : nat | forall n:nat, le p n ->
684 partialApply (CharacFunc (An p)) x (xn p)
685 = partialApply (CharacFunc (An n)) x (xn n) }.
686 Proof.
687 intros. destruct (H 2%positive) as [p pcv]. auto. exists p.
688 intros. simpl. simpl in pcv.
689 specialize (pcv p n (Nat.le_refl _) H0).
690 assert (CR_of_Q R (1 # 2) < 1).
691 { apply CR_of_Q_lt. reflexivity. }
692 destruct (xn p), (xn n). reflexivity. 3: reflexivity.
693 - exfalso. unfold CRminus in pcv.
694 rewrite CRopp_0, CRplus_0_r, CRabs_right in pcv.
695 contradiction. apply CRlt_asym, CRzero_lt_one.
696 - exfalso. unfold CRminus in pcv.
697 rewrite CRplus_0_l, CRabs_opp, CRabs_right in pcv.
698 contradiction. apply CRlt_asym, CRzero_lt_one.
699 Qed.
700
701 Definition IntegrableSetCountableUnion
702 {IS : IntegrationSpace}
703 (An : nat -> X (ElemFunc IS) -> Prop)
704 (AnInt : forall n:nat, IntegrableSet (An n))
705 (a : CRcarrier (RealT (ElemFunc IS)))
706 : CR_cv _ (fun n => MeasureSet (IntegrableSetUnionIterate An AnInt n)) a
707 -> { intUnion : IntegrableSet (fun x => exists n:nat, An n x)
708 | MeasureSet intUnion == a }.
709 Proof.
710 intros.
711 destruct (IntegralMonotoneConvergence
712 IS _ (IntegrableSetUnionIterate An AnInt) a)
713 as [[i restr] cv].
714 - intros n x xdf xdg. simpl. clear H.
715 destruct xdf, xdg. apply CRle_refl. exfalso.
716 apply n0. left. exact u.
717 apply CRlt_asym, CRzero_lt_one. apply CRle_refl.
718 - apply H.
719 - assert (PartialRestriction (XinfiniteSumAbs (IntFn i))
720 (CharacFunc (fun x => exists n:nat, An n x))) as H0.
721 apply (PartialRestriction_trans (X (ElemFunc IS))
722 _ (XpointwiseLimit (fun n : nat => CharacFunc (UnionIterate An n)))).
723 split. apply restr. apply restr. clear i restr cv. split.
724 + intros x xdf. simpl.
725 destruct xdf as [xn xncv].
726 apply CharacFuncStationary in xncv. destruct xncv as [p pcv].
727 simpl in pcv.
728 destruct (xn p). left. apply applyUnionIterate in u.
729 destruct u. exists x0. apply H0. right.
730 intros [k abs]. destruct (le_lt_dec p k).
731 specialize (pcv k l). destruct (xn k).
732 pose proof CRzero_lt_one. specialize (X (RealT (ElemFunc IS))).
733 rewrite pcv in X. exact (CRlt_asym _ _ X X).
734 destruct k. contradiction. simpl in n0. apply n0.
735 right. exact abs. apply n. apply applyUnionIterate.
736 exists k. split. unfold lt in l. apply (Nat.le_trans _ (S k)).
737 apply le_S, Nat.le_refl. exact l. exact abs.
738 + intros. apply applyPointwiseLimit. simpl.
739 destruct xD as [xn xcv]. destruct xG.
740 simpl in xn.
741 destruct (constructive_indefinite_ground_description_nat
742 (fun n => (if xn n then 1 else 0) == CR_of_Q (RealT (ElemFunc IS)) 1))
743 as [n ncv].
744 intro n. destruct (xn n). left. reflexivity. right.
745 intros [abs _]. apply abs, CRzero_lt_one.
746 destruct e as [n ncv]. exists n.
747 destruct (xn n). reflexivity. exfalso.
748 destruct n. contradiction. apply n0. right. exact ncv.
749 exists n. intros. destruct (xn i).
750 unfold CRminus. rewrite CRplus_opp_r, CRabs_right.
751 2: apply CRle_refl.
752 apply CR_of_Q_le; discriminate.
753 exfalso. apply n0. apply applyUnionIterate. exists n.
754 split. exact H0. destruct (xn n).
755 exfalso. apply n0. apply applyUnionIterate in u.
756 destruct u. apply applyUnionIterate. exists x0. split.
757 apply (Nat.le_trans _ n). apply H1. exact H0. apply H1.
758 exfalso. destruct ncv. apply H1, CRzero_lt_one.
759 exists O. intros n0 _. destruct (xn n0). exfalso.
760 apply n. apply applyUnionIterate in u. destruct u. exists x0. apply H0.
761 unfold CRminus. rewrite CRplus_opp_r, CRabs_right.
762 apply CR_of_Q_le; discriminate. apply CRle_refl.
763 + exists (existT _ i H0). exact cv.
764 Defined.
765
766 Definition IntegrableSetCountableIntersect
767 {IS : IntegrationSpace}
768 (An : nat -> X (ElemFunc IS) -> Prop)
769 (AnInt : forall n:nat, IntegrableSet (An n))
770 (a : CRcarrier (RealT (ElemFunc IS)))
771 : CR_cv _ (fun n => MeasureSet (IntegrableSetIntersectIterate An AnInt n)) a
772 -> { intIntersect : IntegrableSet (fun x => forall n:nat, An n x)
773 | MeasureSet intIntersect == a }.
774 Proof.
775 intros.
776 destruct (IntegralMonotoneConvergenceDecr
777 IS _ (IntegrableSetIntersectIterate An AnInt) a)
778 as [[i restr] cv].
779 - intros n x xdf xdg. simpl. clear H.
780 destruct xdf, xdg. apply CRle_refl. exfalso.
781 apply n0. apply i.
782 apply CRlt_asym, CRzero_lt_one. apply CRle_refl.
783 - apply H.
784 - assert (PartialRestriction (XinfiniteSumAbs (IntFn i))
785 (CharacFunc (fun x => forall n:nat, An n x))) as H0.
786 apply (PartialRestriction_trans (X (ElemFunc IS))
787 _ (XpointwiseLimit (fun n : nat => CharacFunc (IntersectIterate An n)))).
788 split. apply restr. apply restr. clear i restr cv. split.
789 + intros x xdf. simpl.
790 destruct xdf as [xn xncv].
791 apply CharacFuncStationary in xncv. destruct xncv as [p pcv].
792 simpl in pcv.
793 destruct (xn p). left. intros.
794 destruct (le_lt_dec p n). specialize (pcv n l).
795 destruct (xn n). rewrite applyIntersectIterate in i0. apply i0, Nat.le_refl.
796 exfalso. symmetry in pcv. pose proof CRzero_lt_one.
797 specialize (X (RealT (ElemFunc IS))) as H0.
798 rewrite pcv in H0. exact (CRlt_asym _ _ H0 H0).
799 rewrite applyIntersectIterate in i. apply i.
800 apply (Nat.le_trans _ (S n)).
801 apply le_S, Nat.le_refl. exact l.
802 right. intro abs. apply n. rewrite applyIntersectIterate. intros.
803 apply abs.
804 + intros. apply applyPointwiseLimit. simpl.
805 destruct xD as [xn xcv].
806 destruct xG. exists O. intros n H0.
807 destruct (xn n).
808 unfold CRminus. rewrite CRplus_opp_r, CRabs_right.
809 apply CR_of_Q_le; discriminate. apply CRle_refl.
810 exfalso. apply n0. rewrite applyIntersectIterate. intros. apply a0.
811
812 apply CharacFuncStationary in xcv. destruct xcv as [p pcv].
813 exists p. intros. simpl in pcv. destruct (xn p).
814 exfalso. (* if in all An above p and intersect p, means all n *)
815 apply n. intros n1.
816 destruct (le_lt_dec p n1). specialize (pcv n1 l).
817 destruct (xn n1). rewrite applyIntersectIterate in i1. apply i1, Nat.le_refl.
818 exfalso. symmetry in pcv. pose proof CRzero_lt_one.
819 specialize (X (RealT (ElemFunc IS))).
820 rewrite pcv in X. exact (CRlt_asym _ _ X X).
821 rewrite applyIntersectIterate in i0. apply i0.
822 apply (Nat.le_trans _ (S n1)). apply le_S, Nat.le_refl. exact l.
823 (* So it is not in the intersection at p *)
824 specialize (pcv i H0). destruct (xn i).
825 exfalso. pose proof CRzero_lt_one.
826 specialize (X (RealT (ElemFunc IS))).
827 rewrite pcv in X. exact (CRlt_asym _ _ X X).
828 unfold CRminus. rewrite CRplus_opp_r, CRabs_right.
829 apply CR_of_Q_le; discriminate. apply CRle_refl.
830 + exists (existT _ i H0). exact cv.
831 Defined.
832
833 Lemma MeasureIntersectIncr
834 : forall {IS : IntegrationSpace}
835 (A B : X (ElemFunc IS) -> Prop)
836 (aInt : IntegrableSet A)
837 (bInt : IntegrableSet B),
838 MeasureSet (IntegrableSetIntersect A B aInt bInt) <= MeasureSet bInt.
839 Proof.
840 intros. apply MeasureNonDecreasing. intros. apply H.
841 Qed.
842
843
844 (* Integrable sets can serve as partial integration domains.
845 Actually those domains can be enlarged to the measure sets,
846 defined in a later file. This is proposition 4.2 of Bishop. *)
847
848 Lemma growing_infinite : forall un : nat -> nat,
849 (forall n:nat, lt (un n) (un (S n)))
850 -> forall n : nat, le n (un n).
851 Proof.
852 induction n.
853 - apply Nat.le_0_l.
854 - specialize (H n). unfold lt in H.
855 apply (Nat.le_trans _ (S (un n))). apply le_n_S, IHn. exact H.
856 Qed.
857
858 Lemma SliceBar
859 : forall {R : ConstructiveReals} {X : Set}
860 (x : CRcarrier R)
861 (nk : nat -> nat),
862 (forall n:nat, lt (nk n) (nk (S n)))
863 -> nk O = O
864 -> 0 <= x
865 -> series_cv
866 (fun n : nat =>
867 CRmin (INR (nk (S n) - nk n))
868 (x - CRmin x (INR (nk n)))) x.
869 Proof.
870 intros.
871 assert (forall k:nat, CRsum (fun n : nat =>
872 CRmin (INR (nk (S n) - nk n))
873 (x - CRmin x (INR (nk n)))) k
874 == CRmin x (INR (nk (S k)))).
875 { induction k.
876 - intros. simpl.
877 rewrite (CRmin_right x (INR (nk 0%nat))).
878 rewrite H0. rewrite CRmin_sym.
879 rewrite Nat.sub_0_r.
880 setoid_replace (x - INR 0) with x. reflexivity.
881 unfold INR. simpl. unfold CRminus.
882 rewrite CRopp_0, CRplus_0_r.
883 reflexivity. rewrite H0. unfold INR. apply H1.
884 - intros. simpl. rewrite IHk. clear IHk.
885 rewrite CRmin_plus.
886 setoid_replace (CRmin x (INR (nk (S k))) + (x - CRmin x (INR (nk (S k)))))
887 with x.
888 rewrite CRmin_sym, CRplus_comm, CRmin_plus.
889 setoid_replace (@INR R (nk (S (S k)) - nk (S k)) + INR (nk (S k)))
890 with (@INR R (nk (S (S k)))).
891 rewrite CRmin_assoc.
892 rewrite (CRmin_left x). reflexivity.
893 apply (CRle_trans _ (0+x)). rewrite CRplus_0_l.
894 apply CRle_refl. apply CRplus_le_compat.
895 apply CR_of_Q_le. unfold Qle; simpl. rewrite Z.mul_1_r.
896 apply Nat2Z.is_nonneg. apply CRle_refl.
897 unfold INR. rewrite <- CR_of_Q_plus. apply CR_of_Q_morph.
898 rewrite Qinv_plus_distr. rewrite <- Nat2Z.inj_add.
899 rewrite Nat.sub_add. reflexivity. specialize (H (S k)).
900 apply (Nat.le_trans _ (S (nk (S k)))). apply le_S, Nat.le_refl.
901 apply H. rewrite CRplus_comm. unfold CRminus.
902 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r.
903 reflexivity. }
904 destruct (CRup_nat x) as [n nmaj]. exists n.
905 intros. rewrite H2. rewrite CRmin_left.
906 unfold CRminus. rewrite CRplus_opp_r, CRabs_right.
907 apply CR_of_Q_le. discriminate. apply CRle_refl.
908 apply (CRle_trans _ (INR n)). apply CRlt_asym, nmaj.
909 apply CR_of_Q_le. unfold Qle; simpl.
910 do 2 rewrite Z.mul_1_r. apply Nat2Z.inj_le.
911 apply (Nat.le_trans _ _ _ H3). apply (Nat.le_trans _ (S i)).
912 apply le_S, Nat.le_refl. apply growing_infinite. exact H.
913 Qed.
914
915 Lemma SliceNonNegFunc
916 : forall {R : ConstructiveReals} {X : Set}
917 (f : @PartialFunction R X)
918 (A : X -> Prop)
919 (nk : nat -> nat),
920 (forall n:nat, lt (nk n) (nk (S n)))
921 -> nk O = O
922 -> nonNegFunc f
923 -> PartialRestriction
924 (XinfiniteSumAbs (fun k : nat =>
925 Xmin (Xscale (INR (nk (S k) - nk k)) (CharacFunc A))
926 (Xminus f (XminConst f (INR (nk k))))))
927 (Xmult (CharacFunc A) f).
928 Proof.
929 split.
930 - intros x [xn _]. specialize (xn O).
931 destruct f, xn, d0, d0; split. exact d0. apply d.
932 - intros. apply applyInfiniteSumAbs.
933 assert (forall n:nat, Domain (Xscale (INR (nk (S n) - nk n)) (@CharacFunc R _ A)) x)
934 as H2.
935 { intro n. apply (domainInfiniteSumAbsIncReverse _ _ xD n). }
936 assert (forall n:nat, Domain (Xminus f (XminConst f (INR (nk n)))) x) as H3.
937 { intro n. apply (domainInfiniteSumAbsIncReverse _ _ xD n). }
938 destruct xG. destruct d as [inA | notInA].
939 + (* Inside of A, prove convergence towards f x *)
940 assert (Domain f x) as H4.
941 { specialize (H3 O). apply H3. }
942 apply (series_cv_eq (fun n : nat =>
943 CRmin (INR (nk (S n) - nk n))
944 (partialApply f x H4
945 - CRmin (partialApply f x H4) (INR (nk n))))).
946 intro n. rewrite (applyXmin _ _ x (H2 n) (H3 n)).
947 apply CRmin_morph. rewrite applyXscale.
948 rewrite (DomainProp (CharacFunc A) x _ (left inA)).
949 unfold CharacFunc, partialApply. rewrite CRmult_1_r. reflexivity.
950 destruct (H3 n).
951 rewrite (applyXminus f (XminConst f (INR (nk n)))). apply CRplus_morph.
952 apply DomainProp. apply CRopp_morph. rewrite applyXminConst.
953 apply CRmin_morph. apply DomainProp. reflexivity.
954 setoid_replace (partialApply (Xmult (CharacFunc A) f) x (left inA, d0))
955 with (partialApply f x H4).
956 apply (@SliceBar R X). exact H. exact H0. apply H1.
957 destruct f; simpl. rewrite CRmult_1_l.
958 apply DomainProp.
959 + (* Outside of A we have 0 == 0 *)
960 apply (series_cv_eq (fun _ => 0)).
961 intro n. rewrite (applyXmin _ _ x (H2 n) (H3 n)), CRmin_left.
962 rewrite applyXscale.
963 rewrite (DomainProp (CharacFunc A) x _ (right notInA)).
964 unfold CharacFunc, partialApply. rewrite CRmult_0_r. reflexivity.
965 rewrite applyXscale.
966 rewrite (DomainProp (CharacFunc A) x _ (right notInA)).
967 apply (CRle_trans _ 0).
968 unfold CharacFunc, partialApply. rewrite CRmult_0_r.
969 apply CRle_refl. destruct (H3 n).
970 rewrite (applyXminus f (XminConst f (INR (nk n)))).
971 apply CRle_minus.
972 rewrite applyXminConst. rewrite (DomainProp f x d1 d).
973 apply CRmin_l.
974 setoid_replace (partialApply (Xmult (CharacFunc A) f) x (right notInA, d0))
975 with (CR_of_Q R 0).
976 intro p. exists O. intros. rewrite sum_const, CRmult_0_l.
977 unfold CRminus. rewrite CRplus_opp_r, CRabs_right.
978 apply CR_of_Q_le. discriminate. apply CRle_refl.
979 clear xD. destruct f; simpl. apply CRmult_0_l.
980 Qed.
981
982 (* Add zero before sequence un, if it does not already start with zero. *)
983 Definition StartZero (un : nat -> nat) (n : nat)
984 := match n with
985 | O => O
986 | S p => match un O with | O => un (S p) | S _ => un p end
987 end.
988
989 Lemma StartZeroInc : forall (un : nat -> nat),
990 (forall n:nat, lt (un n) (un (S n)))
991 -> (forall n:nat, lt (StartZero un n) (StartZero un (S n))).
992 Proof.
993 intros. destruct n.
994 - simpl. destruct (un O) eqn:des.
995 apply (Nat.le_lt_trans _ (un O)). apply Nat.le_0_l. apply H.
996 apply le_n_S, Nat.le_0_l.
997 - simpl. destruct (un O); apply H.
998 Qed.
999
1000 Definition RestrictedIntegralNonneg
1001 {IS : IntegrationSpace}
1002 (f : PartialFunction (X (ElemFunc IS)))
1003 (A : (X (ElemFunc IS)) -> Prop)
1004 : IntegrableFunction f
1005 -> nonNegFunc f
1006 -> IntegrableSet A
1007 -> IntegrableFunction (Xmult (CharacFunc A) f).
1008 Proof.
1009 intros fInt fNonNeg AInt.
1010 assert (forall k : nat, 0 < CRpow (CR_of_Q (RealT (ElemFunc IS)) (1 # 2)) k) as boundPos.
1011 { intro k. apply CRpow_gt_zero. simpl.
1012 apply CR_of_Q_lt. reflexivity. }
1013 pose (StartZero (fun n => let (p,_) := ControlSubSeqCv _ _ (CRpow (CR_of_Q _ (1#2)))
1014 (IntegralTruncateLimit f fInt) boundPos n in p)) as nk.
1015 (* Cut f's non-negative graph horizontally, according to the nk *)
1016 pose (fun k:nat => Xmin (Xscale (INR (nk (S k) - nk k)) (CharacFunc A))
1017 (Xminus f (XminConst f (INR (nk k))))) as fk.
1018 pose (fun k:nat => IntegrableMinus fInt (IntegrableMinInt _ (nk k) fInt))
1019 as fTopkInt.
1020 assert (forall k, IntegrableFunction (fk k)) as fkInt.
1021 { intro k. apply IntegrableMin. apply IntegrableScale, AInt.
1022 apply fTopkInt. }
1023 (* Majorate the series by the right-hand term of the minimum,
1024 which is itself lower than 2^k, a convergent series. *)
1025 destruct (series_cv_maj
1026 (fun n => Integral (IntegrableAbs (fkInt (S O + n)%nat)))
1027 (CRpow (CR_of_Q _ (1#2))) (CR_of_Q _ 2)) as [l llim].
1028 2: exact GeoHalfTwo.
1029 - intro n.
1030 rewrite CRabs_right.
1031 apply (CRle_trans _ (Integral (fTopkInt (S n)))).
1032 apply IntegralNonDecreasing. intros x xdf xdg.
1033 rewrite applyXabs.
1034 assert (Domain (Xscale (INR (nk (S (S n)) - nk (S n))) (@CharacFunc (RealT (ElemFunc IS)) _ A)) x)
1035 as H.
1036 { destruct xdf. apply d0. }
1037 rewrite CRabs_right. unfold fk.
1038 rewrite (applyXmin _ _ x H xdg). apply CRmin_r.
1039 unfold fk.
1040 rewrite (applyXmin _ _ x H xdg). apply CRmin_glb.
1041 rewrite applyXscale. rewrite <- (CRmult_0_r (INR (nk (S (S n)) - nk (S n)))).
1042 apply CRmult_le_compat_l. apply CR_of_Q_le.
1043 unfold Qle, Qnum, Qden. do 2 rewrite Z.mul_1_r. apply Nat2Z.is_nonneg.
1044 simpl. destruct H. apply CRlt_asym, CRzero_lt_one. apply CRle_refl.
1045 destruct xdg.
1046 rewrite (applyXminus f (XminConst f (INR (nk (S n))))).
1047 apply CRle_minus. rewrite applyXminConst.
1048 rewrite (DomainProp f x d0 d).
1049 apply CRmin_l. unfold fTopkInt. rewrite IntegralMinus.
1050 unfold nk, StartZero.
1051 destruct (ControlSubSeqCv
1052 (fun n0 : nat => Integral (IntegrableMinInt f n0 fInt))
1053 (Integral fInt) (CRpow (CR_of_Q _ (1 # 2)))
1054 (IntegralTruncateLimit f fInt) boundPos 0), x.
1055 destruct (ControlSubSeqCv
1056 (fun n0 : nat => Integral (IntegrableMinInt f n0 fInt))
1057 (Integral fInt) (CRpow (CR_of_Q _ (1 # 2)))
1058 (IntegralTruncateLimit f fInt) boundPos (S n)).
1059 rewrite CRabs_minus_sym in c0.
1060 apply (CRle_trans _ _ _ (CRle_abs _)).
1061 apply (CRle_trans _ (CRpow (CR_of_Q _ (1 # 2)) (S n))).
1062 apply CRlt_asym, c0.
1063 apply (CRmult_le_reg_l (CRpow (CR_of_Q _ 2) (S n))).
1064 apply CRpow_gt_zero. apply CR_of_Q_lt. reflexivity.
1065 rewrite CRpow_mult. rewrite (CRpow_proper _ 1), CRpow_one.
1066 replace (CRpow (CR_of_Q _ 2) (S n))
1067 with (CR_of_Q (RealT (ElemFunc IS)) 2 * CRpow (CR_of_Q _ 2) n). 2: reflexivity.
1068 rewrite CRmult_assoc, CRpow_mult.
1069 rewrite (CRpow_proper _ 1), CRpow_one. rewrite CRmult_1_r.
1070 apply CR_of_Q_le. discriminate. rewrite <- CR_of_Q_mult.
1071 setoid_replace (2 * (1 # 2))%Q with 1%Q. reflexivity. reflexivity.
1072 rewrite <- CR_of_Q_mult.
1073 setoid_replace (2 * (1 # 2))%Q with 1%Q. reflexivity. reflexivity.
1074 destruct (ControlSubSeqCv
1075 (fun n0 : nat => Integral (IntegrableMinInt f n0 fInt))
1076 (Integral fInt) (CRpow (CR_of_Q _ (1 # 2)))
1077 (IntegralTruncateLimit f fInt) boundPos n).
1078 rewrite CRabs_minus_sym in c0.
1079 apply (CRle_trans _ _ _ (CRle_abs _)).
1080 apply CRlt_asym, c0.
1081 apply IntegralNonNeg. intros x xdf. rewrite applyXabs.
1082 apply CRabs_pos.
1083 - destruct (IntegrableFunctionsComplete
1084 IS fk fkInt (l+Integral (IntegrableAbs (fkInt O)))).
1085 destruct llim.
1086 apply (series_cv_shift (fun n : nat =>
1087 Integral (IntegrableAbs (fkInt n))) O) in s.
1088 exact s. exists x.
1089 apply (PartialRestriction_trans _ _ (XinfiniteSumAbs fk)).
1090 apply p. clear p x llim l.
1091 apply (SliceNonNegFunc f A nk). apply StartZeroInc.
1092 apply ControlSubSeqCvInc. reflexivity. exact fNonNeg.
1093 Qed.
1094
1095 Definition RestrictedIntegrable
1096 {IS : IntegrationSpace}
1097 {f : PartialFunction (X (ElemFunc IS))}
1098 {A : (X (ElemFunc IS)) -> Prop}
1099 : IntegrableFunction f
1100 -> IntegrableSet A
1101 -> IntegrableFunction (Xmult (CharacFunc A) f).
1102 Proof.
1103 intros.
1104 apply (IntegrableFunctionExtensional
1105 (Xminus (Xmult (CharacFunc A) (XposPart f))
1106 (Xmult (CharacFunc A) (XnegPart f)))).
1107 split.
1108 - intros x xdf. destruct f; split; apply xdf.
1109 - intros. destruct xG, xD.
1110 rewrite (applyXmult (CharacFunc A) f).
1111 rewrite (applyXminus (Xmult (CharacFunc A) (XposPart f))
1112 (Xmult (CharacFunc A) (XnegPart f))).
1113 unfold CRminus.
1114 destruct d1, d2.
1115 rewrite (applyXmult (CharacFunc A) (XposPart f)).
1116 rewrite (applyXmult (CharacFunc A) (XnegPart f)).
1117 rewrite (DomainProp _ x d2 d1), (DomainProp _ x d4 d3).
1118 rewrite CRopp_mult_distr_r, <- CRmult_plus_distr_l.
1119 apply CRmult_morph. apply DomainProp. apply SplitPosNegParts.
1120 - apply IntegrableMinus.
1121 apply RestrictedIntegralNonneg. apply IntegrablePosPart, X.
1122 apply applyXposPartNonNeg. exact X0.
1123 apply RestrictedIntegralNonneg. apply IntegrableNegPart, X.
1124 apply XnegPartNonNeg. exact X0.
1125 Qed.
1126
1127 Definition RestrictedIntegral
1128 {IS : IntegrationSpace}
1129 {f : PartialFunction (X (ElemFunc IS))}
1130 {A : (X (ElemFunc IS)) -> Prop}
1131 (fInt : IntegrableFunction f)
1132 (aInt : IntegrableSet A)
1133 := Integral (RestrictedIntegrable fInt aInt).
1134
1135
1136
1137 (* A variant for the countable union, that allows redundancies in the sum. *)
1138 Definition IntegrableSetCountableUnionLe
1139 {IS : IntegrationSpace}
1140 (An : nat -> X (ElemFunc IS) -> Prop)
1141 (AnInt : forall n:nat, IntegrableSet (An n))
1142 (a : CRcarrier (RealT (ElemFunc IS)))
1143 : series_cv (fun n => MeasureSet (AnInt n)) a
1144 -> { intUnion : IntegrableSet (fun x => exists n:nat, An n x)
1145 | MeasureSet intUnion <= a }.
1146 Proof.
1147 intros.
1148 pose (fun n:nat => match n with
1149 | O => MeasureSet (AnInt O)
1150 | S p => MeasureSet (IntegrableSetUnionIterate An AnInt n)
1151 - MeasureSet (IntegrableSetUnionIterate An AnInt p)
1152 end)
1153 as incrMes.
1154 destruct (series_cv_maj incrMes (fun n => MeasureSet (AnInt n)) a) as [l [lcv lle]].
1155 2: exact H.
1156 - intro n. unfold incrMes. destruct n.
1157 + rewrite CRabs_right. apply CRle_refl. apply MeasureNonNeg.
1158 + rewrite <- MeasureDifferenceIncluded. rewrite CRabs_right.
1159 2: apply MeasureNonNeg. apply IntegralNonDecreasing.
1160 intros x xdf xdg. simpl. destruct xdf, xdg. apply CRle_refl.
1161 3: apply CRle_refl. 2: apply CRlt_asym, CRzero_lt_one. exfalso.
1162 destruct a0. destruct H0; contradiction.
1163 intros. left. exact H0.
1164 - destruct (IntegrableSetCountableUnion An AnInt l).
1165 + apply (CR_cv_eq _ (CRsum incrMes)). 2: exact lcv.
1166 induction n. reflexivity. simpl. rewrite IHn. clear IHn.
1167 rewrite CRplus_comm. unfold CRminus.
1168 rewrite CRplus_assoc, CRplus_opp_l, CRplus_0_r. reflexivity.
1169 + exists x. rewrite c. exact lle.
1170 Qed.