Class Note for MATH 300 at UMass(2)
Class Note for MATH 300 at UMass(2)
Popular in Course
Popular in Department
This 78 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 17 views.
Reviews for Class Note for MATH 300 at UMass(2)
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: 02/06/15
FUNDAMENTAL CONCEPTS OF MATHEMATICS SPRING 2006 William H Meeks February 14 2006 1 Introduction This preliminary version of a book is based on my notes from teaching Math 300 Fundamental Concepts of Mathematics77 at the University of Massachusetts at Amherst The Department of Mathematics views Math 300 as the course where its mathematics majors are introduced to doing proofs in a more rigorous way than in earlier mathematics classes The course which is typically considered to be at the second semester sophomore level is preparation for later more difficult and more theoretical classes in analysis and algebra My motivation in writing this book is to help my students accomplish the following goals during the course 1 Do real mathematics in order to learn how to do proofsl 2 Discover the power of de nitions and their importance in developing a mathematical theory 3 Learn to speak uently the language of mathematics in order to work with it and to under stand it better 4 Realize the importance of understanding both why a given theorem is true and how to write down its proof 5 See unifying principles and proof techniques used over and over again in different contexts 6 Be trained to be mathematicians and to think as mathematicians 7 Be acquainted with the values that a research mathematician has towards important ideas and results I have found that by covering four basic areas of modern mathematics I could accomplish the above goals in my teaching of Math 300 The rst area is related to set theory and basic logic with an emphasis on the notion of the size of a set This material is covered in Section 2 and includes truth tables equivalence relations mathematical induction basic mathematical notation and de nitions the properties of 11 and onto for functions and a variety of theorems on countable and uncountable sets The second area is covered in Section 3 and concerns the algebraic object called a group In this section we cover the standard results from group theory such as Lagrange7s Theorem and the First lsomorphism Theoreml In Section 4 we cover the theory of nite dimensional vector spaces over a eld and then we use this theory to prove that the set A of algebraic numbers is an algebraically closed sub eld of C having countable in nite dimension over Q Consequently we show that the real algebraic numbers AR A Q R forms a sub eld of R with countable dimension over The fourth area is covered in Section 5 and deals with metric spaces topological spaces topological notions such as connectedness and compactness and theorems that relate these concepts to continuous functions Included in this last material is a careful discussion of limits and a rigorous proof of the Fundamental Theorem of Calculusl The intent of this course is to transform a beginning mathematics major into a junior mathe maticiani As such I expect that the students learn and understand over ninety new concepts and de nitions I also expect them to be able to present complete proofs of most of the theorems given in these notes Copies of four typical midterms eight quizzes and a typical nal exam covering this material appear in Section 6 Since I rmly believe that the students in this class need training to develop into mathemati cians I break the class into smaller groups with 3 to 5 students for attending onehour weekly group meetings in my of cer In these small group meetings we practice proofs and go over in detail new or related concepts and theoremsi ln Fall semester 2004 these small group meetings were handled by undergraduate teaching assistants from my previous Math 300 classes A proposed schedule for material to be covered in the small group meetings is listed in Section 7 at the end of these notes I have found that when this course is presented in the manner just described and with this material then the students bene t greatly It has been my experience that this course not only changes how Math 300 students view mathematics but it also presents them with the essential proof techniques that they will need in their future upper division coursesi While I have taught all of the material presented in these notes at least once in my teaching of this course there does not seem to be enough time to cover every result presented here in a given semesteri In the Fall semester of 2004 I did manage to cover all the main theorems but I could only do this by giving the four long midterm exams outside of classroom hoursi Future teachers of this course who use these notes as a main text may want to consider skipping Section 4 on basic linear algebra or at least skip the portion of this section that begins with the de nition of a eld and in this second case include any linear algebra covered in the group theory exami See the course Web page for Math 300 course information and the location and times for section meetings homework quizzes and exams You can nd the Web page for Math 300 by going to www mathumass edu and clicking on the link under Spring 2006 course Web pages or by going directly to wwwmathumass edu bi11m300i 2 Set theory logic and the size of sets Recall the following notation concerning sets and functions De nition 21 Notation 1 If A is a set then x E A means that z is an element of A and z A means that z is not an element of Al to i The symbol 7 7 means both 77for each77 and for alllli 3 The symbol 3 means there exists h 4 The symbol gt means implieslli 5 The symbol ltgt means if and only ifwi 6 If A and B are sets then A C B means 7735 E A gt z 6 Bi77 7 If A and B are sets then A B if A and B have the elements Equivalently A B if A C B and B C A 8 The symbol 0 or circle is used for denoting the composition of two functions as follows lff A gt B and g B gt C are functions then a new function gof A gt C is de ned by the following rule V35 6 A g o When one speaks g o f77 one says 9 circle 1 7 or g composed with f77 or the composition ofg with f77 I prefer to say 9 circle f77 Example 22 Let R denote the set of real numbers Suppose that f R gt R and g R gt R are de ned by x2 and 935 2x1 Then 9 o f R gt R is de ned as g ofx 9352 2752 1 and fog R gt R is de ned as f 0935 f2xl 2x12 Below is a list of important sets which we will be discussing during the course De nition 23 l N l23 n the set of positive integers The set N is also called the set of natural numbers Z 0i1i2 in the set of integers Q reduced to lowest terms l mn E N the set of positive rational numbers F90 Q the set of all rational numbers reduced to lowest terms l m E Zn E N 5 R the set of all real numbers or points on the real number line 6 R4r the set of positive real numbers 7 AR nCllleClg l n E Z and clC 6 012 89 set of abstract decimal numbers in base 10 8 C the set of complex numbers a b71 l ab E R 9 Q is the set with no elements or the empty set We will say that two sets A and B have the same size if they can be put into a 11 correspon dence The idea of a 11 correspondence is intuitive and it is the way that a young child thinks about the number of elements in a set For example if the child has a set of 4 apples and a set of 4 oranges then by lining up the oranges next to a lineup of the apples he can see that these two sets have the same size On the other hand in the related situation where there are two sets one with 4 apples and another with 5 oranges the child can line up the 4 apples with 4 of the oranges and has one left over orange and so he understands that these two sets do not have the same size We now make precise the notion of two sets A and B having the same size We do this by de ning 11 correspondence which is an intuitive concept by the rigorous notion of a function f A A B which is 11 and onto De nition 24 A function f A gt B is 11 if for any 1352 6 A with 751 f 352 then f Equivalently f is 11 if whenever 752 then 751 352 De nition 25 A function f A gt B is onto if for each b E B 3a 6 A such that at b De nition 26 A function f A gt B is a 11 correspondence or a bijection between A and B if it is both 11 and onto In the case where such a function exists we write lAl lBl and we say that A and B have the same size The following two theorems play important unifying roles in this book Theorem 27 Iff A gt B andg B gt C are 1 functions thengof A gt C is a 1 function Proof Suppose f A gt B and g B gt C are 11 functions and we will prove that gof A gt C is a 11 function Let 1352 6 A with 751 f 352 Since f is 11 then f Since 9 B gt C is 11 then mail i 9W2 which implies that g o f iii i g 0 mm By de nition of 11 function g o f is a 11 function This completes the proof of the theorem At times in mathematics it is helpful in order to get a better understanding or to get a better feel for why a theorem is true to give a second proof of a theorem This theorem is a good instance of when having two different proofs is helpful and I leave it up to you to decide if you prefer the proof that we just gave or the following one We now give an alternative proof of Theorem 26 using the second equivalent de nition of 11 function Assume that f A gt B and g B gt C are 11 functions and x1 x2 6 A Suppose a 0 mail g 0 MM By de nition of 0 9mm 9W2 Since 9 is 11 m1 m2 Since f is 11 751 352 By de nition of 11 function g o f is a 11 function This completes our second proof of the theorem D Theorem 28 If f A gt B and g B gt C are onto functions then 9 o f A gt C is an onto function Proof Suppose f A gt B and g B gt C are onto functions Let c E C Since 9 is onto Sb 6 B such that 91 c Since f is onto 3a 6 A such that at 17 Therefore 9 o fa gfa 91 c By the de nition of onto function g o f is an onto function E The following result is a simple consequence or corollary of Theorems 26 and 27 and the de nition of 11 correspondence Corollary 29 Iff A gt B andg B gt C are 11 correspondences then 9 o f A gt C is a 11 correspondence De nition 210 Let R be a relation on a set S In other words for ab E 5 either aRb is true or aRb is false lf aRb is true then we say that a is R related to 17 Furthermore we have the following additional properties that R may satisfy for a b c E S l R is reflexive if a E S gt aRa 2 R is symmetric if aRb gt bRa 3 R is transitive if aRb and bRc gt aRc 4 R is called an equivalence relation on S if it is re exive symmetric and transitive Example 211 The relation lt77 or less than77 is a relation on N If abc E N then a lt b and b lt c gt a lt c and so lt is transitive Since 3 lt 4 and it is false that 4 lt 3 then lt is not symmetric Since it is false that 1 lt 1 then lt is not re exive In particular lt is not an equivalence relation on N Example 212 There are many familiar examples of equivalence relations For example let S be the set of students in our class Then the relation RBday that a student A is related to a student B if student A has the same birthday in the year as student B is an equivalence relation on S The relation RBdate that a student A is related to a student B if student A has the same birth date as student B gives rise to a possibly different equivalence relation on 5 Similarly the relations that a student A has the same rst name or the same last name or the same year of birth as a student B give rise to several possibly different equivalence relations on 5 Example 213 In plane geometry one studies two natural equivalence relations R0 RS on the set of triangles T in the Euclidean plane speci cally the relations of congruence and similarity For T1T2 E T we write TlRCTQ if T1 is congruent to T2 and TleTg if T1 is similar to T2 Theorems in plane geometry imply that the relations of congruence and similarity are both examples of equivalence relations on T The next theorem gives another familiar example of an equivalence relation related to the property of having the same size Theorem 214 Let S be a collection of sets and let R be the relation on S of two sets having the same size In other words for AB E S then ARB is true means A Then R is an equivalence relation on S In other words 1 VA 6 S lAl lAl 2 IfAB E S and A B then B A 3 Suppose A BC E S I A B and B C then A Proof Let A BC be sets in S The identity function iclA A gt A de ned by iclAx x is clearly 11 and onto and so A If A B then there exists a 11 correspondence f A gt B Then the inverse function f lz B gt A is a 11 correspondence and so B Finally suppose A B and B Then there exist 11 correspondences f A gt B and g B gt C By Corollary 28 g o f A gt C is a 11 correspondence and so A This completes the proof of the theorem D De nition 215 A set A is nite if A Q or it has the same size as 12 n for some n E N De nition 216 A set A is countable if it is a nite set or if A N it is uncountable if it is not countable Suppose A is a countable in nite set and f N gt A is a 11 correspondence Then A fl f2 Thus A is a countable in nite set just means that we can make A into an in nite list A a1a2a3an Lemma 217 N In particular Z is a countable set Proof We need to nd a 11 correspondence between the set N and the set Z Clearly the following vertical correspondence works 0 1 71 2 373 4 74 n in This ll correspondence makes Z into the in nite list 01 71 2 72 n in and so Z is a countable set D De nition 218 If A and B are sets then 1 A B x l x E A and z E B is called the intersection of A and B 2 AUBzleAorz B is calledthe unionofA and B 3 A 7 B z E A l z B is called the set cli erence of A and B or the complement of B in A De nition 219 If A Aaae is a collection of sets indexed by the set I then 1 HA ag Aa x l x 6 Ad for every Oz 6 I is called the intersection of A 2 UA UaE Aa 96 l 96 E Aa for some Oz 6 I is called the union of A Frequently the indexing set I for A is the set of natural numbers N In this case A AieN A1A2An and we also write UA U1Ai A1 UAg U UAn U and HA 1114 Al Ag An Example 220 Suppose A A1A3A5 where A1 abfA3 facle and A5 afn Then the indexing set is I 1 36 and we could write A Aiie Then A AA1 A3 A5 av 2396 UA UAA1UA3UA5 abdefn 23961 Proposition 221 If A and B are countable sets then A U B is a countable set Proof If A a1 an is a set with n elements and B 171 bm is a set with m elements then clearly A U B a1 an 171 bm is a set with a nite number of elements Suppose A a1an has n elements and B is an in nite countable set with the size of N Since B has the size of N we can express it as an in nite list B 51bgbn In this case A U B ah anl71l72l7n is an in nite list and so lA U B If both A and B have the same size as N then we can express A and B as in nite lists A a1a2 an and B 171192 bm Then A U B a1blag 172 on b makes A U B into an in nite list Since we have considered all of the essential possibilities for the sets A and B to be countable and have shown in each instance that A UB can be made into a list then AU B is countable This completes the proof of the proposition D If A B 3e Q then to be precise in the above proof one should remove repeated copies of elements in the list of A U B that arise from elements in A B However this minor problem does not affect the validity of the proof we just gave for the following reason If we have a list of the elements in a countable set C then one can always make a new listing by removing repeated elements For example C 1 21 4 2 5 1 2 4 5 De nition 222 If A and B are sets then their cross product is the set of all ordered pairs with rst coordinate in A and second coordinate in B In other words A X B ab l a E A and b E B If A1A2An is an ordered nite collection of sets then their cross product is 111Ai A1 gtlt A2 gtlt gtlt An the set of all ordered n tuples a1a2 an 1 ak E Ak for k E 12n Example 223 If A a b and B 123 then A X B al a2 a3 191 192 19 Theorem 224 The cross product of two countable sets is a countable set Proof First suppose that A and B are two countable in nite sets Their elements can be listed A a1 a2 an and B 171 172 b Consider an in nite twodimensional grid picture of A X B 04171771 azbn ambn 0427177171 5 17 172 607171 172 an 192 a1 bl a2bl 171 blanbl 1n the above picture the rst column in the grid is Cl a1bl a1bg a1 1771 and the n th column is CH ambl anbg anbn Starting at the lower left hand corner of the above grid count diagonally to make the following in nite listing of A X B AXB 0017 b1 6017172 6027 b1 0017173 6027172 a37bla 7 a1 1771 a2 57171 7 anvbl7 Note that the partial list a1bnagbn1anbl in the above list for A X B are the elements on the n th diagonal of the grid Since every diagonal of the grid picture appears on the list and the arbitrary element ahbj E A X B appears on the nth diagonal where n i j 7 1 then the above list for A X B is complete Therefore A X B is a countable set when A and B are in nite sets The proof of the case when A or B is not in nite is similar D Corollary 225 lQl Proof Recall that Q can be expressed as Q reduced to lowest terms l m E Z andn E N We may naturally identify Q with a subset of the countable set Z X N under the correspondence 2 gt gt m Since a subset of countable set is a countable set Q is a countable set Since Q is n in nite D We now give an important generalization of Proposition 220 which states that the union of two countable sets is a countable set We will use the next theorem later on in these notes in order to understand deeper questions in mathematics Theorem 226 The countable union of countable sets is a countable set Proof What this statement means is that the union of a nite number of countable sets is a countable set and if A A1 A2 Ak is a in nite countable collection of countable sets then UZ1 Ak is a countable set Suppose for the moment that A AkkeN where each of the sets Ak is an in nite countable set In this case we can make an in nite list for each Ak Ak ak1ak2 ak Then 00 U A U Ale 60117 60127 60217 60137 60227 60317 7 601717 a27 i717 7 60717127 an17 k1 Note that in the above listing the partial list a1 a2n1 an712 aml corresponds to the n th diagonal of a twodimensional grid picture of A where Ak is the hth column in the grid compare this with the proof of Theorem 223 As in the proof of Theorem 223 the general element am lies in the j 7 lth diagonal or in the partial listing a1 a2n1 an12 aml where n i j 7 1 Thus this sequential listing of elements of the union proves the theorem in the case where A AkkeN and each Ak is a countable in nite set A slight modi cation of this argument proves the theorem in the other cases D We now give an interesting application of Corollary 224 and Theorem 225 We will prove that the set of all complex roots or zeroes to polynomials of degree two with rational coef cients is a countable set A complex number r E C is said to be algebraic if it is a root of some nonzero polynomial with coef cients in ln homework problem 29 you will get a chance to generalize the next proposition you will prove that the set A of all complex algebraic numbers is a countable set Note that the real number 2 is algebraic since it is a root of the polynomial 2 7 2 and the complex number 2g is algebraic since it is a root to the polynomial 2 4 Proposition 227 Let a0 an big l a0a1a2 E Q a f 0 denote the set of polynomials of degree two with rational coe icients Then the set R of roots or zeroes in the complex numbers C a b7l l ab E R of the polynomials in is a countable set Proof By Corollary 224 Q is a countable set and so Q 7 0 is also a countable set Since the cross product of two countable sets is a countable set the set Q X Q is a countable set Again since the cross product of two countable sets is a countable set and Q X Q and Q 7 0 are countable sets then gtlt gtlt 7 is a countable set Consider the natural function f gtlt gtlt 7 7gt de ned by fa0a1a2 a0 an ang Clearly f is a 11 correspondence from the countable set gtlt gtlt 7 to the set Q22 and so is also a countable set Since is countable we can make it into an in nite list of polynomials Q2lxl p1x7p2x7pnx By the quadratic formula the set Rn of roots of the n th polynomial pn c bx as can be calculated to be b b2 7 4ac b 7 b2 7 4ac 2a 7 2a 7 and so Rn has one or two elements depending on whether or not b2 7 4ac 0 In any case Rn is a nite set and so it is also a countable set Since R U1 Rn R1 U UR U is the countable union of countable sets Theorem 225 implies R is a countable set This completes the proof of Proposition 226 D Rn We now brie y explain how to write an integer n E N in a base b 2 g b g 10 We write n in base b as dkdk71 do with div 6 01 2 b71 ifn has the value dkbkdk71bk 1d1b1dob0 For example the integer 22 in base 10 can be expressed as 22 2 32 13130 18 3 1 and so in base 3 we write the number n 22 base 10 as n 211 base 3 Similarly we can express any real number r in any base b 2 g b g 10 If r nd1d2 base 10 for n E Z then we express r as the base b number elk d1d0d1d2 if the in nite series elk bC d1 b1 do b0 cl1b 1 CLQ b 2 converges to r and where di 6 012b 71 For example the base 10 number 55 can be expressed as 112 in base 4 Similarly we can convert any real number expressed in a base b 2 g b g 10 to a decimal number in base 10 For example the base 6 number 213 is the number 2 6 160 3 6 1 133 135 in base 10 Note that for a base b gt 10 one needs to add more basic digits to 01 2 9 in order to express numbers in NorR Theorem 228 The set of abstract decimal numbers AR also using any other base has the same size as the set of points on the real number line R Proof We shall prove the theorem in the case of base 10 Note that two abstract decimal numbers nd1d2 and me1e2 represent the same real number or point on the real number line if the distance between the points on the real number line is zero For example the distance between the in nite repeating decimal numbers 1999 and 2000 is zero and so these two abstract decimal numbers represent the same real number In fact a simple argument shows that the only way that a nonzero real number nd1d2 has more than one representation as an abstract decimal number is that for some positive integer k and for all i 2 h then di 0 or for i 2 h then div 9 Thus if r is a real number of nonunique decimal representation then r must have a decimal representation which ends in all zeroes But if r nd1d2 ends in all zeroes then it is clearly representable as a rational number i where h E Zm E N and m is a power of 10 For example 24300 In particular since the set of rational numbers is a countable set then the set X of the real numbers of nonunique decimal representation is a countable set Let Y R 7 X be the set of real numbers with unique decimal expansions De ne AR X be the subset of AR representing numbers in X and similarly de ne ARY Since AR X is the union of two countable in nite sets namely the decimals ending in all 07s except for the number 0 0007 which has a unique decimal representation or in all 97s7 ARX is a countable in nite set Since ARX and X are both countable in nite sets7 they have the same size Let fX AOR X gt X be a 11 correspondence and let fy ARY gt Y be the obvious ll correspondence Then7 the function f AUR gt R de ned to be fX on AOR X and fy on ARY is a 11 correspondence7 which proves the theorem D We now develop the notion of a set A having smaller size than another set B To do this7 we rst need to de ne what it means for the set A to have size less than or equal to the size of B lntuitively7 A should have size less than or equal to the size of B if A has the same size as a subset of B For example7 if A abc and B 1 2 34 then A has the same size as the subset C 123 ofB in other words there is a 11 correspondence f A gt C C B By considering f to be a function from A to B7 we see that f A gt B is a 11 function This discussion motivates the next de nition De nition 229 Given two sets A and B we write lAl lBl if there exists a 11 function f A gt B We write lAl lt lBl if lAl lBl and lAl lf lAl lBl then we say that 77the size of A is less than or equal to the size of B If lAl lt B we say that 77the size of A is less than the size of B77 De nition 230 The power set of a set A7 denoted by PA is the set of all subsets of A Example 231 l2 Q l2l2 Over a hundred years ago Cantor de ned the notion of the size of sets7 in terms of the existence of 11 correspondences7 and introduced the de nitions of countable and uncountable sets He also proved the following interesting results 1 The set Q is countable 2 The set R is uncountable 3 73N 4 For any set A7 then lAl lt We now prove this last result Theorem 232 Cantor s Theorem For any set A lAl lt In particular there are in nite sets of arbitrarily large size Proof Let f A gt PA be the function fa a Clearly7 f is 11 and so7 lAl lf lAl lPAl then there exists a function F A gt PA which is onto in fact7 11 and onto We will prove that such an onto function F cannot exist7 which will prove Cantorls Theorem Suppose to the contrary7 there exists a function F A gt PA which is onto De ne the special subset AF z E A l z E PA Since we are assuming F is onto there exists a y E A such that Fy AF We now ask the question ls y 6 AF If y E AF7 then by de nition of AF y Fy but Fy AF7 and so7 y AF7 which is a contradiction So we conclude that y AF Since y AF7 then by the de nition of AF y E Fy AF7 which is a contradiction Since y 6 AF or y AF7 we obtain the desired contradiction This means that the onto function F does not exist7 and so7 lAl 3e Since lAl lPAl and lAl 3e lPAl then lAl lt D 10 De nition 233 Given two sets A and B let FAB be the set of all functions f A gt B from A to B Theorem 234 Given a set A then WAN FA7071 Proaf We need to nd a function H PA gt FA0 1 which is 11 and onto For B E BA de ne the function HB A gt 01 by 0 if z B 1 ifz E B Clearly different subsets determine different functions and so H is 11 Let f A gt 01 6 FA0 De ne the subset Bf f 11z E A 1 Then HBf f and so H is onto Since H is 11 and onto the theorem is proved D Theorem 235 PN has the same size as the set 5 Of all in nite sequences 0f 0 s and 1 s Proaf Let A C N 12n be a subset Let SA be the sequence of zeros and ones we obtain by replacing every element of A in this list of N by a 1 and every element of N 7 A by a zero and then remove the set brackets and commas For example if A 256 then SA 010011000 the rst digit of SA is 0 since 1 A the second digit of SA is 1 since 2 E A the third digit of SA is 0 since 4 A and so on Clearly the function 5 PN gt S is 11 and onto by using an argument similar to that used in the proof of the previous theorem By de nition of size PN and 5 have the same size which proves the theorem D Corollary 236 73N Proaf The set S of in nite sequences of 07s and 17s after placing a decimal point at the beginning of the sequence can be identi ed with the abstract base 2 numbers in the interval 0 1 Theorem 227 then implies that S 0 Since the removal of a point from an in nite set does not change its size S 01 By homework problem 13 01 By Theorem 234 PN Since PN S 01 and 01 R then the transitive property of size implies PN D Corollary 237 R is an uncountable set Proaf By Cantorls Theorem PN is an uncountable set By Corollary 235 we conclude that R is also an uncountable set D We now give a more direct proof that R is an uncountable set You will need to know this proof for your exams Theorem 238 R is an uncountable set 11 Proof Suppose to the contrary that R is a countable set Then the open unit interval I 01 in R of numbers between 0 and 1 is a countable set Since I is countable then we can make I into an in nite list I r1r2 rn Making this listing r1r2 rm of elements in I into a vertical listing we obtain n d11d12d1n r2 d21d22d2n rndn1dn2dnn with digits elm E 0 1 9 Now de ne the decimal number r cllcl2 cln where cln 5 if an lt 5 and cln 4 if an 2 5 Note that the real number r has a unique expression as an abstract decimal number since none of its digits are 0 or 9 Note r f 0 and r f l and so r E I 01 Since r E I then r m for some k E N But the kth digit of m is clkJC and the kth digit of r is clk clkJC and so r f m for any k E N This contradiction proves the theorem D De nition 239 Let p and g be logical statements which are either true or false Then 1 7p is true 4 p is false qu is true ltgtpor q is true p A q is true 4 p and q are true HgtCA3IO p gt q is false 4 p is true and q is false 5 p lt gt q is true 4 p and q are both true or both false In this case we say that p and q are logically equivalent 6 The contrapositive of the implication p gt q is the implication iq gt 7p It is logically equivalent to p gt q see homework problem 19 7 p is a tautology if it is logically true truth table is all true 8 p is a contradiction if it is logically false truth table is all false The statement p gt q above is called an implication with premise p and conclusion q The premise p in an implication p gt q is also called the hypothesis Two examples of tautologies are 19 V 7p or p gt 19 V q An example of a contradiction is p A 7p 12 Many theorems in mathematics take the form of an implication If p is true then q is true77 For example If A gt B and g B gt C is 11 functions then gofz A gt C is a 11 functionli77 Even many de nitions in mathematics give a de ning property in terms of an implicationi For example a function f A gt B is 11 if 961 i 962 gt f961 f752l Using the fact that the contrapositive of an implication is logically equivalent to it we obtain the alternative second de nition A function f A gt B is 11 if Wm 10062 i 961 262 By statement 4 in De nition 215 an implication p gt q is true whenever its premise p is false In particular the implication 124 gt56 is a true statement since the hypothesis 1 2 4 of the implication is false Many students nd this type of logical argument counterintuitive and difficult to accept until they realize that this is just a consequence of the mathematical de nition or the truth table for p gt g which we give belowi q jHHe q jl mz a Truth tables for logical statements give a tabular method for calculating the truth values of the statement for different assignments of truth or false for the logical variables Below are the truth tables for the logical statements p gt 7p and p gt q gt p More truth tables appear in the homework exercisesi p q peg 99qu p 7p paip T T T T T F F T F F T F T F T T F F F T F The next theorem can be proven by writing down the truth tables for p A q A r and for p A g V p A r and then checking that they are the same Theorem 240 p A g V r lt gt p A g V p A Theorems in logic such as Theorem 239 can be useful at times for proving that two differently described sets are really the same De nition 241 Let A and B be sets Then 13 l ACBmeansthatxEAgtxEBifACBthenwesayAisasubsetofB 2 A B means that A C B and B C A or equivalently that A and B have the same elements We now apply the previous theorem to prove one of the distributive rules for unions and intersections of sets given in the next theorem Theorem 242 Distributive Rules Let A BC be sets Then A BUC A BUA C AUB C AUB AUC Proof We will prove the rst equation Actually we will show that A B U C C A B U A 70 and will leave the proof that A B U A C C A BUC as homework problem 23 By de nition of equality of two sets the two containment equations then prove that A BUC A BUA C Let x E A B U C By de nition of intersection x E A and x E B U C and so by de nition of union we obtain the statement as E A and x E B or x E C By the previous theorem letting p x E A q x E B and r x E C we obtain the logically equivalent statement as E A and x E B or x E A and x E C By de nition of intersection x E A B or x E A C By de nition of union x E A B U A C By de nition of containment C we have shown A B CCA BUA C D De nition 243 If A C X then the complement of A in X is AC x E X l 75 A X 7 A Theorem 244 DeMorgan s Laws Let A and B be subsets of X Let AC and BC denote their complements in X Then AUBC ACnBC and A BV ACUBC Proof We will prove the rst equation A U BC AC B It holds since as E A U BC 4 75 AUBltgtx A and ltgtx AC and xEBCltgtxEAC BC D The following axiom for the natural numbers N clearly holds but cannot be proved hence the word axiom or principle WellOrdering Principle Given any nonempty subset A C N then A contains a least element ie there exists an element x E A such that for all y E A then x g y We now use this axiom for N to prove the principle of mathematical induction Theorem 245 Principle of Mathematical Induction Suppose S 51 SQ Sn is a collection of logical statements indexed by the natural numbers N If 51 is true and Sn gt Sn1 for every n E N then all of the statements in S are true 14 Proof Arguing by contradiction assume that the principle of mathematical induction fails Then there exists a collection 5 51 SQ Sn of logical statements for which 51 is true Sn gt Sn1 for all n E N but some statement Sm is false Let F E N l Si is false Since m E F F Q By the wellordering principle F has a smallest element k E F Since 51 is true k f 1 and so k 71 E N 7 F which means Sk1 is true Since Sk1 gt 51C with true premise Sk71 then the conclusion 51C must be true but it is not since k E F This contradiction proves the principle of mathematical induction holds D Some interesting summation formulas in number theory can be proved by applying the principle of mathematical induction Below is one such formula See homework problem 25 for four more examples Theorem 246 For every integer n E N Proof We will prove the theorem by applying the principle of induction We will consider the formulas Sn 221k l n E N to be an in nite sequence of logical statements indexed by the natural numbers 1 51 is true since 21 k 1 2 Assume Sn holds and we will prove Sn1 holds this will prove that Sn gt S7114 So x it E N and assume Sn is true nn1 n 12nZk 2 k1 Adding n 1 to each side of the above formula we obtain the following related formula n1 12nn1ZkM k1 2 n1 Simplifying the right hand side of this equation we obtain n1 2k nn1n1 nn1 2n1 nn12n1 n1n2 k1 2 2 2 2 2 Thus k W which means that Sn1 holds Since 51 is true and Sn gt Sn1 for all n E N then the formula 221 k holds for all n E N by the principle of mathematical induction D De nition 247 A collection A of nonempty subsets of a set A is called a partition of A if it satis es the following two statements 15 1 The union UA Al 2 The subsets in A are pairwise disjoint in the sense that any two different subsets in A are disjoint Equivalently if BC E A and B C 3e Q then B Ci Example 248 Let E 2n n E Z be the set of even integers and let 0 2nl n E Z be the set of odd integers Then A EO is a partition of Z Another familiar partition of Z is into the subset of negative integers the subset of positive integers and the subset containing 0 Example 249 In the proof of Theorem 22 we de ned the subset AUR X C AUR Whose elements represent real numbers Which have two representatives in AOR and the subset AOR Y C AOR Whose elements represent real numbers With unique representatives in AUR Since AUR X AOR Y A AR XARY is a partition of AOR Theorem 250 If A is a set with n elements then 73Al 2 Proof We Will prove this theorem by induction on the size of A First note that if A 0 then the theorem is true since the power set of the empty set has one element and l 20 Assume that the theorem holds for any set A With A nl Let B be a set With B 51 bnbn1l Let A blbn B 7 17144 Then PA is a subset PB With 2 elements by our inductive hypothesis Note that PB PA U PAC Where PAC is the complement of PA in PBl There is a natural function F PA gt PAC de ned by FW W U 19144 Which is clearly 11 and onto Hence lPAl lPACll Since PAPAC is a partition of PB then lPBl lPAl lPACl 2 2 2714A Which proves the theorem by induction D Note that Theorem 249 is also an immediate corollary of Theorem 23 and Theorem 2 50 belowl Recall that FA B A gt Bl Theorem 251 HA and B are nite nonempty sets then FABl B lAl Proof Suppose A a1 a2 an and B 171 172 hm Note that in this situation for each ak E A there are m possible choices of values for a given function f E FA B We Will prove the theorem by induction on n Which is the size of Al If n 1 then clearly FAB m mlAll Now assume that Whenever C is a set With size n and B is a nite set then FC B B 0 Blnl Let A a1 an an1 and let C a1 a2 an Then by our inductive hypothesis FCBl B lcll Note that every function f E FCB gives rise for each hl g h g m to the function fk A gt B Where fkltCLgt fa if a E C and fkan1 bkl Also note that every 9 E FAB With gan1 bk is of the formg fk Where f gla1an here ghabm n is the restriction of g to the subset a1 on C A This means that FABl mlFCBl Hence by elementary arithmetic MAB mFCB mwBHC mwai mm mi BHA Which proves the theorem by the principle of mathematical inductions D De nition 252 If R is an equivalence relation on a set S and a E S then the equivalence class of a Written as a consists of all elements in S Which are R related to oil In other words a z E S aRz Let SR a l a E 5 denote the set of equivalence classes in Si 16 Example 253 Consider the following relation R on Z Two integers in Z are R equivalent if their difference is an even integer or equivalently an for nm E Z if 3k 6 Z such that n 7 m 2k It is easy to see that the equivalence class of an odd integer is the set 0 of odd integers and that the equivalence class of an even integer is the set E of even integers Thus the set of equivalence classes SR 0E is a partition of Z This partitioning property of the equivalence relation R on Z demonstrates a special case of the next theorem Theorem 254 Fundamental Theorem of Equivalence Relations Suppose R is an equiv alence relation on a set S Then the set of equivalence classes SR is a partition of 5 Proof First note that for any a E S aRa by the re exive property of R Therefore for every a E S a E a and so 5 C USR Since SR consists of subsets of S then USR C 5 Since 5 C USR and USR C S then S USR Next we must check that two different equivalence classes are disjoint this is the pairwise disjoint property that a partition of 5 must satisfy Equivalently we must verify that if two equivalence classes in SR intersect then they are equal Suppose that a b 6 SR and a QM 0 Our goal is to prove a b which means that we must prove a C b and b C a We rst show a C Let y E a which means aRy holds and we will prove that y E Since a 1 3e Q there exists an x E a 9 which means that x E a and x E Thus aRx and bRx hold and by the symmetry property of R we obtain xRa as well Thus bRx and xRa hold and by transitivity bRa holds Since bRa and aRy hold transitivity shows bRy holds which implies y E This proves a C Arguing similarly we obtain 17 C a and so a Thus SR is a partition of S D Homework Problems 1 Let f 12 gt a 170 be de ned by a and 0 Let g a 170 gt 35 be de ned by 9a 3 91 3 90 5 a Which of the functions in fgg o are 11 functions Explain why b Which of the functions in fgg o are onto functions Explain why 2 SupposeA A1A2A5whereA1 7123A2 234 andA5 123 n nEN a What is RA A1 A2 A5 b What is UA A1 U A2 U A5 3 ls an equivalence relation on R Which properties of an equivalence relation are satis ed 4 ls an equivalence relation on R Which properties of an equivalence relation are satis ed 5 Suppose A 12 B abc and C 34 What is the set A X B What is the set AgtltAgtltC7WhatisthesetAgtlt AXC 6 Express the base 10 number 15 E N as a base 3 number 17 10 11 12 13 14 15 16 17 18 19 20 21 22 Express the base 2 number 1101 as a base 10 number List all the elements in the power set P1 23 Note that a function f R gt R is 11 when its graph G 75 E R2 l x E R satis es the following horizontal line test Every horizontal line in R2 intersects C in at most one point Also note that f R gt R is onto if it satis es Every horizontal line in R2 intersects C in at least one point Write down functions f R gt R satisfying each of the following conditions a f is 11 but not onto b f is onto but not 11 c f is both 11 and onto d f is neither 11 nor onto a Is the function f R gt R de ned by z sinz a 11 function b Is onto Explain your answers Prove that the set of irrational numbers I in R is an uncountable set Hint First note that R Q U I and then apply the statements of Proposition 220 and Theorem 237 Write down a linear function f 01 gt 25 of the form ax b which is a 11 correspondence Prove that the open interval 01 t E R l 0 lt t lt 1 has the same size as R Prove this fact by drawing the graph of a function f 0 1 gt R which is 11 and onto Hint Consider a graph that has the appearance of the graph of tanz Suppose f A gt B and g B gt C Prove that ifgof A gt C is onto then 9 B gt C is onto Suppose f A gt B and g B gt C Prove that ifg of A gt C is 11 then f is 11 Hint Prove the contrapositive of this implication or give a proof by contradiction Suppose A BC are sets Prove that if lAl lBl and lBl lCl then lAl Suppose F 123 gt P123 is de ned by F1 1 F2 13 F3 Q What is the set AF z 6 123 1 z Fz Write down the truth table for p gt q gt p Prove that p gt q and its contrapositive iq gt 7p are logically equivalent by showing that they have the same truth tables Write down the truth table for 19 V q gt p A q Prove the statement p gt 19 V q is a tautology Use De nition 240 to prove that for two sets A B if A U B A B then A B Hint First show that if z E A then x E B under the assumption A U B A B 18 23 24 25 26 27 28 29 Prove that A B U A C C Am B UC Prove that A BC AC U B Hint Try to mimic the proof of the rst equation in Theorem 213 Prove the following summation formulas by using the principle of mathematical induction 1 2 1 a 221 k2 b 2212k 1 n2 0 220 2k 2 1 d 221 Let A 1 234 5 Then A 123 45 is a partition of A Give three different examples A1 A2 A3 of partitions of A that are different from A and where A1 contains the subset 12 3 as one of its elements but no subset in A2 or in A3 has three elements Use Proposition 220 and the principle of mathematical induction to prove that for n 2 1 if A1 AnAn1 is a nite collection of countable sets then A UZT Ai is a countable set You can use the obvious fact that A A1 U A2 U U An U A7144 Here is a suggestion for showing this result For a nite collection A1 An A7144 of countable sets consider Sn to be the statement n1 U Ai is a countable set i1 For n l 51 is true by Proposition 220 Assume Sn is true and then prove Sn1 is true using the fact that Uzal An Ugll Ai U An1 and applying Proposition 220 Then conclude the problem by applying the principle of mathematical induction Suppose C A1 An is an arbitrary nite collection of sets a For n gt 2 show that lAl gtlt A2 gtlt gtlt An gtlt An1l lA1 gtlt A2 gtlt gtlt An gtlt An1l by constructing an obvious 11 correspondence f A1 gtlt gtlt An gtlt An1 gt A1 gtlt A2 gtlt gtlt An gtlt An1 You don7t need to prove that the function f is 11 and onto you just need to de ne it b Use the principle of mathematical induction to prove that the nite cross product of countable sets is a countable set In other words if A1 An are n countable sets then A1 gtlt A2 gtlt gtlt An is a countable set Hint Let Sn be the statement that A1 gtlt A2 gtlt An is countable when C A1An consists of n countable sets Start the induction proof with n 2 countable sets and then apply Theorem 22 to conclude that the rst statement 52 is true Next apply part a of this problem to show that Sn gt 57144 for n 2 2 For eachn E N let the set a0a1x anx l ak E Q and an for n gt 0 be the set of rational coef cient polynomials of degree 71 Let QOM Q be the set of constant polynomials 19 3 30 31 32 a Prove that is a countable set Hint Thinking in terms of the coefficients a0a1 an ofa polynomial a0a1x anx E for n gt 0 prove that has the same size as the cross product HZ1Q gtlt Q7 0 where HZ1Q Q X gtlt Q is the cross product of Q with itself n times and then apply part b of the previous homework problem Note that we did this directly for n 2 in the proof of Proposi tion 226 Prove that the set of all rational coefficient polynomials is a countable set Hint Prove that is a countable union of countable sets and apply Theorem 225 b c A complex number a E C is called an algebraic number if it is a root or zero ofa nonzero polynomial 1935 6 Prove that the set A of algebraic numbers is a countable set Hint By part b we can make an infinite list p1xp2x pk x Use the fundamental theorem of algebra which implies that each polynomial in has at most n complex roots to prove that A is a countable union of countable sets and so is itself a countable set Also see the proof of Proposition 226 for this argument d A real number r E R is called transcendental if it is not algebraic For example it can be shown that the numbers 7r and e are transcendental Prove that the set T of transcendental real numbers is uncountable Hint Apply part c and then apply an argument similar to the one used in the proof of homework problem 11 Prove that xi is an algebraic number but not a rational number Hint To prove xi is not rational assume to the contrary that xi g is reduced to lowest terms Square each side of the equation and simplify by multiplying each side by n2 and then show 2 divides both m and n to obtain a contradiction to the assumption that 7 is reduced to lowest terms You can use the fact that if a prime divides the product of two integers then it divides one of the integers Let R3 be the following relation on Z Given m n E Z then ngn if there exists a k E Z such that n 7 m 3k a Prove R3 is an equivalence relation on Z b Describe the equivalence class 2 as a subset of Z Is 4 E 2 Let S a b a b c 5 3 4 6 7 Let R be the equivalence relation on S of two sets having the same size Write down the set of equivalence classes SR for this equivalence relation R on S Hint SR has 3 elements Elementary group theory A binary operation 96 on a set A assigns to each ordered pair of elements a b E A X A another element in A usually denoted by CHI Familiar binary operations are addition and multiplication on the set of integers Z Note that on Z induces a binary operation on the set of even integers E 2k l k E Z since for 2k12k2 E E then 2 21 2k1 kg 6 E However is not a binary operation on the set of odd integers O 2k 1 l k E Z since 1 3 4 which is not an odd integer 20 De nition 31 A graup G 96 is a set C together with a binary operation satisfying 13 anelementeEG such that VgEG eggeg 2 V9 6 G there exists an element g E G such that g 96 y 9 e 3 The operation 96 is associative Va 170 6 G a 96 b 95 c a 96 b 96 c When the group operation 96 of a group G is wellunderstood then we usually use multiplicative notation rather than emphasize the operation In other words instead of writing a b we write ab In the de nition of a group C any element a such as e which satis es V9 6 G a 96 g g 95 a g is called an identity element for C By the next proposition G has a unique identity element and so from now on we will call e in the de nition of a group the identity element of G The element g such that g g e given in the de nition of a group G is called an inverse of g and it is also unique by the next proposition we will denote this element by 9 1 and call it the inverse of 9 When the group operation on G is denoted by the symbol 77 then the unique inverse of 9 will be denoted by g77 rather than 9 1 and in this case we will use 0 to denote the identity element of G instead of e Proposition 32 If G is a graup then the fallowing statements hold 1 Far axy E G ax ay gt x y and 75a ya gt x cancelation laws G has a unique identity element uniqueness of identity Every element ofG has a unique inverse element uniqueness of inverse Vab E G ab 1 b la l Va 170 6 G abcfl c lb la l F0rxy Gxyeltgtyx 1 R9t Far a E G a 1 1 a Proaf We rst prove the left cancelation law Suppose ax ay Multiply each side of this equation on left by the inverse 6 whose existence is given in statement 2 of the de nition of group to obtain ax May and so 6075 Han gt ex ey gt x y This proves the left cancelation law holds The proof of the right cancelation law is similar Suppose el and eg are identity elements in G Since e1 is an identity element then 6162 e2 Since e2 is an identity element then 6162 e1 These two equations imply e1 eg and so G has a unique identity element which is the element e given in the de nition of a group If 9192 6 G are inverse elements ofg then 919 e and 929 e Thus glg 929 and so by the right cancelation law 91 92 which proves the uniqueness of the inverse of g In order to prove statement 4 rst multiply ab and b la l to get abb 1a 1 abb 1a 1 aecf1 acf1 e A similar calculation shows bilail ab e and so by de nition of inverse abrl bilafl which proves statement 4 holds 21 A slight modi cation of the proof of statement 4 proves statement 5 Clearly if y x l then my e On the other hand if my e we can multiply each side of this equation on the left by 75 1 to obtain x 1xy x le x l So 75 1 x 1xy x lxy ey y which proves statement 6 holds Let a E G and let CF1 6 G be its inverse By de nition of inverse aa 1 a la e This equation also means a a 1 1 This completes the proof of the proposition D Example 33 1 One familiar example of a group is the set of integers Z Here e 0 and the inverse of n E Z is 7n 2 R Q and R 7 0 are also wellknown examples of groups with e 0 in the rst example and e 1 in the other two multiplicative groups 3 Another familiar group is M2 R of 2 X 2 real matrices under the operation of addition a b e f 7 a e b f c d T g h 7 c g d h 0 0 The zero matr1x 0 lt0 0 plays the role of the 1dent1ty element 4 The general linear group of real 2 X 2 invertible matrices denoted by GL2 R is a group under multiplication of matrices See Section 4 for how to multiply matrices 5 Any subspace of the vector space R is a group under addition of vectors More generally every vector space V over a eld F is a group under by the axioms for a vector space See Section 4 for the de nition of vector space over a eld if you have not yet studied linear algebra In all of the above examples of groups except GL2 R the group operation is commutative De nition 34 A group G 96 is an abelian or a commutative group if Va 17 E G a 96 b b 96 a De nition 35 Given n E N and m E N U 0 01 2 then m mod is the remainder of dividing m by n For example 10 mod 6 4 and 14 mod 3 2 The proof of the following proposition is straightforward and will be left to the reader Proposition 36 Let Zn 012n 7 l and de ne for ah 6 Zn the binary operation a b a 19 mod Note that the operation of on the right hand side of the equation is addition of the integers ab if a b lt n and equals a b 7 n if a b 2 n Then 1 Zn is an abelian group under 2 e 0 3 The inverse ofO is 0 and the inverse ofa 6 Zn 7 0 is n 7 a 22 The nite abelian group Zn 012 n 7 1 is the important building block example for all nite abelian groups By taking cross products of such groups we see by homework problem 15 that we can make new abelian groups For example Z2 gtlt Z2 0 0 1 0 01 11 is a new abelian group under with four elements where we add ordered pairs by adding their coordinates For example 101 1 1101 2 0 01 6 Z2 gtlt Z2 note that 00 is the identity element in Z2 gtlt Z2 Sometimes we consider Zn to correspond to the set of hours on a clock with n hour positions with the operation of clock arithmetic Our familiar case of this would be Z12 012 11 where we consider 12 olclock to correspond to 0 olclock We then consider 2 3 to be the hour 5 or 8 6 14 mod 12 2 mod 12 to be the hour 2 Here we consider all the possible hour times as elements in Z but we identify any hour time h E Z with h mod 6 Z12 on the clock Note that if h E Z is negative then h mod corresponds to n 7 mod in Zn De nition 37 If g E G and n E N then we let g denote the product of g with itself n times under our multiplicative convention for a group For example g3 ggg The order of an element g E G denoted by 0g is the smallest positive integer n E N such that g e if there is no such positive integer n then we say that g has in nite order Example 38 The element 2 E Z5 has order 3 since the group operation in Z5 is and 222 0 but 2 2 4 f 0 The element 2 E Z has in nite order since no nite sum 2 2 is ever equal to 0 It is easy to check that every element in Z2 gtlt Z2 7 00 has order 2 for instance 10 10 20 00 and so 10 has order 2 The element 71 E R 7 0 has order 2 in the multiplicative group R 7 0 since 712 1 which is the identity element of the group The next proposition follows directly from the de nition of a group Proposition 39 A subset H of a group G is itself a group under the binary operation in G if and only if the following three statements hold 1 e E H where e is the identity element in G 2 Vh E H h 1 E H where h 1 is the inverse ofh in the group G 3 Vab H abEH Proposition 33 motivates our next de nition De nition 310 A subset H C G is called a subgroup if the following three statements hold 1 e E H where e is the identity element of G existence of identity 2 Vh E H then h 1 E H where h 1 is the inverse of h in G existence of inverse 3 Va b E H then ab 6 H closure Example 311 We now show that the set of even integers E 2n 1 n E Z is a subgroup of Z Recall that e 0 and the additive inverse of h E Z is 7h Since 0 2 0 E E E contains the identity element of Z If 2n 6 E then 72n 27n E E and so the the additive inverse of each element of E lies in E Finally if 2m 2n 6 E then 2m 2n 2m n E E which proves that E is closed under the operation By de nition of subgroup we see that E is a subgroup of Z 23 Theorem 312 If H1H2 are two subgroups Of a graup G then H1 H2 is a subgraup OfG Proaf 1 Since H1 and H2 are subgroups e 6 H1 and e 6 H2 By de nition of intersection e E Hl Hg 2 If a 6 H1 H2 then a 6 H1 and a 6 H2 by de nition of intersection Since H1 and H2 are subgroups a 1 6 H1 and a 1 6 H2 By de nition of intersection a 1 6 H1 H2 3 If ab 6 H1 H2 then ab 6 H1 and ab 6 H2 Since H1 and H2 are subgroups ab 6 H1 and ab 6 H2 Hence ab 6 H1 H2 by de nition of intersection By de nition of subgroup H1 H2 is a subgroup D The proof of the next theorem is a warmup exercise for homework problem 5 Where you Will be asked to prove that the intersection of an arbitrary collection of subgroups of a given group is again a subgroup of the group Theorem 313 The intersectian 0f three subgraups Of a graup is again a subgraup 0f the graup Proaf Suppose A H1H2H3 Hii6123 is a collection of three subgroups of a group G We now check that A H1 H2 H3 is a subgroup of G 1 Since e 6 Hi for each i E I then e 6 HA by de nition of intersection 2 Let a 6 DA By de nition of intersection a 6 Hi for each i E I Since Hi is a subgroup a 1 6 Hi for each i E I By de nition of intersection ail 6 HA 3 Let a b 6 HA By de nition of intersection ab 6 Hi for eachi E I Since Hi is a subgroup ab 6 Hi for each i E I By de nition of intersection ab 6 HA By de nition of subgroup HA is a subgroup D De nition 314 If G is a group then the center of G is CG a E G l V35 6 G ax 75a Example 315 Recall that GL2R is the group of real 2 X 2 invertible matrices With binary operation being the multiplication of matrices and With identity element It is not dif cult to prove that the center of GL2R consists of the matrices lta 2 Where a E R 7 0 Theorem 316 RC is a graup then the center CG is a subgroup Proaf 1 Since ex ace for V35 6 G then e E CG 2 Suppose a E CG Then ax 75a for all x E G Multiply this equation on left and right by ail to obtain ailaxail ailxaail Which implies ailaxa 1 ailxaa 1 Which implies eaca 1 a lxe Which implies xa l a lx V35 6 G Hence a 1 E CG 24 3 Finally suppose ab E CG and let x E G Then using the associative law abx abx axb axb mab dab and so ab 6 CG By de nition of subgroup CG is a subgroup of G D Theorem 317 Suppose H is a subgroup of the group G and a E G De ne CLHCL 1 aha l l h E Then CLHCF1 2s a subgroup ofG Proof 1 Since H is a subgroup e 6 Hi Note that aea 1 aa l e and so e E aHa li 2 Let b E aHa li Then b aha l for some h 6 Hi Since H is a subgroup h 1 E H and so ah la l E aHa li Since a 1 1 a statement 5 of Proposition 32 implies b 1 aha U l a 1 1h 1a 1 ah la l and so b 1 E aHa li 3 We now check the closure propertyi Suppose ahla l ahga l E aHa l where h1 h2 E H By the closure property in H hlhg E H Now multiply ahla l ahga l ah1a 1ah2a 1 ahlehga l ah1h2a 1 E aHa l By de nition of subgroup aHa l is a subgroup of G1 D De nition 318 A function f G1 gt G2 between groups G1 and G2 is called a group homomor phism if Va b E G then ab More speci cally if 96 is the operation on G1 and o is the operation on G2 then f is a homomorphism if fa b at 0 Example 3 19 1 Consider R to be a group under and R4r to be a group under multiplication Then e R gt RJr is a group homomorphism since e1y ezeyi 2 Similarly the inverse function to e the natural log function lnx R1r gt R is a group homomorphism since lnxy lnx lnyi 3 Recall that GL2R is the group of real 2 X 2 invertible matrices The determinant function det GL2 R gt R70 is a group homomorphism since detAB detAdet Here we consider R 7 0 to be a group under multiplication See homework problem 7 in Section 4 for the definition of det and the proof of the homomorphism property 4 Let G be the group of infinitely differentiable functions on the unit interval 01 under the operation of addition of functions Then the derivative function is a group homomorphism D G gt G since gx gx Also the integral function I G gt R de ned by fol is a group homomorphism since the integral of a sum of functions is the sum of their integrals 5 If V and W are vector spaces over a eld F and L V gt W is a linear transformation then L is a group homomorphism since Lv1 172 Lv1 Lv2i See Section 4 for the de nition of linear transformation if you have not yet studied linear algebra 25 De nition 320 Let f A gt B be a function Then lmf b E B l 3a 6 A such that b fa is the set of values of the function The set lmf or is called the image of the function Note that f A gt B is onto if and only if B Example 321 Let A 733 45 and B R Let x2 and consider f to be a function from A to B Then lmf 91625 Theorem 322 Suppose that f G1 gt G2 is a gmup hamomorphism and that e1 6 G1e2 6 G2 are the respective identity elements Then 1 fe1 e2 2 Va 6 017 fa 1fa 1 3 The image fG1 is a subgroup 0f G2 Proaf 1 Since e1 e1e1 then this equation and the homomorphism property for f gives fe1 fe1e1 fe1fe1 Which implies fe1 fe1fe1 Since e2 is the identity element in G2 fe1e2 fe1fe1 By the left cancelation law e2 fe1 2 If a 6 G1 then aa 1 e1 By statement 1 and the homomorphism property for f fafa 1 aa l 61 62 and SO fafa 1 62 Statement 6 in Proposition 32 now implies fa 1 fa 1 3 We now prove fG1 is a subgroup of G2 a By statement 1 e2 f 1 6 all b Let h E fG1 Then by de nition of the image fG1 3a 6 G1 such that b fa By statement 2 fa 1 fa 1 5 1 Hence 5 1 E fG1 c Let a b E fG1 Then by de nition of the image fG1 375 y 6 G1 such that a and b Then ab and so ab 6 fG1 By de nition of subgroup fG1 is a subgroup of G2 D De nition 323 If f A gt B and W C B then f 1W a E A l fa E The subset f 1W of A is called the inverse image of W Example 324 Consider the function x2 to be a function from R to R Let W 760124 Then F 1W 0i1i i2 Theorem 325 Suppose f G1 gt G2 is a gmup homomarphism and H C G2 is a subgmup 0f G2 Then the inverse image f 1H 0f H is a subgmup 0f G1 Proaf 26 1 Since H is a subgroup of G2 e2 6 H By statement 1 of Theorem 322 fe1 e2 Since fe1 e2 then e1 6 f 1H by de nition of inverse image 2 Let a E f 1H Then at 6 H by the de nition of inverse image Since H is a subgroup fa 1 E H By statement 2 of Theorem 322 fa 1 fa 1 E H and so a 1 E f 71H 3 Finally let ab E f 1H which means that fafb E H Note that ab fafb E H since H is closed under the group operation in G2 This shows ab 6 f 1H Thus we have shown that f 1H satis es the three properties existence of identity existence of inverses and closure of the group operation necessary to be a subgroup of G1 D De nition 326 Suppose f G1 gt G2 is a group homomorphism The kernel of f is the set Kerf a 6 G1 l fa e2 where eg is the identity element of G2 Theorem 327 Iff G1 gt G2 is a group homomorphism theri Kerf is a subgroup of G1 Proof 1 By statement 1 of Theorem 322 fe1 eg and so e1 6 Kerf 2 If a E Kerf then by Theorem 322 fa 1 fa 1 egl eg and so a 1 E Kerf 3 If ab E Kerf then ab fafb 262 eg and so ab 6 Kerf By de nition of subgroup Kerf is a subgroup of G1 D Theorem 328 Iff G1 gt G2 mng G2 gt G3 are group homomorphisms theri gof G1 gt G3 is a group homomorphism Proof Let a b 6 G1 For the sake of clarity we will use the multiplicative notation convention for the group operation for G1 let 96 be the group operation in G2 and let be the operation in G3 Since f and g homomorphism g o f ab gfab gltfltagt fb gltfltagtgtgltfltbgtgt g o fag o By de nition of homomorphism g o f is a group homomorphism D De nition 329 If H C G is a subgroup and a E G then de ne aHah GlhEH and HahaEGlh H The set CLH is called the left coset of a and H Similarly Ha is called the right coset of a and H Let GH denote the set of left cosets of H Note that GH CLH l a E G is a collection of certain subsets of G and so it is a subset of the power set PG of G We now turn our attention to the proof of Lagrange7s Theorem which describes a fundamental relationship between the size of a nite group G and the size of any of its subgroups H Lagrange7s Theorem will follow easily from a series of ve lemmas concerning the left cosets of H in G Lemma 330 IfH C G is a subgroup and h E H then H hH 27 Proof Since h E H then hH hh l h E H C H by the closure property of the subgroup H In particular since h 1 E H then h lH C H Now multiply on the left each side of the containment equation h lH C H by h to obtain hh 1H C hH and so H eH hh 1H hh 1H C hH Thus H C hH Since hH C H also holds H hH D Lemma 331 IfH C G is a subgroup and ab E G with aH bH 3e Q then aH bH Proof Suppose aH bH Q By de nition of intersection there exists an element ahl E aH and an element bhg E bH such that ahl bhg for some h1h2 E H Because ahl bhg then ah1H bh2H But ah1H ah1H aH by the preVious lemma Similarly bh2H bH and so aH bH D Lemma 332 IfH C G is a subgroup and a E G then a E aH Proof Since e E H then a ae E aH D Lemma 333 IfH C G is a subgroup then A GH is a partition of G Proof By Lemma 332 every a E G is in its own coset aH and so the union UA C By Lemma 331 different cosets are disjoint which implies A GH is a partition of G by the de nition of partition D Lemma 334 IfH C G is a subgroup and aH is a left coset of H then laHl which means that every left coset of H has the same size as H Proof Recall that two sets have the same size means that there exists a function between the sets that is both 11 and onto De ne f H gt aH by am If 752 then an axg which implies by the left cancelation law that 1 352 By de nition of 11 f is 11 The function f is clearly onto since for any element ah E aH ah This proves f is both 11 and onto and so laHl D Theorem 335 Lagrange s Theorem If G is a nite group and H C G is a subgroup then lGl In particular ifG is a nite group and H is a subgroup then divides Proof This theorem is a simple consequence of Lemmas 333 and 334 Lemma 333 implies that the set of left cosets GH partitions G into a nite number of pairwise disjoint subsets alH agHanH where n It follows that lGl lalHl lel lanHl By Lemma 334 each akH has the size lHl and so lGllalHlla2HllanHllHllHllHllHlnlHllGHl This equation completes the proof of Lagrangels Theorem D 28 Proposition 336 Suppose G is a nite 9roup and9 E G Then lt9 9 l n E N is a subgroup of G Furthermore the integer size of this subgroup which we denote by llt9l is equal to the order 09 of 9 In particular Lagrange s Theorem implies 09 divides Proof 1 Since G is a nite set and lt9 992 9 C G then the subset lt9 is nite Hence for some n h E N 9 9 lC 9 9k So 9 e 9 9 9k By the left cancelation law e 9k and so e E In particular 9 has nite order 09 and suppose that from now on 09 h Then clearly lt9 9929lC e 2 For any n 1 g n lt h 9 9k 9C e and so every element 9 in lt9 has an inverse m mn 3 Given two elements a 9 and b 9 in lt9 then ab 97 9 9 lt9 is closed under the operation of G lies in Hence This completes the proof that lt9 is a subgroup of G We now prove that the elements in 992 9C e are distinct By our choice of h 0a the element e appears only once in this list If 9i 9217 where ij E N and i j lt h then 9ie 9297 and so by the left cancelation law e 97 This equation contradicts the fact that e 9C appears only once in 992 9C e This contradiction proves that 09 D Corollary 337 IfG is a nite group with n elements and a E G then a e Proof Let a E G with order k 0a and so aC e By Proposition 336 the order of a divides Cl n which means that we can factor n as n hm Then a am ak7 em e D De nition 338 Recall from the statement of Proposition 336 that if G is a nite group then lt9 9 l n E N When G is an in nite group and 9 E G then we de ne lt9 9 l n E Z A group G is called a cyclic group if for some 9 E G then G If G lt9 then we call 9 a generator of G Note that Zn lt1 and so it is a nite cyclic group of order or size n with 1 as a generator Since Z4 0123 3 33 2 333 1 3333 0 then we also see that Z4 lt3 and so 3 is a generator for Z4 However 2 E Z4 is not a generator since lt2 2 2 2 0 Z4 Note that Z lt1 lt71 is an in nite cyclic group with generators 1 and 71 Finally note that any cyclic group G lt9 is abelian since 9297 9H7 97H 979i Theorem 339 Suppose f G1 gt G2 is a group homomorphism Then f is 1 if and only Kerltfgt 61 Proof Suppose f is 11 and we will show that Kerf e1 By part 1 of Theorem 322 fe1 eg and so e1 6 Kerf If a E Kerf then fa e2 fe1 and so by de nition of 11 a e1 This proves Kerf e1 Now assume that Kerf el and we will prove that f is 11 Suppose fa and we will verify that a 1 Multiply each side of the equation fa on the left by fb 1 to 29 obtain fb 1fa fb 1fb e2 Using the additional fact that fb 1 fb 1 and the homomorphism property for f we get N775 fb 1fa fb 1fa 62 Since fb 1a e2 then b la E Kerf e1 and so b la e1 Multiply each side of the equation bila e1 on the left by b to get a bel b which proves f is 11 B De nition 340 A homomorphism f G1 gt G2 is an isomorphism if it is 11 and onto If there exists an isomorphism f G1 gt G2 then we say that the groups G1 and G2 are isomorphic Theorem 341 Suppose G is a group anda E G De ne fa G gt G by axa l Then fa is a group isomorphism Proof We rst show fa is a group homomorphism Let xy E G Then 1 faxy axya asceycf1 axa 1aya 1 axa 1aya 1 We now check that fa is 11 Note that gt a7ch1 aya l Applying the cancelation laws twice gives as y which implies fa is 11 To prove fa is onto we let y 6 G and we will nd an x E G such that fa y Note that fax y gives the equation a7ch1 y We can easily solve for x by multiplying both sides of the equation a7ch1 y on left by of1 and on the right by a to obtain as a lya Hence fax faa 1ya aa lyaa 1 eye y This proves fa is onto Since fa G gt G is homomorphism which is 11 and onto then fa is an isomorphism D Theorem 342 If G is a group then the set AutG G gt G l f is agroup isomorphism is a group under the binary operation of composition of functions AutG is called the group of automorphisms of G Proof First note that the composition of isomorphisms is an isomorphism since the composition of 11 and onto functions is again 11 and onto and the composition of homomorphisms is a homomorphism Thus composition of functions in Aut G is a binary operation Let idai G gt G be the function idgx 35 Then ida is easily seen to be a 11 and onto group homomorphism Since for any function f G gt G idG o f f o idG f then ida is the identity element in Aut Since the inverse function f lz G gt G of an f E AutG is 11 and onto as well as being a group homomorphism easy to check then f 1 E AutG Since composition of functions is associative homework problem 1 AutG is a group under composition of functions D Theorem 343 Suppose G is a group Then the function I G gt AutG de ned by a fa G gt G is a group homomorphism with KerI CG center of G 30 Proof We rst check that I is a group homomorphism This just means that ab fab is the same function as fa 0 f5 By de nition fabx abxab 1 abacb la 1 abxb 1a 1 12107351971 fafbx z o This proves that fab fa 0 f5 and so I is a group homomorphism We now check that KerI CG Clearly CG C KerI since for any a E CG anca 1 acaa 1 ace x iclgx But if a E KerI then V75 6 Gfax iclgx and so V35 6 G aaca 1 x Multiplying this equation on the right by a gives the equation axa la xa gt axe xa gt ax xa gt a E CG Thus KerI C CG and so KerI CG D De nition 344 The group isomorphism fa G gt G de ned by aaca 1 is called conjuga tion by a The set lnnerG fa l a E G is the image of the homomorphism I G gt AutG in the previous theorem and so it is a subgroup of Aut The group lnnerG is called the group of inner automorphism of C By Corollary 348 to the First lsomorphism Theorem stated below lnnerG is isomorphic to the quotient group or group of left cosets GCG Theorem 345 Normal Subgroup Theorem A subgroup H C G is called normal if any of the following equivalent properties hold 1 Va 6 Gthen aH Ha 2 H is the kernel of some group homomorphism f G gt G 3 VaEG anthE H then aha 1 E H 4 Va 6 G then aHa 1 C H 5 Va 6 G then aHa 1 H Proof Suppose H satis es statement 1 Let G GH set of left cosets of H We now check that for aH 17H 6 GH then the set aHbH aHbH ahlbhg l h1h2 E H is the coset abH Lemma 330 implies HH H and so using associativity and statement 1 we obtain aHbH aHbH abHH abHH abH Hence the product of two left cosets is again a left coset Note that aH eH aeH aH and similarly eH aH aH This means that the left coset eH H plays the role of an identity element in GH under the operation aH 19H abH Also note that a lH is the inverse coset of aH and that the multiplication is associative Hence GH is a group Now consider the function f G gt GH de ned by fa aH Then ab abH aHbH fafb which implies f is a homomorphism We claim that Kerf H which will prove that l gt 2 with G GH Clearly H C Kerf since for h E H hH H eH which is the identity element in GH Now suppose that a E Kerf Then fa aH H since H is the identity element in GH Since a ae E aH H then Kerf C H Since H C Kerf and Kerf C H we conclude that H Kerf and so 1 gt 31 Suppose H is the kernel of some homomorphism f G gt G Then Va 6 G and Vh E H me l fafhfa 1 fa 2fa 1 fafa 1 52 Therefore aha 1 E Ker H which proves that 2 gt Note that 3 gt 4 by de nition of the containment symbol C Suppose that Va 6 G aHa 1 C H Then this containment equation holds for a 1 which means that a 1Ha 1 1 C H Since a 1 1 a we obtain a lHa C H Multiplying the containment equation a lHa C H on the left by a and on right by a l gives H eHe aa lHaa 1 C aHa l and so H C aHa l Since chF1 C H and H C aHa l then H aHa l which shows 4 gt Assume 5 holds and let a E G Note that 5 gt 1 because we can multiply each side of the equation chF1 H on the right by a to obtain aHaila aHe aH Ha Since 1 gt 2 gt 3 gt 4 gt 5 gt 1 then all of these statements are equivalent which completes the proof of the theorem D By the proof of the Normal Subgroup Theorem whenever f G1 gt G2 is a group homomor phism then the set of left cosets GlKerf is a new group The next theorem concerning this coset group GlKerf plays an important role in group theory and its applications to other parts of mathematics Theorem 346 First Isomorphism Theorem If f GI gt G2 is an onto group homomor phism then there is a naturally induced group isomorphism G1Kerf gt G2 where aKerf fa In particular GlKerf is isomorphic to G2 Proof For a 6 G1 let ah E aKerf Then fah fafh fae2 fa Hence aKerf faKerf fa is a wellde ned function where faKerf denotes the unique element fa ofthe image off ofthe subset aKerf Note that aKerf bKerf abKerf fab fafb aKerf bKerf which proves is a homomorphism lf aKerf E Ker then aKerf fa eg and so a E Kerf Since a E Kerf Lemma 331 implies aKerf Kerf which is the identity element in GlKerf This proves that Ker consists only of the identity element and so by Theorem 339 f is 11 We now check that is onto Let y 6 G2 Since f is onto there exists an x 6 G1 with y But then xKerf y and so is onto By de nition of isomorphism is a group isomorphism D Since every group homomorphism f G1 gt G2 is onto its image lmf which is a subgroup of G2 then Theorem 346 implies the next corollary Corollary 347 Iff G1 gt G2 is a group homomorphism then GlKerf is isomorphic to the image of f Corollary 348 lnnerG is isomorphic to GCG where CG is the center ofG 32 Proof By Theorem 34 the homomorphism I G gt lnnerG C AutG is an onto homo morphism with KerI CG By the First lsomorphism Theorem lnnerG is isomorphic to GC D Homework Problems 1 Suppose f A gt B Q B gt C and h C gt D Prove that the composition of functions is associative by showing that h o g o h o g 0 for GVery 75 6 Al Hint Recall that g o evaluates to be Completely evaluate each side of the desired equation to show equality 2 Let A be a set and de ne the set of permutations of A to be PermA A gt A f is 11 and onto By Corollary 28 0 is a binary operation on PermA Prove PermA is a group under this binary operation What is the identity element in PermA Given f E PermA then what is the inverse element Hint Use homework problem 1 and the proof of Theorem 213 3 Prove that for k E N kZ kn n E Z is a subgroup of Z Hint See the discussion in Example 311 4 Prove that the union 2 U 3 is not a subgroup of Z by showing it is not closed under 5 Suppose A Hague is a collection of subgroups of a group G Prove that H A ag Ha is a subgroup of G Hint See the proof of Theorem 313 6 Suppose G is a group such that a 96 a e for all a E G Prove that G is abelian Hint Note that this equation implies that Va 6 Ga a l Apply this fact to the element ab and then use statement 4 in Proposition 32 7 What is the order of 6 in Z20 8 What is the intersection of the subgroups H2 0 2 4 6 28 C Z30 and H3 0 3 6 27 C Z30 9 Suppose G is a group and b E G Then the centralizer subgroup of b denoted by Cb equals 75 E G bx nub or equivalently Cb is the set of elements in G that commute with b Prove Cb is a subgroup of G 10 Let H SZ 3n n E Z List the three different cosets of H in Z 11 Let G Z5 and let H 0 3 C Z5 List the different cosets of H in Z5 12 List all the subgroups in Z5 Hint They are all cyclic and you can assume this fact 13 List all the generators for Z3 14 Let G1 and G2 be groups Consider the binary operation a1blagbg a1a2blbg on the cross product G1 gtlt G2 Show that this binary operation makes G1 gtlt G2 into a group For example if 51 6 G1 and 52 6 G2 are the identity elements then show 5152 is an identity element in G1 gtlt G2 33 15 l6 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Prove that the group Z2 gtlt Z3 is cyclic under the binary operation de ned in the previous homework problem Make a list of all of the generators of this cyclic group Prove that if G is a group With a prime number p of elements then G is cyclic Hint Apply Proposition 336 to any element a E G 7 5 What is the image of the function 752 R gt R What is the image of the function 935 752 24 gt R What is the image of the function e R gt R Let 752 R gt R a What is f 103 b What is f 14eo c What is f 17104 If f A gt B is 11 then prove that A and lmf have the same size lAl Suppose f A gt B and W1 and W2 are subsets of B Prove that a f 1W1 U W2 f 1W1U f 1W2 b f 1W1 W2 f 1W1 f 1W2 C filoV1 f 1W1C Let f R gt R be de ned by 3x Prove that f is a group homomorphism of the group R Prove the center CG of a group G is a normal subgroup of G You do not need to prove it is a subgroup Challenge Problems ls the group Z4 isomorphic to the group Z5 Why Prove Z4 is not isomorphic to Z2 gtlt Z2 Hint ls Z2 gtlt Z2 a cyclic group Prove Z5 is isomorphic to Z2 gtlt Z3 by constructing an isomorphism f Z5 gt Z2 gtlt Z3 Hint Also see homework problem 15 Suppose G is a nite group and H is a subgroup With 2 Prove that H is a normal subgroup of G Hint Use Lemma 333 Which also holds for right cosets Think in terms of the complement of the coset H 5H He Also note that by the proof of Lagrange7s Theorem each of the two left or right cosets of H have half the size of G Prove that the subgroup lnnerG C AutG is a normal subgroup Hint Use property 3 in the statement of Theorem 345 for the de nition of normal Let C 0 27d be the set of in nitely differentiable functions f 027r gt R 34 a Prove C 0 27d is a group under addition of functions g b What is the kernel of the derivative homomorphism D C 027r gt C 027rl where f x c ls x2 0 2W gt R in the kernel of the group homomorphism f C 0 27d gt R de ned by 02 fxclx Why Prove that cosx is in the kernel of 4 Elementary linear algebra and eld theory We now review some basic results from linear algebra As we have already seen group theory is the study of groups subgroups and relationships of subgroups with group homomorphismsi In a similar way linear algebra is the study of vector spaces subspaces and relationships of subspaces with linear transformations We now recall these basic de nitions De nition 41 A real vector space V is an abelian group V together with a map R X V gt V called scalar multiplication we write Av for the value of A 17 under this map which satis es the following distributive and associative laws 1 VA1A2 E R and V17 6 V then A1 A2v A117 A217 2 VA 6 R and V171va E V then Av1 172 A171 A172 3 VA1A2 E R and V17 6 V then A1A2v A1A2v1 De nition 42 A subgroup W ofa vector space V is a subspace if VA 6 R and Vw E W then Aw E Wi De nition 43 Suppose V and W are real vector spaces A function L V gt W is linear if L is a group homomorphism Vv w E V Lv w Lv Lw and VA 6 R and V17 6 V LAv ALvi By Theorems 3 and 327 for a linear transformation L V gt W the kernel KerL C V and the image lmL C W are subgroups of their respective spaces In fact simple arguments prove that KerL is a subspace of V and lmL is a subspace of Wi See homework problems 2 and 3 We recall that R ULIR R X X R the cross product n times of R is our standard example of a vector space In linear algebra one considers a vector v E R to be a column vector For example the vector v E R2 has rst coordinate 1 and second coordinate 3 Addition of vectors in R is then addition of coordinates of the vectors For example Finally we recall the de nition of matrix multiplication of a real entry m X nmatrix a1gt1 a1 a1n all a2 Hag A aml amg am 35 n 2 6mm i1 with an nvector X E R to be the mvector AX t E Rm n x Z am i i1 It is straightforward to check that matrix multiplication by A gives rise to a linear transforma tion A R gt Rm Theorem 44 IfL R gt Rm is a linear transformation then L is the same function as the one de ned by multiplication by the matrix ML L51L52Len where the hth column of ML is value of L on the hth basis element ek of R where all the coordinates of ek are zero except for the hth coordinate which is 1 For example for e1 6 R then e1 171 Proof Given a vector v E R then 17 blel bgeg bnen Z bkek bn k1 and so a linear transformation L R gt R has the value Lv L bkek Z Lbkek k1 k1 Z bkLeC In particular L is determined by its values Le1Le2 Lek on the standard k0 basis e1 e2 en of R But given a mgtlt nmatrix A am a simple calculation shows that AeC is its hth column Thus the linear function ML R gt Rm de ned by matrix multiplication by ML is the same linear transformation as L D Theorem 45 IfL R gt Rm andH Rm gt RC are linear transformations then the composition H o L R gt Rm is a linear transformation with matrix MHoL o L e1 H o L en Proof The proof that H o L is a group homomorphism follows from Theorem 328 Let x E R and v E R Then since H and L are linear we have H 0 not Haw Hum AHLv MH 0 Lv This calculation proves H o L R gt RC is linear and Theorem 44 completes the proof D The above theorem tells us how we should multiply matrices In other words if A is a k X m matrix and B is a m X nmatrix then thought of as linear transformations A o B R gt RC is a linear transformation with k X nmatrix MACE ABe1ABen In particular since the ith column of B is Bei then the ith column of MACE is equal to the matrix multiplication of A with the ith column of B Motivated by this observation we de ne 36 the matrix multiplication of a k X mmatrix A with a m X nmatrix B with i th column Bi to be AB AB1 MB AB1 MAB One can also add two mgtlt n matrices A am and B bid AB C cm aijbij Theorem 46 If A is a k X mmatriz B is a m X nmatriz and C is a n X pmatriz then ABC ABC In other words multiplication of matrices is associative Proof Consider A BC to be the matrices for their corresponding linear functions A Rm 7 RIC B R 7gt R C R 7gt R Then ABC is the matrix for the linear transformation Ao B 00 RP gt RC and ABC is the matrix for the linear transformation AoB 00 RP 7gt RIC By homework problem 1 in Section 3 A o B o C A o B o C and so ABC ABC D Theorem 47 Consider the function By R2 7gt R2 which is the rotation counterclockwise by angle 9 E 0 2 around the origin 00 Then 1 R9 is a linear function cos 9 7 sine 239 MRquot 7 sine cosQ gt39 Proof We rst check that R9 is linear Let 1 E R2 and x E R Then geometrically speaking Av is pointed in the direction 17 but is made longer by the factor x in the opposite direction when x is negative Clearly then By Av ARg Now consider two vectors v1 v2 6 R2 Note that v1v2 is the far corner point of the parallelogram with side vectors v1 and 172 Since this parallelogram rotates under R9 to the parallelogram with side vectors Rgv1 and R9 172 and far corner point R9 171 R9 172 then R9 171 172 R9 171 R9 172 This proves R9 is linear By de nition of cosQ and sin 9 R9 and R9 Statement 2 now follows immediately from Theorem 44 D Besides considering vector spaces with scalar multiplication by real numbers mathematicians and scientists also nd it useful to consider vector spaces with multiplication by scalars in number systems other than R For example one might want to de ne scalar multiplication of vectors by rational numbers in Q or by complex numbers in C a luj l ab E R Recall the multiplication rule for two complex numbers a1 bufl a2 52F alag 7 191192 CLle agbl More generally we will consider vector spaces with scalar multiplication by elements in an arbitrary eld where Q R and C are our classical examples of elds De nition 48 A eld F is a set F together with two binary operations and which are commutative and satisfy the following properties 1 F is a commutative group under with identity element 0 2 Multiplication induces a binary operation on F 7 0 and with respect to this binary operation F 7 0 is a commutative group 37 3 The operations of and satisfy the distributive law Va b c E F a b c a b a c Remark 49 As in group theory for a eld F we usually write ab instead of a b the inverse of a E F under is written 7a the identity element of F 7 0 under multiplication is written as 1 is unique and we write a 177 for the unique multiplicative inverse of an a E F 7 We say that a subset F of a eld F is a sub eld of F if F is a subgroup of F and F 7 0 is a subgroup of F 7 0 The rational numbers Q with the usual operations of addition and multiplication is a sub eld of R Similarly the set of complex numbers C a b l ab E R is an example of a eld with R as a sub eld There are also important examples of elds which are nite The most wellknown examples of nite elds come from the groups Zn when n is a prime In each Zn we can de ne multiplication mod For example in Z5 01 2 3 4 5 we have 2 3 6 0 mod 6 and 4 5 20 2 mod Since 2 3 0 mod 6 then does not induce a binary operation on Z5 7 0 and so Z5 is not a eld although multiplication is a binary operation on Z5 The proof of the next proposition is straightforward Proposition 410 The binary operations of addition and multiplication on Zn satisfy the following properties 1 Va bc 6 Zn abc abc 2 Va bc 6 Zn ab c ab ac 3 Va b 6 Zn ab ba 4 VaEZn laa Theorem 411 pr is a prime number then Zp is a eld under the binary operations of addition and multiplication Proof By Proposition 36 Zn is a commutative group under By Proposition 410 it remains to prove that Zn 7 0 is a group under a We rst check that is a binary operation in Zn 7 Let m n 6 Zn 7 Then m n mn mod lf mn mod p is zero then p divides mn But if a prime divides the product of two positive integers then it divides one of them Since m and n are both positive integers less than p then we conclude that p does not divide mn and so m n mn mod p is an element in Zn 7 By Proposition 410 it remains only to show that each element n of Zp7 0 has a multiplicative inverse Fix n 6 Zn 7 0 consider the function fn Zn 7 0 7 Zn 7 0 de ned by nx lf fn is onto then there exists an m 6 Zn 7 0 such that nm l and then m will be the multiplicative inverse for n Thus we need only prove that fn is an onto function Whenever A is a nite set and f A 7gt A is a 11 function then f is also an onto function One way to see this interesting additional property holds for a 11 function f is given by the following argument By homework problem 21 in Section 3 lAl llmfl where lmf C A But any subset B C A with the same size as A must be equal to A since A is nite Hence lmf A which means that f is onto 38 By the discussion in the previous paragraph in order to complete the proof of the theorem it remains only to show that f Zn 7 0 7 Zn 7 0 is 11 Suppose where 0lt x yltp Then nxnyian70andsonx7nynx7y Oian This means that the prime p divides n or p divides x 7 y Since 0 lt n lt p 19 does not divide n and so 19 divides x 7 y Since 0 g x 7 y lt p and p divides x 7 y which means as 7 y 0 and so as y This proves that fn is 11 which completes the proof that every n 6 Zn 7 0 has a multiplicative inverse D Note that we can identify Zn 012n 7 l with the set of left cosets ZH for the subgroup H nZ kn l k E Z In this case we can write ZH 0 H 6 1 H T 2 H 2 n 7 l H 612 m Also note that the function or Z 7 Zn de ned by 0k k mod n is a group homomorphism with Kero H nZ this is because for ij E Z oi j j mod 239 mod j mod Also note that for ij E Z oij oioj which means that 0 also preserves the multiplicative operations we have on Z and on Zn Corollary 412 Fermat s Little Theorem Let p E Z be a prime number If a E N is not divisible by p then ap l 1 mod Proof Let p be a prime and suppose a E N is not divisible by p In this case 0a a a mod p is an element of Zn 7 Our goal is to show that a 1 7 l is a multiple of p which just means that a 1 7 l is in the kernel of the homomorphism a which is the subgroup pZ C Z Consider 0ap 1 7 1 Since 0 is a group homomorphism 0ap 1 7 l 0ap 1 071 0ap 17l where 7l p71 is the additive inverse ofl in Zp Since 0 sends products to products 0ap 1 0ap 1 5P4 By Theorem 411 Zn 7 0 is a group with p 7 1 elements and so by Corollary 337 530 1 l which is the identity element in Zn 7 Hence 0ap 1 7 l 0ap 1 7l Ep 1 7 l l 7 l 0 in Zp which means that a 1 7 l is divisible by p D Recall from homework problem 29 in Section 2 a complex number r E C is algebraic if it is a root or zero of some nonzero polynomial a0 alx anx with coef cients at E The main goal of the remainder of this section is to prove that the set A C C of algebraic numbers forms a sub eld of C To prove this interesting theorem in number theory we rst need to develop the notion of a vector space with scalar multiplication in a general eld From this point on in this section the reader may assume that all of the elds we are considering are sub elds of the complex numbers C if heshe prefers In any case the reader should think of F as a number system where the usual laws of arithmetic hold De nition 413 A vector space V over a eld F is a group V under together with a map F X V 7gt V called scalar multiplication which satis es the following distributive and associative rules 1 VALAQ E F and V17 6 V A1 A2v A117 2v 2 VA 6 F and V171 v2 6 V M171 172 A171 Avg 3 VA12E F and V17 6 V A1091 x xg z 39 Note that if a eld F is a sub eld of a larger eld F then for x E F and v E F one obtains Av E F where Av is the product of and v in F i Note that for x E F and 171172 6 F xv1v2 A171 Avg by the distributive rule for multiplication in F i It is easy to check that this 77scalar multiplication of elements in F by elements of F makes F into a vector space over Fr In this way we can consider R to be a vector space over the sub eld Q and consider C to be a vector space over the sub eld R We want to de ne new examples of sub elds of C which are different from R and Since any sub eld F of C has 1 E F and since F is a group under then F contains the integers Z as a subgroup Since F 7 0 is also a group under multiplication then it also holds that Q C Fl Proposition 414 Let a bxi 1 ab E Then addition and multiplication are binary operations on which makes into a sub eld ofR that is di erent from Proof Clearly addition and multiplication on R induce binary operations on For example 2 3 7 7 14 217 2 7 6 8 19xii It is also clear that is a group under addition with 0 0 0 and the additive inverse of a bxi is 7a 7b i Also note that 1 1 0 is the multiplicative identity element for 7 Since C R the associative and distributive laws for R automatically hold for The only thing left to check to show that is a eld is to verify that any a bxi E 7 0 has a multiplicative inverse in 7 0 where either a f 0 or b 0 H b 0 then a bxi a E Q 7 0 has a multiplicative inversei Assume now b 0 By homework problem 30 in Section 2 is not a rational number Since a bxi 0 and Q then a 7 bxi is not a rational number and so a 7 bxi 0 Hence 1 7 1 a7b 7a7b 7 a 7b aw ab a75 a272b2 7a272b2 a272b2 Since 6 but xi Q then is a sub eld of R which is different from D MW V27 912 De nition 415 Given a vector space V over a eld F we say that 1 A subset S C V spans V if every 17 E V is a nite linear combination of vectors in 5 In other words for v E V there exist a nite number of vectors 171172 171 6 S and scalars 12 An 6 F such that v A1v1nvn 2 If S C V then SpanS is the set of all nite linear combinations of vectors in Si 3 A subset S C V is a set of linearly independent vectors if whenever v1 vn E S and A1n E F such that A1171 A2172 gtnvn 07 then A1 A2 xn 0 We say that S is a linearly dependent set of vectors if it is not a linearly independent set of vectors 4 A subset S C V is a basis for V if it spans V and consists of linearly independent vectorsi 40 5 A vector space V over F has nite dimension n ifthere exists a nite subset S 171 172 vn which spans V and any subset of V with less than n vectors will not span Vi In this case we write dimFV nl Note that the standard basis e1 e2 is a basis for R2 considered to be a real vector space Another basis for R2 is S v1 3 v2 To see this rst note that e1 v1 and eg v2 7 v1 Then lt2 ael beg avl bv2 7 v1 a 7 bv1 bvg and so 5 spans R Furthermore if avl bvg 0 g for some ab E R then alt gtb SW a 6 Hence b 0 and since a b 0 then a 0 and so the set S is a linearly independent set of vectogsi Since 5 spans R2 and it is a linearly independent set of vectors then S is another basis for R i For the eld described in Proposition 414 clearly dimQQ 2 with basis v1 1 v2 In the proof of the next lemma we will use the easy to prove fact that if S C V is a nonempty subset then SpanS is a subspace of V and so SpanS it is closed under additioni Lemma 416 Suppose V is a vector space over F and S C V is a possibly in nite subset of V Then 1 If S is a linearly dependent set of vectors with at least two elements then some vk E S can be expressed as a nite linear combination of vectors in S which are di erent from vk In this case SpanS SpanS 7 2 If S is a linearly independent set of vectors and the vector v E V can be expressed as v 2211 aivi 2211 bivi for some v1v2vn C S then ai bi for all i 6 12 n 3 HS is a basis for V then every v E V can be expressed uniquely as a nite linear combination of vectors in 5 Proof Suppose g 171 172 vn C S is a linearly dependent set of vectors with n 2 2 Then A1171 Anvn 0 where some M f 0 After reindexing S we may assume that A1 0 Since A1171 7 22 xivi and A1 0 v1 xf17ivi Z gt1gtivi Zaiviv i2 i2 i2 where ai 7f1i E F In order to prove SpanS SpanS 7 v1 we need to check the containment equations SpanS C SpanS7v1 and SpanS7v1 C SpanSi Since S7v1 C S then the de nition of the span of a set implies SpanS 7 v1 C SpanSi We now show that SpanS C SpanS 7 v1 where we are assuming v1 2212 aivzx If v E SpanS then v 41 221 biwi where wi E 5 Note that we may assume that wl v1 if v1 does not originally appear then force it to appear by letting wl v1 and b1 0 Hence v blvl 2212 blwi b1v1 w where v1 and w lie in SpanS 7 v1 Since the span of a set is a subspace blv v1 w E SpanS 7 v1 By de nition of containmentSpanS C SpanS 7 v1 which completes the proof of the rst statement of the lemma Suppose S is a linearly independent set of vectors and 21 aivi 2211 bivi for some subset 171 172 vn C S Then 0 2211 aivi 7 21 bivi 2211ai 7 bivi By de nition of linear independence ca 7 bi 0 for all i which means that ai bi for all i 6 12 n which proves the second statement of the lemma Statement 3 is an immediate consequence of the de nition of basis and of statement 2 which completes the proof of the lemma D The following result is one of the basic main theorems in linear algebra Theorem 417 If V is a vector space of nite dimension n over a eld F then the following statements hold 1 If S 171 172 vn is a spanning set with n elements then S is a basis for V 2 If A w1w2 wk is a set of h linearly independent vectors then h g n and if h n then A is a basis for V In particular a basis for V exists and has n elements 3 If A 101202 wk is a set of h linearly independent vectors then B can be extended to a basis B w1 wkvk1 vn for V for some set vk1 vn C V In particular h g n and ifh n then A is a basis for V Proof Let S v1v2 vn be a minimal spanning set for V By Lemma 416 if S is a linearly dependent set of vectors then after possibly reindexing Spanv2 vn SpanS V But the spanning set v2 vn has n 7 l vectors which contradicts the de nition of the dimension which is n This proves statement 1 Let So v1 vn be a minimal spanning set and let A w1w2 wk be a set of linearly independent vectors If n or k is 0 then statement 2 clearly holds so assume that both n and h are greater than 0 Suppose for the moment after some possible reindexing of S that Sm w1 wm vm1 vn is a minimal spanning set for some m 0 g m lt n and we will show that a similar set Sm1 exists when m lt h Since m lt h there exists wm1 E A and since Sm spans V wm1 A1101 Amwm Am1vm1 Anvn Since the set A is a linearly independent set of vectors then statement 2 of Lemma 416 implies wm1 1 wm1 A1101 Amwm and so after possibly reindexing the set vm1 vn we may assume that Am1 0 Therefore vm1 can be expressed as a linear combination of the vectors in Sm1 w1 wm wm1 vm2 vn lt easily follows that SpanSm1 SpanSm and since SpanSm V then SpanSm1 V as well Hence Sm1 is also a minimal spanning set for V We can continue inductively de ning Sm as long as m g h and m g n If h n then we see that 51C Sn 1121 1122 wn is a minimal spanning set and so by statement 1 it is a basis for V If h gt n then we have that Sn 1121 1122 wn is a minimal spanning set Since Sn spans then wn1 E SpanSn Here wn1 1 wn1 2211 aiwi which contradicts the uniqueness of statement 2 of Lemma 416 because A 1121 1122 wk is a linearly independent set of vectors This completes the proof of statement 2 42 Let S 171172 vn be a basis for V From the proof of statement 2 we see that after reindexing S the set B w1wkvk1vn is a basis for V and that h g n This completes the proof of the theorem D The next result is an immediate consequence of statement 2 of Theorem 417 Corollary 418 Suppose V is a vector space of nite dimension n over a eld F IfS C V is a subset with more than n elements then S is a linearly dependent set of vectors in V De nition 419 Suppose F is a sub eld of a eld F We say that oz 6 F is algebraic over F if oz is the root of a nonzero polynomial in Fx a0 a1x anx l n E N U 0 ai E F We say that F is algebraic over F if every oz 6 F is algebraic over F Proposition 420 Suppose F is a sub eld of F and F is a vector space of nite dimension n over F Then every a E F is the root or zero of some nonzero polynomial px 2210 My 6 FM of degree at most n In particular F is algebraic over F Proof Let oz 6 F and consider the set S l0z0z2 Ozn of n1 vectors in F Since the dimension of F is n Corollary 418 implies that this set of vectors is a linearly dependent set over F In other words there exist scalars A0 A E F not all zero such that 2210 xiozi 0 It follows that oz is a root to the nonzero polynomial px 2210 Ami D Corollary 421 IfF C R or F C C is a sub eld of nite dimension over Q then F C A where A is the set of algebraic numbers in C In particular since the sub eld has dimension 2 over Q the numbers in are all algebraic numbers over Proposition 422 Suppose F is a sub eld of a eld F Suppose oz 6 F is the root of a nonzero polynomial px E Fx of smallest positive degree n 1 Let Foz r E F l r 2210 ciozi where ci 6 F Spanl oz oz2 oz Then 1 Foz is a vector space of dimension n 1 over F with basis 1oz Ozn 2 Foz is a sub eld of F 3 The eld Foz is algebraic over F Proof Foz is clearly a vector space over F We now show that l0z0z2 Ozn is a basis for FOz By de nition of Foz A 1 oz oz2 ozn spans FOz If for some scalars ca 6 F 2210 aiozi 0 then oz is a root of the polynomial gx 2211 aixi Since we are assuming that a nonzero polynomial with oz as a root has degree at least degree n l the polynomial gx must be identically zero Therefore a0 a1 an 0 which means that the set A is a linearly independent set of vectors This completes the proof of statement 1 In order to show that Foz is a sub eld of F we rst have to show that multiplication is a binary operation on FOz In other words for bi ci 6 F the product 2210 biozi0 ciozi E FOz By the distributive law for multiplication on F there exist constants di 6 F such that n n 2n 2 bioZ ciozi Zdzozi i0 i0 i0 43 We claim that there exist scalars ho h1 hn E F such that 2220 dial 2210 hiai which by de nition of Fa is an element in Fo i By the wellordering principle there exists a smallest integer k 0 g h g 2n such that 2220 dial 250 fiai for some scalars E F If h g n then we have proved our claim So suppose h gt n and we will obtain a contradiction In this case 250 fiai fiozifcoC aia 1fkak 1i We will obtain the desired contradiction of the minimality of h by showing that an1 can be expressed as a linear combination of lower degree powers of Oz thereby lowering the degree h of the term fkoC If the nonzero polynomial of least degree which has Oz as a root is pz 22101 aizi then 2201 aiai 0 and so an1 2210 iagilaiai 2210 Mod 6 Fa where A iagilazx Since an1 2210 A20 is a linear combination of lower degree powers of Oz we obtain a contradiction to the minimality of the positive integer k Hence n n 271 71 Z bioZ ciaz Zdzai Zhiaz E Fa i0 i0 i0 i0 for some scalars ho hl hn E F which proves that Fa is closed under multiplication We now prove that every nonzero 8 E Fa has a multiplicative inverse To do this consider the subset of Fa consisting of all Fa multiplies of 8 A8 l x E Fozi Note that if 1 E then for some x E Fa x8 l and so 8 has the multiplicative inverse gt Also note that C Fa is a subspace of Fa over F and so has nite dimension at most n 1 In particular 882 8 2 C is a linearly dependent set over F and so there exists a nonzero polynomial qz 22112 aizi such that 22112 ai8i 0 Note that 22112 ai8i ai8i 1i Factoring out the largest power 8C of 8 in this sum we get 8C ai8i k 0 where ak 0 Since 8C 0 and the product of two nonzero elements in a eld is nonzero then ai8i k ak ak181 an28 2 k 0 Since is a group under and ak181 an28 2 k r E then ak 7r E Since is a vector space over F ak E F and ak 0 then aglak E and so 1 E As observed before 1 E implies 8 has a multiplicative inverse This proves Fa is a sub eld of F By Proposition 420 Fa is algebraic over F which completes the proof of Proposition 422 D Proposition 423 Suppose that F3 is a eld which is a vector space of nite dimension n over a svb eld F2 C F3 If F2 is a vector space of nite dimension m over a svb eld F1 C F2 then F3 has nite dimension mn over the svb eld F1 In particular F3 is algebraic over F1 and both m and n divide the dimension of F3 over F1 Proof Let B 61 H871 be a basis for F2 considered to be a vector space over F1 Let A a1 Ozm be a basis for F3 considered to be a vector space over F2 We will show that C 8jozi 6 F3 l 1 g i g ml g j g n is a basis for F3 considered to be a vector space over F1 Note that C has mn elements We rst show that with respect to F1 SpanC F3 Let v 6 F3 Since the vectors in A span F3 over F2 v aid for some CL 6 F2 Since B spans F2 over F1 for each i E 1 m ai 2271 bji8j for some bji 6 F1 Hence by substitution v Zaivi EX bjz jwz39 ZbMBg a i1 11 j1 23339 44 and so SpanC F3 We now prove that C is a set of linearly independent vectors in F3 when considered to be a vector space over F1 So suppose EM bjiwjozi 0 for some bji 6 F1 Then 0 21Z1 bji j0zi and since A is a linearly independent set of vectors over F2 the coefficient 2271 bjz j of ai must vanish for each i Hence for each i 2271 bjz j 0 Since B is a linearly independent set of vectors over F1 we conclude that for each i by b2i bm39 0 By de nition of linear independence C is a linearly independent set of mn vectors over F1 We have shown that C is a basis for F3 over F1 and so the dimension of F3 over F1 is mni Since F3 has nite dimension over F1 Proposition 420 implies F3 is algebraic over F1 D Corollary 424 Suppose F C F is a sub eld and a1 a2 an C F is a nite set such that al is algebraic over F and ak is algebraic over the eld Fa1 a2 ak71 where Fa1 a2 aj Fa1 a2 aj71aj is de ned inductively for 2 g j g n Then Fa1a2 an is a sub eld of F of nite dimension over F and so it is algebraic over F Proof Let F0 F and Fk Fa1a2 ak for h g n By Proposition 422 and the principle of mathematical induction Fk is a eld for h g n Then we have F0 C F1 C F2 C C F71 where the dimension of Fk over Fk1 is some nite positive integer mk By the principle of mathematical induction and Proposition 423 the dimension of Fa1 a2 an over F is equal to m1m2 mn which is nite D Corollary 425 Suppose F1 C F2 C F3 where F1 is a sub eld of F2 and F2 is a sub eld of F3 If F2 is algebraic over F1 and oz 6 F3 is algebraic over F2 then oz is also algebraic over F1 Proof Since oz is algebraic over F2 oz is a root ofa nonzero polynomial px 220 akxk for some ca 6 F2 Since a1 a2 an are algebraic over F1 F1a1 a2 an has nite dimension over F1 by the previous corollary Since oz is algebraic over F1a1 a2 an then F1a1 a2 an oz F1a1a2 anoz has nite dimension over F1 again by the previous corollary Since oz 6 F1a1 a2 anoz Proposition 420 implies oz is algebraic over F1 D De nition 426 A eld F is algebraically closed if every polynomial px 6 FM can be factored into linear factors px cx 7 a1x 7 a2 x 7 an where c ca 6 F The fundamental theorem of algebra implies that every polynomial px 6 CM of degree at least 1 has a root in C and so by induction on the degree of px the polynomial px can be factored into linear factors Thus the complex numbers C is an algebraically closed eld Theorem 427 Let A C C be the set of algebraic numbers Then 1 A is a sub eld of C 2 A is algebraically closed 3 Considered as a vector space over Q A has a countable in nite basis Ozl0z2 Ozn 45 Proof We rst show that A is a eld Given an element a E A Proposition 42 implies Qa is a nite dimensional vector space over Q Qa is a eld and Qa C A In particular if a f 0 then the multiplicative inverse of a in Qa is also algebraic We now verify that the binary operations of addition and multiplication induce binary op erations on A It then follows that A is a sub eld of C Let a8 E A By Corollary 424 Qa8 Qa is a sub eld of C which is algebraic over Q hence Qa8 C A Since a 8 and Q8 6 Qa8 then a 8 and Q8 lie in A which proves the rst statement in the theorem If a E C is algebraic over A then Corollary 425 implies a is algebraic over Q which proves statement 2 We now prove that A has a countable basis By homework problem 29 in Section 1 A is an in nite countable set and so A can be made into an in nite list A 08182 8 Let a1 81 and let 51 a1 Since no nite subset of A spans A as a vector space over Q there exists a rst index E N such that 822 SpanSl De ne a2 822 and let 52 011012 lnductively de ne 51C k E N as follows Given the set 51C a1 ak let ik 1 be the rst index such that 8C1 SpanSC De ne ak1 8C1 and let Sk1 a1 akak1 Finally let S U21 51C a1agan lf8 E A then 8 8C for some k E N and by de nition of 51C 8 E SpanSC Therefore 8 21 xiozi which implies the complex numbers in S span A If S were a linear dependent set then there would exist a nite set of elements a01 a02 adm C S with max0l 02 001 071 and rational numbers A E Q such that 2211 A2000 0 where some A f 0 But a1a2 adm is a basis for SpanSan and so it is a linearly in dependent set But a subset of a linearly independent set of vectors is also a linearly independent set of vectors which gives the desired contradiction This contradiction completes the proof that Sa1aganisabasis foerver D Homework Problems 1 Let V be a vector space over R with additive identity element 6 called the zero vector or origin of V a Prove that for 0 E R and v E V then 017 0 Hint Use the fact that 017 0 0v 017 017 b Prove that for A e R then A6 6 Hint Use the fact that A6 M6 6 A6 6 2 Let K be the kernel of a linear transformation L V gt W where V and W are vector spaces over R Prove that K is a subspace of V Hint By Theorem 32 K is a subgroup of V Use homework problem lb to show that for v E K and x E R then LOW 0 3 Let I be the image of a linear transformation L V gt W where V and W are vector spaces over R Prove that I is a subspace of W Hint Use part 3 of Theorem 32 and show that for v E Iand E R then Av E I 4 Calculate the matrix product lt72 and the matrix sum lt72 46 5 Calculate the product of the following two matrices MM 6 Write down the matrix for the rotation R1 R3 7gt R3 counterclockwise by 90 degrees around the z axis 7507 OOH Munro OCADH gt707 010 7 Let M2 R be the set of 2 X 2 real matrices The determinant function det M2 R 7gt R is de ned by det lt2 ad 7 be a Prove that detAB detA detB Hint Evaluate each side separately and then compare them b Prove that the matrix I satisfies VA 6 M2 RAI IA A c Suppose that A E M2R has a multiplicative inverse B ie AB BA I Prove detA 0 Hint Use part a and the fact that AB I a b d Suppose that A lt0 01gt and D detA 0 Verify that the matrix ii B3 9 5 is the multiplicative inverse matrix to A e Recall that GL2R C M2R is the subset of matrices With multiplicative inverses By parts c and d GL2R A E M2R l detA 0 Prove that GL2R is a group under multiplication of matrices Hint Use Theorem 46 and parts a b 0 CU f Let R9 2399 be the matrix for rotation in R2 counterclockwise by the angle 9 Prove R9 6 Kerdet Where det GL2R 7gt R 7 0 is the restricted determinant homomorphism Here we are considering R 7 0 to be a group under multiplication The kernel of the determinate function de ned in this homework problem is a famous group in mathematics it is called the special linear group of real 2 X 2matrices and is denoted by SL2R 8 Consider the field of complex numbers to be R2 With polar coordinates r 9 Recall from the class you took in calculus Where you studied infinite series De Moivre s formula 5239s 0059 Sin9j cos9 sin9i Where 51 20 and 2 a bi Then every element 2 a bi 6 C can be Written in polar notation as 2 rely Where r is the length a2 b2 of 2 and 9 is its polar angle a Express the complex numbers 2 l i and 3239 in their polar notation refs 47 10 11 12 13 14 15 16 17 18 19 20 21 b Show that7 if fl is the length of 21 a1 191239 and r2 is the length of 22 a2 172i7 then the length of the product 2122 of the complex numbers is r1r2 c Using the exponent rule7 eaeb eab for any a b E C prove that ifrleig1 and r25292 are complex numbers7 then their product r15291r25292 r1r2ez9192 ln particular7 the polar angle of a product of complex numbers is sum of the polar angles d Use part c to prove that C 7 0 is a commutative group under multiplication What is the multiplicative inverse of rely when r f 0 Suppose a bx7l E C is a nonzero complex number either a f 0 or I f 0 Write down its multiplicative inverse Hint First try multiplying it by its complex conjugate a 7 b71 Suppose F is a eld with zero element 0 Let a E F and show 0 a 0 Hint Use the fact that0a00a0a0a If F1 and F2 are sub elds of a eld F7 then prove F1 F2 is also a sub eld You can use the result from group theory that the intersection of subgroups of a group is a subgroup In the eld Z5 what is the multiplicative inverse of 3 E Z5 In the multiplicative group Z5 7 07 what is the order of 2 Is Z5 7 0 a cyclic group What is the multiplicative inverse of 1 V in Hint See the proof of Proposi tion 414 Prove that 171 v2 is a basis for R2 You can use any of the theorems in this section or verify it directly by using the de nition of basis Suppose F is a sub eld of a eld F Prove that every element oz 6 F is algebraic Hint Consider a polynomial of degree 1 with oz as root What is the dimension of over Q and why You can use the fact that 5 is a root of x3 7 57 but it is not a root of a polynomial in of less degree Use Proposition 423 and the previous homework problem to prove that is not a sub eld of Q5 ls xg xg algebraic over Q Explain your answer Hint See the statement of Theo rem 427 Prove that oz xi is an algebraic number Also7 derive an upper estimate for the dimension of Qoz over Hint Use Proposition 423 and see the proof of Theorem 427 Let Am C R be the set of real algebraic numbers AR A Q R a Show AR is a eld Hint See homework problem 11 and Theorem 427 b Show that AR is not an algebraically closed eld 48 5 Metric and topological spaces In a rst class on calculus the student is introduced to the notion of a continuous function f R gt Ri lntuitively f is continuous if its graph does not have any jumps or equivalently if for any x E R and any sequence of points xnneN converging to x the sequence of values converges to the value Later in this class the student learns the fundamental theorem of calculus This theorem has two parts The rst part states that for any continuous function a b gt R there exists a differentiable function Fx a b gt R with derivative F for all x in the interval a b The second part of this theorem relates the area under the graph of to any such antiderivative F by 1 Area Fb 7 Fa where we assume the function is positive Our primary goal in this section is to develop the general theory of topological spaces and continuous functions between these spaces Along the way you will be introduced to a number of proof techniques and concepts that have a geometrical as well as analytical sidel Some fairly simple applications of this theory will be to give rigorous proofs of the intermediate value theorem the maxmin theorem and the fundamental of calculus The theory of topological spaces begins with and is motivated by the special case of a metric space M which is a set whose elements we call points where one can measure the distance dp q between any two points 19 q 6 Mi The distance function 61 satis es three basic intuitive properties similar to the distance function on the real number line or in the Euclidean plane We now describe precise notion of a metric space De nition 51 A metric space is a pair M d where M is a set and d M X M gt 000 is a distance function on M satisfying for Vp q w E M 1 619979 0ltgtpq 2 619979 Gimp 3i dp 21 dp q dq w Triangle lnequalityl De nition 52 Suppose M d is a metric space The ball centered at p of radius r gt 0 is de ned to be 3419 q E M dpq lt r De nition 53 A subset O C M is an open set if for each 19 E 0 there exists an r gt 0 such that BTp C 0 Theorem 54 A ball BTp in a metric space M d is 27L open set in M Proof Let BTp be the ball centered at p of radius r Let g E BTpl Since dpq lt r then 8 r 7 dpq is positive We now show that BEq C BTpl Let y 6 BE g which by de nition means dq y lt 8 By the triangle inequality 6129 y S 6129 q dqy lt qu 6 61mg r i 619979 r Thus dp y lt r which means y E BTpl This proves that BEq C BTp and so by de nition of open set BT p is open D 49 Example 55 Our standard example of a metric space is Rcl where for xy E R clxy lye For example the distance between the points x 73 and y 6 is cl736 6 7 73 6 3 9 ln homework problem 1 you will verify that Rcl satis es the three properties for cl that de ne a metric space structurei Note that for x E R and r gt 0 then the ball BT centered at x of radius r is the open interval at 7 r x r Theorem 56 Let M cl be a metric space Then the following three statements hold 1 The intersection of a nite number of open sets in M is an open set in M 2 The union of any collection of open sets in M is an open set in M 3 M and Q are open sets of M Proof Let A1 An be a nite number of open sets in Mr Let p E 1211419 By de nition of intersection p E Ak for each h 1 g h g n Since each Ak is open there exists an rk gt 0 such that B p C A Let r minr1r2 rn Note that r gt 0 and BTp C B p C Ak which implies that BT p C Ak for each h By de nition of intersection BTp C 121 A By the de nition of open set the set 121 Ak is open Now suppose Aaae is a collection of open sets in M and p E Uael Aw By de nition of union p is in one of the sets Ad for some index on Suppose p E Ami Since Am1 is open there is a ball BTp C Am Since BTp C Aaland ACZ1 C Uael Aa then BTp C Uael Aw This proves that Uael Ad is open Note that M is an open set since for any point p E M Bl p C Mi Finally the empty set Q is an open set since the de ning property of being an open set is satis ed for every point in Q because there are no points in Q This completes the proof of the theoremi D The previous theorem plays a fundamental role in the development of the remainder of this section Part of the reason for this is that many important ideas such as 1 Convergence of a sequence of points and limits in a metric space 2 Special properties such as compactness and connectedness of a metric space 3 The de nition of a continuous function f M1 gt M2 between two metric spaces can be best understood or de ned just in terms of open sets in the metric space rather than in terms of the distance function Motivated by the statement of Theorem 56 we make the following de nition De nition 57 A topological space is a set X together with a collection TX of subsets called open sets satisfying 1 The intersection of a nite number of open sets in X is an open set in Xi 2 The union of any collection of open sets in X is an open set in Xi 3 X and Q are open sets of Xi 50 We now develop the notion of a limit point p for a sequence of points pnneN in a metric space M cl lntuitively p is a limit point of the sequence pnneN if the sequence of points converges to p in the sense that the distances clppn converge to zero as n approaches in nity We rst show that the understanding of such limits can be carried out solely in terms of the open sets or the topology of M and more generally the concept of a limit point p of a subset A C M also makes sense solely in terms of the topology of M Once we prove these properties we will de ne the notion of a limit point of a subset A of an arbitrary topological space X and we prove that a subset A C X contains all of its limit points if and only if its complement AC in X is an open set De nition 58 We say that a sequence anneN of points in R converges to a point x E R if V6 gt 0 ENE such that for n 2 NE lac 7 anl lt 8 If the sequence anneN converges to x then we write limnn00 an 75 De nition 59 Suppose M cl is a metric space and pnneN is a sequence of points in M We say that this sequence converges to p E M if limnn00 clppn 0 If the sequence pnneN converges to p then we write limnn00 pn p The proof of the next proposition follows immediately from the above de nitions Proposition 510 Suppose M cl is a metric space Then limnn00 pn p if and only if V8 gt 03N such that for n 2 N clppn lt 8 or equivalently V6 gt 03N such that for n 2 N pn E BEltPgt De nition 511 A point p in a metric space M cl is a limit point of a subset A C M if there exists a sequence of points pn E A where pn p such that limnn00 pn p Proposition 512 A point p in a metric space M cl is a limit point ofA C M if and only iffor every open set 0 ofM with p E 0 then 0 7 Q A 3e Q Proof Suppose p is a limit point of a sequence pnneN in A such that Vn E N pn p Suppose that O is an open set in M with p E 0 Since 0 is open 335p C 0 Since limnn00 pn p for n large pn E BEp 7 C O 7 Hence for n large pn E A 0 7 p and so Anlt07pgt am Now suppose that for every open set 0 in M with p E O O 7 Q A 3e Q Consider the ball 3 p for n E N Since 3p is open 3 p 7 Q A 3e Q and so there exists a point pn E A 7 p with clpnp lt By de nition of limit point limnn00 pn p which proves p is a limit point of A D The previous proposition motivates the next important de nition of limit point of a subset A in a topological space X De nition 513 A point p in a topological space X is a limit point of a subset A C X if and only if for every open set 0 of X with p E 0 then 0 7 Q A 3e Q We let LA denote the set of limit points of the subset A De nition 514 A subset A of a topological space X is closed if its complement AC is an open set in X 51 The next theorem gives an important and beautiful relationship between closed sets and subsets of a topological space which contain all of their limit points Theorem 515 Suppose X is a topological space A set A C X is closed and only LA C A Proof Suppose A C X is closed and we will prove LA C A Let p C X Assume that p A and so p 6 AC which is open since A is closed Since AC A Q then AC 7 A Q and so by de nition of limit point p LA Thus p A gt p LA By taking the contrapositive of this implication we obtain p E LA gt p E A which proves the desired containment LA C A Suppose now that LA C A and we will prove that AC is a union of open sets and so by de nition of topological space is itself open Since LA C A then q 6 AC gt g LA Let p E A Since p is not a limit point of A 3 an open set Op with p 6 Op and Op 7 A 0 Since p A in fact Op A Q We claim that AC UpeAa Op which will prove AC is open Since for each p E A Op C A clearly UpeAa Op C A But q 6 AC gt g E Oq C UpeAa Op and so q E UpeAa Op which proves the containment AC C UpeAa Op This proves AC UpeAa Op is open since it is the union of open sets By de nition of closed set A is a closed set in X D Theorem 516 Closed Subsets Theorem If X is a topological space then 1 The intersection of any collection of closed sets in X is a closed set 2 The union of a nite number of closed sets in X is a closed set 3 X and Q are closed sets Proof The above theorem follows immediately from the de nition of topological space the de nition of closed set and the DeMorgan s Laws in from set theory See Theorem 517 below For the sake of completeness we prove statement 1 of Theorem 516 Suppose A Aij ej is a collection of closed sets and consider their intersection A Hie Ai By DeMorgan s laws stated in Theorem 517 below iel AZ Uiel A which is open since it is a union of the open sets A open since Ai is closed in the topological space Hence AC is open which by de nition of closed means HA is a closed set D The proof of the next theorem is straightforward and is similar to the proof of Theorem 243 where we stated DeMorgan s Laws for two sets A B rather than for an arbitrary collection Aaae Theorem 517 DeMorgan s Laws Suppose Alba is a collection of subsets of a set X Then 1 Uael Aalc ag Air 2 aEI Aalc UaET A De nition 518 Suppose A is a subset of a topological space X get C C l where C is any closed subset in X with A C C The closure of A is de ned to be A og C In other words A is the intersection of all closed subsets of X which contain A 52 Theorem 519 SuppOse A C X is a subset Off a tOpOlOgical space X Then A is the smallest clOsed set in X cOntaining A in the sense that A is a clOsed set cOntaining A and any Other clOsed set cOntaining A has A as a subset FurthermOre AAUMm PTOOf Since X is a closed set containing A there is at least one closed set C of X which contains A Since every closed set C used in the de nition of A contains A the de nition of intersection implies A is a set which contains A Since A is the intersection of closed sets Theorem 516 implies A is closed S0 A is a closed set that contains A By the de nition of A A is a subset of every closed set that contains A This implies A is the smallest closed set containing A In order to show that A AULA we need to prove that AULA C A and A C AULA If B and D are subsets of a topological space with B C D then by de nition of limit point LB C LD This observation implies that LA C LA because A C A Since A is closed Theorem 515 implies LA C A As LA C LA and LA C A then LA C A Since it is also the case that A C A then A U LA C A which is one of our desired containment equations It remains to prove A C A U LA Since A is the smallest closed set that contains A it suf ces to show that A U LA is closed The proof that A U LA is closed is a slight modi cation of the argument given in the second paragraph of the proof of Theorem 515 which we now repeat for the sake of completeness We will show that AULA is closed by showing its complement is the union of open sets Note that p E A U LAC gt p A U LA gt p A and p LA Since p LA 3 an open Op with p 6 Op and Op 7 A Q Since p A in fact Op A Q Since Op is an open set in X which is disjoint from A the de nition of limit point implies Op LA Q which means that Op C A ULAC It follows that A U LAC quAULMW Op which implies A ULAC is open and so A U LA is closed D De nition 520 If M dM is a metric space and A is a subset of M then dM induces a distance function dA on A by restriction Vp q E A dA p q dM p q We call A dA a metric subspace of M dM Usually we suppress the subscripts and write d instead of dM and dA Proposition 521 Suppose A C M is a subspace Of a metric space M d with respect t0 the induced distance functiOn A subset O C A is Open if and Only if there exists an Open set OM in M such that O OM A PTOOf Let A C M In order not to get mixed up on notation we will let BTAp denote the ball of radius r in A centered at p and let By p denote the ball of radius r in M centered at p The proof of the proposition depends on the set equality BTA p By p A We rst show that if 0 is an open set in A then there is an open set OM in M such that O OM A By de nition of open set for every p E 0 there exists a ball Bf p C O for some pp gt 0 Clearly O Upeo Bf Since the balls Bf p are open in M and the union of open sets is open OM U intersections p60 Bf p is open in M By the distributive law for unions and oMnAltU BffltpgtgtnA UltB fltpgtmgt U B pO p60 peo peo 53 which proves O OM A where OM is open in M Now suppose OM is an open set in M and we will prove that OM WA is an open set in A Since OM is open in M for each p E OM there exists a ball 3p C OM So if p E OM A then 3 p Eggp A C OM A By de nition of open set in a metric space OM A is an open set in A D The previous proposition motivates the next de nition for topological spaces De nition 522 If A is a subset of a topological space X then de ne a subset O C A to be open in A if there exists an open set OX in X such that O OX A De ning open sets of A in this manner is called the subspace topology on A The proof of the next proposition is straightforward and is homework problem 18 Proposition 523 If A is a subset of a topological space X with the subspace topology then A is a topological space In other words the collection of open sets in A satisfy De nition 57 Proposition 524 If Y is a subspace of a topological space X then A C Y is closed in Y if and only if A C Y where C is a closed set in X Furthermore if Y is a closed set in X then a closed subset A of Y is a closed subset of X Proof Note that A is closed in Y 4 its complement in Y A is open in Y 4 3 an open set 0A C X such that YiA AC OA Y But then A is closed in Y 4 A YiOA Oi Y C Y for the closed set C 02 in X This proves the rst statement in the proposition If A is closed in Y then by the rst statement in the proposition A C Y where C is closed X If Y is also closed in X then A C Y is a closed set in X since it is the intersection of two closed sets in X D De nition 525 A topological space X is disconnected if X is the union of two disjoint nonempty open subsets We say that X is connected if it is not disconnected Example 526 The standard example of a disconnected space is any metric space M d where M consists of exactly two points M p g lfr dp Q then BT p p and BTg g are open sets by Theorem 54 Thus M is the union of the two disjoint nonempty sets BT pBT More generally it can be shown that any connected metric space with more than one point must be an uncountable set Another related example of a disconnected space would be the union of two disjoint disks 310 0 and 313 0 of radius 1 centered respectively at the points 0 0 and 30 in the plane R2 with the subspace topology The open unit disk 310 0 of radius 1 centered at 0 0 in R2 with the subspace topology is path connected in the sense that any two points in 3100 can be joined by a continuous path in 310 0 beginning at the rst point and ending at the second point It is not dif cult to show that a path connected topological space is always a connected space which means 310 0 is connected Proposition 527 A topological space X is connected if and only if the only subsets of X which are both open and closed are the subsets X and Q 54 Proof Suppose X is connected and A C X is a subset which is both open and closed Then AC is open and X is the disjoint union of the open sets A and A By de nition of connected either A or AC is the empty set and so A X or A 0 On the other hand if X is disconnected then it is the union of two nonempty disjoint open sets A and B Since A B A is also closed Since A and B are nonempty A is different from Q and from X Thus if X is disconnected then X contains a subset which is both open and closed and also not equal to X or Q E De nition 528 An interval I C R is any nonempty subset such that for any ab E I with a lt b then a lt t lt b implies t E I Note that every interval in R has the form ab 0 d a0 or 0 b where ab E R U 00700 and 0d 6 R in order to prove this wellknown characterization of intervals one needs the leastupperbound property for R given below De nition 529 A number b E R is an upper bound lower bound for A C R if for all t E A t g b t 2 b A subset A C R is bounded from above below if 3 an upper lower bound for A The subset A is bounded if it is bounded from above and from below equivalently A is bounded if A C ab for some ab E R LeastUpper Bound Property Any nonempty subset A C R which is bounded from above has a least upper bound ie an upper bound M such that for any other upper bound T then M g T Similarly any subset A C R that is bounded from below has a greatest lower bound Example 530 Consider the set of real numbers A 1 The number 5 is an upper bound for A l is the least upper bound for A and 0 is the greatest lower bound for A Theorem 531 A subset X C R with the subspa0e topology is 0onne0ted 4 X is an interval Proof If X is not an interval then 3 a b E X with a lt b and a number t X with a lt t lt b Let Ot s E R t lt s and let Ot7 s E R s lt t Then X is the disjoint union of the two nonempty open subsets Ot X and Ot 7 X of X which implies X is disconnected Now suppose that X is an interval and we shall prove X is connected Suppose to the contrary that X is disconnected and let A C X be a nonempty set which is both open and closed and where AC is nonempty Let a E A and b 6 AC and without loss of generality we may assume that a lt b By intersecting A with the closed interval a b we see by Proposition 524 and the de nition of subspace topology that A ab is both open and closed in ab Let B A a b and recall that a E Bb B and B is open and closed in ab Let I be the union of all intervals contained in B which contain a Since the union of a collection of intervals in R which contain a given number is again an interval see homework problem 13 then I is itself an interval and has the form either I a0 or I a0 where a g 0 g b Since B is a closed set in ab I C B and 0 is a limit point of I then 0 is also a limit point of B and so 0 E B Therefore the interval a 0 C B and by de nition of I I a 0 where 0 lt b But since B is open in a b and 0 lt b for some 8 gt 0 00 8 C B Since I U 00 8 is an interval in B containing a we obtain a contradiction to the fact that I is the largest such interval This contradiction proves that the interval X is connected B One of the most important concepts in mathematics is that of compactness which in the topological setting can be described by a topological space being 0ornpa0t Unfortunately the 55 usual de nition of compactness for a topological space X seems somewhat arti cial However the reader can be assured that this usual de nition is an essential and important one One well known result from calculus which we will derive using compactness is that any continuous function f a b gt R on a closed interval ab has a maximum at some point p 6 ab and a minimum value at some possibly different point q E a b We will prove this result by showing that the closed interval ab is a compact topological space and further that a continuous function f X gt R on any compact topological space X has both a maximum and a minimal value Soon we will go over exactly what it means for a function between topological spaces to be continuous De nition 532 An open cover of a topological space X is a collection of open sets Oaae such that X Uael 0a We say that an open covering Oaae has a nite subcover if there exist a nite number of indices a1a2 an in I such that X OCZ1 U Oat2 U U 0 De nition 533 A topological space X is compact if every open cover of X has a nite subcover De nition 534 A collection of subsets C Cathie of a set X satis es the nite intersection property FIP if every nite intersection Ca1 Can of sets in C is nonempty In the proof of the next theorem we will use the fact that if AC is the complement of A in X then ACC A Theorem 535 A topological space X is compact if and only if every collection Cathie of closed sets in X which satis es the nite intersection property FlP has nonempty intersection ag Ca 0 Proof Suppose X is compact and Cathie is a collection of closed sets lf Q ag Ca then by Theorem 517 X QC ag CaC Uael Cg and so 0ae is an open cover of X Since X is compact there exist a nite number of indices a1 a2 an such that X C1 U U Cg Apply Theorem 517 again to obtain Q XC Ca1 Can Since some nite intersection of sets in Cathie is empty then Cathie does not satisfy FlP By the contrapositive if Cathie satis es FlP then ag Ca Q Now suppose that every collection of closed sets in X which satis es Fl has nonempty total intersection and we will prove that X is compact Let Oaae be an open cover of X Since X Uael 0a Theorem 517 implies Q XC ag 0 It follows that the collection of closed sets 0ae does not satisfy FlP and so there exist a nite number of indices a1 Ozn such that Q 01 0 Taking complements again we obtain X Oat1 U U 0a which means that Oaae has a nite subcover By de nition of compact X is a compact topological space E Theorem 536 A closed bounded interval I a b C R is compact in the subspace topology Proof If a b then I consists of a single point and so it is compact Assume now that a lt I Let Oaae be an open cover of a b and we shall prove this cover of I has a nite subcover Since ab Uaej 0a then a E OCZ1 for some index a1 6 7 Since OCZ1 is open in ab 3 81 gt 0 such that aa 81 C 0a Let K C ab be the union of all intervals in ab which contain a and which can be covered by a nite number of the open sets in Oaae Note that K is itself an 56 interval of the form a c or ac where a lt c g b If c b and K a c then by de nition of K the interval ab is covered by a nite number of open sets in Oaae which completes the proof So we now check that c b and K a c Since Oaae covers I c E 05 for some 8 E J Since 05 is open in the subspace topology on a b 362 gt 0 such that c 7 62c 82 C 05 or else c b and c 7 82 c b C 05 By de nition of K a c 7 62 can be covered by a nite number OCZ1 Oan of open sets in Oaae But then Om Oan05 is a nite open cover of a b or of ac 82 C ab but the possibility a c 82 cannot occur by the de nitions of c and K Hence ab is compact D Theorem 537 Suppose X is a compact topological space HA is a closed set in X then with respect to the subspace topology A is a compact topological space Proof Let Oaae be an open cover of A By de nition of the subspace topology each 0a Off A where Of is open in X Since A5O ae is an open cover of X and X is compact X AC U Oi U U 0 for some nite set of indices a1 an in I But then AXnA ACUOX uu0X nA 0X nA uu 0X mA omuuoa a1 an 011 an By de nition of compact A is a compact topological space D In most of the topological spaces that mathematicians encounter in their research the converse of Theorem 537 also holds As the next theorem shows all metric spaces are included in such spaces Theorem 538 If A is a compact subset of a metric space M then A is a closed set and A is bounded in M in the sense that there exists a point p E M and a positive number R such that A C BR Proof First suppose that A C M is compact If A is not bounded then x a point p E M The open cover Bn BnpneN of M induces an open cover Bn AneN of A This open cover of A does not have a nite subcover since the union of a nite number of the sets of the form B711 ABn2 A 3 A l n1 lt n lt lt nk equals BM A which is a bounded set but A is not bounded This contradiction proves A is bounded For n E N let P g E M l xg be the closed ball of radius centered at p which is a closed set by homework problem 16 If A is not closed then there is a limit point x of A with 75 A Then the open set compliments Jn P give rise to an open cover of M 7 and Vn E NA is not contained in Jn since as is not a point of Jn but it is a limit point of A C UneN J71 Since 75 A then Jn AneN is an open cover of A The union of a nite number of the sets of the form Jm A J712 A Jnk A l n1 lt 712 lt lt nk equals Jnk A f A Hence this open cover of A does not have a nite subcover This contradiction proves A is bounded This completes the proof that A is closed and bounded in M D Theorem 539 HeineBorel Theorem A subset A C R is compact if and only if A is closed and bounded 57 Proof Theorem 538 implies that any compact subset of R is closed and bounded Suppose now that A C R is closed and bounded Then A is a closed subset of some closed interval ab Since a b is compact and A C a b is a closed subset Theorem 537 implies A is compact D De nition 540 Suppose M1cl1 and M2 d2 are two metric spaces A function f M1 gt M2 is continuous at a point p 6 M1 if limnn00 pn 19 implies limnn00 A function f M1 gt M2 is continuous if it is continuous at every point of M1 Theorem 541 A function f M1 gt M2 between two metric spaces is continuous if and only either of the following statements hold 1 V19 6 M1 and V8 gt 0 36 gt 0 such that fB p C Bgfp 2 For every open set 0 C M2 f 1O is an open set in M1 Proof The property f M1 gt M2 is continuous is clearly equivalent to statement 1 It remains to prove that statements 1 and 2 are equivalent Suppose f M1 gt M2 satis es statement 1 and O C M2 is an open set Let p E f 1O Since 0 is open there exists an 8 gt 0 such that Bafp C 0 By statement 1 36 gt 0 such that fB p C Bgfp C 0 Hence fB p C O and by de nition of inverse image 3519 C f 1O This proves that f 1O is an open set in M1 which proves l gt 2 Next suppose f M1 gt M2 and that for every open set 0 C M2 the set f 10 is open in M1 Let p 6 M1 and let 8 gt 0 Since balls are open sets Bgfp is open in M2 and so f 1BEfp is open in X Since 19 E f 1BEfp then by de nition of open set in a metric space 3 a ball 3519 C f 1BEfp Hence fB p C Bgfp which proves that 2 gt 1 D The previous theorem for metric spaces motivates the next de nition for topological spaces De nition 542 A function f X gt Y between topological spaces is continuous if for every open set 0 C Y the set f 1O is open in X One can also de ne what it means for a function f X gt Y to be continuous at a point De nition 543 A function f z X gt Y is continous at p E X if for every open set 0 C Y with E 0 there exists an open set Op C X with p 6 Op such that fOp C 0 Here fOp y E Y l there exists an x 6 Op such that 6 Op is the image of the subset Op Proposition 544 A function f X gt Y is a continuous if and only if it is continuous at every point of X Proof Clearly if f z X gt Y is continuous then it is continuous at every point So assume now that f is continuous at every point of X and we will show f is continuous Let 0 C Y be open and we will prove f 1O is open Let p E f 1O Since f is continuous at 19 there exists an open set Op C X with op C 0 By de nition of inverse image Op C f 1O It follows that f 1O UPS1 0 Op Since f 1O is the union of open sets then it is open This proves f is continuous by de nition of continuous D De nition 545 Let X by a topological space and M a metric space with distance function cl 58 1 We say that a sequence of functions fn X gt M converges pointwise if V35 6 X lirnnn00 fn exists In this case if we de ne the function f X gt M by lirnnn00 and we say that the functions fn converge pointwise to 2 Suppose that a sequence of functions fn X gt M converges pointwise to f X gt M and V8 gt 0 EN such that Vn Z N then lt 8 for V75 6 X In this case we say that the functions fn converge uniformly to Example 546 1 The sequence of continuous functions x 0 1 gt 0 1 converges pointwise to the discontinuous function f 0 1 gt 0 1 with 1 and 0 for x f 1 2 The functions i752 2 R gt R converge pointwise to the constant continuous function 2 R gt R but they do not converge uniformly to On the other hand for any xed interval a b C R the restricted functions fn 15 a b gt R converge uniformly to the constant function 2 The next theorem is a basic and important theorem in analysis Theorem 547 Uniform Limit Theorem Suppose X is a topological space and M is a metric space If a sequence fn X gt M of continuous functions converges uniformly to afunction f X A M then the limit function f is continuous Proof By Proposition 544 it is sufficient to check that f is continuous at every point of X So pick a point p E X and an open set 0 C M and we will prove that there exists an open set Op C X containing p such that its image satis es op C 0 Since 0 is open and E 0 then there exists an 8 gt 0 such that 325fp C 0 Choose N so that for Vn Z N lt 8 for all x E X In particular we see that clfNpfp lt 8 which means that p E Note that Op f 1BEfp is an open set of X since fN is continuous and BEfp is open We now check that op C 0 Since Op C f 10 then for any x 6 Op E Bgfp which means clfNx lt 8 Since lt 8 the triangle inequality implies lt 26 and so E 325fp Since ngfp C 0 we have E 0 as well which proves the desired containment equation fOp E 0 Hence f is continuous and the theorem is proved D Example 548 Consider the set of differentiable functions F 0 1 gt R 71 1 and 71 1 It is rather easy to prove that given any sequence of functions fnneN in F there exists a subsequence fnk keN which converges uniformly to a function f 0 1 gt R By Theorem 547 the limit function f is continuous Theorem 549 Let X YZ be topological spaces anal f X gt Y anal g Y gt Z be continuous functions Then 9 o f X A Z is a continuous function Proof Let A C Z be open Since g is continuous g 1A is open in Y Since f is continuous f 1g 1A is open in X By the next lemma 9 of 1A f 1g 1A and so 9 of 1A is open in X By de nition of continuous function g o f is continuous D 59 Lemma 550 Suppose A BC are sets and f A gt B and g B gt C are functions Then for any subset X C C 9 0 f 1X f 19 1X Proof We rst check that gof 1X C f 1g 1X lfp E gof 1X then gofp E X by de nition of the inverse image But then g o p E X and so E g 1X Which implies p E f 1g 1X Thus gof 1X C f 1g 1X We next check that f 1g 1X C gof 1X lfp E f 1g 1X then E g 1X and so E X by de nition of inverse image Thus g ofp E X This proves p E g of 1X Hence f 1g 1X C g o f 1X Which completes the proof of the lemma D Theorem 551 Suppose f X gt Y is a continuous function between topological spaces IfX is connected then the image is a connected subspace of Y Proof Arguing by contradiction suppose that X is connected but is a disconnected space By de nition of disconnected there are subsets A B C such that l fXAUB 2 AB are open 3 A B 4 AanndBy Q By de nition of subspace topology A AY and B BY Where AY and BY are open in Y Since for every p E X E A U B then E A or E B Thus p E f 1A Uf 1B Which implies X f 1AUf 1B Since f is continuous the sets f 1A f 1AY and f 1B f 1BY are open in X lfp E f 1A f 1B then p E f 1A and p E f 1B Which implies E A B but A B 0 Thus f 1A f 1B Q Since A 3e Q and f X gt is onto 3x 6 X With E A Which proves f 1A 3e 0 Similarly f 1B 3e Q The existence of the disjoint nonempty open sets f 1A f 1B Whose union is X proves X is disconnected Which gives the desired contradiction D The following result is an immediate consequence of Theorem 531 and Theorem 551 Corollary 552 Intermediate Value Theorem IfX is a connected topological space andf X gt R is continuous then is an interval In particular if C R is an interval and f I gt R is continuous then C R is an interval Theorem 553 Suppose f X gt Y is a continuous function between topological spaces IfX is compact then the image is a compact subspace of Y Proof Let Aaae be an open cover of By de nition of the subspace topology for each Oz 6 I AC A fX Where A is an open set in Y Since f is continuous and onto fX f 1Aa f 1Aae is an open cover of X Since X is compact X f 1Aa1 U U f 1Aan for some nite set of indices a1ozn in I Note that since AC C fX then ff 1Aa AC for each Oz 6 I Hence fX ff 1Am u Uff 1Aa Am u UAW 60 By de nition of compact is a compact topological space E Corollary 554 MaxMin Theorem IfX is a compact topological space and f X 7gt R is a continuous function then f has a maximum M anal a minimum value m Proof By Theorem 515 C R is compact and then by the HeineBorel Theorem is a closed and bounded subset of R Since is a bounded set in R it has a least upper bound say M Since is a closed set homework problem 24 implies M E Similarly has a greatest lower bound say m E Hence f has a maximum value M and a minimum value m Corollary 555 If ab is a closed interval in R anal f I 7gt R is a continuous function then is a closed interval of the form mM where m is the minimal value off anal M is the maximum value of Proof By Corollary 552 is an interval By Theorem 553 and Theorem 539 the interval fI must be closed and bounded and so it must be of the form m D De nition 556 A sequence of intervals IkkeN in R is nested if m lt n implies In C Ln Theorem 557 Nested Interval Theorem If ambn neN are nested closed intervals then neNan 1771 Q Furthermore if 171 7 an 7gt 0 as n 7gt 00 then neNanbn is a single point 350 anal for any choice of points pn E ambn then limnn00 pn 350 Proof Suppose anbnneN are nested closed intervals Then this collection of closed subsets of ahbl clearly satis es the nite intersection property FlP By Theorem 535 and Theorem 536 neman 17 3e Q which proves the rst statement in the theorem Suppose 171 7 an 7gt 0 Then neNanbn consists of a single point 350 Otherwise for all n E N there would be two points pq with pq 6 am 1771 and p f q Since clpq 171 7 an and 171 7 an 7gt 0 then clpq 0 which contradicts the rst axiom for the distance function If pn 6 am 1771 then the distance from pn to 0 is less than or equal to 171 7 an since 750 is also a point in ambn Hence by de nition of limit limnn00 pn 350 D De nition 558 A sequence akkeN C R is monotonically increasing if whenever m lt n then am an The sequence is strictly increasing if m lt n implies am lt an The proof of the next proposition is homework problem 30 Proposition 559 If anneN C R is a bounded monotonically increasing sequence then limnn00 an LUBanneN where LUB means the least upper bound De nition 560 A sequence pnneN in ametric space M cl is a Cauchy sequence if V6 gt 0 EN such that for all m n 2 N clpmpn lt 8 Lemma 561 A Cauchy sequence with a convergent subsequence must itself converge 61 Proof Suppose that pnneN is a Cauchy sequence and pm is a subsequence that converges to p E M Let 8 gt 0 and we will nd a positive integer 7 such that for j Z J pj E BEp Since limzvH00 pm p there exists a positive integer K such that for i 2 K pm 6 Bg Since pnneN is a Cauchy sequence there exists a positive integer L such for nm Z L dpnpm lt Let N maxKL Then for n 2 N the triangle inequality implies dppn dppnN dpnNpn lt 3 g 8 which implies pn E BEp This implies limnn00 pn p D De nition 562 M d is a complete metric space if every Cauchy sequence in M converges The main classical examples of complete metric spaces are the n dimensional Euclidean spaces R with the usual Euclidean distance functions This result follows easily from the fact that R is complete a property which holds by Theorem 566 given below The following proposition is an immediate consequence of Lemma 561 Proposition 563 A Cauchy sequence pnneN in a metric space M is bounded In other words there exists a point p E M and number R gt 0 such that Vn E Npn E BRp Proof Given a Cauchy sequence pnneN in M there exists an N such that Vm n 2 N we have dpmpn lt 1 In particular for p pN dppn lt 1 for all n 2 N If R max17dpp1 6199292 dppN71 then clearly pn E BRp Vn E N D Corollary 564 A Cauchy sequence in R is bounded Theorem 565 A bounded sequence pnneN in R has a convergent subsequence Proof If P pnneN is a bounded sequence in R then there exist ab E R a lt I such that Vn E N pn 6 ab Let ahbl be a subinterval of ab of the form a TH or Fail 17 such that pn E ahbl for an in nite set of indices 1 C N Similarly let a2bgl a subinterval of the form ah or 51 such that pn E a2bgl for an in nite set of indices 2 C 1 Continuing inductively de ne the interval ambn C an1 511 and In C 7171 By construction there exists a point pm 6 akbk P where we may assume that i lt j gt ni lt nj Since lbn 7 anl gt 0 as n gt 00 then the Nested lnterval Theorem Theorem 557 implies that the subsequence pm converges to the point nemam 1971 D Theorem 566 R with the usual distance function is a complete metric space Proof By Corollary 564 a Cauchy sequence pnneN in R is bounded By Theorem 565 this Cauchy sequence has a convergent subsequence By Lemma 561 the Cauchy sequence converges D De nition 567 A function f M1 gt M2 between the metric spaces M1d1 and M2d2 is uniformly continuous if V6 gt 0 36 gt 0 such that Vpq 6 M1 dpq lt 6 gt dfpfq lt 8 Equivalently f is uniformly continuous if V6 gt 0 36 gt 0 such that Vp 6 M1 fB C BE 62 Theorem 568 Iff M1 7 M2 is a continuous function between metric spaces and M1 is compact then f M1 7 M2 is uniformly continuous Proof Let 8 gt 0 Since f is continuous for every p 6 M1 36p gt 0 such that fB25p C B Since B5p 19peM1 is an open cover of M1 and M1 is compact there exists a nite subcover A B5P1p1 B5pnpn of Mi Let 6 Inin6p1 6pni We now check that for any p 6 M1 we obtain fB5p C B5fpi Since A covers M1 after reindexing we may assume that p E B5P1p1i Let y E B5p and we will prove that dfp7fy lt 6 By the triangle inequality dyp1 dy pdP7 P1 lt 55p1 5p16p1 26p1 which implies y E B25P1p1 Since fB25p1p1 C B fp1 then and are both contained in B As and lie in Bfp1 the triangle inequality yields dltfltpgtfltp1gtgt dltfltp1gtfltygtgt lt 7 a which implies fBap c Bums a In calculus one shows that if is a continuous positive function on a closed interval a b C R then one can de ne the area under the graph as the limit of the Riemann sums of the form 2211 fxiAxi where a 750 lt 751 lt 457171 lt yon I Am xi 7xi1 and as n 7gt 00 A35 7 0 The existence of such a limit follows easily from the fact that f ab 7gt R is uniformly continuous the compactness of a b and Theorem 568 So we may assume that the area under such a graph makes sense and we will use this result to prove the fundamental theorem of calculus Theorem 569 Fundamental Theorem of Calculus Suppose f a b 7gt R is apositiue con tinuous function Then 1 There exists a function F ab 7gt R such that V35 6 ab Fx limhho w Fx is called an antiderivative of 2 If F ab 7gt R is an antiderivative of then the area under the graph of can be calculated by 1 Area Fb 7 Fa We will need the following lemma in order to prove this theoremi Lemma 570 Let f ab 7gt R be a positive continuous function De ne the area function 1435 ab 7gt R Ax Then Ax is di erentiable and V35 6 a b has derivative Ax For the moment assume Lemma 5 70 holds and we will prove the fundamental theorem of calculus Proof of Theorem 569 Let Ax be the area function given in Lemma 570 This lemma implies the existence of an antiderivative for namely Ax itself This proves the rst statement in the theoremi Let F be an antiderivative function given in the rst statement of the fundamental theorem of calculus Then F 7 A Fx 7 Ax C is a constant function for some C since the 63 derivative F 7 Ax F x 7 A x 7 0 Hence7 Fx Ax C Calculating7 we obtain Fb 7 Fa AU 0 7 Aa 0 Ab 7 Aa But7 Aa 07 and so7 Fb 7 Fa AU ffxdx which proves Theorem 569 B Proof Proof of Lemma 570 By the de nition of derivative for any xed as 6 a7 17 we need to verify that the limit Ax limhno W exists and equals For the moment7 we will assume that x f b and that h gt 0 and suf ciently small so that x h E cub Assume now that x is xed Let Ah be the area of the strip SOL under the graph of f and over the interval 7535 h SOL ty l t E xx h and 0 g y g Note that Ah Ax h 7 Let mh be the minimum value of f restricted to 35 x h and Mh be the maximum value these maximum and minimum values exist by Corollary 555 Since the rectangle Rm with base 7535 h and height mh is contained in the strip SOL then mh h AreaRmh AOL Similarly one can de ne the rectangle BMW with base 75 x h and height and one obtains the inequalities mh h g Ah g Mh h Dividing by h one obtains mlthgt Maw Since f is continuous at x limhnom z limhno Mh Note that for any sequence of positive numbers hl Z hg Z Z 7 which are converging to 07 the intervals mhnMhnneN are nested with 7 7gt 0 as n 7gt 00 Since the values are squeezed between mh and M39Uz7 then the Nested lnterval Theorem implies A x limhno W limhno This completes the proof of Lemma 570 under the assumption that x f b and h gt 0 Note that if x b then h is negative and if h were negative instead of positive7 then Ax h 7 Ax 7Ah and so7 our arguments still apply to prove the lemma D Homework Problems 1 De ne the distance function 61 on R by 6175 y ly 7 Show that this distance function d makes R into a metric space by verifying that d satis es the three axioms of a distance function Hint Note that for real numbers 35352 then l2 7 ml l2 7y y 7 ml lZyyl S lziyldrly ml 2 De ne the taxi cab distance function 61 on R X R by 61351 yl 752 32 lac 7 751 lyg 7 yll This distance function 61 makes R X R into a metric space You do not need to prove the previous statement Draw a picture of the ball 3100 of radius 1 centered at the origin 0 0 3 De ne the Euclidean distance function 61 on R X R by 6196179391 9627 y2 962 i 9612 y2 y12 64 10 11 12 13 Show the set equality zo17lnln 711 71 1 71 1 This distance function 61 makes R X R into a metric space You do not need to prove the previous statement Draw a picture of the ball 3100 of radius 1 centered at the origin 0 0 De ne the distance function 61 on R X R by dx1 yl x2y2 max xg 7 751 lyg 7 This distance function 61 makes R X R into a metric space You do not need to prove the previous statement Draw a picture of the ball 310 0 of radius 1 centered at the origin 0 0 Suppose M d is a metric space 19 E M and xy E BTp Prove that dxy lt 2 This homework problem implies that diameter of a ball of radius r is at most 2 Hint Use the triangle inequality 725 771 0where 77771 t E R l 77 lt t lt This homework problem shows that the intersection of in nitely many open sets in R need not be open Give an example of a countable in nite collection F of closed intervals A in R such that UF UAef A is the open interval 01 This homework problem shows that the union of in nitely many closed sets in R need not be a closed set in R Show that if a lt b then the interval ab is a closed set in R Prove that if p is a limit point of a subset A in a metric space M then every ball BT 19 contains in nitely many different points of A Hint Suppose to the contrary that there is a ball BTp which intersects A in a nite number of points Then produce a smaller ball BTp such that Brp 7 A Q Next apply the de nition of limit point to show that p is not a limit point of A Show that the set A 171 l n E N is not closed in R Hint Apply Theorem 515 or apply the de nition of a closed set Determine the closure A in R of each of the following sets A Here a b c E R with a lt b lt c andabxERlaltxltb a Q 3 R C 071 01 a7 5 U 57 0 6 Q f N 123n Prove that Va 6 R limnH00 nzzv o7gl7lglltegt 0 Hint For a xed 8 gt 0 nd a number N such that for Recall that a nonempty subset A C R is an interval if for ab E A with a g b then a g t g b gt t E A Show that if A Aaae is a collection of intervals with a xed number a0 6 Ad for all a E I then the union UA is an interval 65 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Prove that between any two positive real numbers a lt b there exists a rational number Hint Suppose the decimal expansion of b 71611612 elk does not end all in zeros which can always be assumed why Consider the sequence of nite portions bk 71611612 elk of the decimal expansion for 17 Prove that between any two real numbers a lt b there exists an irrational number Hint Think in terms of size the interval a b is uncountable but Q is not Prove that in a metric space M d that for any r gt 0 and p E M the closed ball Tp q E M dpq g r is a closed set Hint Prove that the complement of P419 is open by using the triangle inequality Prove that if A C B then A C F Hint You can prove this containment directly by using the de nition of closure or indirectly by using Theorem 519 Prove Proposition 523 a Is 01 an open subset of 02 with the subset topology Prove your answer b Is 01 a closed subset of 711 with the subset topology Prove your answer c ls 01 a closed subset of 02 with the subset topology Prove your answer Hint Parts a and b of this problem are testing your understanding of subspace topology Prove that if 0 is an open set in R then 0 is a countable union of disjoint open intervals in R Hint By homework problem 14 each point p E 0 lies in a largest open interval p C O which is the union of all open intervals in O which contain 19 Using the collection of intervals Ippeo show that O is a union of disjoint open intervals Then prove that there is a countable collection of such disjoint intervals where you pick for each interval a xed rational number p E Q in the interval and so one has a countable indexing set see homework problem 14 Is the collection of open intervals 71 71 1 n E Z an open cover of R Why Verify that the set of intervals 771 n n E N is an open cover of R with no nite subcover Prove that the least upper bound of a nonempty bounded set A C R is unique Suppose L is the least upper bound of a set A C R and L A Show L is a limit point of A Suppose f X gt Y is continuous and A C X is a subspace Let F A gt Y be the restriction Fx fxVx E A Prove F is a continuous function on A Let A01C R a Prove that if f A gt R is continuous then f has a maximum value Hint Note that A is a compact subset of R b Prove that if F R gt R is continuous then the restriction of F to A has a maximum value Hint Apply the previous homework problem and part a of this problem Prove that a function f X gt Y is continuous if for all closed sets A C Y then f 1A is closed in X Hint See homework problem 22c in Section 3 66 28 29 30 31 32 33 34 35 36 37 38 Suppose f X gt Y is a continuous function and the image is a subset of a subspace W C Y Let fW X gt W be de ned by for all x E X Prove that y is also a continuous function Hint This problem is just testing your understanding of the subspace topology on the subspace W and your understanding of the de nition of a continuous function Challenge problems Suppose M d is a metric space and p E M De ne D M gt R by Dq dpq which is the distance function to p Prove that D is a continuous function Hint Show that for q E M that f is continuous at q Suppose qnneN is a sequence of points converging to q By the triangle inequality dpqn Dqn Dq dqqn and Dq Dqn dqnq Hence Mg 7 ew S D S 139 dqqn Use the above formula to prove limnn00 Dqn Dq Prove Proposition 559 Prove that a convergent sequence pnneN of points in a metric space M is Cauchy Prove that the function x2 is not uniformly continuous on 0eo Prove that the natural log ln 1 00 gt R is uniformly continuous Suppose M1d1 and M2 612 are metric spaces Given p x1y1q x2 yg 6 M1 gtlt M2 and let dp q maxd1x1 x2 dy1 a Prove M1 gtlt M2 61 is a metric space Hint See homework problem 4 b Prove that if M1d1 and M2d2 are complete metric spaces then M1 gtlt M2d is also complete Suppose A C B C X where X is a topological space Consider B to be a topological subspace of X Show that the subspace topology of A induced from X is the same as the subspace topology of A induced from B Hint You will need to use the de nition of subspace topology to prove this property Suppose A is a connected subspace of a topological space X and A C B C X Consider B to be a topological subspace of X and show A is a connected subspace of B Hint Apply the previous homework problem Suppose A C X is connected and B and C are open sets in X such that A B C Q and A C B U C Prove A C B or A C C Hint You will need to use the de nition of subspace topology to prove this property For each point p E X let the set Cp be the union of all connected subsets A of X which contain 19 Cp is called the connected component of X containing 19 67 39 6 Name 1 2 3 4 10 11 12 13 14 15 16 17 a Suppose A Cathie is a collection of connected subsets of X which all contain a particular point p Prove the union U A is connected Hint Use homework problems 36 and 37 b Prove Cp is a connected set Hint Apply part a of this homework problem c Prove that the set of connected components of X is a partition of X Suppose A C X is a connected subspace of the topological space X a Prove that the closure A is also a connected subspace b Conclude that the connected components of X are closed sets Four typical midterms some quizzes and a typical nal exam Midterm 1 Math 3001 A set A is countable if A set A is uncountable if A function f A gt B is 11 if A function f A gt B is onto if A logical statement 19 is a contradiction if Write down a logical statement with letters that is a tautology A U B A O B lAl lBl means lAl lBl means A relation R on a set S is an equivalence relation if Suppose R is an equivalence relation on S and a E 5 De ne the equivalence class a Write down the contrapositive of If it is cloudy7 then the sun does not shine77 If A is a set7 then the power set PA is 7317 2 A collection A of subsets of a set A is a partition of A if Express the real number 15 in base 10 as a real number in base 4 68 18 If x 1202 is a decimal number in base 4 then express it as a decimal number in base 10 19 State the WellOrdering Principle 20 State the Principle of Mathematical Induction PMI 21 State Cantorls Theorem 22 State the fundamental theorem of equivalence relations 23 Write down a function f R gt R that is 11 but not onto 24 Write down a function f R gt R that is 11 and onto 25 Which of the following sets are countable N Q Z R N X N PN N X R PZ PR 26 Write down the truth table for p gt p A q 27 Prove that if A a1a2anB 51bgbn and C 0102cn are three in nite countable sets then A U B U C is countable 28 Prove by the principle of mathematical induction that 221 k 29 Prove that iff A gt B and g B gt C are 11 functions then 9 o f A gt C is 11 30 Prove that if f A gt B and g B gt C are onto functions then 9 o f A gt C is onto 31 Prove 3 of the following 5 problems Two extra credit points for doing a fourth one correctly a Prove that Q is a countable set by explaining how to make Q into an in nite list List the rst 10 elements in your listing of QT b Prove that the open interval I 01 C R is uncountable c State and prove the Fundamental Theorem of Equivalence Relations d Prove that if f A gt B and g B gt C are functions with g o f A gt C onto then 9 B gt C is onto e State and prove Cantor s Theorem Name Midterm 2 Math 3001 1 A group C 96 is a set C together with a binary operation satisfying 2 If C is a group then prove the identity element 5 is unique 3 If C is a group then prove the left cancelation law ax ay gt x 4 If C is a group then prove that the inverse of a C C is unique 5 A subset H C C is a subgroup of the group C if 6 A subgroup H C C is normal if 69 7 In the group Z12 What is the order of the element 8 8 List all of the generators of Z3 9 If H1 H2 are two subgroups of a group G then prove H1 H2 is a subgroup of Cl 10 De ne the center of a group G CG 11 If G is a group then prove that the center CG is a subgroup 12 For the function 21 R gt R What is f 1744 What is f 1loo 13 For the function x2 71 4 gt R What is lmf 14 If G1 96 and G2 0 are groups then f G1 gt G2 is a group homomorphism if 15 Suppose f G1 gt G2 is a group homomorphism and 51 6 G1 and 52 6 G2 are the respective identity elementsi Let a E Gli Then prove a 51 52 b fa 1fa 1 16 If f G1 gt G2 is a group homomorphism then the kernel of f is Kerf 17 State the First lsomorphism Theoremi 18 State and prove Lagrangels Theoremi This problem counts 10 points 19 Prove 4 of the following 7 theorems Where f G1 gt G2 is a group homomorphismi These proofs count 5 points each One point extra credit for each additional correct proofi Theorem 1 Kerf is a subgroup of Gli Theorem 2 lmf y 6 G2 l 335 6 G1 such that y is a subgroup of G2 Theorem 3 If Kerf 51 then f G1 gt G2 is 11 Theorem 4 If h G2 gt G3 is a group homomorphism then h o f G1 gt G3 is a group homomorphismi Theorem 5 If H C G2 is a subgroup of G2 then f 1H x 6 G1 l E H is a subgroup of Gli Theorem 6 If G is a nite group and a E G then a a l n E N is a subgroup of G Theorem 7 The center CG of a group G is a subgroup Name Midterm 3 Math 3001 1 Let R R2 gt R2 be the re ection Express R as a 2 X 2 matrix 2 Let R R3 gt R3 be rotation by 120 degrees counter clockwise around the vector 111 Write down the matrix for the linear transformation Br 70 10 11 12 13 14 15 16 Calculate the product of the following two matrices 1 1 2 1 1 2 3 0 4 3 0 4 1 0 2 0 1 0 1n what is the multiplicative inverse of 2 2 1 1n the eld Z5 what is the multiplicative inverse of 3 1 1n the multiplicative group Z5 7 07 what is the order of 3 Is 2 an algebraic number Explain your answer i A eld F is algebraically closed if 1 In what follows7 V is a vector space over a eld Fl a A eld F is a set with two binary operations and which satisfy the following prop erties b A subset S C V spans V if c A subset S C V is a linearly independent set of vectors if d A vector space V over F has nite dimension n if e Suppose F is a sub eld of a eld F i Then oz 6 F is algebraic with respect to F if Prove that if S 171 v2 and v E V can be expressed as v 2211 vn is a linearly independent set of vectors in a vector space aim 2211 bivi then ai 172 for i E 12ni Suppose a eld F2 is a vector space of dimension 5 over a sub eld F1 C F21 Prove that every oz 6 F2 is the root of some nonzero polynomial 1975 with coef cients in F1 and of degree at most 5 Prove that if F3 is a eld which is a vector space of nite dimension 71 over a sub eld F2 and F2 is a vector space of nite dimension m over a sub eld F1 C F27 then F3 has nite dimension mn over the sub eld F31 Hint Find a basis for F3 over F1 with mn elementsi De ne and prove it is a sub eld of R1 You do not need to check the associative or distributive laws7 since they hold in R1 Prove that if F is a sub eld of R with dimension 13 over Q then Q and F are the only sub elds of Fl You can use any theorems in this section to prove this result Show that the set of real algebraic numbers AR A R is not an algebraically closed eldi Suppose oz 6 C is a root of a polynomial 1935 22101 aixi of smallest positive degree n 1 Prove that the set S 1ozoz2 Ozn C C is a linearly independent set of numbers over or 71 Name 1 10 11 12 13 14 15 16 17 18 Midterm 4 Math 3001 A metric space M d is a pair where M is a set with a distance function 61 M X M gt 0 00 satisfying If M d is a metric space 19 E M and r gt 0 then BTp A subset O C M in a metric space M d is open if A topological space is a set X together with a collection TX of subsets called open sets satisfying A point p in a topological space X is a limit point of a subset A C X if A subset A of a topological space X is closed if If A is a subset of a topological space X then de ne the closure of A Z A topological space X is disconnected if Is the real number line R connected State the theorem that implies your answer A topological space X is compact if Is the real number line R compact Prove your answer by producing an open cover of R that does not have a nite subcover A function f M1 gt M2 between metric spaces M1d1 and M2d2 is continuous at a point p 6 M1 if A function f X gt Y between topological spaces X and Y is continuous if State the Least Upper Bound Property for a subset A C R which is bounded from above A collection C Ca l Oz 6 I of sets satis ed the nite intersection property if A metric space M d is complete if State and prove the Fundamental Theory of Calculus for a continuous positive function f ab HR Prove 5 of the following 8 theorems These proofs count 5 points each One point extra credit for each additional correct proof over 5 6 Suppose M d is a metric space Then the ball BTp centered at p of radius r is an open set in M If A Aiie1n A1A2 An is a nite collection of open sets in a metric space Md then HA A1 Ag An is an open set in M lf Aaae is a collection of open sets in a metric space M d then the union Uael Ad is an open set in M b C 72 Name 1 2 3 4 5 599071533 10 11 12 13 14 15 16 17 18 19 If A and B are closed sets of a topological space then A U B is a closed set 01 6 Suppose f X gt Y and g Y gt Z are continuous functions between topological spaces Then 9 o f X gt Z is continuous Suppose f X gt Y is a continuous onto function between topological spaces If X is connected then Y is connected f Suppose f X gt Y is a continuous onto function between topological spaces If X is compact then Y is compact h A subset A C X is closed if and only if A contains all of its limit points g Math 3001 Final Exam A set A is countable if A function f A gt B is 11 if A function f A gt B is onto if lAl lBl means Suppose R is an equivalence relation on S and a E 5 De ne the equivalence class a Write down the contrapositive of 77If it is cold then it is not hot77 A collection A of subsets of A is a partition of A if Express the base 2 number 11011 as a base 10 number State the Well Ordering Principle State Cantorls Theorem State the fundamental theorem of equivalence relations Which of the following sets are uncountable N Q Z R N X N POW PZ BUR Write down the truth table for p A q gt p A group G 96 is a set C together with a binary operation 96 which satis es A eld is a set F together with binary operations and which satisfy A subgroup H C G is normal if In the group Z12 what is the order of 8 List all of the generators for Z3 If G1 96 and G2 0 are groups then f G1 gt G2 is a group homomorphism if 73 20 21 22 23 24 25 26 27 28 29 30 31 32 33 lff A gt B and W C B then f 1W What is the image of the function 21 R gt R For the function 21 R gt R what is f 1744 State the normal subgroup theorem Suppose M d is a metric space De ne BTp A subset O C M in a metric space is open if A topological space is a set X together with a collection of subsets TX called open sets satisfying A point p in a topological space X is a limit point of a subset A C X if If A is a subset of a topological space X then de ne the closure of A A A topological space X is disconnected if A collection of sets A Aaae satis es the nite intersection property FIP if Suppose X Y are topological spaces A function f X gt Y is continuous if Prove 8 of the following theorems These proofs count 5 points each One point extra credit for each additional correct proof over 8 a b C d e f lff A gtB andg B gt C are 11 functions thengof AgtC is 11 If f A gt B and g B gt C are onto functions then 9 o f A gt C is onto Prove Q is a countable set and list the rst 10 elements Prove 220 2k 2n1 7 1 by mathematical induction If H1 and H2 are subgroups of a group C then H1 H2 is a subgroup of C Suppose f C1 gt C2 is a group homomorphism and 51 6 C1 and 52 6 C2 are the respective identity elements Prove fel 52 If f C1 gt C2 and 9 C2 gt C3 are group homomorphisms then 9 o f C1 gt C3 is a group homomorphism Suppose F is a sub eld of R of dimension 7 over Prove that Q and F are the only sub elds of F You can use any of the theorems in the linear algebra section of the book to prove this result g h If X Y and Z are topological spaces and f X gt Y and g Y gt Z are continuous then 9 o f X gt Z is continuous i If M d is a metric space and A and B are open sets then A B is an open set k R is noncompact Prove 6 of the following 10 theorems These proofs count 10 points each Two points extra credit for each additional correct proof 74 a R is an uncountable seti b State and prove the fundamental theorem of equivalence relationsi c State and prove Cantor s Theoremi d If f G1 gt G2 is a group homomorphism then Kerf is a normal subgroup of Gli e If f G1 gt G2 is a group homomorphism and Kerf 51 then f is lli f State and prove Lagrange7s Theoremi g What is Prove is a sub eld of R h An open ball BT p in a metric space M is an open set i Suppose f X gt Y is a continuous onto function between topological spacesi If X is connected then Y is connected A subset A C X is closed if and only if A contains all its limit pointsi Quizzes The following quizzes count 1 point per problemi However 1 point is deducted for each wrong answer with negative scores counting as zero You can take a quiz a second time but with 2 points taken off Also 2 points will be deducted for each week late that a quiz is taken H F90 Quiz 1 i N AUR f AgtB is 11 if f A gt B is onto if i A relation R on a set S is an equivalence relation if a b C i A set A is countable if Quiz 2 i Let A 12 Then A X A i P123 Prove that iff A gt B and g B gt C are 11 functions then gof A gt C is a 11 function 75 F90 F90 Prove that if f A gt B and g B gt C are onto functions7 then 9 o f A gt C is an onto function Quiz 3 What does lAl lBl mean Where A and B are sets Write down the truth table for p gt p gt g If R is an equivalence relation on a set S and a E S then de ne the equivalence class a Let A 1 2 3 Give three different examples A1 A2 A3 of partitions of A State the fundamental theorem of equivalence relations State Cantorls Theorem Quiz 4 A group G 96 is a set C together With a binary operation satisfying a b C A subset H C G is a subgroup if a b 0 Suppose H1 and H2 are subgroups of a group G Prove H1 H2 is a subgroup of G What is the order of 8 in Z12 0 1 11 Show your work The center of a group G is CG Quiz 5 Suppose G1 96 and G2 0 are groups A function f G1 gt G2 is a group homomorphism if If f G1 gt G2 is a group homomorphism7 then Kerf If H C G is a subgroup and a 6 G7 then CLH State Lagrange7s Theorem Explain Why 3 is a generator for Z4 but 2 is not a generator Quiz 6 76 Multiply these matrices lt1 0 lt6 1 Show your work 2 3 1 3 A eld F is a set With two binary operations and Which satisfy the following properties Let V be a vector space over a eld F A subset S C V spans V if A subset S C V is a linearly independent set of vectors if A vector space V over F has nite dimension n if Suppose F is a sub eld of a eld F Then a E F is algebraic With respect to F if Quiz 7 A metric space M d is a pair Where M is a set With a distance function 61 M X M gt 0 00 satisfying a b C Suppose Md is a metric space7 p E M and r gt 0 De ne BT p A subset O C M is an open set if A topological space is a set X together With a collection of subsets TX called open sets satisfying a b 0 Quiz 8 A subset A of a topological space X is closed if If A is a subset of a topological space7 then X A topological space X is disconnected if A topological space X is compact if A function f X gt Y between topological spaces is continuous if 77 10 11 12 Proposed schedule for the small group meetings for Spring semester 2004 Answer questions and go over the basic logical symbols in De nition 2 38 and their truth tables Talk about 11 and onto functions and go over the proofs of Theorem 26 and Theo rem 27 Given time go over equivalence relations Answer questions and go over some of the results about countable and uncountable sets Make sure the students understand how to calculate the power set Go over bases other than 10 Start going over homework problems Go over homework problems mathematical induction and the wellordering principle Answer questions and go over old Midterm l exami Last group session before Midterm ll Answer questions about groups and de ne subgroupi Prove Proposition 32 and the proofs of some of the subgroup theorems like H1 H2 is a subgroup Go over the group Z7 Go over more subgroup theorems and Theorem 322 Go over cosets and start discussing about left cosets and the proof of Lagrangels Theoremi Discuss normal subgroups Go over elementary linear algebra and elementary eld theory Answer questions on the homework and go over old Midterm 2 Go over the proof of Theo rem 346 if time permits Last group meeting before Midterm 2i Go over real vector spaces linear transformations matrix multiplication and elementary results about elds Go over vector spaces over elds F and elementary eld theory Go over the de nitions of metric spaces open sets topological spaces and the proofs of Theorems 54 and 56 Talk about limits and convergence of a sequence of points in metric spaces Go over theorems about the limit points of subsets and the de nition of closed sets Discuss the subspace topologyi Go over the properties of connected compact and Flplli Answer questions on the homework Go over continuous functions in metric and in topological spaces Answer questions and go over some of the main theorems Go over the homework and questions on the old Midterm 4 exami Be sure to go over the proof of the Fundamental Theorem of Calculus as it will be a question on the upcoming Midtermi Last group meeting before Midterm 4 78
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'