Extensions of set functions

Mathware&SoftComputing10(2003)5-16 ExtensionsofSetFunctions¤ S.Ovchinnikov1and J.C.Falmagne2 1MathematicsDept.SanFranciscoStateUniv. SanFrancisco,CA94132 2Dept.ofCognitiveSciences.Univ.ofCalifornia Irvine,CA92697 [email protected], [email protected] Abstract We establishanecessaryand su±cientconditionforafunction de¯nedonasubsetofanalgebra ofsetstobe extendableto apositiveadditivefunctiononthealgebra.Itisalsoshownthat thisconditionisnecessaryand su±cientforaregularfunction de¯nedonaregularsubsetoftheBorelalgebra ofsubsetsofa givencompactHausdor®space tobe extendabletoameasure. 1991 MathematicsSubjectClassi¯cation:28A60 1Introduction Astandardmethodofconstructingameasureina givensetXisto de¯ne¯rstanadditivefunctiononanalgebraAofsubsetsofXand thenextend thisfunctiontoameasureonthe¾{algebra generated byA.This`extension problem' isanimportantpart ofthe classical measuretheory.StandardexamplesincludeHahn'sextensiontheorem and theBorelmeasurein[0;1](cf. [3,III.5]). Inthepaper,weare concernedwiththefollowingproblem:Let Xbeasetand Abeanalgebra ofsubsetsofX.GivenasubsetS ¤Thisworkis supported byNSFgrantSES{9986269 toJ.{Cl. Falmagne. 5 6S.Ovchinnikov&J.C.Falmagne ofAand arealvaluedfunction®onS,¯nd necessaryand su±cient conditionsfor®tobe extendableto a positiveadditivefunction¹on A. Thefollowingconditionisinstrumental inour treatmentofthe extension problem: X A2F n(A)ÂA(s)¸0;8s2X)X A2F n(A)®(A)¸0;[R] forany¯nitefamilyFµS,where coe±cientsn(A)'sarearbitrary integersand ÂAstandsfor the characteristicfunctionofasetAµX. Weshowthatcondition[R] isnecessary(Section2)and su±cient (Section3)for®tobe extendableto a positiveadditivesetfunction. Inthe casewhenXisa¯niteset,astronger resultisalsoestablished in Section3.To obtaintheseresults,weonlyassumethatXisa¯nite unionofelementsofS(thisassumptionisdroppedinthe caseofa ¯nitesetX). Wemakeadditionalassumptionsabout thequadruple(X;A;S;®) whentreatingthe extension problemformeasuresinsections4 and 5.In bothsections,XisacompactHausdor®space.In Section4, AistheBorelalgebraBofsubsetsofX,whereasin Section5,Ais the¾{algebra generated byS.Assuming, inaddition,thatSand ® satisfysome`regularity'conditions,weshowthat[R] isanecessary and su±cientconditionfor®tobe extendableto a positiveregular measureonA. Ourapproachtothe extension problemcomesclosetothatof BrunodeFinetti in his\ProbabilityTheory"[4](Sections9 and 10). In particular,his\convexitycondition"(Section15 inAppendix)is equivalent tocondition[R], although deFinettiformulatesitinrather di®erent terms. 2Condition[R] Thefollowinglemmaestablishesausefulequivalentformofcondition [R]. Lemma1. [R]isequivalent tothefollowing condition X A2F c(A)ÂA(s)¸0;8s2X)X A2F c(A)®(A)¸0;(1) ExtensionsofSetFunctions7 forany¯nite familyFµS,where coe±cientsc(A)'sarearbitraryreal numbers. Proof. Itsu±cestoshowthat[R] implies(1).Supposethatforsome realcoe±cientsc(A)'s suchthatPA2Fc(A)ÂA¸0wehave PA2Fc(A)®(A)<0.Therearerationalnumbersp(A)'s suchthat PA2Fp(A)®(A)<0 and p(A)¸c(A)forall A2F.Clearly, X A2F p(A)ÂA¸X A2F c(A)ÂA¸0: MultiplyingbothinequalitiesPA2Fp(A)ÂA¸0 and PA2Fp(A)®(A)< 0byacommonmultipleofthedenominatorsofnonzerocoe±cients p(A)'s,weobtainacontradictionto[R]. Supposethat®isarestrictionofapositiveadditivesetfunction ¹onA.Notethat the¯rstsumin(1)is,byde¯nition,asimple functiononX.Thencondition(1)statesthat theintegralofapositive simplefunctionispositive([3,III.2.14]).Thuswehavethefollowing proposition. Proposition1. [R]isanecessarycondition forafunction®onSto be extendable to a positive additive set functiononA. 3Extensionstopositiveadditivesetfunctions WedenotebyB0thevectorspace ofall simplefunctions(withrespect toA)onXand denotebyB# 0{thealgebraicdualspace.Thespace B# 0isisomorphictothevectorspace ofall additivesetfunctions¹on A.Theisomorphismisgiven by ¹7! f¹wheref¹(x)=Zx(s)¹(ds):(2) ThesetCofall positivesimplefunctionsonXisaconvexcone inB0.ThusB0isanorderedvectorspace.Afunctionalf2B# 0is 8S.Ovchinnikov&J.C.Falmagne monotoneifx¸yimpliesf(x)¸f(y).Afunctionalfismonotoneif and onlyifitispositive, i.e., x¸0impliesf(x)¸0. Weshall usethefollowing generalfactaboutmonotonelinearextensionsoflinearfunctionalsonorderedvectorspaces([1,Theorem1, x6,ch.2]). Theorem 1. Let Lbe avectorspace with a coneC.Let L0be a subspace ofLsuchthatforeachxin L,x+L0meetsCif and only if ¡x+L0meetsC.Let f0in L# 0be monotone.Thenthere existsan extensionfoff0whichismonotoneandin L#. Now weprovethemaintheoremofthis section. Theorem 2. Let Sbe asubset ofAsuchthatXisa¯nite unionof setsin Sand let ®be afunctiononS.Then®canbe extendedto a positive additive function¹onAif and onlyif itsatis¯escondition [R]. Proof. NecessitywasestablishedinProposition1. Su±ciency.LetL0bethesubspace ofB0generated bythe characteristicfunctionsofsetsinS.Forx=PA2Fc(A)ÂA2L0whereFis a¯nitesubsetofS,wede¯ne f0(x)=X A2F c(A)®(A): Itfollowsimmediatelyfrom(1) thatf0iswell{de¯nedand isapositive linearfunctionalonL0. Notethatforanyx2B0thesetx+L0meetsthe coneCof positivefunctionsinB0.Indeed, letX=[n i=1Ai;Ai2Sand de¯ne x0=Pn i=1ÂAi2L0.Then,form= sups2Xjx(s)j,x+mx02C. ByTheorem1,f0admitsanextensionto a positivelinearfunctional fonB0.Byde¯ning¹(A)=f(ÂA)forA2A,weobtainanextension of®toapositiveadditivefunctiononA. Notethat theassumptionthatXisa¯niteunionofsetsinSis essential inthetheorem.Indeed, letXbeanin¯niteset,A=2X, and letSbethefamilyofall singletonsinA.Letusde¯ne®(fsg)= 1;8s2X.Thusde¯ned®satis¯escondition[R]butcannotbe extendedtoamonotoneadditivefunctiononA. ExtensionsofSetFunctions9 Ontheotherhand, inthe caseofa¯nitesetXwehaveastronger result. Theorem 3. Let Xbe a¯nite set,SµA,and®be afunctionon S.Then®canbe extendedto a positive additive function¹onAif and onlyif itsatis¯escondition[R]withcoe±cientsfroma¯nite set of integers. Proof. Again,weneedtoprovesu±ciencyonly.LetX0=[Sand A0bethealgebra ofsubsetsofX0consisting ofsetsinAthatare subsetsofX0.ByTheorem2,®can be extendedtoapositiveadditive setfunction¹0onA0.ForanA2A,wede¯ne¹(A)=¹0(A\X0). Clearly,¹isapositiveadditivesetfunctiononA. LetusconsidercharacteristicfunctionsofsetsinSasintegralvectorsinRjXjand letCbetheintersectionofthesubspace generated by thesevectorswiththepositive coneinRjXj.The coneCisarational polyhedralconeand thereforehasanintegralHilbert basis(Theorem16.4in[5]).Thuswe can useonly vectorsfromthisbasisinthe rightsideoftheimplicationin[R]. Itfollowsthatinthe caseof¯nite setXcoe±cientsin[R]can betakenfroma¯nitesetofintegers. Remark.Itwasnoted byJean{PaulDoignon(personalcommunication) thatsu±ciencyofcondition[R] inthe¯nite caseisadirect consequence ofFarkas' lemma[5,Corollary7.1d]. 4ExtensionstomeasuresI Thefollowingexampleshowsthat, ingeneral, condition[R] isnot su±cientforafunction®tobe extendabletoapositivemeasure(¾{ additiveset{function)ona¾{algebraA. Example1. LetX=[0;1]and S=f[0;t):t2(0;1]g[f[0;t]:t2 [0;1]g.NotethatX2S.Wede¯ne®(f0g)=0 and ®(A)=1ifA is[0;t)or[0;t]for0<t·1.Itiseasytoverifythat thusde¯ned® satis¯escondition[R]. 10 S.Ovchinnikov&J.C.Falmagne Let¹bea¾{additive extensionof®tothe¾{algebraBofBorel subsetsof[0;1]. Wehave ¹((t;1])=1¡®([0;t])=0;fort>0, ¹((0;1])=1¡®(f0g)=1; ¹((s;t])=1¡®([0;s])¡¹((t;1])=0;for0<s<t: By¾{additivityof¹, 1=¹((0;1])=¹Ã1 [ 1µ1 k+1;1 k¸!= 1 X 1 ¹µµ 1 k+1;1 k¸¶=0; acontradiction.Ontheotherhand,bycondition[R], thereisan additive extensionof®toB. Thisexamplesuggeststhatinorder tokeep[R]asanecessary and su±cientconditionforextendibilityofasetfunctionto a measure,some constrains should beimposedonthequadruple(X;A;S;®). Namely,weassumethatXisacompactHausdor®space and introduce thefollowing`regularity'conditionsonSand ®. De¯nition1. (i)AfamilySofsubsetsofXis saidtoberegularif (a)ForeachE2Sand aclosedsetFµEthereisE02Ssuch that FµE0µclE0µE: (b)ForeachE2Sand anopensetG¶EthereisE00 2Ssuch that EµintE00 µE00 µG: (ii)Afunction®onafamilySis saidtoberegularif foreachE2S and ">0thereisasetFinSwhose closureiscontainedinEand a setGwhoseinteriorcontainsEsuchthatj®(G)¡®(F)j<". Inthis section,AistheBorelalgebraBofsubsetsofX. Example2. Since Xisanormalspace,thefamiliesofall opensets and ofall closedsetsinXare examplesofregularfamiliesofBorel sets(cf. [2,VII.3.2(2)]). ExtensionsofSetFunctions11 Example3. LetX=[0;1]and Sbethefamilyofall intervalsinthe form[a;b).Clearly,SisaregularfamilyofBorelsets. Example4. LetS=Band let®=¹{aregularpositiveadditiveset functiononBintheusualsense(cf. [3,III.5.11]).Then®isaregular functioninthesenseofDe¯nition1. Lemma2. Let ¹be aregularpositive measureontheBorel algebraB and let Sbe aregularfamilyofBorelsets.Thentherestrictionof¹ toSisaregularfunctiononS. Proof. LetE2Sand ">0.Since ¹isregularand positive,thereisa closedsetFµEand anopensetG¶Esuchthat¹(G)¡¹(F)<". Since Sisregular,thereareE0;E00 2SsuchthatFµE0µclE0µ EµintE00 µE00 µG.Since ¹ispositive,¹(E00)¡¹(E0)<". Thereforetherestrictionof¹toSisaregularsetfunctiononS. Lemma3. Let Sbe aregularfamilyofBorelsets suchthatXisa ¯nite unionofsetsin Sand let ®be aregularfunctiononSsatisfying condition[R].Then®isextendable to a regularpositive measureon B. Proof. ByTheorem2,®admitsanextensionto a positiveadditiveset function¹onB.Since ¹isbounded, itde¯nesabounded positive linearfunctionalfontheBanachspace Bofall uniformlimitsof functionsinB0endowedwiththenormk¢k1.Thisfunctional isgiven by[3,IV.5.1] f(x)=Zx(s)¹(ds);x2B0: BytheRieszrepresentationtheorem[3,IV.6.3]therestrictionofthis functional(whichwedenotebythesamesymbolf) tothespace C(X) ofcontinuousfunctionsonSisgiven by f(x)=Zx(s)¹¤(ds);x2C(X); where¹¤isaregularpositivemeasureonB. 12 S.Ovchinnikov&J.C.Falmagne Nowitsu±cestoshowthat¹¤(E)=¹(E)onS.LetE2Sand ">0.Since ¹¤ispositiveand regular thereisaclosedsetFand an opensetGsuchthat FµEµG; ¹¤(F)·¹¤(E)·¹¤(G);and ¹¤(G)¡¹¤(F)<": Since Sisregular,thereareE0;E00 2Ssuchthat FµE0µclE0µEµintE00 µE00 µGand ¹(E00)¡¹(E0)<": WedenoteF0=clE0and G0=intE00.Since ¹and ¹¤arepositive, ¹(G0)¡¹(F0)<"and ¹¤(G0)¡¹¤(F0)<":(3) Since Xisanormalspace,byUrysohn'slemma,thereisacontinuousfunctionxsuchthat 0·x(s)·1;forall s2X; x(s)=1;forall s2F0; x(s)=0;forall s=2G0: Foranaturalnumbern,wede¯neafamilyofn+1intervalsin[0;1] by Ik=(£k¡1 n;k n¢;for1·k·n; f1g;fork=n+1. ThefamilyofBorelsetsEk=x¡1(Ik);1·k·n+1,formsapartition ofX.Clearly,Sn k=2EkµG0nF0.Therefore,bythe¯rstinequalityin (3), n X k=2 ¹(Ek)·¹(G0)¡¹(F0)<":(4) Letxnbeafunction de¯ned byxn(s)=k¡1 nfors2Ek;1·k·n+1. Thus jf(x)¡f(xn)j· kfk¢kx¡xnk<1 nkfk(5) ExtensionsofSetFunctions13 Further, xn= n+1 X k=1 k¡1 nÂEk= n X k=2 k¡1 nÂEk+ÂEk+1: Thus f(xn)= n X k=2 k¡1 n¹(Ek)+¹(Ek+1); whichimplies,by(4), f(xn)¡¹(Ek+1)= n X k=2 k¡1 n¹(Ek)<": Thisinequalitytogetherwithonein(5)imply jf(x)¡¹(En+1)j<"+1 nkfk:(6) Clearly,F0µEn+1µG0,and F0µEµG0.Thus,by(3), j¹(En+1)¡¹(E)j<":(7) Since f(x)=Rx(s)¹¤(ds),wehave¹¤(F0)·f(x)·¹¤(G0).Onthe otherhand,¹¤(F0)·¹¤(E)·¹¤(G0).Bythesecond inequalityin(3), j¹¤(E)¡f(x)j<":(8) Combininginequalities(6),(7),and (8),wehave j¹¤(E)¡¹(E)j<3"+1 nkfk: Hence,¹¤(E)=¹(E)=®(E). CombiningtheresultsofLemma 2 and Lemma 3,wehavethe followingtheorem. Theorem 4. Let Sbe aregularfamilyofBorelsets suchthatXisa ¯nite unionofsetsin S.Afunction®onSisextendable to a regular positive measureonBif and onlyif itisregularandsatis¯escondition [R].