Honors Introduction to Analysis
Honors Introduction to Analysis MATH H104
Popular in Course
Popular in Mathematics (M)
This 25 page Class Notes was uploaded by Kavon Feest on Thursday October 22, 2015. The Class Notes belongs to MATH H104 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/226595/math-h104-university-of-california-berkeley in Mathematics (M) at University of California - Berkeley.
Reviews for Honors Introduction to Analysis
Report this Material
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 Ordered Sets An annex to H104 H113 etc Mariusz Wodzicki September 22 2009 1 Vocabulary 11 De nitions De nition 11 A binary relation 5 on a set S is said to be a partial order it is re exive x j x 1 weakly antisymmetric iijyandijthenxy 2 and transitive i ijyandyjzjhensz 3 Above 3 y z are arbitrary elements of S De nition 12 Let E Q S An element y E S is said to be an upper bound for Elf x j y forany x E E 4 By de nition any element of S is declared to be an upper bound for the empty subset We shall denote by UE the set of all upper bounds for E UEy Sxjyforanyer 5 Note that U S De nition 13 We say that a subset E Q S is bounded from above UE 1quot ie when there exists at least one element y E S satisfying 4 De nition 14 lfyy E UE O E then yjy and yjy Thus y y and that unique upper bound of E which belongs to E will be denoted max E and called the largest element of E It follows that UE O E is empty when E has no largest element and consists of a single element namely max E when it does If we replace 5 by everywhere above we shall obtain the defini tions of a lower bound for set E of the set of all lower bounds LEy 5xyforanyx E 6 and respectively of the smallest element of E The latter will be denoted min E 111 The Principle of Duality Note that the relation defined by xjrevy if xiy 7 is also an order relation on S We will refer to it as the reverse ordering Any general statement about partially ordered sets has the correspond ing dual statement that is obtained by replacing S j with 5 5 quot Un der this duality upper bounds become lower bounds maxima becoma minima suprema become infima and vice versa Therefore most general theorems about partially ordered sets possess the corresponding dual theorems Below I will be usually formulating those dual statements for the convenience of reference Exercise 1 Show that E Q S is bounded below and nonempty then LE is bounded above and nonempty Dually if E is bounded above and nonempty then UE is bounded below and nonempty 112 If E Q E Q Sthen max 3 e 11E 8 when max E exists and dually min B e LE 9 when min E exists If both max E and max E exist then max E 5 max E 10 Dually if both minE and min E exist then minE j minE 11 Exercise 2 Sandwich Lemma for maxima Show that E Q E Q E and both max E and max E exist and are equal then max E exists and max E max E max E 12 Dually if both min E and min E exist and are equal then minE exists and min E minE min E 13 De nition 15 When min UE exists it is called the least upper bound of E or the supremum of E and is denoted sup E Dually when max LE exists it is called the largest lower bound of E or the in mum of E and is denoted inf E For the supremum of E to exist subset E must be bounded above The supremum of E may exist for some bounded above subsets of S and may not exist for others 113 Example Let us consider 5 Q the set of rational numbers with the usual order Both the following subset E1 Q Q E1x Q x2lt1 14 and the subset E1 Q Q E2 x g Q I x2 lt 2 15 are simultaneously bounded above and below None of them has either the largest nor the smallest element but sup E1 1 and infE1 71 while neither sup E2 nor inf E2 exist in S Q Exercise 3 Show that sup minS and inf max 5 16 In particular sup exists if and only if S has the smallest element similarly inf exists if and only if S has the largest element 114 Intervals s and Let S j be a partially ordered set For each s E 5 let lt5 x e s I x 5 s lt17 and 5 z y 6 5 I S 5 y 18 Exercise 4 Show thatfor E Q 5 one has LE s for some s E S 19 ifund only inf E exists In this case LE infE 20 Dually UE s for some s E S 21 if and only if sup E exists In this case UE sup E 22 115 Totally ordered sets De nition 16 We say that d partially ordered set S j is totally or lin early ordered my two elements 3 and y of S are comparable either 3 j y or y j x 23 Totally ordered subsets in any given partially ordered set are called chains Exercise 5 Let S j be u totally ordered set and EH Q S be two subsets Show that either LE Q LE or LE Q LE 24 12 Observations 121 For any subset E Q 5 one has E g LUE LUE 25 and E g ULE ULE 26 122 If E Q E Q Sthen UE 2 113 27 and LE 2 LE 28 Exercise 6 Show that E Q E and both sup E and sup E exist then sup E j sup E 29 Dually if both inf E and inf E exist then inf E 5 inf E 30 Exercise 7 Sandwich Lemma for in ma Show that E Q E Q E and both inf E and inf E exist and are equal then inf E exists and inf E inf E inf H 31 Dually if both sup E and sup E exist and are equal then sup E exists and sup E sup E sup E 32 123 By applying 27 to the pair of subsets in 25 one obtains Has 2 mums llamas while 26 applied to subset UE yields 11E g ULUE It follows that UE ULUE 33 Dually Luz Lama lt34 Note that equality 34 is nothing but equality 33 for the reverse or dering 124 For any subsets E Q S and E Q 5 one has 1102 u H 1102 m um lt35 LEUE LE LE 36 125 For any E Q 5 max E exists and only sup E exists and belongs to E and they are equal sup E max E 37 Dually minE exists and only inf E exists and belongs to E and they are equal inf E min E 38 Indeed if max E exists then it is the least element of UE Cf Defi nition 14 If supE exists and is a member of E then it belongs to UE O E which as we established cf Definition 14 consists of the single element max E when UE O E is nonempty The case of min E and inf E follows if we apply the already proven to S jI EV 126 For any E Q S inf UE exists and only sup E exists and they are equal max LUE inf UE min UE sup E 39 Indeed inf UE maxLlIE e 11E in View of E Q LUE Cf 25 combined with 8 where E LUE Thus mug min 11E by 37 Dually sup LE exists and only inf E exists and they are equal min ULE sup LE max LE inf E 40 127 Example the power set as a partially ordered set Let S 9A be the power set of a set A 9A the set of all subsets of A 41 Containment Q is a partial order relation on Subsets 6 of 9 A are the same as families of subsets of A Since 5 9A contains the largest element namely A and the smallest element namely every subset of 9A is bounded above and below The union of all memebers of a family 6 UXa Aa XforsomeX a 42 Xe quot is the smallest subset of A which contains every member of family 6 Hence sup 6 exists and equals 42 Dually the intersection of all members of family 6 Xa Aa XforallX a 43 Xe quot is the largest subset of A which is contained in every member of family 6 Hence inf 6 exists and equals 43 The power set provides an example of a partially ordered set in which every subset including the empty set possesses both suppremum and infimum 13 Partially ordered subsets 131 In S Q T is a subset of a partially ordered set T 5 then it can be regarded as a partially ordered set in its own right One has to be cau tioned however that S with the induced order may have vastly different properties For a subset E Q S the sets of upper and lower bounds will generally depend on whether one considers E as a subset of S or T In particular E may be not bounded as a subset of 5 yet be bounded as a subset of T When necessary we shall indicate this by subscript S or T Thus LTE UTE infTE supTE will denote the set of lower bounds the set of upper bounds the infirnurn and the supremum when E is Viewed as a subset of T Exercise 8 Show that for E Q 5 one has SUPTE 5 suPsE 44 whenever both suprema exist Dually one has iIlfsE 5 ME 45 whenever both infirna exist Exercise 9 For E Q S suppose that supTE exists and belongs to S Show that supSE exists and supSE supTE 46 Dually if infTE exists and belongs to S then infSE exists and infSE infTE 47 Exercise 10 Let E Q S and suppose that S j is a partially ordered subset of T 5 Show that infTE exists then LE infTE OS s E S l s j infTE 48 Here LE L5E Dually one has 1105 sumo m s s e s l was 5 s lt49 if supTE exists Exercise 11 Find examples of pairs E Q S of subsets of Q such that a E is unbounded above in 5 yet bounded in Q b E is bounded in S and supQE exists but supSE does not C E is bounded in S and supSE exists but supQE does not d both supSE and supQE exist but supSE i supQE 132 Density De nition 17 We say that a subset S Q T is supdense every element t E T equals t sup E for some subset E Q 5 By replacing sup with inf one obtains the de nition of a infdense subset 133 Example Suppose that a partially ordered set S j is the union of three subsets S XUYUZ suchthat xjy and 352 foranyxEXy Yandz Z and noyEY andzEZ are comparable Let TSUU where xltUlty foranyxEXy Y and xlt lty foranyxEXz Z Note that U and g are not comparable Finally let T be the subset S U U of T a S j as a subset of Tj One has LTY U and LTZ It follows that U infTY and g infTZ and therefore 5 is inf dense in T In addition Ul SX QOS but U i g they are not even comparable Exercise 12 Show that neither U nor g equals supTE for any E Q S In particular 5 is infrdense in T but not sup dense 10 b S j as a subset of TC 5 One has U infTY hence S is inf dense in T In addition LY 11 OS X LZ and U infTY while infTZ does not exist Exercise 13 Let S j be a partially ordered subset of T 5 Show that t meE 50 for some E Q S then t infTt 5 51 Dually if t suPTE 52 for some 3 Q S then i supTlttl 5 53 Exercise 14 A criterion of equality for in ma Let S j bea partially or dered subset of T j and E Q 5 Suppose that both infE and t infTE exist Show that there exists a subset E Q S such that 52 holds then infTE inf E Exercise 15 Formulate the dual criterion of equality for suprema 14 Morphisms De nition 18 Given two partially ordered sets 5 j and 5 5 a map ping f SSS which preserves order ifs 5 t the fS 5 f0 Srt E 5 54 is said to be a morphism S jgtS 5 11 De nition 19 A mapping 2 SSS is said to be an order embedding 5r 5 m 5C5 55 if it satis es a stronger condition s j t ifand only is 5 it st E S 56 Exercise 16 Show that an order embedding is injective De nition 110 A morphism f S jgtS 5 is said to be an isomor phism it has an inverse ie there is a morphism g 5 5gtS 5 such that fog ids and gof ids Exercise 17 Show that an order embedding 55 is an isomorphism onto its image 15 5 De nition 111 We say that a morphism f S jgtS 5 is sup continuous if f preserves the suprema More precisely it has the following property for any E Q S sup E exists then sup f E exists and SupfE fsup E Here as everywhere else the subset f E Q S is defined to be the image of E Q 5 under f fE y E S i y for some x E E 58 Exercise 18 State the dual de nition of an infcontinuous morphism 57 Exercise 19 For any partially ordered 5 5 let 5 denote the subset obtained by removing max 5 and minS they exist Show that the inclusion 5 5 m 55 59 is both supr and infrcontinuous Exercise 20 A criterion of continuity Let S j be a sup idense subset of T 5 Show that the canonical embedding 55 41 60 is infrcontinuous Dually if S j is a inf dense subset of T 5 then the canonical embedding 60 is sup continuous 12 141 Example the canonical embedding into the power set Let S j be a partially ordered set For any 55 6 5 let s j 5 if and only if 5 Q s 61 Thus the correspondence l1 5mg 5 H 5 62 is an order embedding of S 5 onto the partially ordered subset of 95r Exercise 21 Show that for any E Q S supltEl U lt4 63 SEE and was Luz lt64 in It follows that supE sup E in 95 if and only if maxE exists In particular the canonical embed ding into the power set 62 is nearly never sup continuous supE always exists it equals E but is a proper subset of sup E except when E is an interval of the form 17 The canonical embedding is however inf continuous Exercise 22 Show that the canonical embedding 62 is infrcontinuous Exercise 23 Explain why 5 is generally neither supr nor inf dense in 9 13 15 Closure operations on a partially ordered set De nition 112 Let S j be an ordered set A selfmapping s gt gt s 565 65 is said to be a closure operation it enjoys the following three properties s j s 66 ifs 5 t then g 5 t 67 and s 5 68 where s and t denote arbitrary elements of S In this case we say that an element s E S is closed s s 151 Example a topology on a set To give a topology on a set A is the same as to equip 914 Q with the Closure operation which is infrcontinuous for any family 6 Q 914 one has inf a inf a 69 where g is the family of the Closures of subsets belonging to 6 and nitely sup econtinuous for any nite family 6 Q 914 one has 70 sup 6 sup 3 Exercise 24 Show that for any Closure operation on 914 Q which satis es 70 one has Q 71 Hint Consider the empty family of subsets 14 152 Example two closure operations on the power set of a partially ordered set A partial ordering S j induces two closure operations on 95 Q the Lllrclosure E H E LUE 72 and the UL relosure E gt gt EUL ULE 73 Indeed for the Lllrclosure 25 is property 66 property 67 follows from the combination of 27 and 28 while 34 implies property 68 Note that according to 34 a subset F of S is LII closed if and only if it is of the form F LE for some E Q 5 Note that LU If S has no least element mm 5 otherw1se Dually ULlt gt if S has no largest element max 5 otherw1se It follows that is LII closed respectively LIL closed if and only if S has no least element respectively no largest element On the other hand 5 is always both LU and UL closed 2 DedekindMacNeille Completion of a Partially Ordered Set 21 Completeness De nition 21 We say that a partially ordered set S 5 has the largest lower bound property inf E exists for every subset E Q S which is nonempty and bounded below We shall say in this case that S j is infcomplete Dually we say that S has the leastupper bound property sup E exists for subset E Q S which is nonempty and bounded above We shall say in this case that S j is supcomplete 15 Lemma 22 A partially ordered set S has the largestrlowerrbound property and only it has the leastrupperrbound property Proof Suppose that S is inf complete If E Q S is bounded above and nonempty then the set of upper bounds UE is nonempty Since LUE 2 E i Q subset UE is also bounded below Then inf UE exists in view of our assumption about 5 5 But then it coincides with sup E in accordance with 39 This shows that S is sup complete The reverse implication sup completeness inf completeness follows by applying the already proven implication inf completeness sup completeness to the reverse order on S El Since sup and inf completeness are equivalent we shall simply call such sets complete 211 Lattices De nition 23 A partially ordered set S j is called a prelattice every nonempty nite subset E Q S has supremum and Exercise 25 Show that S j is a prelattice ifand only iffor any st E 5 both supst and infst exist De nition 24 A partially ordered set S j is called a lattice eoery nite subset E Q 5 including Q S has supremum and Complete partially ordered sets with the largest and the smallest ele ments are the same as complete lattices Note that in such sets every subset is bounded below and above For example the totally ordered set of rational numbers Q g is a pre lattice but not a lattice and it is not complete The power set of an arbitrary set 9A Q is an example of a com plete lattice A less obvious example is the subject of the next section 16 212 The set of LU closed subsets of a partially ordered set Let G j be a partially ordered set Let EKG Q 9G be the subset of the power set which consists of all LU closed subsets of 5 Recall that P Q S is LU closed if and only if it has the form F ME 74 for some E Q S In fact one can take E Exercise 26 Show that for any family 6 Q EKG of Lllrclosed subsets of S the supremum of 6 in EKG exists and equals sup aLUltU E 75 Ee quot ie supys a is the Lllrclosure of sup m a LU supers a 5111C 9s a 76 Exercise 27 Show that i S has no least element mmf s f 77 min 5 otherwise Thus every family 6 Q EKG is bounded below and obviously the infimum of the empty family exists and is equal to inf maxEKG 5 By invoking Lemma 22 we deduce that the infimum of every family 6 Q EKG exists in EKG and we established the following fact Proposition 25 For any partially ordered set G j the set of Lllrclosed suhr sets EKG Q is a complete lattice El Exercise 28 Show that in EKG one has SHINE LIKE 78 and infltEl ME 79 213 Since intervals s are LU closed Sl LSr the image of set 5 under the canonical embedding 62 is contained in f Exercise 29 Show that 5 is both supr and in dense in f Exercise 30 Show that the embedding l15r gfg5r 80 is both supr and infrcontinuous In other words show that in 215 one has suPysltEl SUP El 81 whenever sup E exists in S j and mfysltEl infEl 82 whenever infE exists in S 5 By combining the results of Exercises 29 and 30 with Proposition 25 we establish the following important fact Theorem 26 Any partially ordered set S j admits an embedding onto a dense subset of a complete lattice and this embedding preserves suprema and in ma ie is sup and infrcontinuous El The lattice 215 Q is called the DedekindMacneille envelope of a partially ordered set S 5 or the DedekindMacneille completion of S j Strictly speaking the latter should apply to the embedding 80 of 55 into S It is worth noticing that for any subset E Q S which is not bounded above in S j one has supE max 215 S 83 and for a subset not bounded below infE min 3515 84 note that min EKG in this case 18 214 A variant Dedekind MacNeille completion adds to any partially ordered set all the missing suprema and infima including the suprema and infima for unbouded sets A simple variant of the above construction allows to add only the suprema of nonempty subsets that are bounded above and the infima of nonempty subsets which are bounded below while leaving unbounded sets not bounded Let 55 be a partially ordered set Let us consider the subset EXWS Q EKG which consists of the LU closures of nonempty subsets of S which are bounded above Exercise 31 Show that e EXS Exercise 32 Show that S E EXS and only S has the largest element It follows that 5 S if both min 5 and max 5 exist 6 7 EXSUS ifminS exists andmaxS does not 8 i EXS U if maxS exists and minS does not 5 EXS U Q S if neither minS nor max 5 exist Thus EXS has the same elements as 215 except possibly for the two extremal ones and 5 Exercise 33 Show that 5 Q EXS By Exercise 19 suprema and infima in few 5 coincide for nonempty bounded subsets of 15 with those in 215 hence 5X15 C is a complete partially ordered set 7 In particular the embedding l15r5g5r9 86 is both sup and inf continuous Finally since 5 is sup and inf dense in 215 it is dense also in 5 5 We established thus the following variant of Theorem 26 19 Theorem 27 Any partially ordered set S j admits an embedding onto a dense subset of a complete partially ordered set and this embedding preserves suprema and in ma ie is sup and infrcontinuous and also unboundedness of subsets if E Q S is not bounded above below in S then E 8 is not bounded above resp below in the completion 7 El 215 It follows from Exercise 5 that 2 5 Q and therefore also ffS Q are totally ordered if S j is totally ordered Thus one can strengthen the statements of Theorems 26 and 27 by adding that the corresponding completions of totally ordered sets are themselves totally ordered 216 R and E 70000 In the case of Q 3 we obtain two totally ordered completions Q Q is a model for the set of real numbers 88 while Q Q is a model for the set of extended real numbers F1RU70000 70000 89 3 Universal Properties of the DedekindMacNeille Completion In this section 5 5 denotes a subset of T 5 31 Extending the Canonical Embedding 311 The correspondence tMt Ss Slsjt 90 20 defines a morphism Tjgt9 5Q which extends the canonical embedding S j gt 95 Q cf 62 to T 5 Exercise 34 Show that 90 is an order embedding S j is suprdense in T 5 In particular morphism 90 is injectioe S j is sup dense in T j 91 If S j is not sup dense then 90 is generally not injective Thus 11 5 Q 5 in Example 133a but U i g 312 If t infTE for some E Q S then t OS LE E S according to 48 It follows that the image of morphism 90 is contained in m5 if s 5 is mfrdense m T 5 92 The following example demonstrates that the image of morphism 90 may be contained in EXS even though no element of T 5 may be of the form infTE for some E Q 5 313 Example Let T Q0 1 equipped with the usual order Let 5XEQlxlt00rxgt1Qlt0UQgt1 Then all t E TS x E Q l 0 lt x lt 1 are being sent by morphism 90 to one and the same LU closed subset of S M m S QltO LQgt1 Exercise 35 Show that every t E T S is neither of the form infTE nor of the form supTE for some E Q S 21 314 When 5 j is inf dense in T j then one can easily describe the im age of T under morphism 90 a subset E of EXS is in the image if and only if it is of the form me3 m s 7 LTE m s LE 93 for some E Q S which possesses in mum in T This is so since every element of T equals infTE for a suitable subset E Q S and then tl LTE Note however that LE for a particular subset E may belong to the image of morphism 90 while infTE may not exist We only know that there must be another subset E Q S such that LE LE and infTE exists In Example 133b one has LZ 11 5 LY where Y possesses infimum in the larger set which is denoted there T while Z does not 315 By combining 93 with the assertion of Exercise 34 we deduce the follow ing important universal property of the Dedekind MacNeille completion Theorem 31 If S j is a subset of T j which is both infr and sup rdense then morphism 90 embeds T j isomorphically onto the subset of 215 E E EXS E LEfor some E Q S which possesses in mum in T In particular every subset of 5 possesses in mum in T then 90 establishes a canonical isomorphism between T j and the DedekindrMacNeille completion 2 5 Q which extends the embedding of S 5 into 2 5 Q El 22 32 Completing a subset in a bigger partially ordered set 321 In general there is no largest subset T Q T such that S 5 would be sup dense inf dense or both sup and inf dense in T 5 322 Example Let S Q 0 be equipped with usual order and T S U u b with x lt a lt y and x lt b lt y for any x E Qlt0 and y E Qgt0 In this case S is both sup and inf dense in T1 S U a and T2 S U 17 but is neither sup dense nor inf dense in T T1 U T2 Exercise 36 Show that neither a nor 7 is of the form infT E or supT E for any subset E Q 5 Thus T1 and T2 are two distinct maximal subsets of T in which 5 is dense in any of the three spelled out senses 323 For any partially ordered set T 5 containing 5 j there is however a subset that is a perfect analog of the Dedekind MacNeille completion 5 t E T l t infTUE for some E Q S 94 If we identify 5 with its isomorphic image 5 in 95 then 595 55 95 since every F E EKG is of the form F LUE mf9SUE 96 cf equalities 34 and 64 23 324 If t infTUE then E g LUE LTUE OS g LTUE t This shows that t E UTE If another element of 5 say t infTUE belongs to UTE then xj jy for any x E E and y E UE It follows that UE g UE and hence t infTE j infTE 15 cf 30 Thus t is the smallest element of UTE 5 UbaTE ie supbaT E exists and equals t sum E mug 97 Note that in View of 47 the infimum of UE in 5 exists and coincides with infTUE 1m TUE inlelE 98 In particular sum E 13911ng UE 99 We established the following fact Proposition 32 Any subset S of a partially oredered set T j is both supr and infrdense in 5 4 El 325 By the Universal Property of the Dedekind MacNeille completion cf The orem 31 the order embedding of S 5 into EXS Q then extends to an order embedding SE5 gt ffS 100 24 326 If T j is a complete lattice then embedding 100 is surjectioe since for every E Q 5 one has LUE inlelE ms cf Exercise 10 In particular 5 j is isomorphic to the Dedekind MacNeille com pletion This way we arrive at our final result Theorem 33 Any order embedding S j gt T 5 into a complete lattice induces an order embedding of the DedekindrMacNeille completion g5r Tr 5 101 which identi es 2 5 Q with 5 5 In particular 5 4 is itself a complete lattice El 25
Are you sure you want to buy this material for
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'