(* Copyright © 2020 Vincent Semeria 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: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. 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. *) (* This is an implementation of Errett Bishop and Henry Cheng's article, "Constructive Measure Theory". By its many applications and concrete nature, measure theory and probability theory are expected to be constructive. Indeed they are, and this formalization shows exactly how. All measure theories (Riemann, Lebesgue, Daniell and here constructive) follow the same pattern : 1) Observe that the rectangles of Rn [a1,b1] \times ... \times [an,bn] have an obvious measure, which is the product (b1-a1)...(bn-an). 2) Define a notion of limit, to measure more complicated domains by rectangle approximations. For example this is how Archimedes computed the length of a circle 2000 years ago. Nowadays the classical measure theory is that of Lebesgue, and its limit notion is the sigma-algebra generated by the rectangles, aka the Borel sets of Rn. This classically defines a gigantic set of measurable parts, but it is not constructive, because there is no way to effectively compute which rectangles approximate an arbitrary Borel set. It is therefore not surprising that the associated tool, Caratheodory's extension theorem, extends measures from rectangles to Borel sets in a non-constructive manner: by using infimums of arbitrary bounded subsets of R. Bishop and Cheng's measure theory is the constructive expression of Daniell's measure theory. Instead of starting with rectangles as subsets of Rn, this theory considers elementary real-valued functions, for example piecewise-constant functions. Those two concepts are almost the same, because the graph of a piecewise-constant function is a finite union of rectangles. But by starting with functions, we get a very simple notion of limit between a function f and a sequence of elementary functions fn: f(x) = lim fn(x), for all x's such as the real sequence fn(x) converges. This resolves the objection above, because the approximating sequence fn of rectangles is now the very definition of an integrable function f. This restricts the theory to constructively integrable functions, which is precisely what we want. In the constructive definition, fn is not required to converge at every x. This allows to integrate more functions f, but takes the risk of badly approximating their integrals, by ignoring what f does outside of the domain of convergence of fn. To make sure that the sequence fn converges on a subset with full measure, we require that the integrals of the absolute values of fn converge. Roughly speaking, if the |fn| converged to positive infinity on a subset with positive measure, it would contradict the finite integral limit. This condition also makes the integrals of fn converge, which defines the integral of f. Another characteristic of constructive real functions is worth stressing: all total constructive functions R -> R are continuous. So a constructive function R -> R must either be undefined at a point of discontinuity x, or be defined on a topological subspace of R, such as the disconnection of x by taking [x, +\infty[ to be open. In the last 2 cases we will declare the function to be partially defined on R, see PartialFunction below. *) Require Import QArith. Require Import ConstructiveReals. Require Import ConstructiveAbs. Require Import ConstructiveMinMax. Require Import ConstructiveSum. Require Import ConstructiveLimits. Require Import ConstructivePartialFunctions. Local Open Scope ConstructiveReals. (* A Riesz space is a vector space with a lattice structure compatible with the vectorial structure. An important example for measure theory is when vectors are real-valued functions, which allows to define an integral as a linear and non-decreasing functional. *) Structure FunctionRieszSpace := { (* A superset of the domains. Typically, X will be R or R^n, and the functions will be defined almost-everywhere on X. Bishop generalizes to a setoid, to be able to consider functions on quotient spaces ; we do not do it for now, because most of the time the domain is plain R^n.*) X : Set; RealT : ConstructiveReals; (* We use Set instead of Prop, to destruct the witness in the integral function later. In the example of piecewise-linear functions, the Prop would be "there exists a finite list of angular points"; here the type is a sig with this finite list, and a proof that the function is linear between these points. *) L : @PartialFunction RealT X -> Type; (* The integration spaces are usually provably extensional, so we avoid using the functional extensionality axiom. *) Lext : forall f g : PartialFunction X, PartialFunExtEq f g -> L f -> L g; LplusStable : forall f g : PartialFunction X, L f -> L g -> L (Xplus f g); LabsStable : forall (f : PartialFunction X), L f -> L (Xabs f); LminOneStable : forall (f : PartialFunction X), L f -> L (XminConst f 1); LscaleStable : forall (a : CRcarrier RealT) (f : PartialFunction X), L f -> L (Xscale a f); }. (* LminOneStable seems redundant, because the minimum can be built from plus, minus and abs. However the constant function one is not L most of the time : its integral is infinite when the domain X is R or R^n. *) Lemma LminusStable : forall {Elem : FunctionRieszSpace} (f g : PartialFunction (X Elem)) (fL : L Elem f) (gL : L Elem g), L Elem (Xminus f g). Proof. intros. unfold Xminus. apply LplusStable. assumption. apply LscaleStable. assumption. Defined. Lemma LposPartStable : forall {Elem : FunctionRieszSpace} (f : PartialFunction (X Elem)) (fL : L Elem f), L Elem (XposPart f). Proof. intros. unfold XposPart. apply LscaleStable. apply LplusStable. assumption. apply LabsStable. assumption. Defined. Lemma LnegPartStable : forall {Elem : FunctionRieszSpace} (f : PartialFunction (X Elem)) (fL : L Elem f), L Elem (XnegPart f). Proof. intros. unfold XnegPart. apply LscaleStable. apply LminusStable. apply LabsStable. assumption. assumption. Defined. Lemma LminStable : forall {Elem : FunctionRieszSpace} (f g : PartialFunction (X Elem)) (fL : L Elem f) (gL : L Elem g), L Elem (Xmin f g). Proof. intros. apply LminusStable. assumption. apply LnegPartStable. apply LminusStable. assumption. assumption. Qed. Lemma LmaxStable : forall {Elem : FunctionRieszSpace} (f g : PartialFunction (X Elem)) (fL : L Elem f) (gL : L Elem g), L Elem (Xmax f g). Proof. intros. apply LplusStable. assumption. apply LposPartStable. apply LminusStable. assumption. assumption. Qed. Lemma LsumStable : forall {Elem : FunctionRieszSpace} (fn : nat -> PartialFunction (X Elem)) (fnL : forall n:nat, L Elem (fn n)), forall n:nat, L Elem (Xsum fn n). Proof. induction n. simpl. apply fnL. simpl. apply (LplusStable Elem). exact IHn. apply fnL. Defined. Lemma LminConstStable : forall {E : FunctionRieszSpace} (a : CRcarrier (RealT E)) (f : PartialFunction (X E)), 0 < a -> L E f -> L E (XminConst f a). Proof. intros. apply (Lext _ _ _ (XminMultPosDistribOne f a H)). apply LscaleStable. apply LminOneStable. apply LscaleStable. assumption. Defined. (* Include the zero case *) Lemma LminIntStable : forall {E : FunctionRieszSpace} (n : nat) (f : PartialFunction (X E)), L E f -> L E (XminConst f (INR n)). Proof. intros E n f H. destruct n. - apply (Lext _ (Xscale (-(1)) (XnegPart f))). 2: apply LscaleStable, LnegPartStable, H. split. split. + intros x xd. destruct f; apply xd. + intros x xd. destruct f; split; apply xd. + intros. rewrite applyXscale, applyXminConst. simpl in xD, xG. rewrite (DomainProp (XnegPart f) x _ (xG, xG)). rewrite (applyXnegPartMin f x xG), <- CRopp_mult_distr_l. rewrite CRmult_1_l, CRopp_involutive, CRmin_sym. apply CRmin_morph. reflexivity. reflexivity. - apply LminConstStable. apply CR_of_Q_lt. reflexivity. exact H. Qed. Lemma invSuccRealPositive : forall {R : ConstructiveReals} (n : nat), 0 < CR_of_Q R (1# Pos.of_nat (S n)). Proof. intros R n. apply CR_of_Q_lt. reflexivity. Qed. Definition ElemIntegralContinuous {E : FunctionRieszSpace} (I : forall f : PartialFunction (X E), (L E) f -> CRcarrier (RealT E)) : Type := forall (f : PartialFunction (X E)) (fn : nat -> PartialFunction (X E)) (fL : (L E) f) (fnL : forall n:nat, (L E) (fn n)), (forall n:nat, nonNegFunc (fn n)) -> series_cv_lim_lt (fun n => I (fn n) (fnL n)) (I f fL) -> { x : CommonPointFunSeq _ f fn & series_cv_lim_lt (fun n => partialApply (fn n) _ (cpxFn _ _ _ x n)) (partialApply f _ (cpxF _ _ _ x)) }. Record IntegrationSpace := { ElemFunc : FunctionRieszSpace; (* The integrals of the elementary functions. The argument L f is in sort Set, but lemma IExtensional below proves that I does not use it to produce different values. *) I : forall f : PartialFunction (X ElemFunc), (L ElemFunc) f -> CRcarrier (RealT ElemFunc); Iadditive : forall (f g : PartialFunction (X ElemFunc)) (fL : L ElemFunc f) (gL : L ElemFunc g), I (Xplus f g) (LplusStable ElemFunc f g fL gL) == I f fL + I g gL; Ihomogeneous : forall (a : CRcarrier (RealT ElemFunc)) (f : PartialFunction (X ElemFunc)) (fL : L ElemFunc f), I (Xscale a f) (LscaleStable ElemFunc a f fL) == a * (I f fL); Ione : PartialFunction (X ElemFunc); IoneL : L ElemFunc Ione; IoneInt : I Ione IoneL == 1; (* Now the usual majoration of integrals : (forall x, f(x) <= g(x)) -> I f <= I g. See lemma INonDecreasing below for the detailed formulation. Because x is in the intersection of the domains of f and g, it implies that L-functions are defined almost everywhere, ie the abscissas outside any of their domains don't affect integrals. Moreover we require the existential contrapositive, which is constructively stronger : I g < I f -> { x | g(x) < f(x) }. Finally we want the integral to be sigma-linear (the countable limit of Iadditive and Ihomogeneous), so we take g to be a countable sum of nonnegative functions fn. This gives an non-decreasing sequence of functions, as in the monotone convergence theorem (that we will prove later). The function f is actually optional. If the integrals of fn converge towards a limit l, we can take f = (l+1) * Ione. This means that the convergence on the integrals of fn proves that the pointwise limit of fn has a non-empty domain (which will later be proved to have full measure in X ElemFunc). *) Icontinuous : ElemIntegralContinuous I; Ilimit : forall (f : PartialFunction (X ElemFunc)) (fL : L ElemFunc f), prod (CR_cv _ (fun n => I (XminConst f (INR n)) (LminIntStable n f fL)) (I f fL)) (CR_cv _ (fun n => I (XminConst (Xabs f) (CR_of_Q _ (1# Pos.of_nat (S n)))) (LminConstStable (CR_of_Q _ (1# Pos.of_nat (S n))) (Xabs f) (invSuccRealPositive n) (LabsStable ElemFunc f fL))) 0) }. (* Shortcut for the integral of the absolute value, will be used a lot. *) Definition Iabs {IS : IntegrationSpace} (f : PartialFunction (X (ElemFunc IS))) (fL : L (ElemFunc IS) f) := I IS (Xabs f) (LabsStable _ f fL). Lemma Iminus : forall {IS : IntegrationSpace} (f g : PartialFunction (X (ElemFunc IS))) (fL : L (ElemFunc IS) f) (gL : L (ElemFunc IS) g), I IS (Xminus f g) (LminusStable f g fL gL) == I IS f fL - I IS g gL. Proof. intros. unfold Xminus. unfold LminusStable. rewrite Iadditive. apply CRplus_morph. reflexivity. rewrite Ihomogeneous. rewrite <- CRopp_mult_distr_l, CRmult_1_l. reflexivity. Qed. Lemma IadditiveIterate : forall {IS : IntegrationSpace} (fn : nat -> PartialFunction (X (ElemFunc IS))) (fnL : forall n:nat, L (ElemFunc IS) (fn n)) (N : nat), I IS (Xsum fn N) (LsumStable fn fnL N) == CRsum (fun n : nat => I IS (fn n) (fnL n)) N. Proof. induction N. - reflexivity. - simpl. rewrite Iadditive. rewrite IHN. reflexivity. Qed. Definition Izero (IS : IntegrationSpace) := Xscale 0 (Ione IS). Lemma Izero_is_L : forall (IS : IntegrationSpace), L (ElemFunc IS) (Izero IS). Proof. intros IS. unfold Izero. apply LscaleStable. apply IoneL. Defined. Lemma Izero_nonNeg : forall (IS : IntegrationSpace), nonNegFunc (Izero IS). Proof. intros IS x xdf. unfold Izero. rewrite applyXscale, CRmult_0_l. apply CRle_refl. Qed. Lemma Izero_is_zero : forall (IS : IntegrationSpace), I IS (Izero IS) (Izero_is_L IS) == 0. Proof. intros. unfold Izero. unfold Izero_is_L. rewrite Ihomogeneous. rewrite CRmult_0_l. reflexivity. Qed. Lemma applyIzero : forall (IS : IntegrationSpace) (x : X (ElemFunc IS)) (xD : Domain (Izero IS) x), partialApply (Izero IS) x xD == 0. Proof. intros. unfold Izero. rewrite applyXscale, CRmult_0_l. reflexivity. Qed. (* This usual property of integrals also proves that the domains of L-functions are full sets. The majoration f <= g is defined on the intersection of the domains of f and g, and it is enough to imply that I f <= I g. It proves that the difference between the domains of g and f is a null set : g can have arbitrary large negative values on it without breaking the integral majoration. *) Lemma INonDecreasing : forall {IS : IntegrationSpace} (f g : PartialFunction (X (ElemFunc IS))) (fL : L (ElemFunc IS) f) (gL : L (ElemFunc IS) g), (forall (x : X (ElemFunc IS)) (xF : Domain f x) (y : Domain g x), partialApply f x xF <= partialApply g x y) -> I IS f fL <= I IS g gL. Proof. intros. intro abs. destruct (Icontinuous IS (Xminus f g) (fun n:nat => Izero IS) (LminusStable f g fL gL) (fun n:nat => Izero_is_L IS) (fun n:nat => Izero_nonNeg IS)) as [[x xdminus xdfn] [l [H1 H0]]]. - exists 0. split. + intros n. exists O. intros. rewrite CRabs_right. rewrite sum_eq_R0. unfold CRminus. rewrite CRplus_opp_r. apply CR_of_Q_le. discriminate. intro k. apply Izero_is_zero. unfold CRminus. rewrite CRopp_0, CRplus_0_r. rewrite sum_eq_R0. apply CRle_refl. intro k. apply Izero_is_zero. + unfold Xminus. unfold LminusStable. rewrite Iadditive. rewrite Ihomogeneous. rewrite <- (CRopp_mult_distr_l 1). rewrite CRmult_1_l. rewrite <- (CRplus_opp_r (I IS g gL)). apply CRplus_lt_compat_r. exact abs. - unfold cpxF in H0. destruct xdminus. rewrite (applyXminus f g) in H0. simpl in H0. assert (series_cv (fun n : nat => partialApply (Izero IS) x (xdfn n)) 0). { apply (CR_cv_eq _ (fun n => 0)). 2: apply CR_cv_const. intro n. rewrite sum_eq_R0. reflexivity. intro k. apply applyIzero. } assert (l == 0). { apply (series_cv_unique (fun n : nat => partialApply (Izero IS) x (xdfn n))). apply H1. apply H2. } rewrite H3 in H0. clear H1 H2 H3 l. rewrite <- (CRplus_opp_r (partialApply g x d0)) in H0. apply CRplus_lt_reg_r in H0. exact (H x _ _ H0). Qed. (* Again, the extensionality is simplified because f and g are defined almost everywhere. This lemma is rigorously a statement about the intersection of the domains of f and g. In particular, the lemma shows that I does not depend on the L arguments. *) Lemma IExtensional : forall {IS : IntegrationSpace} (f g : PartialFunction (X (ElemFunc IS))) (fL : L (ElemFunc IS) f) (gL : L (ElemFunc IS) g), (forall (x : X (ElemFunc IS)) (xF : Domain f x) (y : Domain g x), partialApply f x xF == partialApply g x y) -> I IS f fL == I IS g gL. Proof. split. + apply INonDecreasing. intros. rewrite (H x y xF). apply CRle_refl. + apply INonDecreasing. intros. rewrite (H x xF y). apply CRle_refl. Qed. (* When we have an integration space, we only need to check stabilities to create smaller spaces. *) Definition SubIntegrationSpace (IS : IntegrationSpace) (Lsub : PartialFunction (X (ElemFunc IS)) -> Set) : (forall f:PartialFunction (X (ElemFunc IS)), Lsub f -> L _ f) -> (forall f g : PartialFunction (X (ElemFunc IS)), PartialFunExtEq f g -> Lsub f -> Lsub g) -> Lsub (Ione IS) -> (forall f g : PartialFunction (X (ElemFunc IS)), (Lsub f -> Lsub g -> Lsub (Xplus f g))) -> (forall f : PartialFunction (X (ElemFunc IS)), Lsub f -> Lsub (Xabs f)) -> (forall f : PartialFunction (X (ElemFunc IS)), Lsub f -> Lsub (XminConst f 1)) -> (forall (a:CRcarrier (RealT (ElemFunc IS))) (f : PartialFunction (X (ElemFunc IS))), Lsub f -> Lsub (Xscale a f)) -> IntegrationSpace. Proof. intros. pose (Build_FunctionRieszSpace (X (ElemFunc IS)) (RealT (ElemFunc IS)) Lsub X1 X2 X3 X4 X5) as ElemSub. pose (fun f fLsub => I _ f (X0 f fLsub)) as Isub. assert (forall (f g : PartialFunction (X (ElemFunc IS))) (fL : Lsub f) (gL : Lsub g), Isub (Xplus f g) (LplusStable ElemSub f g fL gL) == Isub f fL + Isub g gL). { intros. unfold Isub. apply (CReq_trans _ (I IS (Xplus f g) (LplusStable (ElemFunc IS) f g (X0 f fL) (X0 g gL)))). 2: apply Iadditive. apply IExtensional. intros. destruct f,g,xF,y; simpl. apply CRplus_morph. apply DomainProp. apply DomainProp0. } assert (forall (a : CRcarrier (RealT (ElemFunc IS))) (f : PartialFunction (X (ElemFunc IS))) (fL : Lsub f), Isub (Xscale a f) (LscaleStable ElemSub a f fL) == a * (Isub f fL)). { intros. unfold Isub. apply (CReq_trans _ (I IS (Xscale a f) (LscaleStable (ElemFunc IS) a f (X0 f fL)))). 2: apply Ihomogeneous. apply IExtensional. intros. destruct f; simpl. apply CRmult_morph. reflexivity. apply DomainProp. } apply (Build_IntegrationSpace ElemSub Isub H0 H1 (Ione IS) H). - unfold Isub. transitivity (CR_of_Q (RealT (ElemFunc IS)) 1). rewrite <- (IoneInt IS). apply IExtensional. intros. destruct (Ione IS); simpl. apply DomainProp. reflexivity. - intros f fn fL fnL. intros. simpl in fL, fnL. apply (Icontinuous IS f fn (X0 f fL) (fun n => X0 (fn n) (fnL n)) H2 H3). - intros. pose proof (Ilimit IS f (X0 f fL)). split. apply (CR_cv_eq _ (fun n : nat => I IS (XminConst f (INR n)) (@LminIntStable (ElemFunc IS) n f (X0 f fL)))). 2: apply H2. intro n. apply IExtensional. intros. apply DomainProp. apply (CR_cv_eq _ (fun n : nat => I IS (XminConst (Xabs f) (CR_of_Q _ (1# Pos.of_nat (S n)))) (@LminConstStable (ElemFunc IS) (CR_of_Q _ (1# Pos.of_nat (S n))) (Xabs f) (invSuccRealPositive n) (LabsStable (ElemFunc IS) f (X0 f fL))))). 2: apply H2. intro n. apply IExtensional. intros. apply DomainProp. Defined. Lemma IabsHomogeneous : forall {IS : IntegrationSpace} (a : CRcarrier (RealT (ElemFunc IS))) (f : PartialFunction (X (ElemFunc IS))) (fL : L (ElemFunc IS) f), Iabs (Xscale a f) (LscaleStable (ElemFunc IS) a f fL) == (CRabs _ a) * Iabs f fL. Proof. intros. unfold Iabs. rewrite <- Ihomogeneous. apply IExtensional. intros. destruct f; simpl. rewrite CRabs_mult. apply CRmult_morph. reflexivity. rewrite (DomainProp x xF y). reflexivity. Qed. Lemma integralPositive : forall (IS : IntegrationSpace) (f : PartialFunction (X (ElemFunc IS))) (fL : L (ElemFunc IS) f), nonNegFunc f -> 0 <= I IS f fL. Proof. intros. apply (CRle_trans 0 (I IS (Izero IS) (Izero_is_L IS))). unfold Izero. unfold Izero_is_L. rewrite Ihomogeneous. rewrite CRmult_0_l. apply CRle_refl. apply INonDecreasing. intros. rewrite applyIzero. apply H. Qed. (* The usual triangular inequality of integrals : the absolute value of an integral is lower than the integral of the absolute value. *) Lemma integralAbsMaj : forall {IS : IntegrationSpace} (f : PartialFunction (X (ElemFunc IS))) (fL : L (ElemFunc IS) f), CRabs _ (I IS f fL) <= Iabs f fL. Proof. (* Because integral is increasing and I f <= I |f| and -I f <= I |f| *) intros. apply CRabs_le. split. + unfold Iabs. rewrite <- (CRmult_1_l (I IS (Xabs f) (LabsStable (ElemFunc IS) f fL))). rewrite (CRopp_mult_distr_l 1). rewrite <- Ihomogeneous. apply INonDecreasing. intros. rewrite applyXscale. rewrite <- (CRopp_mult_distr_l 1). rewrite CRmult_1_l. destruct f; simpl. rewrite <- (CRopp_involutive (partialApply x y)). rewrite (DomainProp x xF y). rewrite <- CRabs_opp. apply CRopp_ge_le_contravar. apply CRle_abs. + apply INonDecreasing. intros. destruct f; simpl. rewrite (DomainProp x xF y). apply CRle_abs. Qed. Lemma IAbsSumMaj : forall {IS : IntegrationSpace} (fn : nat -> PartialFunction (X (ElemFunc IS))) (fnL : forall n:nat, L (ElemFunc IS) (fn n)) (n : nat), Iabs (Xsum fn n) (LsumStable fn fnL n) <= CRsum (fun n0 : nat => Iabs (fn n0) (fnL n0)) n. Proof. induction n. - simpl. apply CRle_refl. - simpl. apply (CRle_trans _ (I IS (Xplus (Xabs (Xsum fn n)) (Xabs (fn (S n)))) (LplusStable (ElemFunc IS) (Xabs (Xsum fn n)) (Xabs (fn (S n))) (LabsStable (ElemFunc IS) (Xsum fn n) (LsumStable fn fnL n)) (LabsStable (ElemFunc IS) (fn (S n)) (fnL (S n)))))). + clear IHn. apply INonDecreasing. intros. destruct (fn (S n)), (Xsum fn n), xF, y ; simpl. apply (CRle_trans _ _ _ (CRabs_triang _ _)). apply CRplus_le_compat. rewrite (DomainProp0 x d d1). apply CRle_refl. rewrite (DomainProp x d0 d2). apply CRle_refl. + rewrite Iadditive. apply CRplus_le_compat. apply IHn. apply CRle_refl. Qed.