PDF Abstract Algebra With Applications 1St Edition Audrey Terras Ebook Full Chapter
PDF Abstract Algebra With Applications 1St Edition Audrey Terras Ebook Full Chapter
PDF Abstract Algebra With Applications 1St Edition Audrey Terras Ebook Full Chapter
https://textbookfull.com/product/elementary-abstract-algebra-
examples-and-applications-hill/
https://textbookfull.com/product/abstract-algebra-fourth-edition-
john-a-beachy/
https://textbookfull.com/product/problems-in-abstract-
algebra-1st-edition-adrian-r-wadsworth/
https://textbookfull.com/product/a-course-in-abstract-algebra-
nicholas-jackson/
A concrete approach to abstract algebra Sawyer
https://textbookfull.com/product/a-concrete-approach-to-abstract-
algebra-sawyer/
https://textbookfull.com/product/abstract-algebra-a-
comprehensive-introduction-1st-edition-john-w-lawrence/
https://textbookfull.com/product/abstract-algebra-an-interactive-
approach-second-edition-william-paulsen/
https://textbookfull.com/product/abstract-algebra-applications-
to-galois-theory-algebraic-geometry-representation-theory-and-
cryptography-second-edition-celine-carstensen-opitz/
https://textbookfull.com/product/instructors-solutions-manual-
for-elementary-linear-algebra-with-applications-9th-edition-
bernard-kolman/
Abstract Algebra with Applications
Abstract Algebra with Applications provides a friendly and concise introduction to algebra,
with an emphasis on its uses in the modern world. The first part of this book covers groups,
after some preliminaries on sets, functions, relations, and induction, and features applica-
tions such as public-key cryptography, Sudoku, the finite Fourier transform, and symmetry
in chemistry and physics. The second part of this book covers rings and fields, and features
applications such as random number generators, error-correcting codes, the Google page
rank algorithm, communication networks, and elliptic curve cryptography.
The book’s masterful use of colorful figures and images helps illustrate the applications and
concepts in the text. Real-world examples and exercises will help students contextualize the
information. Meant for a year-long undergraduate course in algebra for math, engineering,
and computer science majors, the only prerequisites are calculus and a bit of courage when
asked to do a short proof.
CAMBRIDGE MATHEMATICAL TEXTBOOKS
ADVISORY BOARD
John B. Conway, George Washington University
Gregory F. Lawler, University of Chicago
John M. Lee, University of Washington
John Meier, Lafayette College
Lawrence C. Washington, University of Maryland, College Park
, S. B. Smith
Elections
with Applications
AUDREY TERRAS
University of California, San Diego, CA, USA
University Printing House, Cambridge CB2 8BS, United Kingdom
One Liberty Plaza, 20th Floor, New York, NY 10006, USA
477 Williamstown Road, Port Melbourne, VIC 3207, Australia
314–321, 3rd Floor, Plot 3, Splendor Forum, Jasola District Centre, New Delhi – 110025, India
79 Anson Road, #06-04/06, Singapore 079906
www.cambridge.org
Information on this title: www.cambridge.org/9781107164079
© Audrey Terras 2019
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2019
Printed in the United States of America by Sheridan Books, Inc.
A catalogue record for this publication is available from the British Library.
List of Figures ix
Preface xiii
PART I GROUPS
1 Preliminaries 3
1.1 Introduction 3
1.2 Sets 6
1.3 The Integers 9
1.4 Mathematical Induction 14
1.5 Divisibility, Greatest Common Divisor, Primes, and Unique Factorization 19
1.6 Modular Arithmetic, Congruences 26
1.7 Relations 30
1.8 Functions, the Pigeonhole Principle, and Binary Operations 34
2 Groups: A Beginning 43
PART II RINGS
7.1 Matrices and Vector Spaces over Arbitrary Fields and Rings like Z 206
7.2 Linear Functions or Mappings 218
7.3 Determinants 224
7.4 Extension Fields: Algebraic versus Transcendental 229
7.5 Subfields and Field Extensions of Finite Fields 233
7.6 Galois Theory for Finite Fields 239
References 299
Index 305
Figures
2.8 Group Explorer version of the multiplication table for C6, a cyclic
group of order 6 52
2.9 Group Explorer version of the multiplication table for D3 (alias S3 )
with our upper case R and F replaced by lower case letters 52
2.10 Cayley graph of cyclic group G = ⟨a⟩ of order 6 with generating
set S = {a} 53
2.11 Cayley graph of D3 with generating set {R, F}. Our upper case letters are
replaced by lower case in the diagram. If there are arrows in both directions
on an edge, we omit the arrows 53
2.12 Undirected version of Cayley graph for C6 = ⟨a⟩ , generating set S = {a, a-1} 53
2.13 Cayley graph of C6 = ⟨ a⟩ , generating set S = {a, a3 , a5} 53
2.14 Group Explorer version of the multiplication table for the Klein 4-group 54
2.15 Symmetrical designs 54
2.16 The Platonic solids 57
2.17 Poset diagram for subgroups of D3 as defined in (2.8) 68
2.18 The Group Explorer version of the multiplication table for a cyclic group
of order 10 73
2.19 Cayley graph X (⟨ a⟩ , {a, a- 1}) for a cyclic group ⟨a⟩ of order 10 76
2.20 A less boring picture of a 10-cycle 76
2.21 Poset diagram of the subgroups of Z24 under addition 78
2.22 Cycle diagram in the multiplicative group Z*15 80
3.1 Tetrahedron 87
3.2 On the left is the Cayley graph for the Klein 4-group K4 = {e, h, v, hv},
with generating set S = {h , v} using the notation of Figure 2.14. On the
right is the Schreier graph for K4/H, where H = {e , h }, with the same
set S = {h, v} 97
3.3 Roll up Z to get Z/nZ 105
3.4 Roll up the real line to get a circle T ∼ = R/ Z 106
3.5 Cayley graph for Z2 ⊕ Z2 with the generating set {(1, 0), (0, 1)} and bears
at the vertices 109
3.6 Cayley graph for Z2 ⊕ Z2 ⊕ Z2 with the generating set {(1, 0, 0), (0, 1, 0),
(0, 0, 1)} and koalas at the vertices 109
3.7 Cayley graph for Z2 ⊕ Z2 ⊕ Z2 ⊕ Z2 with the generating set {(1, 0, 0, 0),
(0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1)} 110
3.8 A finite torus, which is the Cayley graph X(Z10 ⊕ Z 5, {(±1, 0), (0, ±1)}) 111
3.9 The continuous torus (obtained from the plane modulo its integer
points; i.e., R ⊕ R modulo Z ⊕ Z) 111
3.10 Cayley graph for the quaternion group with generating set {±i , ±j } 113
3.11 The 13 necklaces with six beads of two colors 121
3.12 The dodecahedron graph drawn by Mathematica 122
3.13 The cuboctahedron drawn by Mathematica 123
4.1 Vibrating system of two masses 142
4.2 Group Explorer’s multiplication table for the semi-direct product C3 o C4 149
4.3 Group Explorer draws the Cayley graph X(C3 o C4, {a, b}) 149
4.4 The Cayley graph X(Aff(5), S 1,2), with generating set defined by
equation (4.16), has edges given by solid green lines while the dashed
magenta lines are the edges of a dodecahedron 150
List of Figures xi
between 1 and 498 and whose second component is the analog with
499 replaced with 503 249
8.7 Points (vi , wi, z i ) from three vectors v, w, z formed from powers of
generators of F*p for p = 499, 503, and 521, respectively 250
8.8 Feedback shift register corresponding to example 2 252
8.9 Sending a message of 0s and 1s to Professor Bolukxy on the planet Xotl 257
8.10 The matrix H32 where the √
1s and -1s have become red and purple 263
8.11 Color at point√ z = x + y δ in H163 is found by computing the Poincaré
distance d(z, δ ) 268
8.12 The graph on the left is X3(-1, 1), an octahedron, and that on the right
is X5(2, 1) with the edges in green. The pink dashed lines on the right
are the dodecahedron 269
8.13 Another version of Figure 5.2 270
xii Abstract Algebra with Applications
My goal for this book is to provide a friendly concise introduction to algebra with empha-
sis on its uses in the modern world – including a little history, concrete examples, and
visualization. Beyond explaining the basics of the theory of groups, rings, and fields, I aim
to give many answers to the question: What is it good for?” The standard undergraduate
mathematics course in the 1960s (when I was an undergraduate) proceeded from Definition
1.1.1 to Corollary 14.5.59 with little room for motivation, examples, history, and applica-
tions. I plan to stay as far as possible from that old format, modeling my discussion on
G. Strang’s book [115], where the preface begins: “I believe that the teaching of linear
algebra has become too abstract.” My feeling is that the teaching of modern algebra (the
non-linear part) has become even more abstract. I will attempt to follow Strang’s lead and
treat modern algebra in a way that will make sense to a large variety of students. On the
other hand, the goal is to deal with some abstractions – groups, rings, and such things. Yes,
it is abstraction and generalization that underlies the power of mathematics. Thus there will
be some conflict between the applied and pure aspects of our subject.
The book is intended for a year-long undergraduate course in algebra. The intended
audience is the less theoretically inclined undergraduates majoring in mathematics, the
physical and social sciences, or engineering – including those in applied mathematics or
those intending to get a teaching credential.
The prerequisites are minimal: comfort with the real numbers, the complex numbers,
matrices, vector spaces at the level of calculus courses – and a bit of courage when asked
to do a short proof.
In this age of computers, algebra may have replaced calculus (analysis) as the most
important part of mathematics. For example:
1. Error-correcting codes are built into the DVD player and the computer. Who do you call
to correct errors? The algebraist, that’s who!
2. Digital signal processing (such as that involved in medical scanners, weather prediction,
the search for oil) is dominated by the fast Fourier transform or FFT. What is this? The
FFT is a finite sum whose computation has been sped up considerably by an algebra
trick which goes back to Gauss in 1805. Once more algebra, not analysis, rules.
3. In chemistry and physics, one studies structures with symmetry such as the benzene
molecule (C6 H6) depicted in Figure 0.1. What does the 6-fold symmetry have to do with
the properties of benzene? Group theory is the tool one needs for this.
4. The search for secret codes – cryptography. Much of the modern world – particularly
that which lives on the internet – depends on these codes being secure. But are they?
We will consider public-key codes. And who do you call to figure out these codes? An
algebraist!
xiv Abstract Algebra with Applications
5. The quest for beauty in art and nature. I would argue that symmetry groups are necessary
tools for this quest. See Figures 0.2–0.4.
C C
H C C H
C C
H H
Our goal here is to figure out enough group and ring theory to understand many of
these applications. And we should note that both algebra and analysis are necessary for
the applications. In fact, we shall see some limits, derivatives, and integrals before the last
pages of this book. You can skip all the applications if you just want to learn the basics
Preface xv
Figure 0.4 Picture with symmetry coming from the action of 2 × 2 matrices with nonzero
of modern algebra. The non-applied sections are all independent of those on applications.
However, you would be missing one of the big reasons that the subject is taught. And feel
free to skip any applied sections you want to skip – or to add any missing application that
you want to understand.
The first part of this book covers groups, after some preliminaries on sets, functions, rela-
tions, the integers, and mathematical induction. Of course every calculus student is familiar
with the group of real numbers under addition and similarly with the group of nonzero real
numbers under multiplication. We will consider many more examples – favorites being
finite groups such as the group of symmetries of an equilateral triangle.
Much of our subject began with those favorite questions from high school algebra such
as finding solutions to polynomial equations. It took methods of group theory to know
when the solutions could not be found in terms only of nth roots. Galois, who died at age
21 in a duel in 1832, laid the foundations to answer such questions by looking at groups of
permutations of the roots of a polynomial. These are now called Galois groups. See Edna E.
Kramer [59, Chapter 16] or Ian Stewart [114] for some of the story of Galois and the history
of algebra. Another reference for stories about Galois and the many people involved in the
creation of this subject is Men of Mathematics by Eric Temple Bell [8]. This book is often
criticized for lack of accuracy, but it is more exciting than most. I found it inspirational as
an undergraduate – despite the title.
Another area that leads to our subject is number theory: the study of the ring of integers
0 1 2 3
Z = { , ± , ± , ± , . . .} .
The origins of this subject go back farther than Euclid’s Elements. Euclid lived in Alexandria
around 300 BC and his book covers more than the plane geometry we learned in high school.
Much of the basic theory of the integers which we cover in Chapter 1 is to be found in
Euclid’s Elements. Why is it that the non-plane geometry part of Euclid’s Elements does not
seem to be taught in high school?
xvi Abstract Algebra with Applications
Polynomial equations with integer coefficients are often called Diophantine equations in
honor of Diophantus who also lived in Alexandria, but much later (around AD 200). Yes,
algebra is an old subject and one studied in many different countries. For example, the
name “algebra” comes the word al-jabr, one of the two operations used to solve quadratic
equations by the Persian mathematician and astronomer Mohamed ibn Musa al-Khwārizmı̄,
who lived around AD 800.
A large part of this subject was created during many attempts to prove Fermat’s last
theorem. This was a conjecture of Pierre de Fermat in 1637 stating that the equation
x + y = z can have no integer solutions x, y, z with xyz̸= 0 and n > 2. Fermat claimed to
n n n
have a proof that did not fit in the margin of the book in which he wrote this conjecture.
People attempted to prove this theorem without success until A. Wiles with the help of
R. Taylor in 1995. People still seek an ”elementary” proof.
Groups are sets with one operation satisfying the axioms to be listed in Section 2.1.
After the basic definitions, we consider examples of small groups. We will visualize groups
using Cayley graphs and various other diagrams such as Hasse or poset diagrams as well
as cycle diagrams. Other topics of study include subgroups, cyclic groups, permutation
groups, functions between groups preserving the group operations (homomorphisms), cosets
of subgroups, building new groups whose elements are cosets of normal subgroups, direct
products of groups, actions of groups on sets. We will consider such applications as public-
key cryptography, the finite Fourier transform, and the chemistry of benzene. Favorite
examples of groups include cyclic groups, permutation groups, symmetry groups of the
regular polygons, matrix groups such as the Heisenberg group of 3 × 3 upper triangu-
lar matrices with real entries and 1 on the diagonal, the group operation being matrix
multiplication.
The second part of this book covers rings and fields. Rings have two operations satisfying
the axioms listed in Section 5.2. We denote the two operations as addition + and multipli-
cation * or · . The identity for addition is denoted 0. It is NOT assumed that multiplication
is commutative: that is, it is not assumed that ab = ba. If multiplication is commutative,
then the ring is called commutative. A field F is a commutative ring with an identity
for multiplication (called 1̸= 0) such that the nonzero elements of F form a multiplicative
group. Most of the rings considered here will be commutative. We will be particularly inter-
ested in finite fields like the field of integers modulo p, Z/pZ where p is prime. You must
already be friends with the field Q of rational numbers – fractions with integer numer-
ator and nonzero integer denominator. And you know the field R of real numbers from
calculus: that is, limits of Cauchy sequences of rationals. We are not supposed to say the
word “limit” as this is algebra. So we will not talk about constructing the field of real
numbers R. Ring theory topics include: definitions and basic properties of rings, fields,
ideals, and functions between rings which preserve the ring operations (ring homomor-
phisms). We will also build new rings (quotient rings) whose elements are cosets x + I of
an ideal I in ring R, for x in ring R. Note that here R is an arbitrary ring, not necessarily
the field of real numbers. We will look at rings of polynomials and their similarity to the
ring of integers. We can do linear algebra for finite-dimensional vector spaces over arbi-
trary fields in a similar way to the linear algebra that is included in calculus sequences.
Our favorite rings are the ring Z of integers and the quotient ring Z/n Z of integers mod-
ulo n, in which x, is identified with all integers of the form x + nk, for integer k. Another
favorite is the ring of Hamilton quaternions which is isomorphic to four-dimensional space
over the real numbers with basis 1, i , j, k and with multiplication defined by ij = k = -ji,
2 2 2
i = j = k = -1.
Preface xvii
Historically, much of our subject came out of number theory and the desire to prove
Fermat’s last theorem by knowing about factorization into irreducibles in rings like
[√ ] { √ }
Z m = a + b m | a, b ∈ Z , where m is a non-square integer. For example, it turns
So the[ fundamental
]
theorem of arithmetic – true for Z as is shown in Section 1.5 – is false
√
for Z -5 .
Assuming that such factorizations were unique, Lamé thought that he had proved
Fermat’s last theorem in 1847. Dedekind fixed up arithmetic in such rings by develop-
ing the arithmetic of ideals, which are certain sets of elements of the ring to be considered
in Section 5.4. One then had (at least in rings of integers in algebraic number fields) unique
factorization of ideals as products of prime ideals, up to order. Of course, Lamé’s proof of
Fermat’s last theorem was still invalid (lame – sorry for that).
The favorite field of the average human mathematics student is the field of real numbers
R. A favorite finite field for a computer is Fp = Z/ pZ, where p = prime. Of course you can
define Z/nZ, for any positive integer n, but you only get a ring and not a field if n is not
a prime. We consider Z/nZ as a group under addition in Section 1.6. In Chapter 5 we view
it as a ring with two operations, addition and multiplication.
Finite rings and fields were really invented by Gauss (1801) and earlier Euler (1750).
Galois and Abel worked on field theory to figure out whether nth degree polynomial equa-
√
tions are solvable with equations involving only radicals a. In fact, finite fields are often
m
the behavior of biological systems such as a cancer), statistics (hypothesis testing), game
design, finance (e.g., to value options, analyze derivatives – the very thing that led to the
horrible recession/depression of 2008), numerical mathematics (e.g., numerical integration,
stochastic optimization), and the gerrymandering of voting districts.
In Section 8.2 we will show how the finite field with two elements and vector spaces
over this field lead to error-correcting codes. These codes are used in DVDs and in the
transmission of information between a Mars spacecraft and NASA on the earth. Section 8.3
concerns (among other things) the construction of Ramanujan graphs which can provide
efficient communication networks.
Section 8.4 gives applications of the eigenvalues of matrices to Googling. Section 8.5
gives applications of elliptic curves over finite fields to cryptography.
The rush to abstraction of twentieth-century mathematics has had some odd conse-
quences. One of the results of the abstract ring theory approach was to create such an
abstract version of Fourier analysis that few can figure out what is going on. A similar
thing has happened in number theory. On the other hand, modern algebra has often made
it easier to see the forest for the trees by simplifying computations, removing subsubscripts,
doing calculations once in the general case rather than many times, once for each example.
The height of abstraction was achieved in the algebra books of Nicolas Bourbaki (really
a group of French mathematicians). I am using the Bourbaki notation for the fields of real
numbers, complex numbers, rational numbers, and the ring of integers. But Bourbaki seems
to have disliked pictures as well as applications. I do not remember seeing enough examples
or history when I attempted to read Bourbaki’s Algebra as an undergrad. In an interview, one
of the members of Bourbaki, Pierre Cartier (see Marjorie Senechal [102]) said: “The Bourbaki
were Puritans, and Puritans are strongly opposed to pictorial representations of truths of
their faith.” More information on Bourbaki as well as other fashions in mathematics can be
found in Edna E. Kramer’s history book [59]. She also includes a brief history of women in
mathematics as well as the artificial separation between pure and applied mathematics.
As I said in my statement of goals, I will attempt to be as non-abstract as possible in this
book and will seek to draw pictures in a subject where few pictures ever appear. I promise
to give examples of every concept, but hope not to bury the reader in examples either, since
I do aim for brevity. As I am a number theorist interested in matrix groups, there will be
lots of numbers and matrices. Each chapter will have many exercises. It is important to do
them – or as many of them as you can. Some exercises will be needed later in the book. The
answers (mostly sketchy outlines) to odd-numbered exercises will be online hopefully. See
my website. There may also be hints on others. No proof is intended to be very long. The
computational problems might be slightly longer and sometimes impossible without the
help of a computer. I will be using Mathematica, Scientific Workplace, and Group Explorer
to help with computations.
A short list of possible references is: Garrett Birkhoff and Saunders Maclane [9], Larry L.
Dornhoff and Franz E. Hohn [25], David S. Dummit and Richard M. Foote [28], Gertrude
Ehrlich [29], John B. Fraleigh [32], Joseph A. Gallian [33], William J. Gilbert and W. Keith
Nicholson [35], Israel N. Herstein [42], Audrey Terras [116]. There is also a free program:
Group Explorer, which you can download and use to explore small groups. Another free but
harder to use program is SAGE. I will be using Mathematica and Scientific Workplace. The
Raspberry Pi computer ($35) comes with Mathematica (and not much else). There are many
Preface xix
books on line as well. One example is Judson [50]. It includes computer exercises using
SAGE. An on line group theory book making use of the Group Explorer program is that of
Carter [12]. Wikipedia is often very useful – or just asking Google to answer a question. It
is easier to be a student now than it was in my time – thanks to the multitude of resources
to answer questions. On the other hand, it was nice just to have the one small book – in
my case, Birkhoff and Maclane [9] – to deal with. And – perhaps needless to say – online
sources can lie. Even the computer can lie – witness the arithmetic error in the Pentium
chip that was revealed by number theorists’ computations in the 1990s. But I have found
that Wikipedia is usually very useful in its discussions of undergraduate mathematics, as is
the mathematical software I have used.
It is often enlightening to look at more than one reference. Where something is mumbled
about in one place, that same thing may be extremely clearly explained in another. Also
feel free to read a book in a non-linear manner. If you are interested in a particular result
or application, start there.
Acknowledgments
I should thank the Mathematical Sciences Research Institute, Berkeley, for support during
the writing of some of this book, as well as the students in my applied algebra courses at
the University of California, San Diego.
Part I
Groups
1
Preliminaries
1.1 Introduction
=⇒ implies
⇐= is implied by
iff (or ⇐⇒) if and only if
∀ for every
∃ there exists
Z, Q, R, C the integers, rationals, reals, complex numbers, respectively
We will not review the basics of proofs here. Hopefully you have figured out the basics,
either from a high school plane geometry class or a college class introducing the subject
of mathematical proof. See K. H. Rosen [93] for an introduction to proof. We will discuss
proof by mathematical induction soon. There is an interesting book [60] by Steven Krantz
on the subject of proof. Edna E. Kramer’s history book [59] gives more perspective on the
subject of proof. Another place to find a discussion of mathematical proof is Wikipedia. A
cautionary tale concerns K. Gödel’s incompleteness theorems from 1931, the first of which
says that for any consistent formal system for the positive integers Z+ , there is a statement
about Z+ that is unprovable within this system.
There are those who argue against proofs. I have heard this at conferences with physicists.
Nature will tell us the truth of a statement they argue. Ramanujan felt the goddess would
inspire him to write true formulas. However, I have no such help myself and really need
to see a proof to know what is true and what is false. This makes me very bad at real life,
where there is rarely a proof of any statement. Thus I have grown to be happier writing an
algebra book than a book on politics.
If you need more convincing about the need for proofs, look at the following two exer-
cises, once you know what a prime is — an integer p > 1 such that p = ab, with positive
integers a, b implies either a or b = 1. These exercises are silly if you can use your computer
and Mathematica or some other similar program.
Exercise 1.1.1
2
Show that x - x + 41 is prime for all integers x such that 0 ≤ x ≤ 40, but is
not a prime when x = 41. Feel free to use a computer.
Number theory has multitudes of statements like that in Exercise 1.1.1 that have been
checked for a huge number of cases, but yet fail to be true in all cases. Of course, now
4 Part I Groups
computers can do much more than the puny 41 cases in the preceding exercise. For exam-
ple, Mersenne primes are primes of the form Mp = 2p - 1, where p is a prime. Mersenne
compiled a list of Mersenne primes in the 1600s, but there were some mistakes after p = 31.
Much computer time has been devoted to the search for these primes. Always bigger ones
are found. In January, 2017 the biggest known prime was found to be M77 232 917 . It is
conjectured that there are infinitely many Mersenne primes, but the proof has eluded
mathematicians. See Wikipedia or Shanks [103] for more information on this subject and
other unsolved problems in number theory. Wikipedia notes that these large primes have
a cult following – moreover they have applications to random number generators and
cryptography.
In the 1800s – before any computers existed – there was a conjecture by E. C. Catalan
that MM is prime, assuming that Mp is a Mersenne prime. Years passed before Catalan’s
p
conjecture was shown to be false. In 1953 the ILLIAC computer (after 100 hours of com-
puting) showed that MM is not prime when p = 11. MM is prime for p = 2, 3, 5, 7. It was
p p
subsequently found that the conjecture is false for p = 17, 19, 31 as well. The next case is
too large to test at the moment. Wikipedia conjectures that the four known MM that are p
prime are the only ones. Anyway, hopefully, you get the point that you can find a large
number of cases of some proposition that are true without the general proposition being
valid. Stark gives many more examples in the introduction to [110].
Exercise 1.1.2 (Mersenne Primes). Show that 2p - 1 is prime for p = 2, 3, 5, 7, 13, but not
for p = 11.
Hint. The Mathematica command below will do the problem for the first 10 primes.
Table[{Prime[n],FactorInteger[(2^Prime[n])-1]},{n,1,10}]
We assume that you can write down the converse of the statement “proposition A implies
proposition B .” Yes, it is “proposition B implies proposition A.” Recall that A =⇒ B is not
equivalent to B =⇒ A. However A =⇒ B is equivalent to its contrapositive: (not B) =⇒
(not A).
We will sometimes use proof by contradiction. There are those who would object. In proof
by contradiction of A =⇒ B we assume A and (not B) and deduce a contradiction of the
form R and (not R). Those who would object to this and to any sort of “non-constructive”
proof have a point, and so we will try to give constructive proofs when possible. See Krantz
[60] for a bit of the history of constructive proofs in mathematics.
It is also possible that you can prove something that may at first be unbelievable. See the
exercise below, which really belongs to an analysis course covering the geometric series –
the formula for which follows from Exercise 1.4.7 below. If you accept the axioms of the
system of real numbers, then you have to believe the formula.
A controversial method of proof is proof by computer. First you have to believe that
the computer has been programmed correctly. This has not always been the case; e.g., the
problem with the Pentium chip. Here I will choose to believe what my computer tells me
Preliminaries 5
when I use Mathematica to say whether an integer is a prime, or when used to compute
eigenvalues of matrices, or graphs of functions, or to multiply elements of finite fields. There
are more elaborate computer proofs that are hard to verify without even faster computers
than the cheap laptop (vintage 2011) that I am using – for example, the proof of the four
color problem in the 1970s or the recent proof of the Kepler conjecture on the densest
packing of spheres in 3-space. See Krantz [60] for more information.
We are also going to assume that you view the following types of numbers as old friends:
the integers 0 1 2 3
Z = { , ± , ± , ± , . . .}
±
,
{ }
the rationals Q=
m
n
± m, n ∈ Z, n̸= 0 ,
We will list the axioms for Z in Chapter 1 and will construct Q from Z in Chapter 6. Of
course, the construction of Q from Z just involves the algebra of fractions and could be
done in Chapter 1 – minus the verbiage about fields and integral domains. We should define
the real numbers as limits of Cauchy sequences of rationals rather then to say real numbers
are represented by all possible decimals, but that would be calculus and we won’t go there.
Such a construction can be found for example in the book by Leon Cohen and Gertrude
Ehrlich [17]. A serious student should really prove that Z, Q, R, and C exist by constructing
them from scratch, sort of like a serious chef makes a pie, but we will not do that here.
In contemplating the lower rows of our table of number systems, philosophers have
found their hair standing on end. Around
√
500 BC the Pythagoreans were horribly √
shocked
to find that irrational numbers like 2 existed. You will be asked to prove that 2 ∈ / Q in
Section 1.6. What was the problem for the Pythagoreans? You can read about it in Shanks
[103, Chapter III]. What would they have thought about transcendental numbers like π?
√
Later the complex numbers were so controversial that people called numbers like i = -1
“imaginary.” Non-Euclidean geometry was so upsetting that Gauss did not publish his work
on the subject.
Warning. This course is like a language course. It is extremely important to memorize the
vocabulary – the definitions. If you neglect to do this, after a week or so, the lectures – or
the reading – will become meaningless. One confusing aspect of the vocabulary is the use of
everyday words in a very different but precise way. Then one needs the axioms, the rules of
constructing proofs. Those are our rules of grammar for the mathematical language. These
too must be memorized. We should perhaps add that it is folly to argue with the definitions
or axioms – unless you have found the equivalent of non-Euclidean geometry. To some our
subject appears arcane. But they should remember that it is just a language – there is no
mystery once you know the vocabulary and grammar rules.
Practice doing proofs. This means practice speaking or writing the language. One can
begin by imitating the proofs in the text or other texts or those given by your professor. It
is important to practice writing proofs daily. In particular, one must do as many exercises
as possible. If your calculus class did not include proofs, this may be something of a shock.
Mathematics seemed to be just calculations in those sad proof-less classes. And we will
have a few calculations too. But the main goal is to be able to derive “everything” from
a few basic definitions and axioms – thus to understand the subject. One can do this for
calculus too. That is advanced calculus. If you do not practice conversations in a language,
you are extremely unlikely to become fluent. The same goes with mathematics.
6 Part I Groups
You should also be warned that sometimes when reading a proof you may doubt a state-
ment and then be tempted to stop reading. Sadly, often the next sentence explains why that
unbelievable statement is true. So always keep reading. This happens to “real” mathemati-
cians all the time so do not feel bad. I have heard a story about a thesis advisor who told
a student he did not understand the proof of a lemma in the student’s thesis. The student
almost had a heart attack worrying about that important lemma. But it turned out that the
advisor had not turned the page to find the rest of the proof.
Our second goal is to apply the algebra we derive so carefully. We will not be able to
go too deeply into any one application, but hopefully we will give the reader a taste of
each one.
1.2 Sets
We first review a bit of set theory. Georg Cantor (1845–1918) developed the theory of infinite
sets. It was controversial. There are paradoxes for those who throw caution to the winds
and consider sets whose elements are sets. For example, consider Russell’s paradox . It was
stated by B. Russell (1872–1970). We use the notation: x ∈ S to mean that x is an element
of the set S; x ∈
/ S means x is not an element of the set S. The notation { x|x has property P}
is read as the set of x such that x has property P. Consider the set X defined by
X ={ sets S | S∈
/ S}.
Then X ∈ X implies X ∈ / X and X ∈ / X implies X ∈ X. This is a paradox. The set X can neither
be a member of itself nor not a member of itself. There are similar paradoxes that sound
less abstract. Consider the barber who must shave every man in town who does not shave
himself. Does the barber shave himself? A mystery was written inspired by the paradox: The
Library Paradox by Catharine Shaw. There is also a comic book about Russell, Logicomix
by A. Doxiadis and C. Papadimitriou (see [26]). A nice reference for set theory illustrated
by pictures and stories is the book by Vilenkin [122].
We will hopefully avoid paradoxes by restricting consideration to sets of numbers, vec-
tors, and functions. This would not be enough for “constructionists” such as Errett Bishop
who was on the faculty at the University of California San Diego. until his premature death.
I am still haunted by his probing questions of colloquium speakers. Anyway, for applied
mathematics, one can hope that paradoxical sets and barbers do not appear. Thus we will
be using proof by contradiction, as we have already promised.
Most books on calculus do a little set theory. We assume you are familiar with the notation
which we are about to review. We will draw pictures in the plane. We write A ⊂ B (or B ⊃ A)
if A is a subset of B: that is, x ∈ A implies x ∈ B . We might also say B contains A. If A ⊂ B,
the complement of A in B is B - A = {x ∈ B |x ∈ / A }. 1 The empty set is denoted ∅ . It has no
elements. The intersection of sets A and B is
A ∩ B = {x | x ∈ A and x ∈ B}.
A ∪ B = {x | x ∈ A or x ∈ B }.
1
We will not use the other common notation B/A for set complement since it conflicts with our later
notation for quotient groups.
Preliminaries 7
Here – as is usual in mathematics – “or” means either or both. See Figure 1.1. Sets A and
B are said to be disjoint iff A ∩ B = ∅.
Intersection of A and B
is pink
Union of A and B
is purple
The easiest way to do the following exercises on the equality of various sets is to show
first that the set on the left is contained in the set on the right and second that the set on
the right is contained in the set on the left.
Exercise 1.2.1
A - (B ∪ C) = (A - B) ∩ (A - C).
A - (B ∩ C) = (A - B) ∪ (A - C).
with ∪ replaced by ∩.
Definition 1.2.1 If A and B are sets, the Cartesian product of A and B is the set of
A × B = {(a, b) | a ∈ A, b ∈ B }.
It is understood that we have equality of two ordered pairs (a , b ) = (c , d) iff a=c and
b = d.
8 Part I Groups
Example 1. Suppose A and B are both equal to the set of all real numbers; A = B = R. Then
A × B =R × R= R
2 . That is, the Cartesian product of the real line with itself is the set of
C ×D
2
C D
1 2
Of course you can also define the Cartesian product of any number of sets – even an
infinite number of sets. We mostly restrict ourselves to a finite number of sets here. Given
n sets Si , i ∈ {1, 2, . . . , n }, define the Cartesian product S1 × S 2 × · · · × Sn to be the set of
Example 3. [ 0, 1] × [0, 1] × [0, 1] = [ 0, 1] 3 is the unit cube in 3-space. See Figure 1.3. ▲
3
Figure 1.3 [0, 1]
4
Example 4. [ 0, 1] × [0, 1] × [0, 1] × [ 0, 1] = [0, 1]
is the four-dimensional cube or tesseract.
Draw it by “pulling out” the three-dimensional cube. See T. Banchoff [6]. Figure 1.4 below
shows the edges and vertices of the four-dimensional cube or tesseract (actually more of
Preliminaries 9
a 4-rectangular solid) as drawn by Mathematica. Of course both Figures 1.3 and 1.4 are
really projections of the cube and hypercube onto the plane. ▲
Exercise 1.2.4 Show that A × (B ∩ C) = (A × B) ∩ (A × C). Does the same equality hold
when you replace ∩ with ∪?
Exercise 1.2.5 State whether the following set-theoretic equalities are true or false and give
(a) (A - C) ∩ (B - C) = (A ∩ B) - C;
(b) A × (B - C) = ( A × B) - (A × C).
Notation.
We assume that you have been familiar with the basic facts about the integers since child-
hood. Despite that familiarity, we must list the 10 basic axioms for Z in order to be able
to prove anything about Z. By an axiom, we mean a basic unproved assumption. We must
deduce everything we say about Z from our 10 axioms – forgetting what we know from
elementary school. In Section 5.3 we will find that much of what we do here – especially in
the pure algebra part (R1 to R6) – works for any integral domain and not just Z . Sometimes
Z
+
or Z+ ∪ { 0} is referred to as the “natural numbers.” This seems somewhat prejudicial
to the other types of numbers one may use and so we will try to avoid that terminology.
10 Part I Groups
For every n, m ∈ Z there is a unique integer m + n and a unique integer n · m such that
the following laws are valid for all m, n, k ∈ Z. This says the set of integers is closed under
addition and multiplication.
R5 Distributive law: k · (m + n) = k · m + k · n.
We sometimes write n · m = n * m = nm. Thanks to the associative laws, we can leave out
parentheses in sums like k + m + n or in products like kmn. Of course we still need those
parentheses in the distributive law.
As a result of axioms R1–R5, we say that Z is a “commutative ring with identity for
multiplication.” As a result of the additional axiom R6 we say that Z is an “integral domain.”
Rings will be the topic for the last half of this book – starting with Chapter 5.
Exercise 1.3.1
1
x = -m = (- ) · m. Prove that -(-m) = m.
Exercise 1.3.4 (Cancellation Laws) . Show that if a, b , c ∈ Z, then we have the following laws.
(a) If a + b = a + c, then b = c.
Exercise 1.3.6 Prove that for any a, b ∈ Z we can solve the equation a + x = b for x ∈ Z.
Additional axioms for Z involve the ordering < of Z which behaves well with respect
to addition and multiplication. The properties of inequalities can be derived from three
simple axioms for the set P = Z+ of positive integers.
Another random document with
no related content on Scribd:
THE STRAIN THAT MAKES THE CORNING EGG FARM FAMOUS
As The Corning Egg Farm was located within a few miles of New
York City the breeds which laid the white shelled egg were the only
ones worthy of consideration, and, in the study of the question, it
was found there was another important matter confronting the egg
farmer, as to the breed which he should keep, whether a setter, or a
non-setter. On an egg farm, where hundreds of layers are to be kept,
if any of the Asiatics, or so called American Breeds, were kept, they
would be a source of considerable added expense, first, in the way
of loss of eggs during their numerous broody periods; second, in the
necessary buildings in which to carry the “broody biddies” until they
have become sensible, and are in a proper frame of mind to be
returned to the Laying House. This might look on its face a small
affair, but success to The Corning Egg Farm has come through
watching every corner, and while sparing no needed expenditure,
avoiding unnecessary and foolish outlay.
So, to the man who would really meet with a large success, all the
breeds which lay the dark shelled egg, because of their setting
propensity, must be eliminated.
All the members of the Mediterranean family are layers of the
white shelled egg, and are what is termed “non-setting.”
Now, if the anatomy of these two birds had been studied, it would
have been found at once that hen No. 1 was much better qualified to
take a place in the breeding pen than hen No. 2. The mere fact that
the trap nest record of any female shows a phenomenal number of
eggs laid in ten or twelve months does not necessarily prove that
she is a proper animal to breed from. Post-mortem examinations
show in many cases that they are freaks, and, while they have laid a
great number of eggs, there was much to be desired in regard to the
eggs, as to their size, shape, and color. As a matter of fact it would
have been a great mistake to have bred from such an individual.