1.3.EXERCISES 15 (a)Prove f(A1UA2)=f(A1)Uf(A2). (b)Prove f(A1nA2)C f(A1)nf(A2).Give an example in which equality fails (c)Prove f-1(B1UB2)=f-1(B1)Uf-1(B2),where f-(B)={x∈X:f(x)∈B}. (d)Prove f-1(Bi0B2)=f-1(B1)nf-1(B2) (e)Prove f(Y\B1)=X\f(B1). 25.Determine whether or not the following relations are equivalence relations on the given set.If the relation is an equivalence relation,describe the partition given by it.If the relation is not an equivalence relation,state why it fails to be one. (a)x~y in R if x≥y (c)x~y in R if x-y≤4 (b)m~n in Z if mn >0 (d)m~n in Z if m=n (mod 6) 26.Define a relation on R2 by stating that (a,b)~(c,d)if and only if a2+62<c2+d2. Show that ~is reflexive and transitive but not symmetric. 27.Show that an m x n matrix gives rise to a well-defined map from Rn to Rm. 28.Find the error in the following argument by providing a counterexample."The reflexive property is redundant in the axioms for an equivalence relation.If x ~y,then y~x by the symmetric property.Using the transitive property,we can deduce that x~z." 29.Projective Real Line.Define a relation on R2\{(0,0)}by letting (z1,1)~(x2,2) if there exists a nonzero real number A such that (1,41)=(Ax2,Ay2).Prove that defines an equivalence relation on R2(0,0).What are the corresponding equivalence classes?This equivalence relation defines the projective line,denoted by P(R),which is very important in geometry. References and Suggested Readings [1]Artin,M.Abstract Algebra.2nd ed.Pearson,Upper Saddle River,NJ,2011. [2]Childs,L.A Concrete Introduction to Higher Algebra.2nd ed.Springer-Verlag,New York,1995. [3]Dummit,D.and Foote,R.Abstract Algebra.3rd ed.Wiley,New York,2003 [4]Ehrlich,G.Fundamental Concepts of Algebra.PWS-KENT,Boston,1991. [5]Fraleigh,J.B.A First Course in Abstract Algebra.7th ed.Pearson,Upper Saddle River,NJ,2003. [6]Gallian,J.A.Contemporary Abstract Algebra.7th ed.Brooks/Cole,Belmont,CA, 2009. [7]Halmos,P.Naive Set Theory.Springer,New York,1991.One of the best references for set theory. [8]Herstein,I.N.Abstract Algebra.3rd ed.Wiley,New York,1996. [9) Hungerford,T.W.Algebra.Springer,New York,1974.One of the standard graduate algebra texts
1.3. EXERCISES 15 (a) Prove f(A1 ∪ A2) = f(A1) ∪ f(A2). (b) Prove f(A1 ∩ A2) ⊂ f(A1) ∩ f(A2). Give an example in which equality fails. (c) Prove f −1 (B1 ∪ B2) = f −1 (B1) ∪ f −1 (B2), where f −1 (B) = {x ∈ X : f(x) ∈ B}. (d) Prove f −1 (B1 ∩ B2) = f −1 (B1) ∩ f −1 (B2). (e) Prove f −1 (Y \ B1) = X \ f −1 (B1). 25. Determine whether or not the following relations are equivalence relations on the given set. If the relation is an equivalence relation, describe the partition given by it. If the relation is not an equivalence relation, state why it fails to be one. (a) x ∼ y in R if x ≥ y (b) m ∼ n in Z if mn > 0 (c) x ∼ y in R if |x − y| ≤ 4 (d) m ∼ n in Z if m ≡ n (mod 6) 26. Define a relation ∼ on R 2 by stating that (a, b) ∼ (c, d) if and only if a 2+b 2 ≤ c 2+d 2 . Show that ∼ is reflexive and transitive but not symmetric. 27. Show that an m × n matrix gives rise to a well-defined map from R n to R m. 28. Find the error in the following argument by providing a counterexample. “The reflexive property is redundant in the axioms for an equivalence relation. If x ∼ y, then y ∼ x by the symmetric property. Using the transitive property, we can deduce that x ∼ x.” 29. Projective Real Line. Define a relation on R 2 \{(0, 0)} by letting (x1, y1) ∼ (x2, y2) if there exists a nonzero real number λ such that (x1, y1) = (λx2, λy2). Prove that ∼ defines an equivalence relation on R 2 \(0, 0). What are the corresponding equivalence classes? This equivalence relation defines the projective line, denoted by P(R), which is very important in geometry. References and Suggested Readings [1] Artin, M. Abstract Algebra. 2nd ed. Pearson, Upper Saddle River, NJ, 2011. [2] Childs, L. A Concrete Introduction to Higher Algebra. 2nd ed. Springer-Verlag, New York, 1995. [3] Dummit, D. and Foote, R. Abstract Algebra. 3rd ed. Wiley, New York, 2003. [4] Ehrlich, G. Fundamental Concepts of Algebra. PWS-KENT, Boston, 1991. [5] Fraleigh, J. B. A First Course in Abstract Algebra. 7th ed. Pearson, Upper Saddle River, NJ, 2003. [6] Gallian, J. A. Contemporary Abstract Algebra. 7th ed. Brooks/Cole, Belmont, CA, 2009. [7] Halmos, P. Naive Set Theory. Springer, New York, 1991. One of the best references for set theory. [8] Herstein, I. N. Abstract Algebra. 3rd ed. Wiley, New York, 1996. [9] Hungerford, T. W. Algebra. Springer, New York, 1974. One of the standard graduate algebra texts
16 CHAPTER 1.PRELIMINARIES [10]Lang,S.Algebra.3rd ed.Springer,New York,2002.Another standard graduate text. [11]Lidl,R.and Pilz,G.Applied Abstract Algebra.2nd ed.Springer,New York,1998. [12]Mackiw,G.Applications of Abstract Algebra.Wiley,New York,1985. [13]Nickelson,W.K.Introduction to Abstract Algebra.3rd ed.Wiley,New York,2006. [14]Solow,D.How to Read and Do Proofs.5th ed.Wiley,New York,2009. [15]van der Waerden,B.L.A History of Algebra.Springer-Verlag,New York,1985.An account of the historical development of algebra. 1.4 Sage Sage is a powerful system for studying and exploring many different areas of mathematics. In this textbook,you will study a variety of algebraic structures,such as groups,rings and fields.Sage does an excellent job of implementing many features of these objects as we will see in the chapters ahead.But here and now,in this initial chapter,we will concentrate on a few general ways of getting the most out of working with Sage. You may use Sage several different ways.It may be used as a command-line program when installed on your own computer.Or it might be a web application such as the SageMathCloud.Our writing will assume that you are reading this as a worksheet within the Sage Notebook(a web browser interface),or this is a section of the entire book presented as web pages,and you are employing the Sage Cell Server via those pages.After the first few chapters the explanations should work equally well for whatever vehicle you use to execute Sage commands. Executing Sage Commands Most of your interaction will be by typing commands into a compute cell.If you are reading this in the Sage Notebook or as a webpage version of the book,then you will see a compute cell just below this paragraph.Click once inside the compute cell and if you are in the Sage Notebook,you will get a more distinctive border around it,a blinking cursor inside,plus a cute little "evaluate"link below.At the cursor,type 2+2 and then click on the evaluate link. Did a 4 appear below the cell?If so,you have successfully sent a command off for Sage to evaluate and you have received back the (correct)answer. Here is another compute cell.Try evaluating the command factorial(300)here.Hmmmmm. That is quite a big integer!If you see slashes at the end of each line,this means the result is continued onto the next line,since there are 615 total digits in the result. To make new compute cells in the Sage Notebook (only),hover your mouse just above another compute cell,or just below some output from a compute cell.When you see a skinny blue bar across the width of your worksheet,click and you will open up a new compute cell,ready for input.Note that your worksheet will remember any calculations you make,in the order you make them,no matter where you put the cells,so it is best to stay organized and add new cells at the bottom. Try placing your cursor just below the monstrous value of 300!that you have.Click on the blue bar and try another factorial computation in the new compute cell. Each compute cell will show output due to only the very last command in the cell.Try to predict the following output before evaluating the cell. a=10 b=6 b=b-10
16 CHAPTER 1. PRELIMINARIES [10] Lang, S. Algebra. 3rd ed. Springer, New York, 2002. Another standard graduate text. [11] Lidl, R. and Pilz, G. Applied Abstract Algebra. 2nd ed. Springer, New York, 1998. [12] Mackiw, G. Applications of Abstract Algebra. Wiley, New York, 1985. [13] Nickelson, W. K. Introduction to Abstract Algebra. 3rd ed. Wiley, New York, 2006. [14] Solow, D. How to Read and Do Proofs. 5th ed. Wiley, New York, 2009. [15] van der Waerden, B. L. A History of Algebra. Springer-Verlag, New York, 1985. An account of the historical development of algebra. 1.4 Sage Sage is a powerful system for studying and exploring many different areas of mathematics. In this textbook, you will study a variety of algebraic structures, such as groups, rings and fields. Sage does an excellent job of implementing many features of these objects as we will see in the chapters ahead. But here and now, in this initial chapter, we will concentrate on a few general ways of getting the most out of working with Sage. You may use Sage several different ways. It may be used as a command-line program when installed on your own computer. Or it might be a web application such as the SageMathCloud. Our writing will assume that you are reading this as a worksheet within the Sage Notebook (a web browser interface), or this is a section of the entire book presented as web pages, and you are employing the Sage Cell Server via those pages. After the first few chapters the explanations should work equally well for whatever vehicle you use to execute Sage commands. Executing Sage Commands Most of your interaction will be by typing commands into a compute cell. If you are reading this in the Sage Notebook or as a webpage version of the book, then you will see a compute cell just below this paragraph. Click once inside the compute cell and if you are in the Sage Notebook, you will get a more distinctive border around it, a blinking cursor inside, plus a cute little “evaluate” link below.At the cursor, type 2+2 and then click on the evaluate link. Did a 4 appear below the cell? If so, you have successfully sent a command off for Sage to evaluate and you have received back the (correct) answer. Here is another compute cell. Try evaluating the command factorial(300) here.Hmmmmm. That is quite a big integer! If you see slashes at the end of each line, this means the result is continued onto the next line, since there are 615 total digits in the result. To make new compute cells in the Sage Notebook (only), hover your mouse just above another compute cell, or just below some output from a compute cell. When you see a skinny blue bar across the width of your worksheet, click and you will open up a new compute cell, ready for input. Note that your worksheet will remember any calculations you make, in the order you make them, no matter where you put the cells, so it is best to stay organized and add new cells at the bottom. Try placing your cursor just below the monstrous value of 300! that you have. Click on the blue bar and try another factorial computation in the new compute cell. Each compute cell will show output due to only the very last command in the cell. Try to predict the following output before evaluating the cell. a = 10 b = 6 b = b - 10
1.4.SAGE 17 a=a+20 a 30 The following compute cell will not print anything since the one command does not create output.But it will have an effect,as you can see when you execute the subsequent cell. Notice how this uses the value of b from above.Execute this compute cell once.Exactly once.Even if it appears to do nothing.If you execute the cell twice,your credit card may be charged twice. b=b+50 Now execute this cell,which will produce some output. b+20 66 So b came into existence as 6.We subtracted 10 immediately afterward.Then a subsequent cell added 50.This assumes you executed this cell eractly once!In the last cell we create b+20(but do not save it)and it is this value(66)that is output,while b is still 46. You can combine several commands on one line with a semi-colon.This is a great way to get multiple outputs from a compute cell.The syntax for building a matrix should be somewhat obvious when you see the output,but if not,it is not particularly important to understand now. A=matrix([[3,1],[5,2]]);A [31] [52] print(A);print();print(A.inverse()) [31] [52] <BLANKLINE> [2-1] [-53] Immediate Help Some commands in Sage are "functions,"an example is factorial()above.Other com- mands are "methods"of an object and are like characteristics of objects,an example is inverse()as a method of a matrix.Once you know how to create an object (such as a matrix),then it is easy to see all the available methods.Write the name of the object,place a period("dot")and hit the TAB key.If you have A defined from above,then the compute cell below is ready to go,click into it and then hit TAB (not "evaluate"!).You should get a long list of possible methods. A To get some help on how to use a method with an object,write its name after a dot(with no parentheses)and then use a question-mark and hit TAB.(Hit the escape key "ESC"to remove the list,or click on the text for a method.) A.inverse?
1.4. SAGE 17 a = a + 20 a 30 The following compute cell will not print anything since the one command does not create output. But it will have an effect, as you can see when you execute the subsequent cell. Notice how this uses the value of b from above. Execute this compute cell once. Exactly once. Even if it appears to do nothing. If you execute the cell twice, your credit card may be charged twice. b = b + 50 Now execute this cell, which will produce some output. b + 20 66 So b came into existence as 6. We subtracted 10 immediately afterward. Then a subsequent cell added 50. This assumes you executed this cell exactly once! In the last cell we create b+20 (but do not save it) and it is this value (66) that is output, while b is still 46. You can combine several commands on one line with a semi-colon. This is a great way to get multiple outputs from a compute cell. The syntax for building a matrix should be somewhat obvious when you see the output, but if not, it is not particularly important to understand now. A = matrix ([[3 , 1] , [5 ,2]]) ; A [3 1] [5 2] print (A ) ; print () ; print (A . inverse () ) [3 1] [5 2] < BLANKLINE > [ 2 -1] [ -5 3] Immediate Help Some commands in Sage are “functions,” an example is factorial() above. Other commands are “methods” of an object and are like characteristics of objects, an example is .inverse() as a method of a matrix. Once you know how to create an object (such as a matrix), then it is easy to see all the available methods. Write the name of the object, place a period (“dot”) and hit the TAB key. If you have A defined from above, then the compute cell below is ready to go, click into it and then hit TAB (not “evaluate”!). You should get a long list of possible methods. A . To get some help on how to use a method with an object, write its name after a dot (with no parentheses) and then use a question-mark and hit TAB. (Hit the escape key “ESC” to remove the list, or click on the text for a method.) A . inverse ?
18 CHAPTER 1.PRELIMINARIES With one more question-mark and a TAB you can see the actual computer instructions that were programmed into Sage to make the method work,once you scoll down past the documentation delimited by the triple quotes("""): A.inverse?? It is worthwhile to see what Sage does when there is an error.You will probably see a lot of these at first,and initially they will be a bit intimidating.But with time,you will learn how to use them effectively and you will also become more proficient with Sage and see them less often.Execute the compute cell below,it asks for the inverse of a matrix that has no inverse.Then reread the commentary. B=matrix([[2,20],[5,50]) B.inverse() Traceback (most recent call last): ZeroDivisionError:Matrix is singular Click just to the left of the error message to expand it fully (another click hides it totally, and a third click brings back the abbreviated form).Read the bottom of an error message first,it is your best explanation.Here a ZeroDivisionError is not 100%accurate,but is close.The matrix is not invertible,not dissimilar to how we cannot divide scalars by zero. The remainder of the message begins at the top showing were the error first happened in your code and then the various places where intermediate functions were called,until the actual piece of Sage where the problem occurred.Sometimes this information will give you some clues,sometimes it is totally undecipherable.So do not let it scare you if it seems mysterious,but do remember to always read the last line first,then go back and read the first few lines for something that looks like your code. Annotating Your Work It is easy to comment on your work when you use the Sage Notebook.(The following only applies if you are reading this within a Sage Notebook.If you are not,then perhaps you can go open up a worksheet in the Sage Notebook and experiment there.)You can open up a small word-processor by hovering your mouse until you get a skinny blue bar again,but now when you click,also hold the SHIFT key at the same time.Experiment with fonts, colors,bullet lists,etc and then click the "Save changes"button to exit.Double-click on your text if you need to go back and edit it later. Open the word-processor again to create a new bit of text (maybe next to the empty compute cell just below).Type all of the following eractly, Pythagorean Theorem:$c2=a2+b^2$ and save your changes.The symbols between the dollar signs are written according to the mathematical typesetting language known as TEX-cruise the internet to learn more about this very popular tool.(Well,it is extremely popular among mathematicians and physical scientists.】 Lists Much of our interaction with sets will be through Sage lists.These are not really sets-they allow duplicates,and order matters.But they are so close to sets,and so easy and powerful to use that we will use them regularly.We will use a fun made-up list for practice,the
18 CHAPTER 1. PRELIMINARIES With one more question-mark and a TAB you can see the actual computer instructions that were programmed into Sage to make the method work, once you scoll down past the documentation delimited by the triple quotes ("""): A . inverse ?? It is worthwhile to see what Sage does when there is an error. You will probably see a lot of these at first, and initially they will be a bit intimidating. But with time, you will learn how to use them effectively and you will also become more proficient with Sage and see them less often. Execute the compute cell below, it asks for the inverse of a matrix that has no inverse. Then reread the commentary. B = matrix ([[2 , 20] , [5 , 50]]) B . inverse () Traceback ( most recent call last ) : ... ZeroDivisionError : Matrix is singular Click just to the left of the error message to expand it fully (another click hides it totally, and a third click brings back the abbreviated form). Read the bottom of an error message first, it is your best explanation. Here a ZeroDivisionError is not 100% accurate, but is close. The matrix is not invertible, not dissimilar to how we cannot divide scalars by zero. The remainder of the message begins at the top showing were the error first happened in your code and then the various places where intermediate functions were called, until the actual piece of Sage where the problem occurred. Sometimes this information will give you some clues, sometimes it is totally undecipherable. So do not let it scare you if it seems mysterious, but do remember to always read the last line first, then go back and read the first few lines for something that looks like your code. Annotating Your Work It is easy to comment on your work when you use the Sage Notebook. (The following only applies if you are reading this within a Sage Notebook. If you are not, then perhaps you can go open up a worksheet in the Sage Notebook and experiment there.) You can open up a small word-processor by hovering your mouse until you get a skinny blue bar again, but now when you click, also hold the SHIFT key at the same time. Experiment with fonts, colors, bullet lists, etc and then click the “Save changes” button to exit. Double-click on your text if you need to go back and edit it later. Open the word-processor again to create a new bit of text (maybe next to the empty compute cell just below). Type all of the following exactly, Pythagorean Theorem: $c^2=a^2+b^2$ and save your changes. The symbols between the dollar signs are written according to the mathematical typesetting language known as TEX — cruise the internet to learn more about this very popular tool. (Well, it is extremely popular among mathematicians and physical scientists.) Lists Much of our interaction with sets will be through Sage lists. These are not really sets — they allow duplicates, and order matters. But they are so close to sets, and so easy and powerful to use that we will use them regularly. We will use a fun made-up list for practice, the
1.4.SAGE 19 quote marks mean the items are just text,with no special mathematical meaning.Execute these compute cells as we work through them. zoo =[snake','parrot','elephant','baboon','beetle'] Z00 ['snake','parrot','elephant','baboon','beetle'] So the square brackets define the boundaries of our list,commas separate items,and we can give the list a name.To work with just one element of the list,we use the name and a pair of brackets with an index.Notice that lists have indices that begin counting at zero. This will seem odd at first and will seem very natural later. z0o[2] 'elephant' We can add a new creature to the zoo,it is joined up at the far right end. zoo.append('ostrich');zoo [snake','parrot','elephant','baboon','beetle','ostrich'] We can remove a creature. zoo.remove('parrot') Z00 [snake','elephant','baboon','beetle','ostrich'] We can extract a sublist.Here we start with element 1 (the elephant)and go all the way up to,but not including,element 3 (the beetle).Again a bit odd,but it will feel natural later.For now,notice that we are extracting two elements of the lists,exactly 3-1=2 elements. mammals zoo[1:3] mammals ['elephant','baboon'] Often we will want to see if two lists are equal.To do that we will need to sort a list first. A function creates a new,sorted list,leaving the original alone.So we need to save the new one with a new name. newzoo sorted(zoo) newzoo ['baboon', 'beetle','elephant','ostrich','snake'] zoo.sort() Z00 ['baboon', 'beetle','elephant','ostrich','snake'] Notice that if you run this last compute cell your zoo has changed and some commands above will not necessarily execute the same way.If you want to experiment,go all the way back to the first creation of the zoo and start executing cells again from there with a fresh Z00. A construction called a list comprehension is especially powerful,especially since it almost exactly mirrors notation we use to describe sets.Suppose we want to form the plural of the names of the creatures in our zoo.We build a new list,based on all of the elements of our old list
1.4. SAGE 19 quote marks mean the items are just text, with no special mathematical meaning. Execute these compute cells as we work through them. zoo = [ ' snake ' , ' parrot ' , ' elephant ' , ' baboon ' , ' beetle ' ] zoo [ ' snake ' , ' parrot ' , ' elephant ' , ' baboon ' , ' beetle ' ] So the square brackets define the boundaries of our list, commas separate items, and we can give the list a name. To work with just one element of the list, we use the name and a pair of brackets with an index. Notice that lists have indices that begin counting at zero. This will seem odd at first and will seem very natural later. zoo [2] ' elephant ' We can add a new creature to the zoo, it is joined up at the far right end. zoo . append ( ' ostrich ' ) ; zoo [ ' snake ' , ' parrot ' , ' elephant ' , ' baboon ' , ' beetle ' , ' ostrich ' ] We can remove a creature. zoo . remove ( ' parrot ' ) zoo [ ' snake ' , ' elephant ' , ' baboon ' , ' beetle ' , ' ostrich ' ] We can extract a sublist. Here we start with element 1 (the elephant) and go all the way up to, but not including, element 3 (the beetle). Again a bit odd, but it will feel natural later. For now, notice that we are extracting two elements of the lists, exactly 3 − 1 = 2 elements. mammals = zoo [1:3] mammals [ ' elephant ' , ' baboon ' ] Often we will want to see if two lists are equal. To do that we will need to sort a list first. A function creates a new, sorted list, leaving the original alone. So we need to save the new one with a new name. newzoo = sorted ( zoo ) newzoo [ ' baboon ' , ' beetle ' , ' elephant ' , ' ostrich ' , ' snake ' ] zoo . sort () zoo [ ' baboon ' , ' beetle ' , ' elephant ' , ' ostrich ' , ' snake ' ] Notice that if you run this last compute cell your zoo has changed and some commands above will not necessarily execute the same way. If you want to experiment, go all the way back to the first creation of the zoo and start executing cells again from there with a fresh zoo. A construction called a list comprehension is especially powerful, especially since it almost exactly mirrors notation we use to describe sets. Suppose we want to form the plural of the names of the creatures in our zoo. We build a new list, based on all of the elements of our old list