### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Introduction to Analysis MATH 104

GPA 3.93

### View Full Document

## 10

## 0

## Popular in Course

## Popular in Mathematics (M)

This 147 page Class Notes was uploaded by Kavon Feest on Thursday October 22, 2015. The Class Notes belongs to MATH 104 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/226608/math-104-university-of-california-berkeley in Mathematics (M) at University of California - Berkeley.

## Reviews for Introduction to Analysis

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15

NOTES ON THE LIFTING THEOREM WILLIAM ARVESON We have seen that the proof of existence of inverses for elements of ExtX can be based on a lifting theorem for completely positive maps of CX into a quotient C algebra of the form EIC where E Q 3H is a C algebra containing the compact operators IC That argument works equally well for arbitrary C algebras in place of CX whenever a completely positive lifting exists Thus we are led to ask if every completely positive linear map 1 of an arbitrary C algebra A into a quotient C algebra BK has a completely positive lifting 10 A 7 B The answer is yes if A is nuclear by a theorem of Choi and Effros CE76 but no in general We will sketch a proof ofthe Choi Effros theorem that is based on the existence of quasicentral approximate units full details can be found in Arv77 Throughout this lecture all Hilbert spaces are assumed to be separable 1 QUASICENTRAL APPROXIMATE UNITS An operator T E 3H is said to be quasidiagonal if there is a sequence Fn of nite rank projections such that Fn T 1 and HFnT 7 TFnH 7 0 as n 7 00 It is not hard to see that this is equivalent to the existence of a sequence of mutually orthogonal nite dimensional projections E1 E2 in 3H such that 2 En 1 and T 231 EnTEn K where K is a compact operator Equivalently T is quasidiagonal if and only if it is a compact perturbation of a block diagonal operator 7 a countable direct sum of nite dimensional operators Not all operators are quasidiagonal Indeed it is an instructive exercise to show that if a Fredholm operator T is quasidiagonal then its index satis es indT 0 Thus the simple unilateral shift is not quasidiagonal Neverthe less in this section we will show that it is always possible to nd a sequence of positive nite rank operators Fn such that Fn T 1 and HFnT 7 TFnH 7 0 as n 7 00 Given that result it is not hard to deduce that there is a se quence of positive nite rank operators E1E2 such that 2 E3 1 and Zn EnTEn is a compact perturbation of T Of course 2 EnTEn is not necessarily block diagonal or even quasidiagonal but one can show that it and T itself is always a direct summand of a quasidiagonal operator Let K be a two sided ideal in a C algebra A not necessarily closed Recall that an approximate unit for K is is an increasing net u of positive elements ofK such that g 1 and lim HuAk7kH 0 If u also satis es lim HuAa 7 auAH 0 for all a E A then u will be called quasicentral Date 29 September 2003 2 WILLIAM ARVESON Theorem 11 Every ideal K in a C algebra A has a quasicentral approx imate unit If A is separable the approximate unit can be chosen to be a sequence ul U2 We sketch the main idea of the proof which requires two observations First if a is any approximate unit for K and f is any bounded linear functional on A then we have 11 liInfua7au 0 a GA Indeed since every bounded linear functional on A is a linear combination of four positive linear functionals of norm 1 it suf ces to prove 11 for the states 1 and in that case the proof is a straightforward argument using the GNS representation for 1 Second given any approximate unit aA E A for K we point out that one can view its convex hull A as an approximate unit Indeed by de nition A consists of all nite convex combinations A01u10nunAjEA 973920 Using the fact that the original net a is directed increasing one nds that A is an increasing directed set with respect to the operator ordering of A Thus we may regard A as an increasing directed net of positive operators relative to the operator ordering that indexes itself One can now show that A is also an approximate unit for K as on page 330 of Arv77 Here is the key observation Lemma 12 Let A be a convex approximate unit for an ideal K in a 0 algebra A Then for every nite set of elements a1 an E A and every 6 gt 0 there is an element a E A such that 12 Huak 7 akuH e 1 h g n Proof of Lemma 12 One can immediately reduce to the case n 1 by replacing A with the n fold direct sum n A A 63 63 A of copies of A K with n K A with a 63 63 a a E A a convex approximate unit for n K and then considering the single element a1 63 eaan E A 63 63 A For the case of a single element a E A 12 simply asserts that 0 belongs to the norm closure of the set C aa 7 an a E A But if 0 6 then since C is convex a standard separation theorem implies that there is a bounded linear functional 1 on A such that lfva 7 aal 2 e gt 0 for every n E A and that contradicts 11 above Proof of Theorem 1 Choose an arbitrary approximate unit aA E A for K and let A be its convex hull Choose elements a1 an E A v E A and e gt 0 Since a E A a 2 v is a co nal convex subnet of A it is also a convex approximate unit for K Thus Lemma 12 implies that there is an element w 2 v in A such that Hwak 7 aka g e for k 1 n That assertion is clearly enough to allow us to extract a subnet v of A with the prOperty that limA llvAa 7 avAH 0 for every a E A and such a NOTES ON THE LIFTING THEOREM 3 subnet 12A is a quasicentral approximate unit The proof that 12A can be chosen as a sequence when A is separable is a straightforward argument that we omit Remark 13 Theorem 11 was discovered during the writing of Arv77 it was discovered independently by Charles Akemann and Gert Pedersen in their work on ideal perturbations of elements of C algebras at about the same time 2 LIFTABLE MAPS Let A be and B be unital C algebras We consider completely positive linear maps 1 A a B which preserve units in the sense that gt1A 13 and we refer to such a j as a U0 map Given a closed two sided ideal K Q B in a unital C algebra B we want to know if there is a UCP map 1 BK a B that provides a lifting for the projection b E B H b E BK More generally given a U0 map from a given C algebra A into a quotient BK the lifting problem for j is the the problem of nding a UCP map 1b A a B such that 1ba gta a E A If such a map 1b exists then 1 is said to be liftable and we write 1 In this section we discuss some results about liftable maps in general most of which depend strongly on quasicentral approximate units Throughout this section and the next A will denote a separable C algebra with unit Let us x an ideal K in another unital C algebra B B need not be separable and consider the set UCPABK of all UCP maps 1 A a BK as a topological space in its point norm topology Thus a net gt A a BK of linear maps converges to a map 1 A a BK iff lirnH Aa7 gtaH 0 a GA The rst key fact is that in general the set of liftable maps is closed Theorem 21 Let A be a separable unital C algebra Then the set of all liftable UC P maps from A to a quotient BK is closed in the point norm topology of UCPA We will say something about what goes into the proof of Theorem 21 skipping over the technicalities The rst observation is that the point norm topology is metrizable when A is separable Indeed if we x a sequence a1 a2 of elements that is dense in the unit ball of A then 00 WmJ Z 2 ll gtan 7 WWH rL1 is a metric with the stated property Let us x a sequence a1 a2 through out the discussion thereby xing a single metric d on UCPA BK that makes it into a complete metric space 4 WILLIAM ARVESON Suppose that we are given a pair of U0 maps gt1J A a Then we may compose both maps with the natural projection b E B H b E BK to obtain UCP maps gtzJ A a BK into the quotient Obviously aim dlt gtwgt What is important here is that the left side of this inequality can almost be realized by perturbing one of the two maps gtzJ A a B Lemma 22 For any two UC P maps gt1J A gt and every 6 gt 0 there is a UC P map 1 A gt B such that d 11 d gt1J 6 Sketch of proof Let u be an approximate unit for K that is quasicentral in B For every A we can de ne a U0 map in A a B by 11a uy2 au2 1 7 uA121Ja1 7 WW a e A Obviously 12 The main property of these perturbations 1 is 21 limfupdw w E KWJ The estimates required for the proof of 21 can be found on pp 3467347 of Arv77 Once one has 21 one obtains the assertion of Lemma 22 by choosing an appropriately large A D Proof of Theorem 21 To prove Theorem 21 let 11 g be a sequence of liftable maps in UCPA BK that converges to a UCP map 100 By passing to a subsequence if necessary we can also arrange that d gtn 100 lt 12 We claim that there is a sequence 111 112 in UCPA BK satisfying it on and d n n1 lt 12 71 1 2 Indeed let 11 be any UCP lifting of 11 Assuming that 111 1Jn have been de ned and satisfy the stated conditions choose any lifting A of on Noting that twin A d gtn gtn1 lt 12 Lemma 12 implies that there is a UCP map 11 satisfying 11 A on and d1Jn11n1 lt 12 Since Zn d1Jn11n1 lt 00 11 is a Cauchy sequence relative to the it metric and we can de ne a U0 map 1100 as the limit limnwn Since 1 on converges to 100 1100 is a lifting of 100 D The second key fact that we require is that the lifting problem can always be solved for matrix algebras Mn MMC 71 1 2 Proposition 23 M D Choi Every UCP map 1 Mn a BK 239s liftable Sketch of Proof Let em 1 g p q n be a system ofmatrix units for Mn Thus epqem ogre ezq eqp and Mn is spanned by em De ne an array of elements qu E BK by qu ew The n x 71 matrix qu can be considered an element of Mn X E Mn X K It is positive because 1 is n positive An elementary exercise with the functional calculus shows that every positive element of a quotient of C algebras can be lifted to a positive element of the ambient C algebra Applying this to the ideal NOTES ON THE LIFTING THEOREM 5 Mn X K in Mn X B we obtain a positive n x n matrix Fm of elements of B such that qu projects to 1 1quot via the map B a BK 1g pq n Now let to Mn a B be the unique linear map satisfying gt0qu Fm 1 pq n Since the n x n matrix gt0epq Fm is positive it follows that to must be completely positive see Lemma 32 of Arv77 Obviously to is a lifting of j to need not carry unit to unit but a simple argument shows that it can be perturbed into another completely positive lifting that does see p 350 of Arv77 3 LIFTINGS AND NUCLEARITY We now show that the results of the preceding section imply the lifting theorem for nuclear C algebras Let A and B be unital C algebras A UCP map 1 A a B is called factorable if it can be factored through some matrix algebra Mn n 1 2 in the sense that there are UCP maps a A a Mn and r Mn a B such that j r 00 j is called a nuclear map if it belongs to the point norm closure of the set of all factorable maps in UCPA B Finally a C algebra A is called nuclear if the identity map of A is a nuclear map The notion of nuclearity is equivalent to several natural and useful properties when A is separable including i For any C algebra B the natural homomorphism of A max B onto A min B is an isomorphism ii A is amenable iii The weak closure of A in any representation is injective iv The weak closure of A in any factor representation is hyper nite The following result was originally proved in CE76 by a rather different method Theorem 31 Choi Effros Every nuclear UC P map from a separable 0 algebra A into a quotient BK 239s liftable Proof Let 1 A a BK be a nuclear UCP map By Theorem 21 the set of liftable maps in UCPA BK is closed in the point norm topology Since 1 is the point norm limit of a set of factorable UCP maps it suf ces to show that every factorable UCP map is liftable But if j is a composition r o a where a A a Mn and r Mn a BK are UCP maps then Proposition 23 implies that r can be lifted to a UCP map To Mn a B and clearly r0 0 a is a lifting of j r o a D Corollary 32 Euery UC P map of a separable nuclear C algebra A into a quotient BK 239s liftable REFERENCES AIV77 W Arveson Notes on extensions of Calgebras Dulce Math 1 4423297355 CE76 MD Choi and E E ros The completely positive lifting problem for Calgebras Ann Math 10435857609 1976 Real Analysis July 10 2006 1 Introduction These notes are intended for use in the warm up camp for incoming Berkeley Statistics graduate students Welcome to Call The real analysis review presented here is intended to prepare you for Stat 204 and occasional topics in other statistics courses We will not cover measure theory topics and some other material that you should be very familiar with if you intend to take Stat 205 If you have never taken a real analysis course7 you are strongly encouraged to do so by taking math 104 or the honors version of it Math 105 usually of fered in the spring will provide you with necessary measure theoretical background essential for Stat 205 The presentation follows closely and borrows heavily from 7Real Mathematical Analysis7 by CC Pugh7 the standard textbook for honors version of math 104 The empha sis is on metric space concepts and the pertinent results on the reals are presented as speci c cases of more general results7 and a lot of them are presented together as exersises in section 38 We do not expect you to be familiar with the metric space concepts but we do expect you to be familiar with speci c results on real line7 as that is usually the approach taken in most real analysis courses We hope that you nd these notes helpfull Go Bears 2 Some De nitions We will denote by RQZ and N the sets of all real numbers rational numbers integers and positive integers respectively We will take for granted the familiarity with notions of nite countably in nite and uncountably in nite sets Given a set SC R ME R is an upper bound for S if V5 6 S it is true that s S M S is said to be bounded above by M M is said to be the least upper bound or lub for S if for all upper bounds M it is true that M S M note that it implies that lub is unique The lower bounds and the greatest lower bound glb are de ned sirnilarly For example if S01 then 1 and 4 are upper bounds and 0 4 are lower bounds with 0 and 1 being glb and lub respectively A set is said to be bounded if it is bounded from above and below A set S is said to be unbounded from above if VN 35 E S st 5 gt N The de nition of a set unbounded below is similar A set is unbounded if its either unbounded from above or below The supremum sup of a set S C R is de ned to be lub for S if S is bounded from above and to be 00 otherwise The in num inf is de ned to be glb for a set bounded form below and to be foo otherwiseThe following results will be assumed about R proofs can be looked up in any analysis textbook 1 If S C R is bounded from abovebelow then the lubglb for S exists and is unique 2 Triangle Inequality lx yl S 3 6principle lf Xy E R and V6 gt 0 x S y 6 then x S y Also if V6 gt 0 lx iyl S 6 then Xy 4 Every interval a7b contains countably in nitely many rationals and uncountably in nitely many irrationals 3 Metric Spaces 31 De nition A metric space M is a set of elements together with a function dM gtlt M a R known as metric that satis es the following 3 properties For all X7 y7 Z 6 M 1 dXy2 0 and dXy0 iff Xy 2 dX7y dy7x 3 dxy S dxz dzy When metric d is understood7 we refer to M as the metric space When we want to specify that the metric is in M 7 we might use notation dMxy It also helps sometimes to think of d as the distance function7 since it makes the 3 properties more intuitive we usually think of distance as being nonnegative7 and the distance from A to B should be the same as the distance from B to A Here are some examples 1 R with usual distance function dxy ix 7 yl 2 Q with the same metric 3 R with Euclidean distance dxy 7 4 Any metric space for ex R or N with the discrete metric dXy1 if z 31 y dxy 0 otherwise This metric makes the distance from a point to itself be 0 and the distance between any two distinct points be 1 You should check for yourself that the metrics above satisfy the 3 conditions 32 Sequences We will use the notation for the sequence of points 12 x in metric space M The members of a sequence are not assumed to be distinct thus 1111 is a legit imate sequence of points in Q A sequence is a subsequence of if there exists sequence 1 S 711 lt 712 lt 713 lt st yk mm Some subsequences of the sequence 112123123412345 are 1 twos22222 77777quot39 E0 odds 1357 9 9 primes 235711 7 original sequence with duplicates removed 1234567 U the previous subsequence with rst 3 elements removed 4567 A sequence of points in M is said to converge to the limit X in M if V6 gt 0 3 N st 71 2 N gt dznx lt 6 We then say that M a x Notice that if our metric space is R then replacing dx m by the usual metric lznizl gives the familiar de nition of a limit Theorem The limit of a sequence7 if it exists7 is unique Proof Let be a sequence in M that converges and suppose its limit is not unique Let Xy denote two of possibly even more limits Let E gt 0 be given Then 3N1 st 71 2 N1 gt dznx lt 62 Similarly 3N2 st 71 2 N2 gt dxny lt 62 Let N mazN1N27 and let n 2 N Then by the 3rd property of metric function 6196711 dawn dxny lt 62 62 6 Since this is true for every 6 we have Xy by the 6 principle Theorem Every subsequence of a convergent sequence converges7 and it converges to the same limit as the original sequence Proof Easy A sequence in M is said to be Cauchy if V6 gt 0 EN st 717 m 2 N gt dzn7 zm lt 6 In other words a sequence is Cauchy if eventually all the terms are all very close to each other Theorem Every convergent sequence is Cauchy Proof Suppose xn a z in M Let E gt 0 be given Then 3N st 71 2 N gt dzmz lt 62 Let mm 2 N Then dznxm S dznz dxm lt 62 62 lt E gt is Cauchy Does every Cauchy sequence converge to a limit Consider the sequence 3 314 3141 31415 This sequence is clearly Cauchy When considered as a sequence in R it does converge to 7139 However we can also think of it as a sequence in Q in which case it doesnt converge since 7139 Q The following de nition formalizes the difference between Q and R the metric space M is said to be complete if all Cauchy sequences in M converge to a limit in M Theorem R is complete Proof Let an be a Cauchy sequence in R and let A be the set of elements of the sequence ie AxER3nENandanx Let 61 Then since an is Cauchy 3N1 st Vnm 2 N1 lan7aml lt 1 Therefore V71 2 N1 we have lan 7 aNl lt1 and thus 71 2 N1 gt an E aN171aN11 The nite set 11 a2 11111 7 1aN1 1 is bounded as is every nite subset of R and therefore all of its elements belong to some interval 7LL Since both IN 7 1aN1 1 6 7L L we conclude that 0N1 71aN1 1 C 7LL and therefore an E 7LL Vn and A is bounded Now consider set S s E 7L7 L 3 in nitely many 71 E N for which an 2 s Obviously7 7L E S and S is bounded from above by L We then know that the lub for S exists call it b We will show that an 7 b Let 6 gt 0 be given Then since an is Cauchy7 3N2 st mm 2 N2 gt lan 7 aml lt 62 Since V5 6 S7 5 3 b7 we have that b 62 S That means that an exceeds b 62 only nitely often and 3N3 2 N2 st 71 2 N3 gt an S b 62 Since b is the least upper bound for S we have that b 7 62 is not an upper bound for S and therefore 35 E S st 5 gt b 7 62 and an 2 s gt b 7 62 in nitely often In particular that gurantees that there exists some N4 2 N3 st 1M gt b7 62 Moreover7 since N4 2 N3 we have 1M 6 b7 62b 62 And since N4 gt N2 we get 71 2 N4 gt lan7bl S lan7aN4llaN47bl lt6262 lt6 and therefore an 7 b It is an easy exersise to show that every discrete metric space for exarnple7 N with dis crete metric is complete 33 Open and Closed Sets Let M be a metric space and let S be a subset of M We say that z E M is a limitpoint of S note that S is not a sequence here7 but a subset of M if there exists a sequence in S st xn 7 x For exarnple7 let M R and SQ Then 2 is an example of a limit point of S 7 2 2222 or 1 1 12 1 23 1 34 that belongs to S and 7139 is a an example of a limit point of S 331314314131415 that does not belong to S of course it still belongs to A set is said to be closed in underlying metric space M if it contains all of its limits For example a singleton set x is closed in M assuming M is non empty since the only possible sequence is xxx a x Clearly M is a closed subset of itself A set S is said to be open in underlying mertric space M if Vm E S 37 gt 0 st dxy lt r gt y E S The set of points y E M dxy lt r is called open r neighborhood of x and is denoted Bz for example B25 in R is simply the open interval 37 Thus a set S is open in M if for every point in S there exists some small neighborhood of that point in M contained entirely in S Its easy to see that interval ab is an open set in R and clearly every metric space M is an open subset of itself since every r neighborhood of x is still in The following theorem provides a connection between open and closed sets Theorem The compliment of an open set is closed and the compliment of a closed set is open ProofSuppose S C M is open Suppose xn a z in M and moreover xn E S0 V71 We need to show that z 6 SC Suppose not then x E S Since S is open 37 gt 0 st dy lt r gt y E S Now since xn a z 3N st 71 2 N gt dznz lt r gt xn E S That is clearly impossible since no point could be in both S and Sc and we have reached a condtradiction Therefore Sc is closed Now suppose that S C M is closed Suppose Sc is not open then Hm E S0 st V73 gt 0 3 8 st dzn lt Tn but xn E S Now let Tn 171 and pick xn as above Then xn E S Vn and xn a z 6 SC gt S is not closed since it fails to contain all of its limits gt contradiction Therefore Sc is open Notice that some sets like the space M itself are both closed and open7 they are referred to as clopen sets By theorern above7 MC g is clopen Now consider interval 01 C R It is neither open every r neighborhood of 0 includes points in 0710 C R nor closed it fails to include 17 which is the limit of the sequence xn 1 7 171 in 07 Thus subsets of a metric space can be open7 closed7 both7 or neither Theorem Arbitrary union of open sets is open Proof Suppose Uais a collection of open sets in M7 and let U UUD Then z E U gt z E Ua for some 04 and 37 gt 0 st dy lt r gt y E Ua gt y E U Therefore U is open Theorem Intersection of nitely many open sets is open Proof Suppose U17U2 Un are open sets in M Let U Uk If U g then U is open Now suppose z 6 U7 then x 6 Uk for k 172737 n Since each Uk is open7 37 gt 0 st dxy lt rk gt y 6 Uk Let r mmr1r2rn then dy lt r gt y 6 Uk Vk gt y E U Therefore U is open Notice that the in nite intersection of open sets is not necessarily open For example its easy to see that Uk flk 1k is an open subset of R but Uk 0 is clearly not open in R TheoremArbitrary intersection of closed sets is closed Also nite union of closed sets is closed Proof well use DeMorgan7s Laws UUkc Ukc Let K0 be a collection of closed sets in M Then Ka UKjf and since each Kac is open their union is open and its complement is closed The proof of the second part of the theorem is similar Notice that the in nite union of closed sets is not guaranteed to be closed For example even though each Kk 01 7 1k is closed in R the intersection UKk 01 is not TheoremLet M be a complete metric space N C M be closed Then N is complete as a metric space in its own right Proof Let be a Cauchy sequence in N Since is also a Cauchy sequence in M and M is complete we have xn a z E M But N is closed in M therefore z E N and we conclude that N is complete Let lim S denote the set of all limit points of S in M It is pretty clear that z 6 lim S ltgt V7quot gt 0 BTW S 31 g you can easily prove it as an exersise We can also show that lim S is a closed set Let E gt 0 be given and let be a sequence of points in lim S st 10 yn a y in M Then 3N st 71 2 N gt dyny lt 62 Since each yn 6 lim S7 Hzn E S st dynn lt 62 Vn Then we have n 2 N gt dzmy S dzmyn Gibmy lt E2 E2 6 Therefore xn a y and y 6 lim S We conclude that lim S is closed We can also show that BTW is an open subset of M as follows let y E BTW Let s r 7 dy gt 0 Then dyz lt s gt d2796 S CHM dy72 lt CHM 7quot 7 d96711 7quot gt z E BT Thus if y E BTW 35 st Bsy C BTW7 and therefore BTW is open Theorem Every open set U C R can be expressed as a countable disjoint union of open intervals of the form 17 where a is allowed to take on the value foo and b is allowed to take on the vaule 00 Prooflf U g 007 then the statement is vacuously true If U is not empty7 Vm E U de ne am mfa aw C U7 b1 supb Lb C U Then Ix ahbm is a possibly unbounded open interval7 containing X It is maximal in the following sense suppose b1 6 U7 then by construction above 3 C U7 an open interval st b1 6 J You can prove for yourself that the union of two open intervals with non empty intersection is in fact7 an open interval you just have to take care of a number of base cases for endpoints 11 We then have that IE U J is an open interval containing X and moreover since J is open and b1 6 J Elf E J st b gt bx But then b E b Lb C U which contradicts b1 being the suprernurn of such a set Thereofre b1 U and similarly am U Now let Ly E U and suppose IE 7 31 Then once again Ix UIy is an open interval containing both z and y and by rnaxirnality we have Ix Ix UIy Iy Thus we conclude that VLy E U either Ix 1 or the two intervals are disjoint So U is a disjoint union of open intervals To show that the union is countable pick a rational number in each interval Since the intervals are disjoint the numbers are distinct and their collection is countable since rationals are countable A few more de nitions are in order As before S is some subset of a metric space M The closure of S is S KD where K0 is the collection of all closed sets that contain S The interior of S is intS UUa where U0 is the collection of all open sets contained in S Finally the boundary of S is 3S S S0 For example if MR and Sab then S ab intS ab and 3S a U b If SQ then S R intS Q and 3S R Notice that the closure of a closed set S is S istelf and so is the interior of an open set S Also notice that both S and 3S are closed as intersections of closed sets and intS is open as a union of open sets Theorem Slirn S Proof We have shown before that lirn S is a closed set also since each point of S is also a limit of point of S its the limit of a sequence 555 we have S Clirn S and we conclude that S Clirn S Also since S C S and S is closed it must contain all the limit 12 points of S thus lim S C S We conclude that S lim S You may check for yourself at this point that every subset of a discrete metric space M for example N with discrete metric is clopen why would it suf ce to show that a singleton z is open and that therefore VS C M intS S S and 3S g A subset S of a metric space M is said to cluster at point z E M if V7quot gt 0 Bz contains in nitely many points of S S is said to condense at x if each BTW contains uncountably many points of S For example if MR then every point of S ab is a condensation point also a cluster point and no other point is a cluster point If S1n n E Nthen the only cluster point is 0 S and no point is a condensation point no point could have uncountably many members of S in its r neighborhood since S itself is count able lf SQ then x is a cluster point of S Vm E R An open interval ab is an example of a subset of R that contains some but not all of its clustercondensation points Finally N with either discrete metric or with the metric it inherits as subset of R has no cluster points We emphasize that if x is a cluster point of S each r neighborhood of x must contain in nitely many distinct points of S It is easy to see that x is a cluster point of S iff 3xn a sequence of distinct points in S st xn a x We denote the set of all cluster points of S by S Theorem SU S S S is closed iff S C S Proof We already know that S C S Moreover by above we have that a cluster point is a limit point and therefore S Clim S S Thus S U S C S Also if z E S lim S then 13 either z E S or HQ a sequence of distinct points in S7 st xn a 7 but that would make z a cluster point So we have S C S U S and we conclude that S U S S Now7 we know thatSisclosediffSSSUS iffS CS We notice here that if S C R is a bounded from abovebelow7 then its lubglb are its cluster points you can check it for yourself7 and therefore by above theorern belong to the closure of S Thus a closed and bounded subset of R contains both its lub and glb Up to this point7 instead ofjust saying S is open7 or S is closed77 we often said S is open in M7 or S is closed in M7 We can drop the mention of M7 when it is understood what the underlying metric space is7 but we point out that it is essential to the opennessclosedness of S For exarnple7 both Q and the half open interval ab are clopen when considered as metric spaces in their own right Neither one7 of course7 is either open or closed when treated as a subset of R Another example is a set S Q 7W 7T7 a set of all rational numbers in the interval 77n7r As a subset of metric space Q S is both closed if is a sequence in S7 and xn a z E Q then x E S and open check for yourself As a subset of R how ever7 it is neither open if z E S then every neighborhood of z contains some y Q nor closed there are sequences in S converging to 7139 E R The following few theorerns establish the relationship between being openclosed in metric space M and some rnetric subspace N of M that inherits its rnetric from M ie dNxy dMzy We will denote the clousre of set S in M by clMS7 and the closure of S in N by clNS Note that clNS clMS N Theorem If S C N C M7 then S is closed in N iff 3L C M st L is closed in M and 14 SL N Proof Suppose S is closed in N then let L clMS Clearly L is closed in M and L N clNS S since S is closed in N Now suppose that L as in the statement of theorem exists Since L is closed it contains all of its limit points and S L N contains all of its limit points in N therefore S is closed in N Theorem If S C N C M then S is open in N iff 3L C M st L is open in M and SL N ProofNotice that the complement of L N in N is L0 N where L0 si the complement of L in M Now take complements and apply previous theorem A popular way to summarize the preceding two theorems is to say that metric subspace N inherits its opens and closeds from M We also introduce here the notion of boundedness S C M is bounded if Em C M 37 gt 0 st S C BTW ie S is bounded if there7s some point z E M st S is contained in some neighborhood of X For example 711 is bounded in R since its contained in B52 or B20 On the other hand the graph of function f smw is an unbounded subset of R2 although the range of f is a bounded subset of R range 71 In general we say that f is a bounded function if its range is a bounded subset of the target space Theorem Let be a Cauchy sequence in M Then S x E M z xn for some n is bounded In other words7 Cauchy sequences are bounded Proof Let E 1 Then 3N st mm 2 N gt dmzm lt 17 in particular 71 2 N gt dznxN lt1 Now7 let 7 1maxdz12d13d1xN Clearly V1 3 k S N d1xk lt r 71lt 7 For k 2 N7 d1k S dz1zN dzNzk lt 7 711 7 Thus S C BT1 and the sequence is bounded As a consequence of preceding theorern7 all convergent sequences are bounded since convergence irnplies Cauchy 34 Continuous Functions Let M7 N be two metric spaces A function f M a N is continous at z E M if V6 gt 0 36 gt 0 st y E M and dMxy lt 6 gt dNfxfy lt 6 We say that f is continuous on M if its continuous at every x E M Notice that a speci c 6 depends on both z and 6 If the choice of 6 does not depend on X7 then we have the following de nition a function f M a N is uniformly continuous if V6 gt 07 36 gt 0st y E M and dMxy lt 6 gt dNf967 fy lt 6 For exarnple7 function 1X on the interval 01 is continuous note that 0 is outside of the dornain7 but is not uniformly continuous given 6 no matter how small we choose 6 to be7 there are always points Ly in the interval 06 st 7 gt 6 The following theorem provides some alternative characterizations of continous functions Theorem The following de nitions of continuity are equivalent 1 6 6 de nition 2 f M a N is continuous if for each convergent sequence M a z in M7 we have x a f in N Thus continous functions send convergent sequences to convergent sequences7 preserving the limits 3 f M a N is continuous if V closed S C N7 f 1S is closed in M Here f 1 is the notation for preirnage of a set in a target space 4 f M a N is continuous ifV open S C N7 f 1S is open in M Proof 1 gt 2 Suppose f is continuous7 is a sequence in M st xn a x Let E gt 0 be given By 17 we know that 36 gt 0 st dMxy lt 0 gt dNfx7 lt 6 Since xn a z 3L st 71 2 L gt dMzmz lt 6 But that means that n 2 L gt dNfznfx lt 6 and therefore x a 2 gt 3 Let S C N be closed in N7 and let be a sequence in S 1 fquotlS7 st xn a z E M We need to show that z E S l By 2 and by the fact that xn a x we know that x a Since is a sequence in S and S is closed7 we have fx 6 S7 and therefore z E S l 3 gt 4 Let S C N be open in N Then f 1S fquotlS0c7 and since the latter is the complement of a closed set by 37 it is open in M 4 gt 1 Let x E M and E gt 0 be given Then we know that B5fz is open in N and 17 therefore f 1B5f is open in M by 4 Since z E f 1B5fz and f 1B5fz is open 36 gt 0 st B5z C f 1B5f ie dMxy lt 6 gt dNfxfy lt 6 Theorem Composite of continuous functions is continuous Proof Let f M a N and g N a L be continuous and let U C L be open in L and denote h g o f M a L Then g 1U is open in N and f 1g 1U h 1U is open in M by de nition 4 above We conclude that h is continuous by de nition 4 It is worth pointing out that while continuous functions preserve the convergent se quences they in general do not preserve the nonconvergent Cauchy sequences For exam ple the continuous funcion f 01 a R given by f 1z maps the Cauchy sequence 1121314 in 01 to non Cauchy sequence 1234 in R Uniforrn continuity en sures the preservation of Cauchy sequences Theorem Let MN be metric spaces f M a N a uniformly continuous function and a Cauchy sequence in M Then is a Cauchy sequence in N Proof Let E gt 0 be given Then since f is uniformly continuous 36 gt 0 st dMxy lt 6 gt dNfxfy lt 6 Since is Cauchy 3L st 77171 gt L gt dMzmn lt 6 gt dfznfm lt E gt is Cauchy You can show pretty easily that every function de ned on a discrete metric space is 18 uniformly continuous why Example Consistent Estimates ln statistics we usually estimate parameters of interest from the sample we have at hand Suppose that 6 is the estimate based on sample of size n then we say that the estimate is consistent in probability if V 6 gt 0 7 6 gt 6 7 0 as n 7 00 For example the Weak Law of Large Numbers states that if we have a sequence of HD random variables X1X2Xn with expected value M and variance 02 then the sam ple mean 21 X is a consistent estimate of u Moreover if we consider 391 the sequence XlkX2k ZXnk then by applying the Weak Law again we conclude that k 77 iXZk is a consistent estimate of k th moment of X Mk i1 Theorem Suppose 6 is a consistent estimate of 6 and suppose that f is continuous Then n is a consistent estimate of p f6 Proof Suppose not Then for some 6 gt 0 7 f6 gt 6 7a 0 ie for some L gt 0 3 subsequence of st 7 f6 gt 6 gt L Now since f is con tinuous 3 6 gt 0 st 7 6 S 6 gt 7 f6 S 6 and therefore we have that 7 f6 gt 6 gt 7 6 gt 6 Also since 6 is a consistent estimate of 6 we know that 3N st 71 2 N gt 7 6 gt 6 lt L in particular this holds V nk 2 N Combining the last two results with the fact that A gt B gt PA S PB we have nk 2 N gt L lt 7 f6 gt 6 S 7 6 gt 6 lt L which leads to a contradiction 19 Therefore we conclude that n is indeed a consistent estimate of p f0 This result is very useful in general and is the foundation of estimation technique known as Method of Moments Once again suppose we have a sequence of HD random variables X1X2Xn with expected value p and variance 02 We know that X is a consistent estimate of u and by above result we have X2 is a consistent estimate of 2 Then you can prove yourself that v 7 X2 is a consistent estimate of 02 VarX do itl In general if there is a continuous function 6 fu1u2 uk then f 1 2 k is a consistent estimate of 0 Therefore if we can express a parameter of interest as a continuous function of the moments of distribution then applying function to sample moments will give us a consistent estimate of the parameter For example if we are sampling from Nu02 distribution and we have a sample of size n then u M1 and 02 EX2 7 2 M2 7 M12 and therefore A X and 72 Zn 7X2 X 7 X2 are consistent estimates i1 i1 of u and 02 respectively 35 Product Metrics Let M M1 gtlt M2 be the Cartesian product of metric spaces M1 M2 ie M is the set of all points z zhxg st 1 6 M1 and 2 6 M2 For example R2 R gtlt R is the set of all points in the plane How would one de ne a useful metric on this product space Three of the possibilities are listed below 1 dMxy 1dM1 951111 dM2x2y22 dEzy a Euclidean metric 2 dMW madM1 9617y17dM29627y2 dmamWw 20 3 dMW dM117y1dM29 27y2 dsumWw Continuing with our example7 if we took points z 752 and y 711 in R2 then dExy V122 92 157dmmzy maz129 12 and dsumzy 12 9 217 where we use the usual distance metric on R It turns out that in a way7 all these metrics are equivalent Theorem dmmxy S dEW S dsumW S Qdmaszl Proof Some basic arithmetic Theorem Let M M1 gtlt M2 and let Amman be a sequence in M Then xn converges with respect to wrt dmm iff it converges wrt dE iff it converges wrt dsum iff both and converge in M1 and M2 respectively Proof The equivalence of the rst 3 convergences is obvious from previous theorem For example7 suppose converges to some z E ert dmm Let E gt 0 be given7 then 3N st 71 2 N gt dmmwmz lt 62 gt dEm lt dsumwms S 6 The convergence of component sequences is obviously equivalent to convergence wrt dmm ln particular7 if xn a z and yn a y in R 7 then 2 zmyn a z my in R2 Theorem The above results extend to the Cartesian product of n gt 2 metric spaces Proof By induction Theorem R is complete Proof Let be a Cauchy sequence in R wrt any of the above metrics Then each component sequence for k 17 27 37 7m is Cauchy in R by same reasoning as convergence equivalence theorem above7 and since R is complete7 all component sequences converge7 mm converges to some xk Vk therefore M a 17 2 mm 36 Connectedness A metric space M is said to be disconnected if it can be written as a disjoint union of two non empty clopen sets Note that it is suf cient to discover one proper ie 31 g or M itself clopen subset S of M7 since its complement would also have to be clopen and proper hence non empty7 and we7d have M S U 807 where symbol U indicates disjoint union M is said to be connected if it is not disconnected S C M is said to be connected if its connected when considered as metric space in its own right with metric inherited from M7 and is disconnected otherwise For example7 interval 25 is a connected subset of R but 27 5U58 is not Q is also disconnected7 since Q Q 7oo7 7T M Q 7r7 Theorem Suppose M is connected7 and f M a N is a continuous function onto N Then N is connected Proof We note here rst that f M a N is onto if Vy E N 3x 6 M st y fx ie every point in N is image under f of some point in M there could be many points in M all mapping to same point in N Now suppose N is not connected and let S C N be a proper clopen subset then f 1S is a non ernpty since f is onto clopen since f is continuous subset of M and so is f 1Sc resulting in M f 1S U f 1Sc is a disjoint union of proper clopen subsets contradicting the connectedness of M We conclude that N is connected Thus a continuous image of a connected set is connected A discontinuous image of a connected set need not be connected however For example if f R a R sends all negative numbers to 0 and all non negative numbers to 1 then the image is 01 a nite set which is clearly disconnected Of course this example only works if R was connected to begin with Theorem R is connected Proof Suppose R is disconnected Then 3S C R st S is proper and clopen Since S is opein in R we know that S is a countable disjoint union of open intervals Let a b be one of these intervals we know that S is non ernpty since its proper so ab exists We have seen in the proof of the theorem about every open set U in R being the countable disjoint union of open intervals that the endpoints of hte intervals do not belong to U thus a b S Suppose b lt 00 then b is clearly a limit point of of S and b S contradicts S being closed Therefore b 00 and similarly a foo But then S R and S is not proper and we arrive at contradiction Thus R is connected Theorem Open and closed intervals in R are connected Proof Let a7b C R We know that f R a 77r277r2 given by f tan 1x is continuous you can verify that for yourself You are also invited to nd continuous func tion 9 7W277r2 a cab which is easy Then 9 o f is continuous as a composition of continuous functions and therefore 17 b is connected as a continuous image of the connected set R Now7 let 17 C R Then de ne f R a 17 as follows a iflta fa z ifagng b ifxgtb Clearly f is continuous and therefore 17 is connected Theorem Suppose that S04 is a collection of connected sets and that Sa 31 Then S USO is connected Proof Let x E Sa Now suppose that S is disconnected7 S A U Ac7 where A and A0 are disjoint non ernpty clopen subsets of S Now7 z E Sa gt z E SW for some a gt z E S USO gt z E A or z 6 Ac Without loss of generality7 assurne z E A Since each Sa is a subset of S7 Sa inherits its closed and open sets from S Va by the inheritance theorern7 and since z E SW Va we have A Sa is a non ernpty clopen subset of SW Va Since each Sa 24 is connected7 we conclude that A Sa Sa Va and therefore A UA S04 USO S7 contradicting A being a proper subset of S We conclude that S is connected Theorem Let S C M be connected Then S C T C S gt T is connected In particu lar7 the closure of a connected set is connected Proof Suppose T is disconnected7 T A U Ac7 where A and A0 are proper clopen subsets of T By intheritance principle7 A S is a clopen subset of S Since S is connected7 B A S cannot be proper7 therefore either B S or B Without loss of generality7 suppose B g if B S7 just look at C Ac S7 the complement of B in S7 which leads toC SinceA S wehaveSCAcinT ButA andACTCSgt3x A st z is a limit point of S Since A is open7 37 gt 07 st BTW C A But z is a limit point of S and therefore BTW S 31 g gt A Ac 31 o and we arrive at a contradiction We conclude that T is connected Now we introduce the intermediate value property Let f M a R be a func tion Then f is said to have intermediate value property if me E M it is true that if f a lt b fy then V0 6 Lab 32 E M st fz 0 In other words7 if function assumes two distinct values in R then it also has to assume all the values in between to have the intermediate value property Theorem Let M be connected7 and f M a R be continuous Then f has the in termediate value property In particular7 every continuous function f R a R has the 25 intermediate value property Proof Suppose not Then 3xy E M st f a lt b fy and 30 6 Lab st V2 6 M fz 31 0 Let A 70007 and A 0700 Then M B U B07 where B f 1A and B0 f 1A is the complement of B in M Note that z E B and y 6 B07 so B 31 g 31 B0 Since f is continuous7 the preimage of an open set is open and since both A and A are open subsets of R we have that B and B0 are both open7 and therefore also both closed as complements of each other We conclude that M is a disjoint union of non empty clopen sets and is therefore disconnected7 which contradicts our assumption Thus7 we conclude that f has the intermediate value property 37 Compactness We say that S C M is sequentially compact if every sequence in S7 has a conver gent subsequence st znk a z for some z E S For example7 every nite subset S 17x2 xn of a metric space M is compact7 since any sequence in S has to repeat at least one xk in nitely many times7 and that results in existence of at least one convergent subsequence xhxhxk Notice also that the convergent subsequence or indeed the limit need not be unique7 as the example of a sequence 1271271271727 in S 17 2 C N shows Also7 N is not a compact subset of R since the sequence 1273475 does not converge to a point in N Other non compact subsets of R include 01 sequence 17 127 137 does not have a subsequence that would converge to a point in 071 and Q every subsequence of the sequence 37 317 3147 31417 converges to 7139 Q We say that a collection Ua of open subsets of M is an open cover for S C M if Vm E S 304 st z 6 U0 We say that a collection V is a subcover of U0 if VB V U0 for some 04 ie V C Ua We then also say that Ua reduces to V We say that S C M is covering compact if every open cover Ua reduces to nite subcover In other words if were given any open cover for S whatsoever and we can always throw away enough members of it so that were left with only nitely many and they still cover all of S then S is covering compact Note that every subset S of M has at least one open cover namely M since M is open and de nitely covers S this particular open cover is already nite Also in order to see that not all subsets are covering compact consider the cover of 01 C R by open intervals Un 1n1 Clearly Un n E N is an open cover for 01 but you can easily see that it cant be reduced to a nite subcover since in that case we7d be left with Unw Um UM and letting N mazn1n2 nk we observe that Vm E 01N z is not contained in any of Um Um Unk Now let S C M and let Ua be some open cover for S Then if 3A gt 0 st Vm E S BAx C U0 for some 04 we say that A is a Lebesgue number for U0 In other words a Lebesgue number for an open cover of S is some small radius st neighborhood of every point in S of that radius is contained in some member of the cover obviously which member it is depends on the particular point Notice that a given cover for a given set might not have a Lebesgue number For example 01 C R has as one possible cover 01 ie it7s covered by itself Suppose it had Lebesgue number A then pick z E 0 A Since BAx x 7 Ax A contains negative points we have BAx g 01 and thus this 27 neighborhood is not contained in any member of the cover7 leading to contradiction Theorem Every open covering of a sequentially compact S C M has a Lebesgue number Proof Suppose not Let Ua be an open cover for S st VA 3 E S st BM g Ua Va Let An 1717 and xn be as above Then since S is sequentially compact7 has some convergent subsequence a z E S Since U0 is a cover for S7 z E Ua for some a Since Ua is open7 37 gt 0 st BTW C U0 Now7 since znk a x 3N1 st nk 2 N1 gt dwam lt r2 Moreover7 3N2 2 N1 st nk 2 N2 gt AM lt r2 Now pick some an st nN gt N2 Let y 6 BMW xmv7 then dy S dzmv dany lt r2 AnN lt r2r2 7quot We conclude that BAW mm C BTW C Um contrary to our assumption that Vn BM g Ua Va Thus7 every open covering of a sequentically compact set does indeed have a Lebesgue number Theorem S C M is sequentially compact iff it is covering compact Proof Suppose S is covering compact7 but not sequentially compact Then let be a sequence in S st no subsequence of converges to a point in S That implies that V E S 3 gt 0 st BMW contains only nitely many terms of otherwise there7d be a subsequence converging to Now7 BM is an open cover for S and since S is covering compact7 it reduces to a nite subcover BM1 17 BWQZ B and since 7 Tank 28 each member of this subcover contains only nitely many terms of zn we conclude that S contains nitely many terms of xn an obvious contradiction Thus covering compactness implies sequential compactness Now suppose S is sequentially compact and let Ua be some open cover for S We know that Ua has some Lebesgue number A gt 0 Pick 1 6 S and some U1 6 U0 st BAz1 C U1 If S C U1 then we have succeded in reducing Ua to a nite subcover If not then pick uncovered point 2 6 S x E S U10 and U2 st BAz2 C U2 If S C U1 U U2 were done if not we continue picking uncovered points to obtain a sequence of points in S and a sequence Un of members of U0 st BAn C Un and xn E A U10 U20 UK If at some point the sequences terminate if for some N A U1 UUZU UUN then we have reduced Ua to a nite subcover Now suppose the sequences never terminate Then since S is sequentially compact there is some subsequence of st znk a z E S There fore HN st nk 2 N gt dwmw lt A In particular dxNx lt A gt z E BAQN C UN Since UN is open 37 gt 0 st BTW C UN But nk gt N gt znk UN and therefore BTW contains only nitely many terms of mm a clear contradiction to convergence We conclude that in fact Ua reduces to a nite subcover and sequential compactness implies covering compactness S C M is said to be compact if it is sequentiallycovering compact In the proofs of the theorems about compactness that follow we will use whichever de nition of compactness leads to a more direct proof and we will supply two proofs for some of the theorems to give you better understanding of both kinds of compactness Theorem Let 51 C M1 and 2 C M2 be compact Then S Sl gtlt SQ C M1 gtlt M2 M is compact Proof Let mmyn be a sequence in S we avoid here cumbersome notation Then is a sequence in 1 and therefore has some subsequence xnk that converges in 51 Now is then a sequence in 2 and therefore has some subsequence ynkl that converges in SQ Moreover since was a convergent sequence in 1 the subsequence mm is also a convergent sequence in 51 Therefore the sequence mmyn has a convergent subsequence mnklynkl with respect to all product space metrics discussed above since both component sequences converge and we conclude that Cartesian product of two compact sets is compact Theorem The Cartesian product of n compact sets is compact Proof By induction and above theorem Theorem Closed interval ab C R is compact Proof 1 Let be a sequence in ab Consider set C x 6 ab xn lt z only nitely often Clearly a E C and b is an upper bound for C therefore C has a least upper bound x We will show that there is some subsequence of converging to at z Suppose f b then 3N st 71 2 N gt xn b and clearly we have a subsequence converging to b f Now suppose f lt b and no subsequence converges to f then 3 b 7 f gt r gt 0 st xn E Brz f 7 hf 7quot only nitely often But then f r E C 30 note that f 7 6 1 bl7 contradiction to f being the lub for C We conclude that in fact there is some subsequence converging to f and therefore 17 is a compact subset of R Proof 2 Let Ua be some open cover for 17 and consider set C x E 1 b nitely many Ua would suf ce to cover the interval az Clearly a E C and b is an upper bound7 therefore 0 has the lub Suppose f lt b7 and let Ua17Ua27H U be those nitely many members of U0 that suf ce to cover mf Then f E UM for some k not neces sarily unique7 and since UM is open7 37 gt 0 st Brz f 7 hf r C UM Now Vy E f f 7quot y is covered by same U0417 UM as xi and therefore picking some speci c y we have that nitely many members of Ualpha suf ce to cover my which contradicts f being the lub for C We conclude that f b and therefore nitely many Ua cover 17 and thus 17 is compact Theorem Closed box ahbll gtlt a27b2 gtlt gtlt ambn C R is compact Proof It is a nite Cartesian product of compact sets Theorem Bolzano Weierstrass Any bounded sequence in R has a convergent sub sequence Proof Any bounded sequence in R is contained in some closed box7 and therefore has a subsequence that converges to some point in that box Theorem Suppose M is compact and S C M is closed Then S is compact Proof 1 Let be a sequence in S7 then is also a sequence in M and therefore has a convergent subsequence znk a z E M Since S is closed in M7 we have x 6 S7 and therefore has a subsequence that converges in S We conclude that S is compact Proof 2 Let Ua be some open cover for S7 then since Sc is open7 Ua USc is an open cover for M and since M is compact7 it reduces to a nite subcover for M and therefore it is a nite cover for S Now there are two possibilities First7 Sc might not be a member of this nite subcover7 then we have reduced Ua to a nite subcover for S Now7 suppose Sc is a member of the nite subcover we found ourselves with7 then it is obvious that the rest of the nite subcover still covers S since no element of S is contained in S0 and by excluding S0 we are left with the nite subcover for S to which the original cover U0 is now reduced We conclude that S is compact Theorem Compact set S C M is closed and bounded Proof Suppose S is not closed7 then HQ a sequence in S st xn a z S Since S is compact7 3 some subsequence znk a f 6 S7 but since is a convergent sequence in M7 all of its subsequences converge to the same limit in M7 and we have that znk a x and by uniqueness of limits we have x f 6 S7 a contradiction to z not being in S So S is closed Now let x E M and suppose S is not bounded Then V71 6 N Hzn E S st dzxn gt 71 Since S is compact7 3 some subsequence of a sequence in S7 st znk a f E S Since all convergent sequences are bounded7 for some 7 gt 0 and for some y E M for example 32 f we have znk E By Vnk Now let T dzy We observe that by the property 3 of the metric we have dnk S dy dyxnk S W r contradictory to the fact that dnk a 00 as nk a 00 We conclude that S is in fact bounded The converse to that statement every closed and bounded subset of a metric space is compact is not true in general For example let M N with discrete metric Then M is a closed and bounded subset of itself x E B21Vx E M but the sequence 1234 in M has no convergent subsequence and therefore M is not compact The converse is however true in R and a more general converse will be provided again later Theorem HeineBorel Every closed and bounded S C R is compact Proof Since S is bounded it is contained in some closed box in R and is therefore a closed subset of a compact set We conclude that S is compact We will now proceed to construct a more general converse statement We start by intro ducing a new notion S C M is said to be totally bounded if V6 gt 0 there exists a nite covering of S by e neighborhoods Notice that this de nition is different from the de nition of non total boundedness given earlier Theorem Let M be a complete metric space Then S C M is compact iff S is closed and totally bounded Proof Suppose S C M is compact We have already shown that S has to be closed 33 Now let 6 gt 0 be given and consider the following open cover for S B5x z E S Since S is compact the cover reduces to a nite subcover and we have a nite covering of S by e neighborhoods and we conclude that S is totally bounded Now suppose S C M is closed and totally bounded Let be a sequence in S Let 6 171 V71 Since S is totally bounded we have a nite covering for S by el neighborhoods B51y11B51y12B5y1m1 for some y11y12y1m1 E M Then at least one of these neighborhoods contains in nitely many terms of the sequence zn suppose B5y1k1 and let N1 be st xN E B51y1k1 Now since every subset of a totally bounded set is totally bounded you can easily show it we have a nite covering of B51y1k1 by 62 neighborhoods B52y21 B52y22 Bgzy2m2 and once again one of these neighborhoods contains in nitely many terms of the sequence zn suppose B52y2k2 and let N2 gt N1 be st zN2 E B52y2k2 Continuing in this manner we obtain a subsequence mm which is Cauchy since nm gt N gt danan lt 61w 1N Since M is complete sz a z E M Since S is closed in M x E S Thus has a subsequence that converges to a limit in S and we conclude that S is compact We note here that the conditions speci ed are indeed necessary Take cornpleteness for example Consider S Q 77T a subset of a metric space Q with the usual distance rnetric Then S is closed and totally bounded subset of Q but its clearly not cornpact since sequence 3 31 314 315 in S doesnt have a subsequence that converges to a point in S or even in Q for that matter Also substituting boundedness for total boundedness in the theorem above would not suf ce since we have already seen that a complete metric space N with discrete metric is a closed and bounded non cornpact subset of itself 34 Below are some important results on the behavior of continuous functions on compact sets Theorem The continuous image of a compact set is compact Proof 1 Let f M a N be continuous7 let S C M be compact and let fS C N denote the image of S under f Let be a sequence in fS7 then Vn Hzn E S st x y Since S is compact7 the sequence in S has some convergent subsequence znk a z E S By continuity of f7 we then have that ynk fxnk a fx 6 fS7 and therefore has a subsequence that converges to the limit in fS7 and we conclude that fS is compact Proof 2 Let f M a N be continuous7 let S C M be compact and let fS C N denote the image of S under f Let Ua be an open cover for fS in N Then since f is continuous7 f 1Ua is an open set in M V04 and therefore f 1Ua is an open cover for S in M Since S is compact7 f 1Ua reduces to a nite subscover f 1U1f 1U2 7fquotlUn7 and clearly U17U27 Un is an open cover for fS you can easily see it yourself7 which is a nite subcover of the original cover We conclude that fS is compact Theorem Continuous real valued funciton de ned on a compact set assumes its maxi mum and minimum Proof Let f M a R be continuous and let S C M be compact Then fS C R is closed and bounded7 and we have seen that a closed and bounded subset of R contains its 35 glb and its lub Theorem Every continous function de ned on a compact set is uniformly continuous Proof Let M be compact and f M a N continuous Suppose f is not uniformly con tinuous Then 36 gt 0 st V n gt 0 Bang 6 M st dxmyn lt 6 but dfxnfyn gt 6 Let 6 171 and for each 717 let any 6 M be as above Since M is compact7 the se quence in M has some convergent subsequence Moreover7 the sequence also has some convergent subsequence ynkl a y E M Since xnkl is a subsequence of a convergernt sequence7 it also converges and it converges to the same limit as the mother sequence7 and since dxynkl lt 1nkl7 we can easily see that it also converges to y The continuity of f implies that x a y and fy a y Now7 let N be st nkl 2 N gt dfxnklfy lt 62 and dfynklfy lt 627 then we have nkl 2 N gt dfkl7fynkl S dfkl7fy dfy7fynkl lt 62 62 6 which contradicts our assumption that dfxnfyn gt E V71 We then conclude that f indeed is uniformly continuous 38 More Results on R We introduce some notation rst Given sequence in R we say that limn z E R if xn a z in R We say that limzn oo ifVM gt 0 EN st 71 2 N gt xn gt M And similarly7 limzn foo if VM lt 0 EN st 71 2 N gt xn lt M Here are some examples 36 1 3 31 314 3141 Then limzn 7T 2 2 3 5 7 11 Then limzn 00 3 1 4 9 16 Then limzn 700 4 1 1 2 2 3 3 Then limn does not exist Given a sequence in R we say that M lim supxn if M lim sup We de ne Hoe k2 m lim infn similarly Here are some examples 1 12345 then lim supzn lim inf 00 2 112 123 then lim supzn oo lim infzn 1 3 3313143141 then lim supzn lim infzn 7139 We say that sequence is monotone increasing if n gt m gt xn gt zm The sequence is monotone nondecreasing if n gt m gt xn 2 zm The monotone decreas ing and monotone non increasing sequences are de ned similarly A sequence is said to be monotone if its monotone non increasing or monotone non decreasing note that every monotone increasing sequence is also monotone non decreasing and every monotone de creasing sequences is monotone non increasing so these two classes are also covered by the de nition 1 3 31 314 3141 is monotone increasing 2 1 4 9 16 is monotone decreasing 3 1 2 2 3 3 3 4 4 4 4 is monotone non decreasing 37 4 1 1 1 1 is monotone non decreasing and monotone non increasing 5 1 1 2 1 2 3 1 2 3 4 is not monotone but it has many possible monotone subsequences The following are some basic results about sequences in R 1 Let xn a z E R and let k E R Then yn kxn a kx P Let snaxandynayinR Thenzn xnynazy 9 Let xn a z and yn a y in R Then 2 znyn a xy 7 Let xn ax 7amp0 in R st xny OVn Then yn 1zna1z 9 Let xn a z 31 0 in R st xn 31 0 Vn and let yn a y in R Then 2 ynzn a yz 03 Let limzn oo lim gt 0 Then limzn xnyn oo 5 Let be monotone and bounded Then converges in R 00 Let be any sequence in R Then has a monotone subsequence Together this and the previous result imply that every bounded sequence in R has a convergent subsequence 3 Let be a monotone sequence Then limzn exists it could of course take on values of 00 and foo 0 Let fg be real valued funcitons M a R continuous at some z E M Then f 9 fg and fg asusming g 31 0 are all continuous at x 11 Given a sequence xn7 hm supxn and lim infxn are well de ned either they belong to R or take values of ioo 12 xn a z iff hm supxn hm infxn x The proofs of these results are left as exersises 39 Calculus and Function Convergence We say that a real valued funciton f is differentiable at x if one of the following equivalent conditions holds 1 lim M L exists tax It 7 z 2 lim W L exists AmaO Ax 3Vegt036gt0st lt7llt6 lwi lte We call L the derivative of f at z and write f L We say that f is differentiable on the interval a7b if it is differentialbe at every x 6 17 b The following are familiar results from calculus 1 If f is differentiable at x then f is continuous at x 2 If f and g are differentiable at 7 then so is f g and f g x f z g z 3 If f and g are differentiable at x then so is g7 and fg fgf9 4 If f CV then f OVz 5 If f and g are differentiable at z and g 31 07 then fg is differentiable at z and 7 f 9f9 w 7 my 6 Chain Rule If f is differentiable at 7 and g is differentiable at fx7 then 9 o f is differentiable at z and g 0 f 9ff Theorem Let f be differentiable on cab and suppose it achieves a maximum or mini mum at some 0 6 ab Then f c 0 Proof We will prove the theorem for maximum7 and proof for minimum is analogous ftf0 t7c Let t approach 0 from above Then S 0 Vt If we let t approach 0 from below7 then 250 2 0 Vt Since both expressions have to tend to the same limit L f c7 we conclude that f c 0 Theorem Mean Value Suppose f is continuous on 17 and differentiable on a7b Then 3 c 6 ab st fb 7 fa f cb 7 a In particular7 if lf zl S M V x E 177 thethx 6 ab we have lft 7 S Mlt7l Proof Let S w and let g f 7 Sz Clearly g is differentiable on cab and continuous on 17 why Moreover7 9a gb Since 9 is continuous on a compact set7 it achieves maximum and minimum and since 9a gb it achieves at least one of them at some 0 6 ab Then 0 g c f c 7 S gt fb 7 fa f cb 7 a We state the following result without proof which can be found7 for example in Pugh7 p145 If f is differentiable on 177 then f has the intermediate value property Also7 all familiar results from calculus derivative and integral formulas7 L7Hopital7s Rule7 results on series convergence7 etc hold We say that a sequence of functions fn 17 a R converges pointwise to f fn a f7 if V x E 17 fnz a fx as n a 00 We say that a sequence fn 17 a R converges uniformlyto f fn f ifV E gt 07 3 Nst n 2 N gt lfnx7fxl lt EV E 17 You should convince yourself that the sequence of functions fnz x on open interval 01 converges pointwise to the function 0 if 0 S x lt 1 f 96 1 if z 1 but does not converge uniformly Theorem lf fn f and each fn is continuous at x then f is continuous at x Proof Let E gt 0 be given7 and let N be st 71 2 N gt 7 lt 63 V y Since fN is continuous at x 3 6 gt 0 st lx iyl lt 6 gt lfNx 7 fNyl lt 63 Then ls iyl lt 6 WM 7 fyl S lfm fNl WNW 7 fNyllfNyf1l lt 636363 67 and we conclude that f is continuous at x Note that our example above shows that pointwise convergence of continuous functions is not suf cient to ensure continuity of the limit We state two more results without proving them The proofs can be found in Pugh 1 Suppose fn f7 then fndz a ffxd as n a 00 41 N H P3 9 Suppose fn i f and j 9 then 9 f References Pugh 00 7Real Mathematical Analysis Springer 2002 Rice John A 7Mathematical Statistics and Data Analysis 2nd ed Duxbury Press 1995 Ross Kenneth A 7Elementary Analysis The Theory of Calculus7 Springer 2000 F1 ISIH 10 801119111 991111 3111mm em 91114910 9AA 5amp1 HO sow19W I 81 HOWUHGG I 1 gt ffif Z 51 1 W Z 5 Zlt fifx 13gt Jim 13gt z 31 2 1 Z 2 mf fxmZ M mzxml z 1 1 M 2303 gt ZI 3 ZI 3 5 ffif Z 51 OS V o JOOJd anenbaul ZJBAAqoS quneg 131 BIHIHG I 513 110 sognew uo SEqu annoy Hosmpuvggooz 3119161341701 mew 1 011 Elli ll yjl 12 2 0129573 l9 yl 211 W 339 d00x7y max xj yjl 1739 H Theorem 131 d1 d2 and d00 are all metrics on RI Proof The proofs for d1 and d00 are contained in Problem 131 so we consider only d2 The proofs of the rst two proper ties of a metric are obvious so we only need to prove the triangle inequality 6120957 22 ll 2 m yy m yy Z m yfr y2 yy Zy Zy Z lfJ yIZHCJ yy Zly Z2 S II y2205 ylly Zly Zl2 lfr yl ly 2 012957y 01237 22 d27z S 01295730 012172 Real Analysis July 10 2006 1 Introduction These notes are intended for use in the warm up camp for incoming Berkeley Statistics graduate students Welcome to Call The real analysis review presented here is intended to prepare you for Stat 204 and occasional topics in other statistics courses We will not cover measure theory topics and some other material that you should be very familiar with if you intend to take Stat 205 If you have never taken a real analysis course7 you are strongly encouraged to do so by taking math 104 or the honors version of it Math 105 usually of fered in the spring will provide you with necessary measure theoretical background essential for Stat 205 The presentation follows closely and borrows heavily from 7Real Mathematical Analysis7 by CC Pugh7 the standard textbook for honors version of math 104 The empha sis is on metric space concepts and the pertinent results on the reals are presented as speci c cases of more general results7 and a lot of them are presented together as exersises in section 38 We do not expect you to be familiar with the metric space concepts but we do expect you to be familiar with speci c results on real line7 as that is usually the approach taken in most real analysis courses We hope that you nd these notes helpfull Go Bears 2 Some De nitions We will denote by RQZ and N the sets of all real numbers rational numbers integers and positive integers respectively We will take for granted the familiarity with notions of nite countably in nite and uncountably in nite sets Given a set SC R ME R is an upper bound for S if V5 6 S it is true that s S M S is said to be bounded above by M M is said to be the least upper bound or lub for S if for all upper bounds M it is true that M S M note that it implies that lub is unique The lower bounds and the greatest lower bound glb are de ned sirnilarly For example if S01 then 1 and 4 are upper bounds and 0 4 are lower bounds with 0 and 1 being glb and lub respectively A set is said to be bounded if it is bounded from above and below A set S is said to be unbounded from above if VN 35 E S st 5 gt N The de nition of a set unbounded below is similar A set is unbounded if its either unbounded from above or below The supremum sup of a set S C R is de ned to be lub for S if S is bounded from above and to be 00 otherwise The in num inf is de ned to be glb for a set bounded form below and to be foo otherwiseThe following results will be assumed about R proofs can be looked up in any analysis textbook 1 If S C R is bounded from abovebelow then the lubglb for S exists and is unique 2 Triangle Inequality lx yl S 3 6principle lf Xy E R and V6 gt 0 x S y 6 then x S y Also if V6 gt 0 lx iyl S 6 then Xy 4 Every interval a7b contains countably in nitely many rationals and uncountably in nitely many irrationals 3 Metric Spaces 31 De nition A metric space M is a set of elements together with a function dM gtlt M a R known as metric that satis es the following 3 properties For all X7 y7 Z 6 M 1 dXy2 0 and dXy0 iff Xy 2 dX7y dy7x 3 dxy S dxz dzy When metric d is understood7 we refer to M as the metric space When we want to specify that the metric is in M 7 we might use notation dMxy It also helps sometimes to think of d as the distance function7 since it makes the 3 properties more intuitive we usually think of distance as being nonnegative7 and the distance from A to B should be the same as the distance from B to A Here are some examples 1 R with usual distance function dxy ix 7 yl 2 Q with the same metric 3 R with Euclidean distance dxy 7 4 Any metric space for ex R or N with the discrete metric dXy1 if z 31 y dxy 0 otherwise This metric makes the distance from a point to itself be 0 and the distance between any two distinct points be 1 You should check for yourself that the metrics above satisfy the 3 conditions 32 Sequences We will use the notation for the sequence of points 12 x in metric space M The members of a sequence are not assumed to be distinct thus 1111 is a legit imate sequence of points in Q A sequence is a subsequence of if there exists sequence 1 S 711 lt 712 lt 713 lt st yk mm Some subsequences of the sequence 112123123412345 are 1 twos22222 77777quot39 E0 odds 1357 9 9 primes 235711 7 original sequence with duplicates removed 1234567 U the previous subsequence with rst 3 elements removed 4567 A sequence of points in M is said to converge to the limit X in M if V6 gt 0 3 N st 71 2 N gt dznx lt 6 We then say that M a x Notice that if our metric space is R then replacing dx m by the usual metric lznizl gives the familiar de nition of a limit Theorem The limit of a sequence7 if it exists7 is unique Proof Let be a sequence in M that converges and suppose its limit is not unique Let Xy denote two of possibly even more limits Let E gt 0 be given Then 3N1 st 71 2 N1 gt dznx lt 62 Similarly 3N2 st 71 2 N2 gt dxny lt 62 Let N mazN1N27 and let n 2 N Then by the 3rd property of metric function 6196711 dawn dxny lt 62 62 6 Since this is true for every 6 we have Xy by the 6 principle Theorem Every subsequence of a convergent sequence converges7 and it converges to the same limit as the original sequence Proof Easy A sequence in M is said to be Cauchy if V6 gt 0 EN st 717 m 2 N gt dzn7 zm lt 6 In other words a sequence is Cauchy if eventually all the terms are all very close to each other Theorem Every convergent sequence is Cauchy Proof Suppose xn a z in M Let E gt 0 be given Then 3N st 71 2 N gt dzmz lt 62 Let mm 2 N Then dznxm S dznz dxm lt 62 62 lt E gt is Cauchy Does every Cauchy sequence converge to a limit Consider the sequence 3 314 3141 31415 This sequence is clearly Cauchy When considered as a sequence in R it does converge to 7139 However we can also think of it as a sequence in Q in which case it doesnt converge since 7139 Q The following de nition formalizes the difference between Q and R the metric space M is said to be complete if all Cauchy sequences in M converge to a limit in M Theorem R is complete Proof Let an be a Cauchy sequence in R and let A be the set of elements of the sequence ie AxER3nENandanx Let 61 Then since an is Cauchy 3N1 st Vnm 2 N1 lan7aml lt 1 Therefore V71 2 N1 we have lan 7 aNl lt1 and thus 71 2 N1 gt an E aN171aN11 The nite set 11 a2 11111 7 1aN1 1 is bounded as is every nite subset of R and therefore all of its elements belong to some interval 7LL Since both IN 7 1aN1 1 6 7L L we conclude that 0N1 71aN1 1 C 7LL and therefore an E 7LL Vn and A is bounded Now consider set S s E 7L7 L 3 in nitely many 71 E N for which an 2 s Obviously7 7L E S and S is bounded from above by L We then know that the lub for S exists call it b We will show that an 7 b Let 6 gt 0 be given Then since an is Cauchy7 3N2 st mm 2 N2 gt lan 7 aml lt 62 Since V5 6 S7 5 3 b7 we have that b 62 S That means that an exceeds b 62 only nitely often and 3N3 2 N2 st 71 2 N3 gt an S b 62 Since b is the least upper bound for S we have that b 7 62 is not an upper bound for S and therefore 35 E S st 5 gt b 7 62 and an 2 s gt b 7 62 in nitely often In particular that gurantees that there exists some N4 2 N3 st 1M gt b7 62 Moreover7 since N4 2 N3 we have 1M 6 b7 62b 62 And since N4 gt N2 we get 71 2 N4 gt lan7bl S lan7aN4llaN47bl lt6262 lt6 and therefore an 7 b It is an easy exersise to show that every discrete metric space for exarnple7 N with dis crete metric is complete 33 Open and Closed Sets Let M be a metric space and let S be a subset of M We say that z E M is a limitpoint of S note that S is not a sequence here7 but a subset of M if there exists a sequence in S st xn 7 x For exarnple7 let M R and SQ Then 2 is an example of a limit point of S 7 2 2222 or 1 1 12 1 23 1 34 that belongs to S and 7139 is a an example of a limit point of S 331314314131415 that does not belong to S of course it still belongs to A set is said to be closed in underlying metric space M if it contains all of its limits For example a singleton set x is closed in M assuming M is non empty since the only possible sequence is xxx a x Clearly M is a closed subset of itself A set S is said to be open in underlying mertric space M if Vm E S 37 gt 0 st dxy lt r gt y E S The set of points y E M dxy lt r is called open r neighborhood of x and is denoted Bz for example B25 in R is simply the open interval 37 Thus a set S is open in M if for every point in S there exists some small neighborhood of that point in M contained entirely in S Its easy to see that interval ab is an open set in R and clearly every metric space M is an open subset of itself since every r neighborhood of x is still in The following theorem provides a connection between open and closed sets Theorem The compliment of an open set is closed and the compliment of a closed set is open ProofSuppose S C M is open Suppose xn a z in M and moreover xn E S0 V71 We need to show that z 6 SC Suppose not then x E S Since S is open 37 gt 0 st dy lt r gt y E S Now since xn a z 3N st 71 2 N gt dznz lt r gt xn E S That is clearly impossible since no point could be in both S and Sc and we have reached a condtradiction Therefore Sc is closed Now suppose that S C M is closed Suppose Sc is not open then Hm E S0 st V73 gt 0 3 8 st dzn lt Tn but xn E S Now let Tn 171 and pick xn as above Then xn E S Vn and xn a z 6 SC gt S is not closed since it fails to contain all of its limits gt contradiction Therefore Sc is open Notice that some sets like the space M itself are both closed and open7 they are referred to as clopen sets By theorern above7 MC g is clopen Now consider interval 01 C R It is neither open every r neighborhood of 0 includes points in 0710 C R nor closed it fails to include 17 which is the limit of the sequence xn 1 7 171 in 07 Thus subsets of a metric space can be open7 closed7 both7 or neither Theorem Arbitrary union of open sets is open Proof Suppose Uais a collection of open sets in M7 and let U UUD Then z E U gt z E Ua for some 04 and 37 gt 0 st dy lt r gt y E Ua gt y E U Therefore U is open Theorem Intersection of nitely many open sets is open Proof Suppose U17U2 Un are open sets in M Let U Uk If U g then U is open Now suppose z 6 U7 then x 6 Uk for k 172737 n Since each Uk is open7 37 gt 0 st dxy lt rk gt y 6 Uk Let r mmr1r2rn then dy lt r gt y 6 Uk Vk gt y E U Therefore U is open Notice that the in nite intersection of open sets is not necessarily open For example its easy to see that Uk flk 1k is an open subset of R but Uk 0 is clearly not open in R TheoremArbitrary intersection of closed sets is closed Also nite union of closed sets is closed Proof well use DeMorgan7s Laws UUkc Ukc Let K0 be a collection of closed sets in M Then Ka UKjf and since each Kac is open their union is open and its complement is closed The proof of the second part of the theorem is similar Notice that the in nite union of closed sets is not guaranteed to be closed For example even though each Kk 01 7 1k is closed in R the intersection UKk 01 is not TheoremLet M be a complete metric space N C M be closed Then N is complete as a metric space in its own right Proof Let be a Cauchy sequence in N Since is also a Cauchy sequence in M and M is complete we have xn a z E M But N is closed in M therefore z E N and we conclude that N is complete Let lim S denote the set of all limit points of S in M It is pretty clear that z 6 lim S ltgt V7quot gt 0 BTW S 31 g you can easily prove it as an exersise We can also show that lim S is a closed set Let E gt 0 be given and let be a sequence of points in lim S st 10 yn a y in M Then 3N st 71 2 N gt dyny lt 62 Since each yn 6 lim S7 Hzn E S st dynn lt 62 Vn Then we have n 2 N gt dzmy S dzmyn Gibmy lt E2 E2 6 Therefore xn a y and y 6 lim S We conclude that lim S is closed We can also show that BTW is an open subset of M as follows let y E BTW Let s r 7 dy gt 0 Then dyz lt s gt d2796 S CHM dy72 lt CHM 7quot 7 d96711 7quot gt z E BT Thus if y E BTW 35 st Bsy C BTW7 and therefore BTW is open Theorem Every open set U C R can be expressed as a countable disjoint union of open intervals of the form 17 where a is allowed to take on the value foo and b is allowed to take on the vaule 00 Prooflf U g 007 then the statement is vacuously true If U is not empty7 Vm E U de ne am mfa aw C U7 b1 supb Lb C U Then Ix ahbm is a possibly unbounded open interval7 containing X It is maximal in the following sense suppose b1 6 U7 then by construction above 3 C U7 an open interval st b1 6 J You can prove for yourself that the union of two open intervals with non empty intersection is in fact7 an open interval you just have to take care of a number of base cases for endpoints 11 We then have that IE U J is an open interval containing X and moreover since J is open and b1 6 J Elf E J st b gt bx But then b E b Lb C U which contradicts b1 being the suprernurn of such a set Thereofre b1 U and similarly am U Now let Ly E U and suppose IE 7 31 Then once again Ix UIy is an open interval containing both z and y and by rnaxirnality we have Ix Ix UIy Iy Thus we conclude that VLy E U either Ix 1 or the two intervals are disjoint So U is a disjoint union of open intervals To show that the union is countable pick a rational number in each interval Since the intervals are disjoint the numbers are distinct and their collection is countable since rationals are countable A few more de nitions are in order As before S is some subset of a metric space M The closure of S is S KD where K0 is the collection of all closed sets that contain S The interior of S is intS UUa where U0 is the collection of all open sets contained in S Finally the boundary of S is 3S S S0 For example if MR and Sab then S ab intS ab and 3S a U b If SQ then S R intS Q and 3S R Notice that the closure of a closed set S is S istelf and so is the interior of an open set S Also notice that both S and 3S are closed as intersections of closed sets and intS is open as a union of open sets Theorem Slirn S Proof We have shown before that lirn S is a closed set also since each point of S is also a limit of point of S its the limit of a sequence 555 we have S Clirn S and we conclude that S Clirn S Also since S C S and S is closed it must contain all the limit 12 points of S thus lim S C S We conclude that S lim S You may check for yourself at this point that every subset of a discrete metric space M for example N with discrete metric is clopen why would it suf ce to show that a singleton z is open and that therefore VS C M intS S S and 3S g A subset S of a metric space M is said to cluster at point z E M if V7quot gt 0 Bz contains in nitely many points of S S is said to condense at x if each BTW contains uncountably many points of S For example if MR then every point of S ab is a condensation point also a cluster point and no other point is a cluster point If S1n n E Nthen the only cluster point is 0 S and no point is a condensation point no point could have uncountably many members of S in its r neighborhood since S itself is count able lf SQ then x is a cluster point of S Vm E R An open interval ab is an example of a subset of R that contains some but not all of its clustercondensation points Finally N with either discrete metric or with the metric it inherits as subset of R has no cluster points We emphasize that if x is a cluster point of S each r neighborhood of x must contain in nitely many distinct points of S It is easy to see that x is a cluster point of S iff 3xn a sequence of distinct points in S st xn a x We denote the set of all cluster points of S by S Theorem SU S S S is closed iff S C S Proof We already know that S C S Moreover by above we have that a cluster point is a limit point and therefore S Clim S S Thus S U S C S Also if z E S lim S then 13 either z E S or HQ a sequence of distinct points in S7 st xn a 7 but that would make z a cluster point So we have S C S U S and we conclude that S U S S Now7 we know thatSisclosediffSSSUS iffS CS We notice here that if S C R is a bounded from abovebelow7 then its lubglb are its cluster points you can check it for yourself7 and therefore by above theorern belong to the closure of S Thus a closed and bounded subset of R contains both its lub and glb Up to this point7 instead ofjust saying S is open7 or S is closed77 we often said S is open in M7 or S is closed in M7 We can drop the mention of M7 when it is understood what the underlying metric space is7 but we point out that it is essential to the opennessclosedness of S For exarnple7 both Q and the half open interval ab are clopen when considered as metric spaces in their own right Neither one7 of course7 is either open or closed when treated as a subset of R Another example is a set S Q 7W 7T7 a set of all rational numbers in the interval 77n7r As a subset of metric space Q S is both closed if is a sequence in S7 and xn a z E Q then x E S and open check for yourself As a subset of R how ever7 it is neither open if z E S then every neighborhood of z contains some y Q nor closed there are sequences in S converging to 7139 E R The following few theorerns establish the relationship between being openclosed in metric space M and some rnetric subspace N of M that inherits its rnetric from M ie dNxy dMzy We will denote the clousre of set S in M by clMS7 and the closure of S in N by clNS Note that clNS clMS N Theorem If S C N C M7 then S is closed in N iff 3L C M st L is closed in M and 14 SL N Proof Suppose S is closed in N then let L clMS Clearly L is closed in M and L N clNS S since S is closed in N Now suppose that L as in the statement of theorem exists Since L is closed it contains all of its limit points and S L N contains all of its limit points in N therefore S is closed in N Theorem If S C N C M then S is open in N iff 3L C M st L is open in M and SL N ProofNotice that the complement of L N in N is L0 N where L0 si the complement of L in M Now take complements and apply previous theorem A popular way to summarize the preceding two theorems is to say that metric subspace N inherits its opens and closeds from M We also introduce here the notion of boundedness S C M is bounded if Em C M 37 gt 0 st S C BTW ie S is bounded if there7s some point z E M st S is contained in some neighborhood of X For example 711 is bounded in R since its contained in B52 or B20 On the other hand the graph of function f smw is an unbounded subset of R2 although the range of f is a bounded subset of R range 71 In general we say that f is a bounded function if its range is a bounded subset of the target space Theorem Let be a Cauchy sequence in M Then S x E M z xn for some n is bounded In other words7 Cauchy sequences are bounded Proof Let E 1 Then 3N st mm 2 N gt dmzm lt 17 in particular 71 2 N gt dznxN lt1 Now7 let 7 1maxdz12d13d1xN Clearly V1 3 k S N d1xk lt r 71lt 7 For k 2 N7 d1k S dz1zN dzNzk lt 7 711 7 Thus S C BT1 and the sequence is bounded As a consequence of preceding theorern7 all convergent sequences are bounded since convergence irnplies Cauchy 34 Continuous Functions Let M7 N be two metric spaces A function f M a N is continous at z E M if V6 gt 0 36 gt 0 st y E M and dMxy lt 6 gt dNfxfy lt 6 We say that f is continuous on M if its continuous at every x E M Notice that a speci c 6 depends on both z and 6 If the choice of 6 does not depend on X7 then we have the following de nition a function f M a N is uniformly continuous if V6 gt 07 36 gt 0st y E M and dMxy lt 6 gt dNf967 fy lt 6 For exarnple7 function 1X on the interval 01 is continuous note that 0 is outside of the dornain7 but is not uniformly continuous given 6 no matter how small we choose 6 to be7 there are always points Ly in the interval 06 st 7 gt 6 The following theorem provides some alternative characterizations of continous functions Theorem The following de nitions of continuity are equivalent 1 6 6 de nition 2 f M a N is continuous if for each convergent sequence M a z in M7 we have x a f in N Thus continous functions send convergent sequences to convergent sequences7 preserving the limits 3 f M a N is continuous if V closed S C N7 f 1S is closed in M Here f 1 is the notation for preirnage of a set in a target space 4 f M a N is continuous ifV open S C N7 f 1S is open in M Proof 1 gt 2 Suppose f is continuous7 is a sequence in M st xn a x Let E gt 0 be given By 17 we know that 36 gt 0 st dMxy lt 0 gt dNfx7 lt 6 Since xn a z 3L st 71 2 L gt dMzmz lt 6 But that means that n 2 L gt dNfznfx lt 6 and therefore x a 2 gt 3 Let S C N be closed in N7 and let be a sequence in S 1 fquotlS7 st xn a z E M We need to show that z E S l By 2 and by the fact that xn a x we know that x a Since is a sequence in S and S is closed7 we have fx 6 S7 and therefore z E S l 3 gt 4 Let S C N be open in N Then f 1S fquotlS0c7 and since the latter is the complement of a closed set by 37 it is open in M 4 gt 1 Let x E M and E gt 0 be given Then we know that B5fz is open in N and 17 therefore f 1B5f is open in M by 4 Since z E f 1B5fz and f 1B5fz is open 36 gt 0 st B5z C f 1B5f ie dMxy lt 6 gt dNfxfy lt 6 Theorem Composite of continuous functions is continuous Proof Let f M a N and g N a L be continuous and let U C L be open in L and denote h g o f M a L Then g 1U is open in N and f 1g 1U h 1U is open in M by de nition 4 above We conclude that h is continuous by de nition 4 It is worth pointing out that while continuous functions preserve the convergent se quences they in general do not preserve the nonconvergent Cauchy sequences For exam ple the continuous funcion f 01 a R given by f 1z maps the Cauchy sequence 1121314 in 01 to non Cauchy sequence 1234 in R Uniforrn continuity en sures the preservation of Cauchy sequences Theorem Let MN be metric spaces f M a N a uniformly continuous function and a Cauchy sequence in M Then is a Cauchy sequence in N Proof Let E gt 0 be given Then since f is uniformly continuous 36 gt 0 st dMxy lt 6 gt dNfxfy lt 6 Since is Cauchy 3L st 77171 gt L gt dMzmn lt 6 gt dfznfm lt E gt is Cauchy You can show pretty easily that every function de ned on a discrete metric space is 18 uniformly continuous why Example Consistent Estimates ln statistics we usually estimate parameters of interest from the sample we have at hand Suppose that 6 is the estimate based on sample of size n then we say that the estimate is consistent in probability if V 6 gt 0 7 6 gt 6 7 0 as n 7 00 For example the Weak Law of Large Numbers states that if we have a sequence of HD random variables X1X2Xn with expected value M and variance 02 then the sam ple mean 21 X is a consistent estimate of u Moreover if we consider 391 the sequence XlkX2k ZXnk then by applying the Weak Law again we conclude that k 77 iXZk is a consistent estimate of k th moment of X Mk i1 Theorem Suppose 6 is a consistent estimate of 6 and suppose that f is continuous Then n is a consistent estimate of p f6 Proof Suppose not Then for some 6 gt 0 7 f6 gt 6 7a 0 ie for some L gt 0 3 subsequence of st 7 f6 gt 6 gt L Now since f is con tinuous 3 6 gt 0 st 7 6 S 6 gt 7 f6 S 6 and therefore we have that 7 f6 gt 6 gt 7 6 gt 6 Also since 6 is a consistent estimate of 6 we know that 3N st 71 2 N gt 7 6 gt 6 lt L in particular this holds V nk 2 N Combining the last two results with the fact that A gt B gt PA S PB we have nk 2 N gt L lt 7 f6 gt 6 S 7 6 gt 6 lt L which leads to a contradiction 19 Therefore we conclude that n is indeed a consistent estimate of p f0 This result is very useful in general and is the foundation of estimation technique known as Method of Moments Once again suppose we have a sequence of HD random variables X1X2Xn with expected value p and variance 02 We know that X is a consistent estimate of u and by above result we have X2 is a consistent estimate of 2 Then you can prove yourself that v 7 X2 is a consistent estimate of 02 VarX do itl In general if there is a continuous function 6 fu1u2 uk then f 1 2 k is a consistent estimate of 0 Therefore if we can express a parameter of interest as a continuous function of the moments of distribution then applying function to sample moments will give us a consistent estimate of the parameter For example if we are sampling from Nu02 distribution and we have a sample of size n then u M1 and 02 EX2 7 2 M2 7 M12 and therefore A X and 72 Zn 7X2 X 7 X2 are consistent estimates i1 i1 of u and 02 respectively 35 Product Metrics Let M M1 gtlt M2 be the Cartesian product of metric spaces M1 M2 ie M is the set of all points z zhxg st 1 6 M1 and 2 6 M2 For example R2 R gtlt R is the set of all points in the plane How would one de ne a useful metric on this product space Three of the possibilities are listed below 1 dMxy 1dM1 951111 dM2x2y22 dEzy a Euclidean metric 2 dMW madM1 9617y17dM29627y2 dmamWw 20 3 dMW dM117y1dM29 27y2 dsumWw Continuing with our example7 if we took points z 752 and y 711 in R2 then dExy V122 92 157dmmzy maz129 12 and dsumzy 12 9 217 where we use the usual distance metric on R It turns out that in a way7 all these metrics are equivalent Theorem dmmxy S dEW S dsumW S Qdmaszl Proof Some basic arithmetic Theorem Let M M1 gtlt M2 and let Amman be a sequence in M Then xn converges with respect to wrt dmm iff it converges wrt dE iff it converges wrt dsum iff both and converge in M1 and M2 respectively Proof The equivalence of the rst 3 convergences is obvious from previous theorem For example7 suppose converges to some z E ert dmm Let E gt 0 be given7 then 3N st 71 2 N gt dmmwmz lt 62 gt dEm lt dsumwms S 6 The convergence of component sequences is obviously equivalent to convergence wrt dmm ln particular7 if xn a z and yn a y in R 7 then 2 zmyn a z my in R2 Theorem The above results extend to the Cartesian product of n gt 2 metric spaces Proof By induction Theorem R is complete Proof Let be a Cauchy sequence in R wrt any of the above metrics Then each component sequence for k 17 27 37 7m is Cauchy in R by same reasoning as convergence equivalence theorem above7 and since R is complete7 all component sequences converge7 mm converges to some xk Vk therefore M a 17 2 mm 36 Connectedness A metric space M is said to be disconnected if it can be written as a disjoint union of two non empty clopen sets Note that it is suf cient to discover one proper ie 31 g or M itself clopen subset S of M7 since its complement would also have to be clopen and proper hence non empty7 and we7d have M S U 807 where symbol U indicates disjoint union M is said to be connected if it is not disconnected S C M is said to be connected if its connected when considered as metric space in its own right with metric inherited from M7 and is disconnected otherwise For example7 interval 25 is a connected subset of R but 27 5U58 is not Q is also disconnected7 since Q Q 7oo7 7T M Q 7r7 Theorem Suppose M is connected7 and f M a N is a continuous function onto N Then N is connected Proof We note here rst that f M a N is onto if Vy E N 3x 6 M st y fx ie every point in N is image under f of some point in M there could be many points in M all mapping to same point in N Now suppose N is not connected and let S C N be a proper clopen subset then f 1S is a non ernpty since f is onto clopen since f is continuous subset of M and so is f 1Sc resulting in M f 1S U f 1Sc is a disjoint union of proper clopen subsets contradicting the connectedness of M We conclude that N is connected Thus a continuous image of a connected set is connected A discontinuous image of a connected set need not be connected however For example if f R a R sends all negative numbers to 0 and all non negative numbers to 1 then the image is 01 a nite set which is clearly disconnected Of course this example only works if R was connected to begin with Theorem R is connected Proof Suppose R is disconnected Then 3S C R st S is proper and clopen Since S is opein in R we know that S is a countable disjoint union of open intervals Let a b be one of these intervals we know that S is non ernpty since its proper so ab exists We have seen in the proof of the theorem about every open set U in R being the countable disjoint union of open intervals that the endpoints of hte intervals do not belong to U thus a b S Suppose b lt 00 then b is clearly a limit point of of S and b S contradicts S being closed Therefore b 00 and similarly a foo But then S R and S is not proper and we arrive at contradiction Thus R is connected Theorem Open and closed intervals in R are connected Proof Let a7b C R We know that f R a 77r277r2 given by f tan 1x is continuous you can verify that for yourself You are also invited to nd continuous func tion 9 7W277r2 a cab which is easy Then 9 o f is continuous as a composition of continuous functions and therefore 17 b is connected as a continuous image of the connected set R Now7 let 17 C R Then de ne f R a 17 as follows a iflta fa z ifagng b ifxgtb Clearly f is continuous and therefore 17 is connected Theorem Suppose that S04 is a collection of connected sets and that Sa 31 Then S USO is connected Proof Let x E Sa Now suppose that S is disconnected7 S A U Ac7 where A and A0 are disjoint non ernpty clopen subsets of S Now7 z E Sa gt z E SW for some a gt z E S USO gt z E A or z 6 Ac Without loss of generality7 assurne z E A Since each Sa is a subset of S7 Sa inherits its closed and open sets from S Va by the inheritance theorern7 and since z E SW Va we have A Sa is a non ernpty clopen subset of SW Va Since each Sa 24 is connected7 we conclude that A Sa Sa Va and therefore A UA S04 USO S7 contradicting A being a proper subset of S We conclude that S is connected Theorem Let S C M be connected Then S C T C S gt T is connected In particu lar7 the closure of a connected set is connected Proof Suppose T is disconnected7 T A U Ac7 where A and A0 are proper clopen subsets of T By intheritance principle7 A S is a clopen subset of S Since S is connected7 B A S cannot be proper7 therefore either B S or B Without loss of generality7 suppose B g if B S7 just look at C Ac S7 the complement of B in S7 which leads toC SinceA S wehaveSCAcinT ButA andACTCSgt3x A st z is a limit point of S Since A is open7 37 gt 07 st BTW C A But z is a limit point of S and therefore BTW S 31 g gt A Ac 31 o and we arrive at a contradiction We conclude that T is connected Now we introduce the intermediate value property Let f M a R be a func tion Then f is said to have intermediate value property if me E M it is true that if f a lt b fy then V0 6 Lab 32 E M st fz 0 In other words7 if function assumes two distinct values in R then it also has to assume all the values in between to have the intermediate value property Theorem Let M be connected7 and f M a R be continuous Then f has the in termediate value property In particular7 every continuous function f R a R has the 25 intermediate value property Proof Suppose not Then 3xy E M st f a lt b fy and 30 6 Lab st V2 6 M fz 31 0 Let A 70007 and A 0700 Then M B U B07 where B f 1A and B0 f 1A is the complement of B in M Note that z E B and y 6 B07 so B 31 g 31 B0 Since f is continuous7 the preimage of an open set is open and since both A and A are open subsets of R we have that B and B0 are both open7 and therefore also both closed as complements of each other We conclude that M is a disjoint union of non empty clopen sets and is therefore disconnected7 which contradicts our assumption Thus7 we conclude that f has the intermediate value property 37 Compactness We say that S C M is sequentially compact if every sequence in S7 has a conver gent subsequence st znk a z for some z E S For example7 every nite subset S 17x2 xn of a metric space M is compact7 since any sequence in S has to repeat at least one xk in nitely many times7 and that results in existence of at least one convergent subsequence xhxhxk Notice also that the convergent subsequence or indeed the limit need not be unique7 as the example of a sequence 1271271271727 in S 17 2 C N shows Also7 N is not a compact subset of R since the sequence 1273475 does not converge to a point in N Other non compact subsets of R include 01 sequence 17 127 137 does not have a subsequence that would converge to a point in 071 and Q every subsequence of the sequence 37 317 3147 31417 converges to 7139 Q We say that a collection Ua of open subsets of M is an open cover for S C M if Vm E S 304 st z 6 U0 We say that a collection V is a subcover of U0 if VB V U0 for some 04 ie V C Ua We then also say that Ua reduces to V We say that S C M is covering compact if every open cover Ua reduces to nite subcover In other words if were given any open cover for S whatsoever and we can always throw away enough members of it so that were left with only nitely many and they still cover all of S then S is covering compact Note that every subset S of M has at least one open cover namely M since M is open and de nitely covers S this particular open cover is already nite Also in order to see that not all subsets are covering compact consider the cover of 01 C R by open intervals Un 1n1 Clearly Un n E N is an open cover for 01 but you can easily see that it cant be reduced to a nite subcover since in that case we7d be left with Unw Um UM and letting N mazn1n2 nk we observe that Vm E 01N z is not contained in any of Um Um Unk Now let S C M and let Ua be some open cover for S Then if 3A gt 0 st Vm E S BAx C U0 for some 04 we say that A is a Lebesgue number for U0 In other words a Lebesgue number for an open cover of S is some small radius st neighborhood of every point in S of that radius is contained in some member of the cover obviously which member it is depends on the particular point Notice that a given cover for a given set might not have a Lebesgue number For example 01 C R has as one possible cover 01 ie it7s covered by itself Suppose it had Lebesgue number A then pick z E 0 A Since BAx x 7 Ax A contains negative points we have BAx g 01 and thus this 27 neighborhood is not contained in any member of the cover7 leading to contradiction Theorem Every open covering of a sequentially compact S C M has a Lebesgue number Proof Suppose not Let Ua be an open cover for S st VA 3 E S st BM g Ua Va Let An 1717 and xn be as above Then since S is sequentially compact7 has some convergent subsequence a z E S Since U0 is a cover for S7 z E Ua for some a Since Ua is open7 37 gt 0 st BTW C U0 Now7 since znk a x 3N1 st nk 2 N1 gt dwam lt r2 Moreover7 3N2 2 N1 st nk 2 N2 gt AM lt r2 Now pick some an st nN gt N2 Let y 6 BMW xmv7 then dy S dzmv dany lt r2 AnN lt r2r2 7quot We conclude that BAW mm C BTW C Um contrary to our assumption that Vn BM g Ua Va Thus7 every open covering of a sequentically compact set does indeed have a Lebesgue number Theorem S C M is sequentially compact iff it is covering compact Proof Suppose S is covering compact7 but not sequentially compact Then let be a sequence in S st no subsequence of converges to a point in S That implies that V E S 3 gt 0 st BMW contains only nitely many terms of otherwise there7d be a subsequence converging to Now7 BM is an open cover for S and since S is covering compact7 it reduces to a nite subcover BM1 17 BWQZ B and since 7 Tank 28 each member of this subcover contains only nitely many terms of zn we conclude that S contains nitely many terms of xn an obvious contradiction Thus covering compactness implies sequential compactness Now suppose S is sequentially compact and let Ua be some open cover for S We know that Ua has some Lebesgue number A gt 0 Pick 1 6 S and some U1 6 U0 st BAz1 C U1 If S C U1 then we have succeded in reducing Ua to a nite subcover If not then pick uncovered point 2 6 S x E S U10 and U2 st BAz2 C U2 If S C U1 U U2 were done if not we continue picking uncovered points to obtain a sequence of points in S and a sequence Un of members of U0 st BAn C Un and xn E A U10 U20 UK If at some point the sequences terminate if for some N A U1 UUZU UUN then we have reduced Ua to a nite subcover Now suppose the sequences never terminate Then since S is sequentially compact there is some subsequence of st znk a z E S There fore HN st nk 2 N gt dwmw lt A In particular dxNx lt A gt z E BAQN C UN Since UN is open 37 gt 0 st BTW C UN But nk gt N gt znk UN and therefore BTW contains only nitely many terms of mm a clear contradiction to convergence We conclude that in fact Ua reduces to a nite subcover and sequential compactness implies covering compactness S C M is said to be compact if it is sequentiallycovering compact In the proofs of the theorems about compactness that follow we will use whichever de nition of compactness leads to a more direct proof and we will supply two proofs for some of the theorems to give you better understanding of both kinds of compactness Theorem Let 51 C M1 and 2 C M2 be compact Then S Sl gtlt SQ C M1 gtlt M2 M is compact Proof Let mmyn be a sequence in S we avoid here cumbersome notation Then is a sequence in 1 and therefore has some subsequence xnk that converges in 51 Now is then a sequence in 2 and therefore has some subsequence ynkl that converges in SQ Moreover since was a convergent sequence in 1 the subsequence mm is also a convergent sequence in 51 Therefore the sequence mmyn has a convergent subsequence mnklynkl with respect to all product space metrics discussed above since both component sequences converge and we conclude that Cartesian product of two compact sets is compact Theorem The Cartesian product of n compact sets is compact Proof By induction and above theorem Theorem Closed interval ab C R is compact Proof 1 Let be a sequence in ab Consider set C x 6 ab xn lt z only nitely often Clearly a E C and b is an upper bound for C therefore C has a least upper bound x We will show that there is some subsequence of converging to at z Suppose f b then 3N st 71 2 N gt xn b and clearly we have a subsequence converging to b f Now suppose f lt b and no subsequence converges to f then 3 b 7 f gt r gt 0 st xn E Brz f 7 hf 7quot only nitely often But then f r E C 30 note that f 7 6 1 bl7 contradiction to f being the lub for C We conclude that in fact there is some subsequence converging to f and therefore 17 is a compact subset of R Proof 2 Let Ua be some open cover for 17 and consider set C x E 1 b nitely many Ua would suf ce to cover the interval az Clearly a E C and b is an upper bound7 therefore 0 has the lub Suppose f lt b7 and let Ua17Ua27H U be those nitely many members of U0 that suf ce to cover mf Then f E UM for some k not neces sarily unique7 and since UM is open7 37 gt 0 st Brz f 7 hf r C UM Now Vy E f f 7quot y is covered by same U0417 UM as xi and therefore picking some speci c y we have that nitely many members of Ualpha suf ce to cover my which contradicts f being the lub for C We conclude that f b and therefore nitely many Ua cover 17 and thus 17 is compact Theorem Closed box ahbll gtlt a27b2 gtlt gtlt ambn C R is compact Proof It is a nite Cartesian product of compact sets Theorem Bolzano Weierstrass Any bounded sequence in R has a convergent sub sequence Proof Any bounded sequence in R is contained in some closed box7 and therefore has a subsequence that converges to some point in that box Theorem Suppose M is compact and S C M is closed Then S is compact Proof 1 Let be a sequence in S7 then is also a sequence in M and therefore has a convergent subsequence znk a z E M Since S is closed in M7 we have x 6 S7 and therefore has a subsequence that converges in S We conclude that S is compact Proof 2 Let Ua be some open cover for S7 then since Sc is open7 Ua USc is an open cover for M and since M is compact7 it reduces to a nite subcover for M and therefore it is a nite cover for S Now there are two possibilities First7 Sc might not be a member of this nite subcover7 then we have reduced Ua to a nite subcover for S Now7 suppose Sc is a member of the nite subcover we found ourselves with7 then it is obvious that the rest of the nite subcover still covers S since no element of S is contained in S0 and by excluding S0 we are left with the nite subcover for S to which the original cover U0 is now reduced We conclude that S is compact Theorem Compact set S C M is closed and bounded Proof Suppose S is not closed7 then HQ a sequence in S st xn a z S Since S is compact7 3 some subsequence znk a f 6 S7 but since is a convergent sequence in M7 all of its subsequences converge to the same limit in M7 and we have that znk a x and by uniqueness of limits we have x f 6 S7 a contradiction to z not being in S So S is closed Now let x E M and suppose S is not bounded Then V71 6 N Hzn E S st dzxn gt 71 Since S is compact7 3 some subsequence of a sequence in S7 st znk a f E S Since all convergent sequences are bounded7 for some 7 gt 0 and for some y E M for example 32 f we have znk E By Vnk Now let T dzy We observe that by the property 3 of the metric we have dnk S dy dyxnk S W r contradictory to the fact that dnk a 00 as nk a 00 We conclude that S is in fact bounded The converse to that statement every closed and bounded subset of a metric space is compact is not true in general For example let M N with discrete metric Then M is a closed and bounded subset of itself x E B21Vx E M but the sequence 1234 in M has no convergent subsequence and therefore M is not compact The converse is however true in R and a more general converse will be provided again later Theorem HeineBorel Every closed and bounded S C R is compact Proof Since S is bounded it is contained in some closed box in R and is therefore a closed subset of a compact set We conclude that S is compact We will now proceed to construct a more general converse statement We start by intro ducing a new notion S C M is said to be totally bounded if V6 gt 0 there exists a nite covering of S by e neighborhoods Notice that this de nition is different from the de nition of non total boundedness given earlier Theorem Let M be a complete metric space Then S C M is compact iff S is closed and totally bounded Proof Suppose S C M is compact We have already shown that S has to be closed 33 Now let 6 gt 0 be given and consider the following open cover for S B5x z E S Since S is compact the cover reduces to a nite subcover and we have a nite covering of S by e neighborhoods and we conclude that S is totally bounded Now suppose S C M is closed and totally bounded Let be a sequence in S Let 6 171 V71 Since S is totally bounded we have a nite covering for S by el neighborhoods B51y11B51y12B5y1m1 for some y11y12y1m1 E M Then at least one of these neighborhoods contains in nitely many terms of the sequence zn suppose B5y1k1 and let N1 be st xN E B51y1k1 Now since every subset of a totally bounded set is totally bounded you can easily show it we have a nite covering of B51y1k1 by 62 neighborhoods B52y21 B52y22 Bgzy2m2 and once again one of these neighborhoods contains in nitely many terms of the sequence zn suppose B52y2k2 and let N2 gt N1 be st zN2 E B52y2k2 Continuing in this manner we obtain a subsequence mm which is Cauchy since nm gt N gt danan lt 61w 1N Since M is complete sz a z E M Since S is closed in M x E S Thus has a subsequence that converges to a limit in S and we conclude that S is compact We note here that the conditions speci ed are indeed necessary Take cornpleteness for example Consider S Q 77T a subset of a metric space Q with the usual distance rnetric Then S is closed and totally bounded subset of Q but its clearly not cornpact since sequence 3 31 314 315 in S doesnt have a subsequence that converges to a point in S or even in Q for that matter Also substituting boundedness for total boundedness in the theorem above would not suf ce since we have already seen that a complete metric space N with discrete metric is a closed and bounded non cornpact subset of itself 34 Below are some important results on the behavior of continuous functions on compact sets Theorem The continuous image of a compact set is compact Proof 1 Let f M a N be continuous7 let S C M be compact and let fS C N denote the image of S under f Let be a sequence in fS7 then Vn Hzn E S st x y Since S is compact7 the sequence in S has some convergent subsequence znk a z E S By continuity of f7 we then have that ynk fxnk a fx 6 fS7 and therefore has a subsequence that converges to the limit in fS7 and we conclude that fS is compact Proof 2 Let f M a N be continuous7 let S C M be compact and let fS C N denote the image of S under f Let Ua be an open cover for fS in N Then since f is continuous7 f 1Ua is an open set in M V04 and therefore f 1Ua is an open cover for S in M Since S is compact7 f 1Ua reduces to a nite subscover f 1U1f 1U2 7fquotlUn7 and clearly U17U27 Un is an open cover for fS you can easily see it yourself7 which is a nite subcover of the original cover We conclude that fS is compact Theorem Continuous real valued funciton de ned on a compact set assumes its maxi mum and minimum Proof Let f M a R be continuous and let S C M be compact Then fS C R is closed and bounded7 and we have seen that a closed and bounded subset of R contains its 35 glb and its lub Theorem Every continous function de ned on a compact set is uniformly continuous Proof Let M be compact and f M a N continuous Suppose f is not uniformly con tinuous Then 36 gt 0 st V n gt 0 Bang 6 M st dxmyn lt 6 but dfxnfyn gt 6 Let 6 171 and for each 717 let any 6 M be as above Since M is compact7 the se quence in M has some convergent subsequence Moreover7 the sequence also has some convergent subsequence ynkl a y E M Since xnkl is a subsequence of a convergernt sequence7 it also converges and it converges to the same limit as the mother sequence7 and since dxynkl lt 1nkl7 we can easily see that it also converges to y The continuity of f implies that x a y and fy a y Now7 let N be st nkl 2 N gt dfxnklfy lt 62 and dfynklfy lt 627 then we have nkl 2 N gt dfkl7fynkl S dfkl7fy dfy7fynkl lt 62 62 6 which contradicts our assumption that dfxnfyn gt E V71 We then conclude that f indeed is uniformly continuous 38 More Results on R We introduce some notation rst Given sequence in R we say that limn z E R if xn a z in R We say that limzn oo ifVM gt 0 EN st 71 2 N gt xn gt M And similarly7 limzn foo if VM lt 0 EN st 71 2 N gt xn lt M Here are some examples 36 1 3 31 314 3141 Then limzn 7T 2 2 3 5 7 11 Then limzn 00 3 1 4 9 16 Then limzn 700 4 1 1 2 2 3 3 Then limn does not exist Given a sequence in R we say that M lim supxn if M lim sup We de ne Hoe k2 m lim infn similarly Here are some examples 1 12345 then lim supzn lim inf 00 2 112 123 then lim supzn oo lim infzn 1 3 3313143141 then lim supzn lim infzn 7139 We say that sequence is monotone increasing if n gt m gt xn gt zm The sequence is monotone nondecreasing if n gt m gt xn 2 zm The monotone decreas ing and monotone non increasing sequences are de ned similarly A sequence is said to be monotone if its monotone non increasing or monotone non decreasing note that every monotone increasing sequence is also monotone non decreasing and every monotone de creasing sequences is monotone non increasing so these two classes are also covered by the de nition 1 3 31 314 3141 is monotone increasing 2 1 4 9 16 is monotone decreasing 3 1 2 2 3 3 3 4 4 4 4 is monotone non decreasing 37 4 1 1 1 1 is monotone non decreasing and monotone non increasing 5 1 1 2 1 2 3 1 2 3 4 is not monotone but it has many possible monotone subsequences The following are some basic results about sequences in R 1 Let xn a z E R and let k E R Then yn kxn a kx P Let snaxandynayinR Thenzn xnynazy 9 Let xn a z and yn a y in R Then 2 znyn a xy 7 Let xn ax 7amp0 in R st xny OVn Then yn 1zna1z 9 Let xn a z 31 0 in R st xn 31 0 Vn and let yn a y in R Then 2 ynzn a yz 03 Let limzn oo lim gt 0 Then limzn xnyn oo 5 Let be monotone and bounded Then converges in R 00 Let be any sequence in R Then has a monotone subsequence Together this and the previous result imply that every bounded sequence in R has a convergent subsequence 3 Let be a monotone sequence Then limzn exists it could of course take on values of 00 and foo 0 Let fg be real valued funcitons M a R continuous at some z E M Then f 9 fg and fg asusming g 31 0 are all continuous at x 11 Given a sequence xn7 hm supxn and lim infxn are well de ned either they belong to R or take values of ioo 12 xn a z iff hm supxn hm infxn x The proofs of these results are left as exersises 39 Calculus and Function Convergence We say that a real valued funciton f is differentiable at x if one of the following equivalent conditions holds 1 lim M L exists tax It 7 z 2 lim W L exists AmaO Ax 3Vegt036gt0st lt7llt6 lwi lte We call L the derivative of f at z and write f L We say that f is differentiable on the interval a7b if it is differentialbe at every x 6 17 b The following are familiar results from calculus 1 If f is differentiable at x then f is continuous at x 2 If f and g are differentiable at 7 then so is f g and f g x f z g z 3 If f and g are differentiable at x then so is g7 and fg fgf9 4 If f CV then f OVz 5 If f and g are differentiable at z and g 31 07 then fg is differentiable at z and 7 f 9f9 w 7 my 6 Chain Rule If f is differentiable at 7 and g is differentiable at fx7 then 9 o f is differentiable at z and g 0 f 9ff Theorem Let f be differentiable on cab and suppose it achieves a maximum or mini mum at some 0 6 ab Then f c 0 Proof We will prove the theorem for maximum7 and proof for minimum is analogous ftf0 t7c Let t approach 0 from above Then S 0 Vt If we let t approach 0 from below7 then 250 2 0 Vt Since both expressions have to tend to the same limit L f c7 we conclude that f c 0 Theorem Mean Value Suppose f is continuous on 17 and differentiable on a7b Then 3 c 6 ab st fb 7 fa f cb 7 a In particular7 if lf zl S M V x E 177 thethx 6 ab we have lft 7 S Mlt7l Proof Let S w and let g f 7 Sz Clearly g is differentiable on cab and continuous on 17 why Moreover7 9a gb Since 9 is continuous on a compact set7 it achieves maximum and minimum and since 9a gb it achieves at least one of them at some 0 6 ab Then 0 g c f c 7 S gt fb 7 fa f cb 7 a We state the following result without proof which can be found7 for example in Pugh7 p145 If f is differentiable on 177 then f has the intermediate value property Also7 all familiar results from calculus derivative and integral formulas7 L7Hopital7s Rule7 results on series convergence7 etc hold We say that a sequence of functions fn 17 a R converges pointwise to f fn a f7 if V x E 17 fnz a fx as n a 00 We say that a sequence fn 17 a R converges uniformlyto f fn f ifV E gt 07 3 Nst n 2 N gt lfnx7fxl lt EV E 17 You should convince yourself that the sequence of functions fnz x on open interval 01 converges pointwise to the function 0 if 0 S x lt 1 f 96 1 if z 1 but does not converge uniformly Theorem lf fn f and each fn is continuous at x then f is continuous at x Proof Let E gt 0 be given7 and let N be st 71 2 N gt 7 lt 63 V y Since fN is continuous at x 3 6 gt 0 st lx iyl lt 6 gt lfNx 7 fNyl lt 63 Then ls iyl lt 6 WM 7 fyl S lfm fNl WNW 7 fNyllfNyf1l lt 636363 67 and we conclude that f is continuous at x Note that our example above shows that pointwise convergence of continuous functions is not suf cient to ensure continuity of the limit We state two more results without proving them The proofs can be found in Pugh 1 Suppose fn f7 then fndz a ffxd as n a 00 41 N H P3 9 Suppose fn i f and j 9 then 9 f References Pugh 00 7Real Mathematical Analysis Springer 2002 Rice John A 7Mathematical Statistics and Data Analysis 2nd ed Duxbury Press 1995 Ross Kenneth A 7Elementary Analysis The Theory of Calculus7 Springer 2000 Math 104Spring 2005Anderson Lecture Notes on Contraction Mapping Theorem De nition 01 Let S7d be a metric space A function f S gt S is a contraction if M E 071 W721 E S dffr7fy S adtny 5 is a xed point of f if fs 5 Theorem 02 Contraction Mapping Theorem fSd is a complete metric space and f S gt S is a contraction then f has a unique xed point Proof We rst show that a xed point exists Since S y we may choose an arbitrary 80 E S Consider the sequence 5n de ned by 81 f50 82 f51 5n1 If 51 so then ee 51 so so 50 is a xed point If 51 y so we claim that dsn15n S oz d5150 The proof of the claim is by induction Note that d52751 df517f50 S 0101091750 1 Now suppose that d5n1 5n 3 oz d5150 Then d5n27 5n1gt df5n17 ozdsn1 5n oz oz d5150 an1d517 50 so the claim follows by induction Next we show that 5n is a Cauchy sequence Let 5 gt 0 Since 0 lt oz lt 1 liInTH00 oz 0 by Example 97b Choose N such that aN lt 51 oz 181 7 80 If m 2 n gt N 7 d5m7 5n S d5m7 572171 1 quot391 d5n17 5n lt am 1d5150 am 2d51750 oz d5150 1 0 1 oz i lt 1 a 1 a gt d5150 by Exerc1se 918 an am d81780 1 a lt dlt51750 N lt 1070Zd81780 lt 8 so 5n is Cauchy Since 37d is complete 5n has a limit 8 E S We will show that f5 5 Fix 5 gt 0 There exists N1 such that ngtN1gtdsns lt3 2 Since 5n is Cauchy there exists N2 such that n gt N2 gt dsn15n lt2 Choose any n gt rnaxN1 N2 Then 6187 NW S 6187 57m d8n17 f8 d57 5n1gt T lt E ozdsn 5 2 lt 22 5 Since 5 is arbitrary d5f5 0 so f5 5 Thus f has a xed point To show the xed point is unique suppose fs 5 and f0 t Then 018715 df87 f0 adst 1 ad5t S 0 so d5t S 0 Since dis a metric d5t 0 and thus 5 If so the xed point is unique I Real Analysis July 10 2006 1 Introduction These notes are intended for use in the warm up camp for incoming Berkeley Statistics graduate students Welcome to Call The real analysis review presented here is intended to prepare you for Stat 204 and occasional topics in other statistics courses We Will not cover measure theory topics and some other material that you should be very familiar With if you intend to take Stat 205 If you have never taken a real analysis course7 you are strongly encouraged to do so by taking math 104 or the honors version of it Math 105 usually of fered in the spring Will provide you With necessary measure theoretical background essential for Stat 205 The presentation follows closely and borrows heavily from 7Real Mathematical Analysis7 by CC Pugh7 the standard textbook for honors version of math 104 The empha sis is on metric space concepts and the pertinent results on the reals are presented as speci c cases of more general results7 and a lot of them are presented together as exersises in section 1 38 We do not expect you to be familiar with the metric space concepts but we do expect you to be familiar with speci c results on real line as that is usually the approach taken in most real analysis courses We hope that you nd these notes helpful Go Bears 2 Some De nitions We will denote by RQZ and N the sets of all real numbers rational numbers integers and positive integers respectively We will take for granted the familiarity with notions of nite countably in nite and uncountably in nite sets Given a set SC R ME R is an upper bound for S if V3 6 S it is true that 3 S M S is said to be bounded above by M M is said to be the least upper bound or lub for S if for all upper bounds M it is true that M S M note that it implies that lub is unique The lower bounds and the greatest lower bound glb are de ned similarly For example if S01 then 1 and 4 are upper bounds and 0 4 are lower bounds with 0 and 1 being glb and lub respectively A set is said to be bounded if it is bounded from above and below A set S is said to be unbounded from above if VN 33 E S st 3 gt N The de nition of a set unbounded below is similar A set is unbounded if its either unbounded from above or below The supremurn sup of a set S C R is de ned to be lub for S if S is bounded from above and to be 00 otherwise The in num inf is de ned to be glb for a set bounded form below and to be 700 otherwiseThe following results will be assumed about R proofs can be looked up in any analysis textbook H If S C R is bounded from abovebelow then the lubglb for S exists and is unique N Triangle Inequality M yl S lyl 03 6principle lf X7y E R 7 and V6 gt 07 m S y then m S y Also if V6 gt 07 mfgl S 6 then Xy 4 Every interval a7b contains countably in nitely many rationals and uncountably in nitely many irratio nals LlMlNF AND LlMSUP 3 Metric Spaces 31 De nition A metric space M is a set of elements together with a function dM X M a R known as metric that satis es the following 3 properties For all X7 y7 Z 6 M 1 dx7y2 0 and dx7y0 i Xy 2 dx7y dy7x 3 dx7y S dxz dz7y When metric d is understood7 we refer to M as the metric space When we want to specify that the metric is in M 7 we might use notation dM7y It also helps sometimes to think of 3 d as the distance function7 since it makes the 3 properties more intuitive we usually think of distance as being nonnegative7 and the distance from A to B should be the same as the distance from B to A Here are some examples 1 R with usual distance function dx7y lm 7 yl N Q with the same metric 03 R with Euclidean distance dxy 7 yH Hgt Any metric space for ex R or N with the discrete metric dxy1 if m a y7 dx7y0 otherwise This metric makes the distance from a point to itself be 0 and the distance between any two distinct points be 1 You should check for yourself that the metrics above satisfy the 3 conditions 3 2 Sequences We will use the notation for the sequence of points 17M 7mm in metric space M The members of a sequence are not assumed to be distinct7 thus 17171717 is a legit imate sequence of points in Q A sequence yk is a subsequence of if there exists sequence 1 S 721 lt 722 lt 723 lt st yk mm Some subsequences of the sequence 1712712312 3 412 345 are 77777 1 twos 22222 77777quot39 2 odds 17357797 3 primes 273577117 4 original sequence With duplicates removed 17273747576777 5 the previous subsequence With rst 3 elements removed 475677 A sequence of points in M is said to converge to the limit X in M if V6 gt 0 3 N st 72 Z N gt dm lt 6 We then say that M a m Notice that if our metric space is R then replacing dn7 m by the usual metric lmnixl gives the familiar de nition of a limit Theorem The limit of a sequence7 if it exists7 is unique Proof Let be a sequence in M that converges and suppose its limit is not unique Let X7y denote two of possibly even more limits Let 6 gt 0 be given Then 3N1 st 72 2 N1 gt dm lt 62 Similarly 3N2 st 72 2 N2 gt dxmy lt 62 Let N ma Nthg7 and let n 2 N Then by the 3rd property of metric function dy S d7n dmy lt 62 62 6 Since this is true for every 6 we have Xy by the 6 principle Theorem Every subsequence of a convergent sequence converges and it converges to the same limit as the original sequence Proof Easy A sequence in M is said to be Cauchy if V6 gt 0 EN st nm Z N gt dn rm lt 6 In other words a sequence is Cauchy if eventually all the terms are all very close to each other Theorem Every convergent sequence is Cauchy Proof Suppose 7 a r in M Let 6 gt 0 be given Then 3N st 72 Z N gt dn lt 62 Let 72771 2 N Then dnm S dn dm lt 62 62 lt 6 gt is Cauchy Does every Cauchy sequence converge to a limit Consider the sequence 3 314 3141 31415 This sequence is clearly Cauchy When considered as a sequence in R it does converge to 7139 However we can also think of it as a sequence in Q in which case it doesn7t converge since 7r Q The following de nition formalizes the di erence between Q and R the metric space M is said to be complete if all Cauchy sequences in M converge to a limit in M Theorem R is complete Proof Let an be a Cauchy sequence in R and let A be the set of elements of the sequence ie AER3nENandan Let 61 Then since an is Cauchy 3N1 st Vnm 2 N1 lan7aml lt 1 Therefore Vn 2 N1 we have lam 7 aNll lt 1 and thus 72 2 N1 gt an E aN171aN11 The nite set 1112 aNHaN1 7 1aN1 1 is bounded as is every nite subset of R and therefore all of its elements belong to some interval 7LL Since both 1N1 7 1aNl 1 6 7L L we conclude that aN1 71lt1N1 1 C 7LL and therefore an E 7LL Vn and A is bounded Now consider set S 3 6 7L L 3 in nitely many 72 E N for which an 2 3 Obviously 7L E S and S is bounded from above by L We then know that the lub for S exists call it b We will show that an 7 b Let 6 gt 0 be given Then since an is Cauchy 3N2 st mn 2 N2 gt lam 7 aml lt 62 Since V3 6 S 3 S b we have that b 62 S That means that an exceeds b 62 only nitely often and 3N3 2 N2 st 72 2 N3 gt an S b 62 Since bis the least upper bound for S we have that b7 62 is not an upper bound for S and therefore 33 E S st 3 gt b7 62 and an 2 3 gt b 7 62 in nitely often In particular that gurantees that there exists some N4 2 N3 st 1N4 gt b7 62 Moreover7 since N4 2 N3 we have 1N4 E b7 627b 62 And since N4 gt N27 we get 72 2 N4 gt lan7bl S lan7aqulaN47bl lt6262 lt6 and therefore an 7 b It is an easy exersise to show that every discrete metric space for exarnple7 N with dis crete metric is complete 33 Open and Closed Sets Let M be a metric space and let S be a subset of M We say that 6 M is a limitpoint of S note that S is not a sequence here7 but a subset of M if there exists a sequence in S st LL 7 m For exarnple7 let M R and SQ Then 2 is an example of a limit point of S 27 27272727 or 17 1 127 1 237 1 347 that belongs to S7 and 7r is a an example of a limit point of S 373173147 3141731417 that does not belong to S of course7 it still belongs to A set is said to be closed in underlying metric space 8 M if it contains all of its limits For eXample a singleton set X is closed in M assuming M is non empty since the only possible sequence is x a m Clearly M is a closed subset of itself A set S is said to be open in underlying mertric space M if Vm E S 37 gt 0 st dy lt r gt y E S The set of points y E M dy lt r is called open r neighborhood of X and is denoted BT for eXample B25 in R is simply the open interval 37 Thus a set S is open in M if for every point in S there exists some small neighborhood of that point in M contained entirely in S Its easy to see that interval ab is an open set in lR and clearly every metric space M is an open subset of itself since every r neighborhood of X is still in The following theorem provides a connection between open and closed sets Theorem The compliment of an open set is closed and the compliment of a closed set is open ProofSuppose S C M is open Suppose 7 a m in M and moreover 7 6 SC Vn We need to show that m 6 SC Suppose not then m E S Since S is open 37 gt 0 st dy lt r gt y E S Now since 7 a m 3N st 72 Z N gt dn lt r gt 7 6 S That is clearly impossible since no point could be in both S and SC and we have reached a condtradiction Therefore SC is closed Now suppose that S C M is closed Suppose SC is not open then Hm 6 SC st Vrn gt 0 3 st d7n lt Tn but LL 6 S Now let Tn 172 and pick LL as above Then LL 6 S Vn and LL a 6 SC gt S is not closed since it fails to contain all of its limits gt contradiction Therefore SC is open Notice that some sets like the space M itself are both closed and open7 they are referred to as clopen sets By theorern above7 MC 9 is clopen Now consider interval 071 C lR It is neither open every r neighborhood of 0 includes points in 0710 C R nor closed it fails to include 17 Which is the limit of the sequence LL 1 7 172 in 07 Thus subsets of a metric space can be open7 closed7 both7 or neither Theorem Arbitrary union of open sets is open Proof Suppose Uais a collection of open sets in M7 and let U UUD Then 6 U gtx6 Ua for someaand 3rgt0st d7y ltrgty E Ua gty E U ThereforeUis open Theorem Intersection of nitely many open sets is open Proof Suppose U17U27 7Un are open sets in M Let U Uk If U 9 then U is open Now suppose 6 U7 then 6 Uk for k 17 27 37 7 n Since each Uk is open7 37 gt 0 st d7y lt rk gt y 6 Uk Let r 7m nr17r27WT 7 then dy lt r gt y 6 Uk Vk gt y E U Therefore U is open Notice that the in nite intersection of open sets is not necessarily open For example7 its easy to see that Uk flk71k is an open subset of R but WUc 0 is clearly not open in lR TheoremArbitrary intersection of closed sets is closed Also7 nite union of closed sets is closed Proof We7ll use DeMorgan7s Laws UUk Uk Let Kat be a collection of closed sets in M Then Ka UK and since each KatC is open7 their union is open and its complement is closed The proof of the second part of the theorem is similar Notice that the in nite union of closed sets is not guaranteed to be closed For example7 even though each Kk 01 7 lk is closed in R the intersection UKc 071 is not TheoremLet M be a complete rnetric space7 N C M be closed Then N is complete as a metric space in its own right Proof Let be a Cauchy sequence in N Since is also a Cauchy sequence in M7 and M is cornplete7 we have LL a 6 M But N is closed in M7 therefore 6 N and we conclude that N is complete Let lirn S denote the set of all limit points of S in M It is pretty clear that 6 lim S ltgt V gt 07 BTW f S a 9 you can easily prove it as an exersise We can also show that lim S is a closed set Let 6 gt 0 be given and let yn be a sequence of points in lirn S st yn a yin M Then 3N st 72 Z N gt dymy lt 62 Since each yn 6 lim S7 3 E S st dymn lt 62 V72 Then we have n 2 N gt dtrmy S dwmyn dyny lt 62 62 6 Therefore LL a y and y 6 lim S We conclude that lim S is closed We can also show that BTW is an open subset of M as follows let y E BT Let s r 7 dy gt 0 Then dy2 lt 3 gt 2756 S dtmx dy72 lt dtml 7 7 dvy 7 gt 2 E BT Thus if y E BTW 33 st Bsy C BTW7 and therefore BTW is open Theorem Every open set U C R can be expressed as a countable disjoint union of open intervals of the form 17 b7 where a is allowed to take on the value 700 and b is allowed to 12 take on the vaule 00 Prooflf U 9 00 then the statement is vacuously true If U is not empty V E U de ne ax mfa a C U bx supb x b C U Then I ambz is a possibly unbounded open interval containing X It is maximal in the following sense suppose bx E U then by construction above HJ C U an open interval st bx E J You can prove for yourself that the union of two open intervals with non empty intersection is in fact an open interval you just have to take care of a number of base cases for endpoints We then have that I U J is an open interval containing X and moreover since J is open and bat E J 3V 6 J st b gt by But then b E b Lb C U which contradicts bx being the supremum of such a set Thereofre bx U and similarly ax U Now let y E U and suppose I 01y a 9 Then once again WUy is an open interval containing both and y and by rnaxirnality we have I Ix Uy 1y Thus we conclude that VL y E U either I y or the two intervals are disjoint So U is a disjoint union of open intervals To show that the union is countable pick a rational number in each interval Since the intervals are disjoint the numbers are distinct and their collection is countable since rationals are countable A few more de nitions are in order As before S is some subset of a metric space M The closure of S is S Ka where K0 is the collection of all closed sets that contain S The interior of S is intS UUD where U0 is the collection of all open sets contained in S Finally7 the boundary of S is BS S 0 SC For example7 if MlR and Sa7 b7 then S a7b7 intS a7b7 and 8S a U b If SQ7 then S R intS 9 and 8S lR Notice that the closure of a closed set S is S istelf7 and so is the interior of an open set S Also notice that both S and 8S are closed as intersections of closed sets7 and intS is open as a union of open sets Theorem Slim S Proof We have shown before that lim S is a closed set7 also since each point of S is also a limit of point of S its the limit of a sequence 373737 7 we have S Clim S7 and we conclude that S Clim S Also7 since S C S7 and S is closed7 it must contain all the limit points of S7 thus lim S C S We conclude that S lim S You may check for yourself at this point that every subset of a discrete metric space M for example7 N with discrete metric is clopen why would it su ice to show that a singleton m is open and that therefore VS C M7 intS S S and 8S 9 A subset S of a metric space M is said to cluster at point m E M if V gt 0 BTW contains in nitely many points of S S is said to condense at X7 if each BTW contains uncountably many points of S For example if MlR7 then every point of S a7b is a condensation point also a cluster point and no other point is a cluster point If S1n n E Nthen the only cluster point is 0 S and no point is a condensation point no point could have uncountably many members of S in its r neighborhood since S itself is count able lf SQ then X is a cluster point of S Vm E R An open interval a b is an example of a subset of R that contains some but not all of its clustercondensation points Finally N with either discrete metric or with the metric it inherits as subset of R has no cluster points We emphasize that if X is a cluster point of S each r neighborhood of X must contain in nitely many distinct points of S It is easy to see that X is a cluster point of S i 3m a sequence of distinct points in S st 7 a m We denote the set ofall cluster points of S by S Theorem SU S S S is closed i S C S Proof We already know that S C S Moreover by above we have that a cluster point is a limit point and therefore S Clim S S Thus S U S C S Also if m E S lim S then either m E S or San a sequence of distinct points in S st M a m but that would make m a cluster point So we have S C S U S and we conclude that S U S S Now we know thatSisclosedi fSSSUS i fS CS We notice here that if S C R is a bounded from abovebelow then its lubglb are its cluster points you can check it for yourself and therefore by above theorem belong to the closure of S Thus a closed and bounded subset of R contains both its lub and glb Up to this point instead ofjust saying 8 is open7 or S is closed we often said 8 is open in M7 or S is closed in M7 We can drop the mention of M when it is understood what the underlying metric space is but we point out that it is essential to the opennessclosedness of S For example both Q and the half open interval 1 b are clopen when considered as metric spaces in their own right Neither one of course is either open or closed when treated as a subset of lR Another example is a set S Q fan a set of all rational numbers in the interval 77137139 As a subset of metric space Q S is both closed if is a sequence in S and 7 a m E Q then m E S and open check for yourself As a subset of lR how ever it is neither open if m E S then every neighborhood of m contains some y Q nor closed there are sequences in S converging to 7r 6 R The following few theorems establish the relationship between being openclosed in metric space M and some metric subspace N of M that inherits its metric from M ie dNy dMy We will denote the clousre of set S in M by clMS and the closure of S in N by clNS Note that clNS clMS N Theorem If S C N C M then S is closed in N i 3L C M st L is closed in M and SL N Proof Suppose S is closed in N then let L clMS Clearly L is closed in M and L f N clNS S since S is closed in N Now suppose that L as in the statement of theorem exists Since L is closed7 it contains all of its limit points and S L f N contains all of its limit points in N7 therefore S is closed in N Theorem If S C N C M7 then S is open in N i 3L C M st L is open in M and SL N ProofNotice that the complement of L f N in N is LC 0 N7 Where LC si the complement of L in M Now take complements and apply previous theorem A popular way to summarize the preceding two theorems is to say that metric subspace N inherits its opens and closeds from M We also introduce here the notion of boundedness S C M is bounded if Em 6 M7 37 gt 0 st S C BTW7 ie S is bounded if there7s some point m E M st S is contained in some neighborhood of X For example7 7171 is bounded in R since its contained in B52 or B20 On the other hand7 the graph of function f mm is an unbounded subset of R27 although the range of f is a bounded subset of R range 717 ln general7 we say that f is a bounded function if its range is a bounded subset of the target space Theorem Let be a Cauchy sequence in M Then S 6 M r LL for some n is bounded In other words7 Cauchy sequences are bounded Proof Let 6 1 Then 3N st mm 2 N gt dmm lt 17 in particular 72 Z N gt dmN lt1 Now7 let 7 1mad1727d1737d17N Clearly V1 3 k S N d17k lt r 71lt 7 For k 2 Nd1k S d17N damn lt 7 711 7 Thus S C BT1 and the sequence is bounded As a consequence of preceding theorern7 all convergent sequences are bounded since convergence implies Cauchy 34 Continuous Functions Let M7 N be two metric spaces A function f M a N is continous at r E M if V6 gt 0 36 gt 0 st y E M and dMy lt 6 gt dNffy lt e We say that f is continuous on M if its continuous at every r E M Notice that a speci c 6 depends on both r and E If the choice of 6 does not depend on X7 then we have the following de nition a function f M a N is uniformly continuous if V6 gt 07 36 gt 0st y E M and dM7y lt 6 gt dNf7f1 lt 6 For example7 function 1X on the interval 071 is continuous note that 0 is outside of the dornain7 but is not uniformly continuous given 67 no matter how small we choose 6 to be7 there are always points L y in the interval 06 st 7 fyl gt E The following theorem provides some alternative characterizations of continous functions Theorem The following de nitions of continuity are equivalent 1 e 6 de nition 2 f M a N is continuous if for each convergent sequence M a in M7 we have x a f in N Thus continous functions send convergent sequences to convergent sequences7 preserving the limits 3 f M a N is continuous ifV closed S C N7 f 1S is closed in M Here f 1 is the notation for preirnage of a set in a target space 4 f M a N is continuous ifV open S C N7 f 1S is open in M Proof 1 gt 2 Suppose fis continuous7 is a sequence in M st LL a m Let 6 gt 0 be given By 17 we know that 36 gt 0 st dM7y lt 0 gt dNf7fy lt 6 Since mm a 3L st 72 Z L gt dMm lt 6 But that means that n 2 L gt dNfn7f lt e and therefore x a 2 gt 3 Let S C N be closed in N7 and let be a sequence in S 1 fquotlS7 st LL a 6 M We need to show that 6 S l By 2 and by the fact that LL a L we know that fan a Since is a sequence in S and S is closed7 we have f 6 S7 and 19 therefore m 6 8 1 3 gt 4 Let S C N be open in N Then f 1S f lScc7 and since the latter is the complement of a closed set by 37 it is open in M 4 gt 1 Let m E M and e gt 0 be given Then we know that B5f is open in N and therefore f 1B5f is open in M by 4 Since m E f 1B5f and f 1B5f is open7 36 gt 0 st B5 C f 1B5fie dM7y lt 6 gt dNf7fy lt 6 Theorem Composite of continuous functions is continuous Proof Let f M a N and g N a L be continuous7 and let U C L be open in L7 and denote h g of M a L Then g 1U is open in N and f 1g 1U h 1U is open in M by de nition 4 above We conclude that h is continuous by de nition 4 It is worth pointing out that while continuous functions preserve the convergent se quences7 they in general do not preserve the nonconvergent Cauchy sequences For exam ple7 the continuous funcion f 071 a R given by f 1 maps the Cauchy sequence 17127137147 in 071 to non Cauchy sequence 17273747 in lR Uniform continuity en sures the preservation of Cauchy sequences Theorem Let M7N be metric spaces7 f M a N a uniformly continuous function7 and a Cauchy sequence in M Then is a Cauchy sequence in N Proof Let 6 gt 0 be given Then since f is uniformly continuous 36 gt 0 st dM y lt 6 gt dNffy lt 6 Since is Cauchy 3L st mn gt L gt dMmn lt 6 gt dfnfm lt e gt is Cauchy You can show pretty easin that every function de ned on a discrete metric space is uniformly continuous why7 Example Consistent Estimates ln statistics we usually estimate parameters of interest from the sample we have at hand Suppose that n is the estimate based on sample of size n then we say that the estimate is consistent in probability if V e gt 0 7 6 gt E a 0 as n a 00 For example the Weak Law of Large Numbers states that if we have a sequence of HD random variables X1X2Xn with expected value p and variance 02 then the sam ple mean 11 X is a consistent estimate of u Moreover if we consider 2 1 the sequence XlkX2k Xnk then by applying the Weak Law again we conclude that m is a consistent estimate of k th moment of X M 2 1 Theorem Suppose 6 is a consistent estimate of 6 and suppose that f is continuous Then n is a consistent estimate of p f6 Proof Suppose not Then for some 6 gt 0 7 f6 gt 6 7 0 ie for some L gt 0 3 subsequence of st 7 f6 gt 6 gt L Now since f is con 3 6 and therefore we have that 7 tinuous a 6 gt 0 st 93 7 0 g 6 gt f 7 100 7 f6 gt 6 gt 7 6 gt 6 Also since 6 is a consistent estimate of 6 we know that 3N st 72 Z N gt P 6An 7 6 gt 6 lt L in particular this holds V 7 Z N Combining the last two results with the fact that A gt B gt PA S PB we have 7 Z N gt L lt 7 f6 gt 6 S 7 6 gt 6 lt L which leads to a contradiction Therefore we conclude that n is indeed a consistent estimate of p f6 This result is very useful in general and is the foundation of estimation technique known as Method of Moments Once again suppose we have a sequence of HD random variables X1X2Xn with expected value p and variance lt72 We know that X is a consistent estimate of u and by above result we have X2 is a consistent estimate of 2 Then you can prove yourself that v 7 X2 is a consistent estimate of lt72 VarX do it In general if there is a continuous function 6 fu1u2 uk then 6 f 1 2 k is a consistent estimate of 6 Therefore if we can express a parameter of interest as a continuous function of the moments of distribution then applying function to sample moments will give us a consistent estimate of the parameter For example7 if we are sampling from Nu702 distribution and we have a sample of size n then u M1 and 02 EX2 7 2 M2 7 12 TL TL and therefore 1 X and 72 7X2 Xi 7 X2 are consistent estimates 2391 i1 of u and lt727 respectively 35 Product Metrics Let M M1 gtlt M2 be the Cartesian product of metric spaces M17 M27 ie M is the set of all points m 17x2 st 1 6 M1 and 2 6 M2 For example7 R2 R X R is the set of all points in the plane How would one de ne a useful metric on this product space Three of the possibilities are listed below 1 dM71 V dM117112 dM227y22 dg17 a Euclidean metric 2 dM7y madM117y17dM2 27y2 dmazlt 7y 339 dM7y dM1x17y1 dM2 27y2 dsum7y Continuing with our example7 if we took points m 757 2 and y 7711 in R2 then dEy V122 92 157dmazy ma1279 127 and jammy 12 9 217 where we use the usual distance metric on lR It turns out that in a way7 all these metrics are equivalent Theorem dmazy S dE7y S jammy S 2dmaz7y Proof Some basic arithmetic Theorem Let M M1 gtlt M27 and let me2 n be a sequence in M Then 71 converges With respect to wrt dmaz i it converges wrt dE i it converges wrt dwm i both and converge in M1 and M27 respectively Proof The equivalence of the rst 3 convergences is obvious from previous theorern For example7 suppose converges to some 6 ert dmaz Let 6 gt 0 be given7 then 3N st 72 Z N gt dmzmmr lt 62 gt dEmx lt dsumm S E The convergence of component sequences is obviously equivalent to convergence wrt dmz ln particular7 if LL a and yn a y in R 7 then 2 myn a 2 Ly in R2 Theorem The above results extend to the Cartesian product of n gt 2 metric spaces Proof By induction Theorem Rm is complete Proof Let be a Cauchy sequence in Rm wrt any of the above metrics Then each component sequence for k 1 2 3 m is Cauchy in R by same reasoning as convergence equivalence theorem above and since R is complete all component sequences converge 1M converges to some 19 Vk therefore M a 1 2 mm 36 Connectedness A metric space M is said to be disconnected if it can be written as a disjoint union of two non empty clopen sets Note that it is su icient to discover one proper ie a 9 or M itself clopen subset S of M since its complement would also have to be clopen and proper hence non empty and we7d have M S LI So where symbol LI indicates disjoint union M is said to be connected if it is not disconnected S C M is said to be connected if its connected when considered as metric space in its own right with metric inherited from M and is disconnected otherwise For example interval 2 5 is a connected subset of lR but 2 5U58 is not Q is also disconnected since Q Q 7oo 7r LI Q 7r Theorem Suppose M is connected and f M a N is a continuous function onto N Then N is connected Proof We note here rst that f M a N is onto if Vy E N Hm E M st y f ie every point in N is image under f of some point in M there could be many points in M all mapping to same point in N Now7 suppose N is not connected7 and let S C N be a proper clopen subset7 then f 1S is a non empty since f is onto7 clopen since f is continuous subset of M and so is fquotlS 7 resulting in M f 1S LI f 1S is a disjoint union of proper clopen subsets7 contradicting the connectedness of M We conclude that N is connected Thus a continuous image of a connected set is connected A discontinuous image of a connected set need not be connected7 however For example if f R a R sends all negative numbers to 0 and all non negative numbers to 17 then the image is 071 a nite set7 which is clearly disconnected Of course this example only works if R was connected to begin with Theorem R is connected Proof Suppose R is disconnected Then 3S C R st S is proper and clopen Since S is opein in R we know that S is a countable disjoint union of open intervals Let 17 b be one of these intervals we know that S is non ernpty since its proper7 so 17 b exists We have seen in the proof of the theorem about every open set U in R being the countable disjoint union of open intervals that the endpoints of hte intervals do not belong to U7 thus a7b S Suppose b lt 007 then b is clearly a limit point of of S and b S contradicts S being closed Therefore b 007 and similarly a 700 But then S R and S is not proper and we arrive at contradiction Thus7 R is connected Theorem Open and closed intervals in R are connected Proof Let 17 C lR We know that f R a 7717277172 given by ftltm 1 is continuous you can verify that for yourself You are also invited to nd continuous func tion 9 7717277172 a 17 b which is easy Then 9 o f is continuous as a composition of continuous functions and therefore 17 b is connected as a continuous image of the connected set lR Now7 let 17 C lR Then de ne f R a 17 b as follows a iflta fa ifa b b ifgtb Clearly f is continuous and therefore 17 is connected Theorem Suppose that Sq is a collection of connected sets and that Sa a 9 Then S USD is connected Proof Let 6 Sa Now suppose that S is disconnected7 S A LI AC7 where A and AC are disjoint non empty clopen subsets of S Now7 6 Sa gt 6 SW for some or gt 27 6 S USO gt 6 A or 6 AC Without loss of generality assume 6 A Since each SD is a subset of S SD inherits its closed and open sets from S Va by the inheritance theorem and since 6 SD Va we have A f SD is a non ernpty clopen subset of SD Va Since each SD is connected we conclude that A f SD SD Va and therefore A UA 0 S0 USO S contradicting A being a proper subset of S We conclude that S is connected Theorem Let S C M be connected Then S C T C S gt T is connected In particu lar the closure of a connected set is connected Proof Suppose T is disconnected T A LI AC where A and AC are proper clopen subsets of T By intheritance principle A f S is a clopen subset of S Since S is connected B A f S cannot be proper therefore either B S or B 9 Without loss of generality suppose B 9 if B S just look at C Ac 0 S the complement of B in S which leads toC SinceA S wehaveSCAcinT ButAa QandACTCSgt3EA st is a limit point of S Since A is open 37 gt 0 st BTW C A But is a limit point of S and therefore BTW f S a 9 gt A 0 AC a 9 and we arrive at a contradiction We conclude that T is connected Now we introduce the intermediate value property Let f M a R be a func tion Then f is said to have intermediate value property if Vy E M it is true that if f a lt b fy then V0 6 a b 32 E M st f2 c In other words if function assumes two distinct values in R then it also has to assume all the values in between to have the intermediate value property Theorem Let M be connected and f M a R be continuous Then f has the in termediate value property In particular every continuous function f R a R has the inter mediate value property Proof Suppose not Then 3y E M st f a lt b y and 30 E a b st V2 6 M f2 a 0 Let A 7000 and 14 0 Then M B LI BC where B f 1A and BC f 1A is the complement of B in M Note that m E B and y 6 BC so B a 9 a BC Since f is continuous the preimage of an open set is open and since both A and 14 are open subsets of R we have that B and B6 are both open and therefore also both closed as complements of each other We conclude that M is a disjoint union of non empty clopen sets and is therefore disconnected which contradicts our assumption Thus we conclude that f has the intermediate value property 3 7 Compactness We say that S C M is sequentially compact if every sequence in S has a conver gent subsequence st 7 a m for some m E S For example every nite subset S 12 mn of a metric space M is compact since any sequence in S has to repeat at least one 19 in nitely many times and that results in existence of at least one convergent subsequence xkkk Notice also that the convergent subsequence or indeed the limit need not be unique as the example of a sequence 12121212 in S 1 2 C N shows Also N is not a compact subset of R since the sequence 12345 does not converge to a point in N Other non compact subsets of R include 01 sequence 1 12 13 does not have a subsequence that would converge to a point in 01 and Q every subsequence of the sequence 3 31 314 3141 converges to 7r Q We say that a collection UH of open subsets of M is an open cover for S C M if Vm E S 304 st m 6 U0 We say that a collection V5 is a subcover of U0 if V5 V5 U0 for some 04 ie C UH We then also say that UH reduces to V5 We say that S C M is covering compact if every open cover UH reduces to nite subcover In other words if were given any open cover for S whatsoever and we can always throw away enough members of it so that were left with only nitely many and they still cover all of S then S is covering compact Note that every subset S of M has at least one open cover namely M since M is open and de nitely covers S this particular open cover is already nite Also in order to see that not all subsets are covering compact consider the cover of 01 C R by open intervals Un 1n1 Clearly Um n E N is an open cover for 01 but you can easily see that it can7t be reduced to a nite subcover since in that case we7d be left with UmUn2 UM and letting N man1n2 nk we observe that V E 01N m is not contained in any of Um Um Unk Now let S C M and let UH be some open cover for S Then if 3A gt 0 st Vm E S BAQ C U0 for some or we say that A is a Lebesgue number for U0 In other words a Lebesgue number for an open cover of S is some small radius st neighborhood of every point in S of that radius is contained in some member of the cover obviously which member it is depends on the particular point Notice that a given cover for a given set might not have a Lebesgue number For example 01 C R has as one possible cover 01 ie it7s covered by itself Suppose it had Lebesgue number A then pick m E 0 Since BAQ m 7 Ax A contains negative points we have BA g 01 and thus this neighborhood is not contained in any member of the cover leading to contradiction Theorem Every open covering of a sequentially compact S C M has a Lebesgue number Proof Suppose not Let UH be an open cover for S st VA 3 E S st BMW g U0 Va Let An 172 and 7 be as above Then since S is sequentially compact has some convergent subsequence a m E S Since U0 is a cover for S m 6 U0 for some 04 Since U0 is open 37 gt 0 st BTW C U0 Now since 7 a L 3N1 st 7 2 N1 gt dnk lt rZ Moreover 3N2 2 N1 st nk 2 N2 gt Am lt rZ Now pick some LUV st nN gt N2 Let y E BMNQWN then d7y S d7mv dcnmy lt T2W lt T2T2 7 We conclude that BMW LIN C BTW C Um contrary to our assumption that Vn BMW g Ua Va Thus7 every open covering of a sequentically compact set does indeed have a Lebesgue number Theorem S C M is sequentially compact i it is covering compact Proof Suppose S is covering compact7 but not sequentially compact Then let be a sequence in S st no subsequence of converges to a point in S That implies that Vm E S 3 gt 0 st BHQ contains only nitely many terms of otherwise there7d be a subsequence converging to Now7 BT is an open cover for S and since S is covering compact7 it reduces to a nite subcover BT2117BH227 Bmk and since each member of this subcover contains only nitely many terms of x717 we conclude that S contains nitely many terms of 717 an obvious contradiction Thus covering compactness implies sequential compactness Now suppose S is sequentially compact7 and let UH be some open cover for S We know that UH has some Lebesgue number A gt 0 Pick x1 6 S and some U1 6 U0 st BA1 C U1 If S C U1 then we have succeded in reducing UH to a nite subcover lf not7 then pick uncovered point 2 6 S m E S f U16 and U2 st BA2 C U2 If S C U1 U U27 we7re done7 32 if not we continue picking uncovered points to obtain a sequence of points in S and a sequence Um of members of U0 st BAQW C Un and n1 E A 0 U16 0 U26 0 Unc If at some point the sequences terminate if for some N714 U1 UU2 U UUN then we have reduced UH to a nite subcover Now suppose7 the sequences never terminate Then since S is sequentially compact7 there is some subsequence of st mm a m E S There fore7 3N st nk Z N gt damn lt A In particular7 dN lt A gt m E BAQN C UN Since UN is open7 37 gt 07 st BTW C UN But nk gt N gt mm UN7 and therefore BTW contains only nitely many terms of 71k7 a clear contradiction to convergence We conclude that in fact7 UH reduces to a nite subcover7 and sequential compactness implies covering compactness S C M is said to be compact if it is sequentiallycovering compact In the proofs of the theorems about compactness that follow7 we will use whichever de nition of compactness leads to a more direct proof and we will supply two proofs for some of the theorems to give you better understanding of both kinds of compactness Theorem Let S1 C M1 and S2 C M2 be compact Then S S1 gtlt S2 C M1 gtlt M2 M is compact Proof Let mmyn be a sequence in S we avoid here cumbersome notation Then is a sequence in 81 and therefore has some subsequence mm that converges in 31 Now ynk is then a sequence in 82 and therefore has some subsequence ynkl that converges in 82 Moreover since was a convergent sequence in 31 the subsequence mnkl is also a convergent sequence in 31 Therefore the sequence mmyn has a convergent subsequence mnklynkl with respect to all product space metrics discussed above since both component sequences converge and we conclude that Cartesian product of two compact sets is compact Theorem The Cartesian product of n compact sets is compact Proof By induction and above theorem Theorem Closed interval 1 b C R is compact Proof 1 Let be a sequence in 1 b Consider set C m E 1 b M lt m only nitely often Clearly a E C and b is an upper bound for 0 therefore 0 has a least upper bound We will show that there is some subsequence of converging to Suppose b then 3N st 72 Z N gt 7 b and clearly we have a subsequence converging to b Now suppose lt b and no subsequence converges to then 3 b7 gt r gt 0 st 7 6 BT 7 T 7 only nitely often But then r E 0 note that 7 6 1 b contradiction to being the lub for C We conclude that in fact there is some subsequence converging to and therefore 17 b is a compact subset of lR Proof 2 Let UH be some open cover for 17 and consider set C m 6 17 b nitely many Ua would su ice to cover the interval 17 Clearly a E C and b is an upper bound7 therefore 0 has the lub Suppose lt b7 and let UDWUDQ7 7Uan be those nitely many members of U0 that su ice to cover my Then 6 Uak for some k not neces sarily unique7 and since Uak is open7 37 gt 0 st BT 7 n 7 C Uak Now Vy 6 7 7 y is covered by same Um17 UDW as 3 and therefore picking some speci c y we have that nitely many members of Ualpha su ice to cover my7 which contradicts being the lub for C We conclude that b and therefore nitely many Ua cover 17 b7 and thus 17 is compact Theorem Closed box abbl X 127 b2 gtlt gtlt ambn C R is compact Proof It is a nite Cartesian product of compact sets Theorem BolzanoWeierstrass Any bounded sequence in R has a convergent sub sequence Proof Any bounded sequence in R is contained in some closed box7 and therefore has a subsequence that converges to some point in that box Theorem Suppose M is compact and S C M is closed Then S is compact Proof 1 Let be a sequence in S then is also a sequence in M and therefore has a convergent subsequence 7 a m E M Since S is closed in M we have m E S and therefore has a subsequence that converges in S We conclude that S is compact Proof 2 Let UH be some open cover for S then since SC is open UH US is an open cover for M and since M is compact it reduces to a nite subcover for M and therefore it is a nite cover for S Now there are two possibilities First SC might not be a member of this nite subcover then we have reduced UH to a nite subcover for S Now suppose SC is a member of the nite subcover we found ourselves with then it is obvious that the rest of the nite subcover still covers S since no element of S is contained in SC and by excluding SC we are left with the nite subcover for S to which the original cover U0 is now reduced We conclude that S is compact Theorem Compact set S C M is closed and bounded Proof Suppose S is not closed then 3m a sequence in S st M a m S Since S is compact 3 some subsequence xnk a 6 S but since is a convergent sequence in M all of its subsequences converge to the same limit in M and we have that 7 a m and by uniqueness of limits we have m 6 S a contradiction to m not being in S So S is closed Now let m E M and suppose S is not bounded Then Vn E N 3 E S st dn gt 71 Since S is compact 3 some subsequence of a sequence in S st 7 a 6 S Since all convergent sequences are bounded for some 7 gt 0 and for some y E M for example we have 7 6 BTy Vnk Now let T dy We observe that by the property 3 of the metric we have dnk S dy dynk S W 7 contradictory to the fact that dnk a 00 as 72 a 00 We conclude that S is in fact bounded The converse to that statement every closed and bounded subset of a metric space is compact is not true in general For example let M N with discrete metric Then M is a closed and bounded subset of itself m E B21V E M but the sequence 1234 in M has no convergent subsequence and therefore M is not compact The converse is however true in R and a more general converse will be provided again later Theorem HeineBorel Every closed and bounded S C R is compact Proof Since S is bounded it is contained in some closed box in R and is therefore a closed subset of a compact set We conclude that S is compact We will now proceed to construct a more general converse statement We start by intro ducing a new notion S C M is said to be totally bounded if V6 gt 0 there exists a nite covering of S by E neighborhoods Notice that this de nition is di erent from the de nition of non total boundedness given earlier Theorem Let M be a complete metric space Then S C M is compact i S is closed and totally bounded Proof Suppose S C M is compact We have already shown that S has to be closed Now let 6 gt 0 be given7 and consider the following open cover for S B5 m E S Since S is compact7 the cover reduces to a nite subcover and we have a nite covering of S by E neighborhoods7 and we conclude that S is totally bounded Now suppose S C M is closed and totally bounded Let be a sequence in S Let En 172 V72 Since S is totally bounded7 we have a nite covering for S by 1 neighborhoods B51y1 17B51y1 277B51y1m1 for some y1 17y1277y1m1 E M Then at least one of these neighborhoods contains in nitely many terms of the sequence 717 suppose Bag1 and let N1 be st mm 6 B51y1 k1 Now7 since every subset of a totally bounded set is totally bounded you can easily show it7 we have a nite covering of Belg1191 by 62 neighborhoods B5212V17B521227 B52y2m and once again one of these neighborhoods contains in nitely many terms of the sequence mm7 suppose Egg21927 and let N2 gt N1 be st N2 6 B52 11192 Continuing in this manner we obtain a subsequence mm which is Cauchy since nm gt N gt dNnNn lt 61w 1N Since M is complete Nk a m E M Since S is closed in M m E S Thus has a subsequence that converges to a limit in S and we conclude that S is compact We note here that the conditions speci ed are indeed necessary Take completeness for example Consider S Q 0 77139 a subset of a metric space Q with the usual distance metric Then S is closed and totally bounded subset of Q but its clearly not compact since sequence 3 31 314 315 in S doesn7t have a subsequence that converges to a point in S or even in Q for that matter Also substituting boundedness for total boundedness in the theorem above would not suf ce since we have already seen that a complete metric space N with discrete metric is a closed and bounded non compact subset of itself Below are some important results on the behavior of continuous functions on compact sets Theorem The continuous image of a compact set is compact Proof 1 Let f M a N be continuous let S C M be compact and let fS C N denote the image of S under f Let yn be a sequence in fS then Vn 3 E S st fan yn Since S is compact the sequence in S has some convergent subsequence xnk a m E S By continuity of f7 we then have that ynk fxnk a f E fS7 and therefore yn has a subsequence that converges to the limit in fS7 and we conclude that fS is compact Proof 2 Let f M a N be continuous7 let S C M be compact and let fS C N denote the image of S under f Let UH be an open cover for fS in N Then since f is continuous7 f 1Ua is an open set in M V047 and therefore f 1Ua is an open cover for S in M Since S is compact7 f 1Ua reduces to a nite subscover f 1U1f 1U27 7fquotlUn7 and clearly U17U27 7U is an open cover for fS you can easin see it yourself7 Which is a nite subcover of the original cover We conclude that fS is compact Theorem Continuous real valued funciton de ned on a compact set assumes its maxi mum and minimum Proof Let f M a R be continuous and let S C M be compact Then fS C R is closed and bounded7 and we have seen that a closed and bounded subset of R contains its glb and its lub Theorem Every continous function de ned on a compact set is uniformly continuous Proof Let M be compact and f M a N continuous Suppose f is not uniformly con tinuous Then 36 gt 0 st V6 gt 0 Emmy E M st dmyn lt 6 but dfn7fyn gt E Let 6 1n and for each 71 let mmyn E M be as above Since M is compact the se quence in M has some convergent subsequence Moreover the sequence ynk also has some convergent subsequence ynk a y E M Since mnkl is a subsequence of a convergernt sequence it also converges and it converges to the same limit as the mother sequence and since dnkynkl lt 1nk we can easily see that it also converges to y The continuity of f implies that fnkl a y and fynkl a y Now let N be st 7 Z N gt dfnklfy lt 62 and dfynklfy lt 62 then we have m N gt dfnk7fym S dfnk7fy dfy7fynk lt E2 E2 6 which contradicts our assumption that dfnfyn gt e V72 We then conclude that f indeed is uniformly continuous 38 More Results on R We introduce some notation rst Given sequence in R we say that limn m 6 R if 7 a m in R We say that limn oo ifVM gt 0 EN st 72 Z N gt 7 gt M And similarly limn 700 if VM lt 0 EN st 72 Z N gt 7 lt M Here are some examples 1 3 31 314 3141 Then limn 7r 2 2 3 5 7 11 Then limn oo 3 1 4 9 16Thenlimn 700 41 4 17 17 27 27 37 37 Then limn does not exist Given a sequence in R7 we say that M hm supxn if M lim sup We de ne 714100 17277 m hm infn similarly Here are some examples 1 17273747 57 7 then hm supn hm inf oo 2 17 1727 17 2737 7 then hm supxn 007 hm infn 1 3 373173147 31417 7 then hm supn hm infn 7r We say that sequence is monotone increasing if n gt m gt 77 gt mm The sequence is monotone nondecreasing if n gt m gt 77 2 mm The monotone decreas ing and monotone non increasing sequences are de ned similarly A sequence is said to be monotone if its monotone non increasing or monotone non decreasing note that every monotone increasing sequence is also monotone non decreasing7 and every monotone de creasing sequences is monotone non increasing7 so these two classes are also covered by the de nition 1 37 317 3147 31417 is monotone increasing 2 17 47 97 167 is monotone decreasing 3 17 27 27 37 37 37 47 47 47 47 is monotone non decreasing 4 17 17 17 17 is monotone non decreasing and monotone non increasing 42 5 7 1 1 2 1 2 3 1 2 3 4 is not monotone but it has many possible monotone subsequences The following are some basic results about sequences in R H 03 Hgt 5quot 53gt 5 00 9 H O Let 7 am ER and let k E lR Then yn kxn a km Letmnamandynayian Thenznnyn y Let 7 a m and yn a y in lR Then 2 mnyn a my Let 7 am 0 in lR st 7 a 0 V72 Then yn 1xna1m Let M a m a 0 in lR st 7 a 0 V72 and let yn a yin lR Then 2 ynxn a yx Let limn oo lim yn gt 0 Then lim2n xnyn 00 Let be monotone and bounded Then converges in lR Let be any sequence in lR Then has a monotone subsequence Together this and the previous result imply that every bounded sequence in R has a convergent subsequence Let be a monotone sequence Then limn exists it could of course take on values of 00 and 700 Let fg be real valued funcitons M a lR continuous at some m E M Then f 9 f9 and fg asusming gm a 0 are all continuous at m 43 11 Given a sequence 77 lirn supn and lim infn are well de ned either they belong to R or take values of too 12 a a r iff lirn supn lirn infn m The proofs of these results are left as exersises 39 Calculus and Function Convergence We say that a real valued funciton f is differentiable at L if one of the following equivalent conditions holds 139 hm N e M tax if 7 x 239 hm fAA5vf AzaO Lexists Lexists 3 Vegt036gt0st ltillt6gtl iLllt We call L the derivative of f at r and write f L We say that f is differentiable on the interval 17 b if it is differentialbe at every r 6 17 b The following are familiar results from calculus 1 If f is differentiable at 7 then f is continuous at m 2 If f and g are differentiable at 7 then so is f g and f g f g 3 lff and g are differentiable at 7 then so is g7 and fg f gmfg 4 lf cV7 then f 0V 5 If f and g are di erentiable at m and ya a 07 then fg is di erentiable at m and rmz 7 747 a 91 a 9 a 6 Chain Rule If f is di erentiable at 7 and g is di erentiable at f7 then 9 o f is di erentiable at m and g 0 f 9ff Theorem Let f be di erentiable on 17 b and suppose it achieves a maximum or mini mum at some 0 6 17 b Then f c 0 Proof We will prove the theorem for maximum7 and proof for minimum is analogous Let 75 approach 0 from above Then AW 3 0 Vt If we let 75 approach 0 from below7 then ai c Z 0 Vt Since both expressions have to tend to the same limit L j c7 we t7c conclude that f c 0 Theorem Mean Value Suppose f is continuous on 17 and di erentiable on 17 Then 3 c E 17 st fb 7 fa f cb 7 a In particular7 if lf l S M V m 617b7 thethJ E 17 we have lft 7fl S Mlt7l Proof Let S W and let gm f 7 Sm Clearly g is di erentiable on 17 b and continuous on 17 why Moreover7 9a 9b Since 9 is continuous on a compact set7 it achieves maximum and minimum and since 9a 9b it achieves at least one of them at some 0 6 17 b Then 0 g c f c 7 S gt fb 7 fa f cb 7 a We state the following result Without proof Which can be found for example in Pugh p145 If f is differentiable on a b then f has the intermediate value property Also all familiar results from calculus derivative and integral formulas L7Hopital7s Rule results on series convergence etc hold We say that a sequence of functions fn 1 b 7 R converges pointWise to f fn 7 f if V m 6 ab fn 7 f as n 7 00 We say that a sequence fn ab 7 R converges uniformly to f fn f ifVe gt 0 3 N st 72 Z N gt lfn7fl lt V 6 ab You should convince yourself that the sequence of functions fnx m on open interval 01 converges pointWise to the function 0 if 0 S lt l fa 1 ifx1 but does not converge uniformly Theorem lf fn f and each fn is continuous at m then f is continuous at m Proof Let 6 gt 0 be given and let N be st 72 Z N gt lfny 7 fyl lt 63 V y Since fN is continuous at m 3 6 gt 0 st lm 7 yl lt 6 gt lfN 7 fNyl lt 63 Then lm 7 yl lt 6 lffyl S lf fNllfN fN1llfNy f1l lt E3 3 3 67 and we conclude that f is continuous at m Note that our example above shows that pointWise convergence of continuous functions is not suf cient to ensure continuity of the limit We state two more results Without proving them The proofs can be found in Pugh H Suppose fn f7 then fndx a ffd as n a 00 N3 Suppose fn f and f j y then 9 f 4 References H Pugh7 CC7 7Real Mathematical Analysis77 Springer7 2002 N Rice7 John A7 7Mathematical Statistics and Data Analysis77 2nd ed7 Duxbury Press7 1995 03 Ross7 Kenneth A7 7Elementary Analysis The Theory of Calculus77 Springer7 2000 M104 Notes Lecture 1 Aaron McMillan August 6 2008 1 Differentiation This section will focus on functions f R a R We7ll frequently use the following notation lirnmna z b if for all sequences Q R a such that a 17 the sequence converges to b Alternatively and equivalently7 liming f b if and only if every B5b contains the image of some B5a neighborhood De nition 11 A function f R a R is differentiable at a E R if hm we 7 fa a man z 7 exists We denote the value of this limit by f a E R and call it the derivative of f at 1 Thus we see7 by our second characterization of limits above7 f is differ entiable at a E R with derivative L7 if and only if V6 gt 07 there exists 6 gt 0 such that if lx ial lt othen lw xia 7 Ll lt 6 Proposition 12 Differentiation Rules Suppose fg R a R i ff is di erentiable then f is continuous ii If g are di erentiable at z E R then so is f 9 Furthermore f QWC Hr 9 06 iii If g are di erentiable at z E R then so is f 9 Furthermore fch f 9 f969 96 1 iv Iffz e is constant then f 0 for all z E R 1 If fg are di erentiable at z E R and 9a 31 0 then so is fg Furthermore W ammo A Proof 1711 include proofs of and v 7 otherwise see Ross i A function is continuous at z E R if lirntnm ft For t 31 x we have nog 9ea a So we see that lirntnm ft f 0 f v Note that Umweumaw 7ltr t x H V WWW f959t 996 900 Since 9 is continuous at x by i and 9a 31 0 there is a small interval around z where gt 31 0 and we can therefore take the limit Thus we see that V Q A V m VA f9tf9w ft9wfw9t 9w9twt 7 1 ft9wfw9wfwgwefwgt 9w9t wit luwrnimaga 99t t Taking the limit as t a a and noting that limtnmgt 9a because 9 is continuous the result follows Corollary 13 pr ans a1z a0 is a polynomial then p nanzn 1L 2a2x a1 Theorem 14 Chain Rule ff is di erentiable at z andg is di erentiable at fx then 9 o f is di erentiable at z and the derivative is g o f z o f96f 95 Proof To prove the chain rule we note that for some small interval around x we can write ft f96 t WWW 110 2 where ut is a function such that ut 7 0 as t 7 x Similarly7 we can write 98 7 99 7 8 7 99 9 718 Using the above equalities7 with y f and s ft7 we can write 9 0 ft 7 9 0 f96 9ft 7 9f96 ft 7 f969 f96 11 ft 1t 7 MIC96 ut 9 f 96 Uft Thus7 we see the derivative is 9 o ft 7 9 o fz t7x gmz l1 gigsxulttgtgtlt9ltfltxgtgtvltflttgtgtgt manz Where ift 7 ifx 0 because f is continuous 11 The Mean Value Theorem Proposition 15 If f c gt 0 then f is increasing at c that is 36 gt 0 such that I ifc76 lt z lt c then f lt fc and ifc lt z lt c6 then f0 lt f39 Proof Since f c gt 07 36 gt 0 such that if lx7cl lt 6 then lw7f1c lt f c The result follows from analyzing the signs in this expression Remark 16 This does NOT mean that f is an increasing function on c 7 Xe 6 Remark 17 One gets an analogous property for f c lt 07 by considering the function 7f Corollary 18 ff a7 b 7 R is di erentiable and has a marimumminimum at c 6 ab then f c 0 Theorem 19 Rolle7s Theorem Suppose f 17 7 R is continuous an ab and di erentiable an ab If fa fb then 3c 6 ab such that f c 0 Proof Since f is continuous on ah the extreme value theorem gives that f takes a minimum and maximum on a7b If f takes either a min or max c E ab7 then f c 0 by the above corollary Otherwise7 the minimum and maximum both occur at the endpoints In this case7 since fa fb7 we have that f is constant7 and so f 0 for all z 6 ab D 3 Theorem 110 Mean Value Theorem Suppose f ab 7 R is continuous on ab and di erentiable on ab Then 30 6 ab such that fb 7fa f 9 b i a Proof De ne the function Md f 7 hz where h Thus we see that a b By Rolle7s Theorem 30 6 ab such that MS 0 However Md f 7 h giving us the desired result Corollary 111 Suppose f ab 7 R is continuous Then iff z 0 for all z 6 ab then f is constant Corollary 112 ff ab 7 R is continuous and f gt 0 for all z 6 ab then f is strictly increasing on ab Theorem 113 lntermediate Value Property of Derivatives If f is dif ferentiable on a 7 eb 6 then f takes every value between f a and f b Proof Suppose f a lt f b and pick f a lt 77 lt f b De ne f 7 77x We want to nd a c such that c 0 Note Ma lt 0 and Nb gt 0 Since o is continuous on ab there exists c 6 ab that c is a minimum lf c gt 0 then c 7 a and 3x1 6 ab such that x1 lt c which contradicts that c is a minimum Similarly if c lt 0 then c 7 b and zz 6 ab such that 2 lt c which again is a contradiction Thus c 0 D Corollary 114 Suppose f ab 7 R is di erentiable If f is discontin uous at c then either limmnci f or limmn f cannot epist In other words f cannot have ajurnp discontinuity at c 12 Inverse Function Theorem Theorem 115 Suppose f ab 7 R is continuous and di erentiable on ab with f 7 0 for all z 6 ab Then the inverse function f 1 epists and is di erentiable on its domain with derivative f 1 x FEW Proof Sketch First one shows that f 1 exists Since f 7 0 and f has the intermediate value property it follows that either 1 f gt 0 for all x in which case f is strictly increasing or 2 f lt 0 for all x in which case f is strictly decreasing In either case this proves f is injective 1 to 1 4 and so f l exists with domain fafb if f is increasing or fbfa if f is decreasing 7 we are implicitly using intermediate value theorem here how Second we need to show that f 1 is continuous To do this x a point 0 6 fafb we assume f is increasing and an E gt 0 Choose 6 lt min0 7 ff 1z0 7 6ff 1x0 6 7 x0 and use the fact that f 1 is also strictly increasing to show this choice of 6 works draw a picture Third to show its differentiable just calculate the derivative of f 1 using the de nition and use the fact that f 1 is continuous to justify that if z 7 0 then f 1z 7 f 1z0 D Example 116 We can use the inverse function theorem to de ne logz from em lf f em we know that f gt 0 for all z E R So if y em then Thus we see that the derivative of logx is Example 117 If f 3 then f is invertible with continuous inverse given by f 1x z However f 1 is not differentiable at z 0 and this is because f 0 0 13 Taylor s Theorem Fix an f I 7 R that7s at least 71 1 times differentiable on some open interval I and two points x a E I We will de ne WW 2 f l t z7t2 n FM ft f t96 t x 7 t We can apply the Mean Value theorem to Fn check that it satis es the hypotheses on the interval 1 z and obtain the existence of some 6 E a m such that 7Fna F 0 x 71 Now we want to decipher both sides of this equality First using the product rule we have f t 2 n1 7f V x 71 FM f tf t1f t itH it2 Note that all the terms cancel except for the last term giving that f 1 t T it FM x 7 t 5 Thus we see that n1 9 Sn 7 a 7 6 z 7 a Next we note that fx and thus 7 Fna F 6 7 a translates to f a n f a f95faf az7a z7a2 x 7a Sn Now we de ne the Taylor remainder by Rn 7 a 1 and observe that lSnl lt There are many ways to estimate the size of Rm and if it can be made small7 then we get Taylor s approximation n ff 7 f a n 22 x 7 a Theorem 118 Suppose that f I 7 R is in nitely di erentiable 7 that is f epists for all n E N and for all z E I If 3M 6 R such that lf xl lt M for all n E N and z E I then converges uniformly to f In other words i fWa n f96 faf aa ria2 f 96 96 7 0 n0 Proof Since lf xl lt M7 we have lSnl lt anl 7a 1l S Since m aln 7 07 the result follows E n Example 119 em Suppose that f is a differentiable function such that 1 f0 1 and 2 f f for all z E R It follows that f is in nitely differentiable Let us restrict the domain of f to I 7r7r for some r E R Then since f is continuous7 it takes a maximum M and minimum in This implies lf xl lt maxJLlMl7 and so f is equal to its taylor expansion on 7r7r Thus 1 n n n n0 n0 Men M n fZ Z z gojx We de ne em x7 and since r was arbitrary7 em is de ned on all of R All the familiar properties of em can be derived from this power series de nition

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.