REAL ANALYSIS AND PROBABILITY Thismuchadmiredtextbook,nowreissuedinpaperback,offersaclearexpo- sitionofmodernprobabilitytheoryandoftheinterplaybetweentheproperties ofmetricspacesandprobabilitymeasures. The first half of the book gives an exposition of real analysis: basic set theory,generaltopology,measuretheory,integration,anintroductiontofunc- tional analysis in Banach and Hilbert spaces, convex sets and functions, and measure on topological spaces. The second half introduces probability basedonmeasuretheory,includinglawsoflargenumbers,ergodictheorems, the central limit theorem, conditional expectations, and martingale conver- gence.AchapteronstochasticprocessesintroducesBrownianmotionandthe Brownianbridge. The new edition has been made even more self-contained than before; it now includes early in the book a foundation of the real number system and the Stone-Weierstrass theorem on uniform approximation in algebras of functions. Several other sections have been revised and improved, and theextensivehistoricalnoteshavebeenfurtheramplified.Anumberofnew exercises,andhintsforsolutionofoldandnewones,havebeenadded. R.M.DudleyisProfessorofMathematicsattheMassachusettsInstituteof TechnologyinCambridge,Massachusetts. CAMBRIDGESTUDIESINADVANCEDMATHEMATICS EditorialBoard: B.Bollobas,W.Fulton,A.Katok,F.Kirwan,P.Sarnak Alreadypublished 17 W.Dicks&M.Dunwoody Groupsactingongraphs 18 L.J.Corwin&F.P.Greenleaf RepresentationsofnilpotentLiegroupsandtheir applications 19 R.Fritsch&R.Piccinini Cellularstructuresintopology 20 H.Klingen IntroductorylecturesonSiegelmodularforms 21 P.Koosis ThelogarithmicintegralII 22 M.J.Collins Representationsandcharactersoffinitegroups 24 H.Kunita Stochasticflowsandstochasticdifferentialequations 25 P.Wojtaszczyk Banachspacesforanalysts 26 J.E.Gilbert&M.A.M.Murray CliffordalgebrasandDiracoperatorsin harmonicanalysis 27 A.Frohlich&M.J.Taylor Algebraicnumbertheory 28 K.Goebel&W.A.Kirk Topicsinmetricfixedpointtheory 29 J.F.Humphreys ReflectiongroupsandCoxetergroups 30 D.J.Benson RepresentationsandcohomologyI 31 D.J.Benson RepresentationsandcohomologyII 32 C.Allday&V.Puppe Cohomologicalmethodsintransformationgroups 33 C.Souleetal. LecturesonArakelovgeometry 34 A.Ambrosetti&G.Prodi Aprimerofnonlinearanalysis 35 J.Palis&F.Takens Hyperbolicity,stabilityandchaosathomoclinicbifurcations 37 Y.Meyer Waveletsandoperators1 38 C.Weibel Anintroductiontohomologicalalgebra 39 W.Bruns&J.Herzog Cohen-Macaulayrings 40 V.Snaith ExplicitBrauerinduction 41 G.Laumon CohomologyofDrinfeldmodularvarietiesI 42 E.B.Davies Spectraltheoryanddifferentialoperators 43 J.Diestel,H.Jarchow,&A.Tonge Absolutelysummingoperators 44 P.Mattila GeometryofsetsandmeasuresinEuclideanspaces 45 R.Pinsky Positiveharmonicfunctionsanddiffusion 46 G.Tenenbaum Introductiontoanalyticandprobabilisticnumbertheory 47 C.Peskine Analgebraicintroductiontocomplexprojectivegeometry 48 Y.Meyer&R.Coifman Wavelets 49 R.Stanley EnumerativecombinatoricsI 50 I.Porteous Cliffordalgebrasandtheclassicalgroups 51 M.Audin Spinningtops 52 V.Jurdjevic Geometriccontroltheory 53 H.Volklein GroupsasGaloisgroups 54 J.LePotier Lecturesonvectorbundles 55 D.Bump Automorphicformsandrepresentations 56 G.Laumon CohomologyofDrinfeldmodularvarietiesII 57 D.M.Clark&B.A.Davey Naturaldualitiesfortheworkingalgebraist 58 J.McCleary Auser’sguidetospectralsequencesII 59 P.Taylor Practicalfoundationsofmathematics 60 M.P.Brodmann&R.Y.Sharp Localcohomology 61 J.D.Dixonetal. Analyticpro-Pgroups 62 R.Stanley EnumerativecombinatoricsII 63 R.M.Dudley Uniformcentrallimittheorems 64 J.Jost&X.Li-Jost Calculusofvariations 65 A.J.Berrick&M.E.Keating Anintroductiontoringsandmodules 66 S.Morosawa Holomorphicdynamics 67 A.J.Berrick&M.E.Keating CategoriesandmoduleswithK-theoryinview 68 K.Sato Levyprocessesandinfinitelydivisibledistributions 69 H.Hida ModularformsandGaloiscohomology 70 R.Iorio&V.Iorio Fourieranalysisandpartialdifferentialequations 71 R.Blei Analysisinintegerandfractionaldimensions 72 F.Borceaux&G.Janelidze Galoistheories 73 B.Bollobas Randomgraphs REAL ANALYSIS AND PROBABILITY R. M. DUDLEY MassachusettsInstituteofTechnology           The Pitt Building, Trumpington Street, Cambridge, United Kingdom    The Edinburgh Building, Cambridge CB2 2RU, UK 40 West 20th Street, New York, NY 10011-4211, USA 477 Williamstown Road, Port Melbourne, VIC 3207, Australia Ruiz de Alarcón 13, 28014 Madrid, Spain Dock House, The Waterfront, Cape Town 8001, South Africa http://www.cambridge.org ©R. M. Dudley 2004 First published in printed format 2002 ISBN 0-511-04208-6 eBook (netLibrary) ISBN 0-521-80972-X hardback ISBN 0-521-00754-2 paperback Contents Preface to the Cambridge Edition page ix 1 Foundations; Set Theory 1 1.1 Definitions for Set Theory and the Real Number System 1 1.2 Relations and Orderings 9 *1.3 Transfinite Induction and Recursion 12 1.4 Cardinality 16 1.5 The Axiom of Choice and Its Equivalents 18 2 General Topology 24 2.1 Topologies, Metrics, and Continuity 24 2.2 Compactness and Product Topologies 34 2.3 Complete and Compact Metric Spaces 44 2.4 Some Metrics for Function Spaces 48 2.5 Completion and Completeness of Metric Spaces 58 *2.6 Extension of Continuous Functions 63 *2.7 Uniformities and Uniform Spaces 67 *2.8 Compactification 71 3 Measures 85 3.1 Introduction to Measures 85 3.2 Semirings and Rings 94 3.3 Completion of Measures 101 3.4 Lebesgue Measure and Nonmeasurable Sets 105 *3.5 Atomic and Nonatomic Measures 109 4 Integration 114 4.1 Simple Functions 114 *4.2 Measurability 123 4.3 Convergence Theorems for Integrals 130 v vi Contents 4.4 Product Measures 134 *4.5 Daniell-Stone Integrals 142 5 L p Spaces; Introduction to Functional Analysis 152 5.1 Inequalities for Integrals 152 5.2 Norms and Completeness of Lp 158 5.3 Hilbert Spaces 160 5.4 Orthonormal Sets and Bases 165 5.5 LinearFormsonHilbertSpaces,InclusionsofLpSpaces, and Relations Between Two Measures 173 5.6 Signed Measures 178 6 Convex Sets and Duality of Normed Spaces 188 6.1 Lipschitz, Continuous, and Bounded Functionals 188 6.2 Convex Sets and Their Separation 195 6.3 Convex Functions 203 *6.4 Duality of Lp Spaces 208 6.5 Uniform Boundedness and Closed Graphs 211 *6.6 The Brunn-Minkowski Inequality 215 7 Measure, Topology, and Differentiation 222 7.1 Baire and Borelσ-Algebras and Regularity of Measures 222 *7.2 Lebesgue’s Differentiation Theorems 228 *7.3 The Regularity Extension 235 *7.4 The Dual of C(K) and Fourier Series 239 *7.5 Almost Uniform Convergence and Lusin’s Theorem 243 8 Introduction to Probability Theory 250 8.1 Basic Definitions 251 8.2 Infinite Products of Probability Spaces 255 8.3 Laws of Large Numbers 260 *8.4 Ergodic Theorems 267 9 Convergence of Laws and Central Limit Theorems 282 9.1 Distribution Functions and Densities 282 9.2 Convergence of Random Variables 287 9.3 Convergence of Laws 291 9.4 Characteristic Functions 298 9.5 UniquenessofCharacteristicFunctions and a Central Limit Theorem 303 9.6 Triangular Arrays and Lindeberg’s Theorem 315 9.7 Sums of Independent Real Random Variables 320 Contents vii *9.8 TheLe´vyContinuityTheorem;InfinitelyDivisible and Stable Laws 325 10 Conditional Expectations and Martingales 336 10.1 Conditional Expectations 336 10.2 RegularConditionalProbabilitiesandJensen’s Inequality 341 10.3 Martingales 353 10.4 Optional Stopping and Uniform Integrability 358 10.5 Convergence of Martingales and Submartingales 364 *10.6 Reversed Martingales and Submartingales 370 *10.7 Subadditive and Superadditive Ergodic Theorems 374 11 Convergence of Laws on Separable Metric Spaces 385 11.1 Laws and Their Convergence 385 11.2 Lipschitz Functions 390 11.3 Metrics for Convergence of Laws 393 11.4 Convergence of Empirical Measures 399 11.5 Tightness and Uniform Tightness 402 *11.6 Strassen’sTheorem:NearbyVariables with Nearby Laws 406 *11.7 AUniformityforLawsandAlmostSurelyConverging Realizations of Converging Laws 413 *11.8 Kantorovich-Rubinstein Theorems 420 *11.9 U-Statistics 426 12 Stochastic Processes 439 12.1 Existence of Processes and Brownian Motion 439 12.2 The Strong Markov Property of Brownian Motion 450 12.3 ReflectionPrinciples,TheBrownianBridge, and Laws of Suprema 459 12.4 LawsofBrownianMotionatMarkovTimes: Skorohod Imbedding 469 12.5 Laws of the Iterated Logarithm 476 13 Measurability: Borel Isomorphism and Analytic Sets 487 *13.1 Borel Isomorphism 487 *13.2 Analytic Sets 493 Appendix A Axiomatic Set Theory 503 A.1 Mathematical Logic 503 A.2 Axioms for Set Theory 505 viii Contents A.3 Ordinals and Cardinals 510 A.4 From Sets to Numbers 515 AppendixB ComplexNumbers,VectorSpaces, and Taylor’s Theorem with Remainder 521 Appendix C The Problem of Measure 526 Appendix D Rearranging Sums of Nonnegative Terms 528 Appendix E Pathologies of Compact Nonmetric Spaces 530 Author Index 541 Subject Index 546 Notation Index 554 Preface to the Cambridge Edition This is a text at the beginning graduate level. Some study of intermediate analysis in Euclidean spaces will provide helpful background, but in this editionsuchbackgroundisnotaformalprerequisite.Effortstomakethebook moreself-containedincludeinsertingmaterialontherealnumbersysteminto Chapter1,addingatreatmentoftheStone-Weierstrasstheorem,andgenerally eliminating references for proofs to other books except at very few points, suchassomecomplexvariabletheoryinAppendixB. Chapters1through5provideaone-semestercourseinrealanalysis.Fol- lowingthat,aone-semestercourseonprobabilitycanbebasedonChapters 8 through 10 and parts of 11 and 12. Starred paragraphs and sections, such asthosefoundinChapter6andmostofChapter7,arecalledonrarely,ifat all,laterinthebook.Theycanbeskipped,atleastonfirstreading,oruntil needed. Relativelyfewproofsoflessvitalfactshavebeenlefttothereader.Iwould beverygladtoknowofanysubstantialunintentionalgapsorerrors.Although I have worked and checked all the problems and hints, experience suggests thatmistakesinproblems,andhintsthatmaymislead,arelessobviousthan errorsinthetext.Sotakehintswithagrainofsaltandperhapsmakeafirst tryattheproblemswithoutusingthehints. Ilookedforthebestandshortestavailableproofsforthetheorems.Short proofsthathaveappearedinjournalarticles,butinfewifanyothertextbooks, aregivenforthecompletionofmetricspaces,thestronglawoflargenumbers, the ergodic theorem, the martingale convergence theorem, the subadditive ergodictheorem,andtheHartman-Wintnerlawoftheiteratedlogarithm. Around1950,whenHalmos’classicMeasureTheoryappeared,themore advanced parts of the subject headed toward measures on locally compact spaces, as in, for example, §7.3 of this book. Since then, much of the re- searchinprobabilitytheoryhasmovedmoreinthedirectionofmetricspaces. Chapter11givessomefactsconnectingmetricsandprobabilitieswhichfol- lowthenewertrend.AppendixEindicateswhatcangowrongwithmeasures ix