Notes on Abstract Algebra August 22, 2013 Course: Instructor: Math 31 - Summer 2013 Scott M. LaLonde Contents 1 Introduction 1 1.1 What is Abstract Algebra? . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Motivating Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 The Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 The integers mod n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . 14 2 Group Theory 19 2.1 Definitions and Examples of Groups . . . . . . . . . . . . . . . . . . 19 2.1.1 Binary Operations . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.2 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.3 Group Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.4 Remarks on Notation . . . . . . . . . . . . . . . . . . . . . . 28 2.2 The Symmetric and Dihedral Groups . . . . . . . . . . . . . . . . . . 29 2.2.1 The Symmetric Group . . . . . . . . . . . . . . . . . . . . . . 29 2.2.2 The Dihedral Group . . . . . . . . . . . . . . . . . . . . . . . 35 2.3 Basic Properties of Groups . . . . . . . . . . . . . . . . . . . . . . . 38 2.4 The Order of an Element and Cyclic Groups . . . . . . . . . . . . . 41 2.4.1 Cyclic Groups. . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4.2 Classification of Cyclic Groups . . . . . . . . . . . . . . . . . 48 2.5 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.5.1 Cyclic Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.5.2 Subgroup Criteria . . . . . . . . . . . . . . . . . . . . . . . . 54 2.5.3 Subgroups of Cylic Groups . . . . . . . . . . . . . . . . . . . 56 2.6 Lagrange’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.6.1 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . 60 2.6.2 Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.7 Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.7.1 Basic Properties of Homomorphisms . . . . . . . . . . . . . . 73 i ii CONTENTS 2.8 The Symmetric Group Redux . . . . . . . . . . . . . . . . . . . . . . 75 2.8.1 Cycle Decomposition . . . . . . . . . . . . . . . . . . . . . . . 75 2.8.2 Application to Dihedral Groups . . . . . . . . . . . . . . . . . 81 2.8.3 Cayley’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . 83 2.8.4 Even and Odd Permutations and the Alternating Group . . . 85 2.9 Kernels of Homomorphisms . . . . . . . . . . . . . . . . . . . . . . . 89 2.10 Quotient Groups and Normal Subgroups . . . . . . . . . . . . . . . . 93 2.10.1 The Integers mod n . . . . . . . . . . . . . . . . . . . . . . . 93 2.10.2 General Quotient Groups . . . . . . . . . . . . . . . . . . . . 94 2.10.3 Normal Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 96 2.10.4 The First Isomorphism Theorem . . . . . . . . . . . . . . . . 99 2.10.5 Aside: Applications of Quotient Groups . . . . . . . . . . . . 101 2.11 Direct Products of Groups . . . . . . . . . . . . . . . . . . . . . . . . 104 2.12 The Classification of Finite Abelian Groups . . . . . . . . . . . . . . 106 3 Ring Theory 111 3.1 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3.2 Basic Facts and Properties of Rings . . . . . . . . . . . . . . . . . . 113 3.2.1 The Quaternions . . . . . . . . . . . . . . . . . . . . . . . . . 116 3.3 Ring Homomorphisms and Ideals . . . . . . . . . . . . . . . . . . . . 118 3.4 Quotient Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 3.5 Polynomials and Galois Theory . . . . . . . . . . . . . . . . . . . . . 122 3.6 Act I: Roots of Polynomials . . . . . . . . . . . . . . . . . . . . . . . 122 3.7 Act II: Field Extensions . . . . . . . . . . . . . . . . . . . . . . . . . 124 3.8 Act III: Galois Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 126 3.8.1 Epilogue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 A Set Theory 131 A.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 A.2 Constructions on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 132 A.3 Set Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 A.4 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 B Techniques for Proof Writing 137 B.1 Basic Proof Writing . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 B.2 Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . 142 B.3 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . 144 B.4 Proof by Contrapositive . . . . . . . . . . . . . . . . . . . . . . . . . 146 B.5 Tips and Tricks for Proofs . . . . . . . . . . . . . . . . . . . . . . . . 148 Chapter 1 Introduction These notes are intended to accompany the summer 2013 incarnation of Math 31 at Dartmouth College. Each section roughly corresponds to one day’s lecture notes, albeit rewritten in a more readable format. The official course text is Abstract Algebra: A First Course by Dan Saracino, but some ideas are taken from other sources. In particular, the following books have all been consulted to some extent: • Abstract Algebra by I. N. Herstein • Contemporary Abstract Algebra by Joseph Gallian • A First Course in Abstract Algebra by John Fraleigh • Abstract Algebra by John A. Beachy and William D. Blair • A Book of Abstract Algebra by Charles C. Pinter The first book above was the course textbook when I taught Math 31 in Summer 2012, and the second is regularly used for this course as well. Many of the historical anecdotes are taken from the first chapter of Pinter’s book. 1.1 What is Abstract Algebra? Inordertoanswerthequestionposedinthetitle, therearereallytwoquestionsthat we must consider. First, you might ask, “What does ‘abstract’ mean?” You also probably have some preconceived notions about the meaning of the word “algebra.” This should naturally lead you to ask, “How does this course relate to what I already know about algebra?” We will see that these two questions are very much intertwined. The second one is somewhat easier to address right now, so we will start there. 1 2 Introduction 1.1.1 History If you’ve looked at the textbook at all, you have probably noticed that “abstract algebra” looks very different from the algebra you know. Many of the words in the table of contents are likely unrecognizable, especially in the context of high school algebra. However, this new notion of abstract algebra does relate to what you already know—the connections just aren’t transparent yet. We will shed some light on these connections by first discussing the history of abstract algebra. This will set the stage for the beginning and the end of the course, and the tools that we develop in between will allow us to link the ideas of modern algebra with your prior knowledge of the subject. In high school, the word “algebra” often means “finding solutions to equations.” Indeed, the Persian poet-mathematician Omar Khayy´am defined algebra to be the “science of solving equations.”1 In high school, this probably meant that you were solving linear equations, which look like ax+b = 0, or quadratic equations, of the form ax2+bx+c = 0 Methods for solving these equations were known even in ancient times.2 Indeed, you learned to solve quadratics by factoring, and also by the quadratic formula, which gives solutions in terms of square roots: √ −b± b2−4ac x = . 2a You may have also learned to factor cubic polynomials, which have the form ax3+bx2+cx+d. Techniques were known to ancient mathematicians, including the Babylonians, for solving certain types of cubic equations. Islamic mathematicians, including Omar Khayy´am3, also made significant progress. However, what about a general formula for the roots? Can we write down a formula, like the quadratic formula, which gives ustherootsofany cubicintermsofsquarerootsandcuberoots? Thereisaformula, 1Khayy´am was not the first to use the term algebra. The Arabic phrase al-jabr, meaning “bal- ancing” or “reduction” was first used by Muhammad ibn al-Khwa¯rizmi. 2This statement deserves clarification. The ancients were able to solve quadratic equations, provided that the solutions didn’t involve complex numbers or even negative numbers. 3It is quite extraordinary that Khayya´m was able to make such progress. He lacked the formal symbolism that we now have, using only words to express problems. Also, negative numbers were still quite mysterious at this time, and his solutions were usually geometric in nature. 1.1 What is Abstract Algebra? 3 which we won’t write down here, but it took quite a longtime for mathematicians to find it. The general formula for cubics4 was discovered in Italy during the Renais- sance, by Niccol´o Fontana Tartaglia. As was the case with many mathematicians, Tartaglia led an interesting and somewhat tragic life. Born in 1500, Tartaglia was not his real name – it is actually an Italian word meaning “the stammerer.” As a child, he suffered a sabre attack during the French invasion of his hometown of Brescia, which resulted in a speech impediment. He was entirely self-taught, and was not only a great mathematician, but also an expert in ballistics. In 1535, he found a general method for solving a cubic equation of the form x3+ax2+b = 0, i.e. with no x term. As was customary in those days, Tartaglia announced his accomplishment, but he kept the details secret. He eventually entered into a “math duel” with Antonio Fiore, who had learned a method for solving cubics of the form x3+ax+b = 0 from his mentor, Scipio del Ferro. These “duels” were not duels in the more familiar andbrutalsense,butpubliccompetitionsinproblemsolving. Theadversarieswould exchange lists of problems, and each competitor would attempt to solve more than the other. A few days beforehand, Tartaglia extended his method to handle Fiore’s brand of cubic equations as well. Within 2 hours, he solved all of Fiore’s problems, and Fiore solved none of Tartaglia’s. His victory over Fiore brought Tartaglia a reasonable amount of fame, and in particular it brought him to the attention of the mathematician (and all-around scoundrel5) Gerolamo Cardano. Born in 1501, Cardano was an accomplished math- ematician and physician, and he was actually the first person to give a clinical description of typhus fever. He was also a compulsive gambler and wrote a manual for fellow gamblers, which was actually an early book on probability. Eventually, Tartaglia cut a deal with Cardano—he divulged his secret method to Cardano in exchange for help in obtaining a job with the military as a ballistics adviser. Car- dano was actually writing an algebra book, titled Ars Magna (“The Great Art”), in which he collected all of the algebra that was known in Europe at the time. He published Tartaglia’s result, while acknowledging del Ferro for his discovery of the solution for cubics with no x2 term. Cardano gave Tartaglia the appropriate credit for rediscovering this result. Tartaglia was furious at this blatant breach of trust, and the two had a long feud after that. Despite this, the formula is now known as the Cardano-Tartaglia formula in honor of both men. 4Again,thisformuladoesnotworkinfullgenerality. Tartagliawasonlyabletodealwithcubics which had nonnegative discriminant—for such cubics, the solution did not involve square roots of negative numbers. These cubics are the ones which have exactly one real root. 5At least one author describes him as a “piece of work.” 4 Introduction After the question of solving cubics was resolved, people turned their attention to the quartic equation: x4+ax3+bx2+cx+d = 0. Lodovico Ferrari, who was Cardano’s personal servant, found the formula. He had learned mathematics, Latin, and Greek from Cardano, and he had actually bested Tartaglia in a duel in 1548. He reduced the problem to that of solving an equation involving the resolvent cubic, and then used Tartaglia’s formula. This in fact led Cardano to his decision to publish Tartaglia’s work, since he needed it in order to publish Ferrari’s result. After Ferrari’s work, the obvious next step was to try to find general methods for finding the roots of fifth (and higher) degree polynomials. This was not so easy. It took over 200 years before any real progress was made on this question. In the early 19th century, two young mathematicians independently showed that there is no general formula for the roots of a quintic polynomial. ThefirstofthesetwoyoungmenwasNielsHenrikAbel, whoprovedhisresultin 1824. He was Norwegian, and he died from tuberculosis 5 years after publishing his work (at the age of 26). The other young prodigy, who has one of the best-known stories among mathematicians, was a French radical by the name of E´variste Galois. He did much of his work around 1830, at the age of 18, though it wasn’t published until about 15 years later. His story was very tragic, beginning in his teenage year’s with his father’s suicide. He was then refused admission to the prestigious E´cole Polytechnique on the basis that his solutions to the entrance exam questions were too radical and original. He eventually entered the E´cole Normale, but was expelled and imprisoned for political reasons. Even his groundbreaking work was largely ignored by the preeminent French mathematicians of his day, including Cauchy, Fourier, and Poisson. Last but not least, he was killed in a duel (under mysterious circumstances) at the age of 20. Fortunately, Galois entrusted his work to a friend on the night before the duel, and it was published posthumously 15 years later. In proving that there is no “quintic formula,” Abel and Galois both essentially invented what is now known as a group. In particular, Galois studied groups of permutations of the roots of a polynomial. In short, he basically studied what happens when you “shuffle” the roots of the polynomial around. Galois’ ideas led to a whole field called Galois theory, which allows one to determine whether any given polynomial has a solution in terms of radicals. Galois theory is regarded as one of the most beautiful branches of mathematics, and it usually makes up a whole course on its own. This is the context in which groups (in their current form) began to arise. Since then, the study of groups has taken off in many directions, and has become quite interestinginitsownright. Groupsareusedtostudypermutations,symmetries,and cryptography, to name a few things. We’ll start off by studying groups abstractly, and we will consider interesting examples of groups along the way. Hopefully this 1.2 Motivating Examples 5 discussion will give you an idea of where groups come from, and where your study of algebra can eventually lead. 1.1.2 Abstraction We’ve just discussed where some of the ideas in a course on abstract algebra come from historically, but where do we go with them? That is, what is the real goal of a course like this? That’s where the “abstract” part comes in. In many other classes that you’ve taken, namely calculus and linear algebra, things are very concrete with lots of examples and computations. In this class, there will still be many examples, but we will take a much more general approach. We will define groups (and other algebraic structures) via a set of desirable axioms, and we will then try to logically deduce properties of groups from these axioms. To give you a preview, let me say the following regarding group theory. A group will basically be a set (often consisting of numbers, or perhaps matrices, but also of other objects) with some sort of operation on it that is designed to play the role of addition or multiplication. Additionally, we’ll require that the operation has certain desirable arithmetic properties. In the second part of the course, we will study objects called rings. These will arise when we allow for two different operations on a set, with the requirement that they interact well (via a distributive law). Along theway, wewilltrytodoasmanyexamplesaspossible. Somewillcomefromthings that are familiar to you (such as number systems and linear algebra), but some will be totally new. In particular, we will emphasize the role of groups in the study of symmetry. Despite the concrete examples, there will still be an overarching theme of classi- fication and structure. That is, once we’ve defined things such as groups and rings and proven some facts about them, we’ll try to answer much broader questions. Namely, we’ll try to determine when two groups are the same (a concept called isomorphism), and when we can break a group down into smaller groups. This idea of classification is something that occurs in pretty much every branch of math (algebra, topology, analysis, etc.). It may seem overly abstract, but it is paramount to the understanding of algebra. We will start off slowly in our abstract approach to algebra—we’ll begin with a couple of motivating examples that should already be familiar to you. Then we’ll study one which is more interesting, and perhaps less familiar. Once we’ve done these, we’ll write down the actual definition of a group and begin to study these objects from an “abstract” viewpoint. 1.2 Motivating Examples As a precursor to group theory, let’s talk a little bit about some structures with which you should already be familiar. We will see shortly that these objects will 6 Introduction turn out to be simple examples of groups. 1.2.1 The Integers Let Z denote the set of all integers. We have an arithmetic operation on Z, given by addition. That is, given two integers, we can add them together to obtain a new integer. We’ll let (cid:104)Z,+(cid:105) denote the set of integers endowed with the operation of addition. (At this point, we’ll pretend that we don’t know how to do anything else yet, such as multiplication of integers.) What desirable properties does (cid:104)Z,+(cid:105) have? First of all, what happens if I try to add three integers, say a+b+c? Formally, addition is an operation that just takes in two integers and produces a new integer. Therefore, to make sense of the above expression, we would have to break things down into steps. We could first add a and b, then add c to the result: a+b+c = (a+b)+c On the other hand, we could add b and c, and then add a: a+b+c = a+(b+c). Both are legitimate ways of defining a+b+c. Fortunately, they turn out to be the same, and it doesn’t matter which way we add things. That is to say, addition on Z is associative. You could also point out that addition is commutative. There is also a special element of Z, which acts as an identity with respect to addition: for any n ∈ Z, we have n+0 = n. Recallthatmiddle/highschoolalgebraisallaboutsolvingsimpleequations. For example, if I have the equation x+5 = 7, how do I find x? I need to subtract 5 from both sides. Since we only know how to add integers, it would be more appropriate to say that we should add −5 to both sides, which gives x = 2. Now imagine instead that I wrote the equation x+5 = 0. Then the solution would instead be x = −5. What we are really saying here is that every integer n has the property that n+(−n) = 0, and we say that n has an additive inverse, −n. It is the presence of an additive inverse that lets us solve simple equations like x + 5 = 7 over the integers. In summary, addition on Z satisfies three nice properties: 1.2 Motivating Examples 7 • associativity • identity • inverses These are the properties that we would really like to have in a group, so that we can perform basic arithmetic. Notice that we’ve left out commutativity, since we won’t always require it to hold. We will soon see an example that will illustrate this. What if I now pretend that we can only multiply integers: (cid:104)Z,·(cid:105)? What prop- erties do we have now? Well, multiplication is still associative. There is also a multiplicative identity: n·1 = 1·n = n for all n ∈ Z. What about inverses? Given n ∈ Z, is there always an integer x so that n·x = 1? No—it even fails if we take n = 2. In fact, it turns out that only 1 and −1 have multiplicative inverses. Thus we have just shown that (cid:104)Z,·(cid:105) does not satisfy our list of axioms, since not every integer possesses a multiplicative inverse. Therefore, it will not fit the definition of a group that we will eventually give. 1.2.2 Matrices Let’s now turn to another example that you should remember from your linear algebra class. You likely spent a lot of time there studying properties of matrices, particularly M (R) = {n×n matrices with entries in R}. n You saw that you can add matrices by simply adding the entries, and you also learned how to multiply matrices (which is slightly more complicated). Let’s think about (cid:104)M (R),+(cid:105) first. Is the operation associative? The answer n is of course yes, since addition of real numbers is associative. Is there an identity? Yes—the zero matrix is an additive identity. How about inverses? Well, if A is a matrix, −A is its additive inverse. Thus (cid:104)M (R),+(cid:105) satisfies the axioms. We should n also note that the operation in question is commutative. What about (cid:104)M (R),·(cid:105)? It should have been pointed out in your linear algebra n class that matrix multiplication is associative. There is also an identity, namely the identity matrix, which has the property that A·I = I ·A = A for all A ∈ M (R). What about inverses? Given an n×n matrix A, can I always n find a matrix B so that AB = BA = I?