In the so-called naive set theory, which is sufficient for the purpose of studying abstract algebra, the notion of a set is not rigorously defined. We describe a set as a well-defined aggregation of objects, which are referred to as members or elements of the set. If a certain object is an element of a set, it is said to be contained in that set. The elements of a set can be anything at all, but in the study of abstract algebra, elements are most frequently numbers or mathematical structures. The elements of a set completely determine the set, and so sets with the same elements as each other are equal. Conversely, sets which are equal contain the same elements.
For an element and a set , we can say either , that is, is contained in , or , that is, is not contained in . To state that multiple elements are contained in , we write .
If it is not possible to list the elements of a set, it can be defined by giving a property that its elements are sole to possess. The set of all objects with some property can be denoted by . Similarly, the set of all elements of a set with some property can be denoted by . The colon : here is read as "such that". The vertical bar | is synonymous with the colon in similar contexts. This notation will appear quite often in the rest of this book, so it is important for the readers to familiarize themselves with this now.
As an example of this notation, the set of integers can be written as , and the set of even integers can be written as .
One can define an empty set, written , such that , where denotes universal quantification (read as "for all" or "for every"). In other words, the empty set is defined as the set which contains no elements. The empty set can be shown to be unique.
Since the empty set contains no elements, it can be shown to be a subset of every set. Similarly, no set but the empty set is a subset of the empty set.
For two sets and , we can define proper set inclusion as follows: is a proper subset of if and only if is a subset of , and does not equal . In other words, there is at least one member in not contained in
where the symbol denotes "is a proper subset of" and the symbol denotes logical and.
The cardinality of a set , denoted by , can be said informally to be a measure of the number of elements in . However, this description is only rigorously accurate for finite sets. To find the cardinality of infinite sets, more sophisticated tools are needed.
For sets and , we define the intersection of and by the set which contains all elements which are common to both and . Symbolically, this can be stated as follows:
Because every element of is an element of and an element of , is, by the definition of set inclusion, a subset of and .
If the sets and have no elements in common, they are said to be disjoint sets. This is equivalent to the statement that and are disjoint if .
Set intersection is an associative and commutative operation; that is, for any sets , , and , and .
By the definition of intersection, one can find that and . Furthermore, .
One can take the intersection of more than two sets at once; since set intersection is associative and commutative, the order in which these intersections are evaluated is irrelevant. If are sets for every , we can denote the intersection of all by
In cases like this, is called an index set, and are said to be indexed by .
For sets and , we define the union of and by the set which contains all elements which are in either or or both. Symbolically,
Since the union of sets and contains the elements of and , and .
Like set intersection, set union is an associative and commutative operation; for any sets , , and , and .
By the definition of union, one can find that . Furthermore, .
Just as with set intersection, one can take the union of more than two sets at once; since set union is associative and commutative, the order in which these unions are evaluated is irrelevant. Let be sets for all . Then the union of all the is denoted by
(Where may be read as "there exists".)
For the union of a finite number of sets , that is, one can either write or abbreviate this as
The Cartesian product of sets and , denoted by , is the set of all ordered pairs which can be formed with the first object in the ordered pair being an element of and the second being an element of . This can be expressed symbolically as
Since different ordered pairs result when one exchanges the objects in the pair, the Cartesian product is not commutative. The Cartesian product is also not associative. The following identities hold for the Cartesian product for any sets :
The Cartesian product of any set and the empty set yields the empty set; symbolically, for any set , .
The Cartesian product can easily be generalized to the n-ary Cartesian product, which is also denoted by . The n-ary Cartesian product forms ordered n-tuples from the elements of sets. Specifically, for sets ,
This can be abbreviated as
In the n-ary Cartesian product, each is referred to as the -th coordinate of .
In the special case where all the factors are the same set , we can generalize even further. Let be the set of all functions . Then, in analogy with the above, is effectively the set of "-tuples" of elements in , and for each such function and each , we call the -th coordinate of . As one might expect, in the simple case when for an integer , this construction is equivalent to , which we can abbreviate further as . We also have the important case of , giving rise to the set of all infinite sequences of elements of , which we can denote by . We will need this construction later, in particular when dealing with polynomial rings.
Let and be any two sets. We then define their disjoint union, denoted to be the following: First create copies and of and such that . Then define . Notice that this definition is not explicit, like the other operations defined so far. The definition does not output a single set, but rather a family of sets. However, these are all "the same" in a sense which will be defined soon. In other words, there exists bijective functions between them.
Luckily, if a disjoint union is needed for explicit computation, one can easily be constructed, for example .
We define some arbitrary set for which every set under consideration is a subset of as the universal set, or universe. The complement of any set is then defined to be the set difference of the universal set and that set. That is, for any set , the complement of is given by . The following identities involving set complements hold true for any sets and :
De Morgan's laws for sets:
Double complement law:
The set complement can be related to the set difference with the identities and .
For sets and , the symmetric set difference of and , denoted by or by , is the set of elements which are contained either in or in but not in both of them. Symbolically, it can be defined as
More commonly, it is represented as
The symmetric difference is commutative and associative so that and . Every set is its own symmetric-difference inverse, and the empty set functions as an identity element for the symmetric difference, that is, and . Furthermore, if and only if .
Set intersection is distributive over the symmetric difference operation. In other words, .
The symmetric difference of two set complements is the same as the symmetric difference of the two sets: .
Commonly-used sets of numbers in mathematics are often denoted by special symbols. The conventional notations used in this book are given below.
Natural numbers with 0: or
Natural numbers without 0:
Equivalence relations and congruence classes
We often wish to describe how two mathematical entities within a set are related. For example, if we were to look at the set of all people on Earth, we could define "is a child of" as a relationship. Similarly, the operator defines a relation on the set of integers. A binary relation, hereafter referred to simply as a relation, is a binary proposition defined on any selection of the elements of two sets.
Formally, a relation is any arbitrary subset of the Cartesian product between two sets and so that, for a relation , . In this case, is referred to as the domain of the relation and is referred to as its codomain. If an ordered pair is an element of (where, by the definition of , and ), then we say that is related to by . We will use to denote the set
In other words, is used to denote the set of all elements in the codomain of to which some in the domain is related.
To denote that two elements and are related for a relation which is a subset of some Cartesian product , we will use an infix operator. We write for some and .
There are very many types of relations. Indeed, further inspection of our earlier examples reveals that the two relations are quite different. In the case of the "is a child of" relationship, we observe that there are some people A,B where neither A is a child of B, nor B is a child of A. In the case of the operator, we know that for any two integers exactly one of or is true. In order to learn about relations, we must look at a smaller class of relations.
In particular, we care about the following properties of relations:
Reflexivity: A relation is reflexive if for all .
Symmetry: A relation is symmetric if for all .
Transitivity: A relation is transitive if for all .
One should note that in all three of these properties, we quantify across all elements of the set .
Any relation which exhibits the properties of reflexivity, symmetry and transitivity is called an equivalence relation on . Two elements related by an equivalence relation are called equivalent under the equivalence relation. We write to denote that and are equivalent under . If only one equivalence relation is under consideration, we can instead write simply . As a notational convenience, we can simply say that is an equivalence relation on a set and let the rest be implied.
Example: For a fixed integer , we define a relation on the set of integers such that if and only if for some . Prove that this defines an equivalence relation on the set of integers.
Reflexivity: For any , it follows immediately that , and thus for all .
Symmetry: For any , assume that . It must then be the case that for some integer , and . Since is an integer, must also be an integer. Thus, for all .
Transitivity: For any , assume that and . Then and for some integers . By adding these two equalities together, we get , and thus .
Remark. In elementary number theory we denote this relation and say a is equivalent to b modulo p.
A partition of a set is a disjoint family of sets , , such that .
Theorem: An equivalence relation on induces a unique partition of , and likewise, a partition induces a unique equivalence relation on , such that these are equivalent.
Proof: (Equivalence relation induces Partition): Let be the set of equivalence classes of . Then, since for each , . Furthermore, by the above theorem, this union is disjoint. Thus the set of equivalence relations of is a partition of .
(Partition induces Equivalence relation): Let be a partition of . Then, define on such that if and only if both and are elements of the same for some . Reflexivity and symmetry of is immediate. For transitivity, if and for the same , we necessarily have , and transitivity follows. Thus, is an equivalence relation with as the equivalence classes.
Lastly obtaining a partition from on and then obtaining an equivalence equation from obviously returns again, so and are equivalent structures.
Let be an equivalence relation on a set . Then, define the set as the set of all equivalence classes of . In order to say anything interesting about this construction we need more theory yet to be developed. However, this is one of the most important constructions we have, and one that will be given much attention throughout the book.
As you see in the definition of a function above, the domain and codomain are an integral part of the definition. In other words, even if the values of don't change, changing the domain or codomain changes the function.
Let's look at the following four functions.
is neither injective nor surjective (these terms will be defined later).
is not injective but surjective.
is injective but not surjective.
is injective and surjective
As you see, all four functions have the same mapping but all four are different. That's why just giving the mapping is insufficient; a function is only defined if its domain and codomain are known.
Note that the image and preimage are written respectively like and its inverse (if it exists). There is however no ambiguity because the domains are different. Note also that the image and preimage are not necessarily inverse of one another. (See the section on bijective functions below).
Lemma: Consider a function and suppose . Then is injective if and only if there exists a function with .
Suppose is injective. As let's define as an arbitrary element of . We can then define a suitable function as follows:
It is now easy to verify that .
Suppose there is a function with . Then . is thus injective.
Definition: A function is surjective if
Lemma: Consider a function . Then is surjective if and only if there exists a function with .
Suppose is surjective. We can define a suitable function as follows:
It is now easy to verify that .
Suppose there is a function with . Then . Then . is thus surjective.
Definition: A function is bijective if
it is both injective and surjective.
Lemma: A function is bijective if and only if there exists a function with and . Furthermore it can be shown that such a is unique. We write it and call it the inverse of .
Left as an exercise.
Proposition: Consider a function . Then
is injective iff
is surjective iff
is bijective iff the image and preimage of are inverse of each other
Example: If and are sets such that , there exists an obviously injective function , called the inclusion , such that for all .
Example: If is an equivalence relation on a set , there is an obviously surjective function , called the canonical projection onto , such that for all .
Theorem: Define the equivalence relation on such that if and only if . Then, if is any function, decomposes into the composition
where is the canonical projection, is the inclusion , and is the bijection for all .
Proof: The definition of immediately implies that , so we only have to prove that is well defined and a bijection. Let . Then . This shows that the value of is independent of the representative chosen from , and so it is well-defined.
For injectivity, we have , so is injective.
For surjectivity, let . Then there exists an such that , and so by definition of . Since is arbitrary in , this proves that is surjective.
Definition: Given a function , is a
(i) Monomorphism if given any two functions such that , then .
(ii) Epimorphism if given any two functions such that , then .
Theorem: A function between sets is
(i) a monomorphism if and only if it is injective.
(ii) an epimorphism if and only if it is surjective.
Proof: (i) Let be a monomorphism. Then, for any two functions , for all . This is the definition if injectivity. For the converse, if is injective, it has a left inverse . Thus, if for all , compose with on the left side to obtain , such that is a monomorphism.
(ii) Let be an epimorphism. Then, for any two functions , for all and . Assume , that is, that is not surjective. Then there exists at least one not in . For this choose two functions which coincide on but disagree on . However, we still have for all . This violates our assumption that is an epimorphism. Consequentally, is surjective. For the converse, assume is surjective. Then the epimorphism property immediately follows.
Remark: The equivalence between monomorphism and injectivity, and between epimorphism and surjectivity is a special property of functions between sets. This not the case in general, and we will see examples of this when discussing structure-preserving functions between groups or rings in later sections.
Example: Given any two sets and , we have the canonical projections sending to , and sending to . These maps are obviously surjective.
In addition, we have the natural inclusions and which are obviously injective as stated above.
The projections and inclusions described above are special, in that they satisfy what are called universal properties. We will give the theorem below. The proof is left to the reader.
Theorem: Let be any sets.
(i) Let and . Then there exists a unique function such that and are simultaneously satisfied. is sometimes denoted .
(ii) Let and . Then there exists a unique function such that and are simultaneously satifsied.
The canonical projections onto quotients also satisfy a universal property.
Theorem: Define the equivalence relation on and let be any function such that for all . Then there exists a unique function such that , where is the canonical projection.
The text in its current form is incomplete.
A binary operation on a set is a function . For , we usually write as . The property that for all is called closure under .
Example: Addition between two integers produces an integer result. Therefore addition is a binary operation on the integers. Whereas division of integers is an example of an operation that is not a binary operation. is not an integer, so the integers are not closed under division.
To indicate that a set has a binary operation defined on it, we can compactly write . Such a pair of a set and a binary operation on that set is collectively called a binary structure. A binary structure may have several interesting properties. The main ones we will be interested in are outlined below.
Definition: A binary operation on is associative if for all , .
Example: Addition of integers is associative: . Notice however, that subtraction is not associative. Indeed, .
Definition: A binary operation on is commutative is for all , .
Example: Multiplication of rational numbers is commutative: . Notice that division is not commutative: while . Notice also that commutativity of multiplication depends on the fact that multiplication of integers is commutative as well.
The reader is expected to have some familiarity with linear algebra. For example, statements such as
Given vector spaces and with bases and and dimensions and , respectively, a linear map corresponds to a unique matrix, dependent on the particular choice of basis.
should be familiar. It is impossible to give a summary of the relevant topics of linear algebra in one section, so the reader is advised to take a look at the linear algebra book.
In any case, the core of linear algebra is the study of linear functions, that is, functions with the property , where greek letters are scalars and roman letters are vectors.
The core of the theory of finitely generated vector spaces is the following:
Every finite-dimensional vector space is isomorphic to for some field and some , called the dimension of . Specifying such an isomorphism is equivalent to choosing a basis for . Thus, any linear map between vector spaces with dimensions and and given bases and induces a unique linear map . These maps are precisely the matrices, and the matrix in question is called the matrix representation of relative to the bases .
Remark: The idea of identifying a basis of a vector space with an isomorphism to may be new to the reader, but the basic principle is the same.
As numbers of various number systems form basic units with which one must work when studying abstract algebra, we will now define the natural numbers and the rational integers as well as the basic operations of addition and multiplication. Using these definitions, we will also derive important properties of these number sets and operations. Following this, we will discuss important concepts in number theory; this will lead us to discussion of the properties of the integers modulo n.
Definition: Using the undefined notions "1" and "successor" (denoted by ), we define the set of natural numbers without zero , hereafter referred to simply as the natural numbers, with the following axioms, which we call the Peano postulates:
We can prove theorems for natural numbers using mathematical induction as a consequence of the fifth Peano Postulate.
Definition: We recursively define addition for the natural numbers as a composition using two more axioms; the other properties of addition can subsequently be derived from these axioms. We denote addition with the infix operator +.
Axiom 6 above relies on the first Peano postulate (for the existence of 1) as well as the second (for the existence of a successor for every number).
Henceforth, we will assume that proven theorems hold for all in .
The set of integers can be constructed from ordered pairs of natural numbers (a, b). We define an equivalence relation on the set of all such ordered pairs such that
Then the set of rational integers is the set of all equivalence classes of such ordered pairs. We will denote the equivalence class of which some pair (a, b) is a member with the notation [(a, b)]. Then, for any natural numbers a and b, [(a, b)] represents a rational integer.
Definition: Multiplication for the integers, like addition, can be defined with a single axiom:
Again, using this definition and the previously-proven properties of natural numbers, it can be shown that integer multiplication is commutative and associative, and furthermore that it is both left- and right-distributive with respect to integer addition.
The text in its current form is incomplete.
In this section we will begin to make use of the definitions we made in the section about binary operations. In the next few sections, we will study a specific type of binary structure called a group. First, however, we need some preliminary work involving a less restrictive type of binary structure.
Definition 1: A monoid is a binary structure satisfying the following properties:
(i) for all . This is defined as associativity.
(ii) There exists an identity element such that for all .
Now we have our axioms in place, we are faced with a pressing question; what is our first theorem going to be? Since the first few theorems are not dependent on one another, we simply have to make an arbitrary choice. We choose the following:
Theorem 2: The identity element of is unique.
Proof: Assume and are both identity elements of . Then both satisfy condition (ii) in the definition above. In particular, , proving the theorem. ∎
This theorem will turn out to be of fundamental importance later when we define groups.
Theorem 3: If are elements of for some , then the product is unambiguous.
Proof: We can prove this by induction. The cases for and are trivially true. Assume that the statement is true for all . For , the product , inserting parentheses, can be "partitioned" into . Both parts of the product have a number of elements less than and are thus unambiguous. The same is true if we consider a different "partition", , where . Thus, we can unambiguously compute the products , , and , and rewrite the two "partitions" as and . These equal each other by the definition of a monoid.∎
This is about as far as we are going to take the idea of a monoid. We now proceed to groups.
Definition 4: A group is a monoid that also satisfies the property
(iii) For each , there exists an element such that .
Such an element is called an inverse of . When the operation on the group is understood, we will conveniently refer to as . In addition, we will gradually stop using the symbol for multiplication when we are dealing with only one group, or when it is understood which operation is meant, instead writing products by juxtaposition, .
Remark 5: Notice how this definition depends on Theorem 2 to be well defined. Therefore, we could not state this definition before at least proving uniqueness of the identity element. Alternatively, we could have included the existence of a distinguished identity element in the definition. In the end, the two approaches are logically equivalent.
Also note that to show that a monoid is a group, it is sufficient to show that each element has either a left-inverse or a right-inverse. Let , let be a right-inverse of , and let be a right-inverse of . Then, . Thus, any right-inverse is also a left-inverse, or . A similar argument can be made for left-inverses.
Theorem 6: The inverse of any element is unique.
Proof: Let and let and be inverses of . Then, . ∎
Thus, we can speak of the inverse of an element, and we will denote this element by . We also observe this nice property:
Proof: This follows immediately since .
The next couple of theorems may appear obvious, but in the interest of keeping matters fairly rigorous, we allow ourselves to state and prove seemingly trivial statements.
Theorem 8: Let be a group and . Then .
Proof: The result follows by direct computation: . ∎
Theorem 9: Let . Then, if and only if . Also, if and only if .
Proof: We will prove the first assertion. The second is identical. Assume . Then, multiply on the left by to obtain . Secondly, assume . Then, multiply on the left by to obtain . ∎
Theorem 10: The equation has a unique solution in for any .
Proof: We must show existence and uniqueness. For existence, observe that is a solution in . For uniqueness, multiply both sides of the equation on the left by to show that this is the only solution. ∎
Notation: Let be a group and . We will often encounter a situation where we have a product . For these situations, we introduce the shorthand notation if is positive, and if is negative. Under these rules, it is straightforward to show and and for all .
Definition 11: (i) The order of a group , denoted or , is the number of elements of if is finite. Otherwise is said to be infinite.
(ii) The order of an element of , similarly denoted or , is defined as the lowest positive integer such that if such an integer exists. Otherwise is said to be infinite.
Theorem 12: Let be a group and . Then .
Proof: Let the order of be . Then, , being the smallest positive integer such that this is true. Now, multiply by on the left and on the right to obtain implying . Thus, we have shown that . A similar argument in the other direction shows that . Thus, we must have , proving the theorem. ∎
Corollary 13: Let be a group with . Then, .
Proof: By Theorem 12, we have that . ∎
Theorem 14: An element of a group not equal to the identity has order 2 if and only if it is its own inverse.
Proof: Let have order 2 in the group . Then, , so by definition, . Now, assume and . Then . Since , 2 is the smallest positive integer satisfying this property, so has order 2. ∎
Definition 15: Let be a group such that for all , . Then, is said to be commutative or abelian.
When we are dealing with an abelian group, we will sometimes use so-called additive notation, writing for our binary operation and replacing with . In such cases, we only need to keep track of the fact that is an integer while is a group element. We will also talk about the sum of elements rather than their product.
Abelian groups are in many ways nicer objects than general groups. They also admit more structure where ordinary groups do not. We will see more about this later when we talk about structure-preserving maps between groups.
Definition 16: Let be a group. A subset is called a generating set for if every element in can be written in terms of elements in . We write .
Now that we have our definitions in place and have a small arsenal of theorems, let us look at three (really, two and a half) important families of groups.
We will now show a convenient way of representing a group structure, or more precisely, the multiplication rule on a set. This notion will not be limited to groups only, but can be used for any structure with any number of operations. As an example, we give the group multiplication table for the Klein 4-group. The multiplication table is structured such that is represented by the element in the "-position", that is, in the intersection of the -row and the -column.
This next group is for the group of integers under addition modulo 4, called . We will learn more about this group later.
We can clearly see that and are "different" groups. There is no way to relabel the elements such that the multiplication tables coincide. There is a notion of "equality" of groups that we have not yet made precise. We will get back to this in the section about group homomorphisms.
The reader might have noticed that each row in the group table features each element of the group exactly once. Indeed, assume that an element appeared twice in some row of the multiplication table for . Then there would exist such that , implying and contradicting the assumption of appearing twice. We state this as a theorem:
Theorem 17: Let be a group and . Then .
Using this, the reader can use a multiplication table to find all groups of order 3. He/she will find that there is only one possibility.
Problem 1: Show that , the set of matrices with real entries, forms a group under the operation of matrix addition.
Problem 2: Let be vector spaces and be the set of linear maps from to . Show that forms an abelian group by defining .
Problem 3: Let be generated by the elements such that , and . Show that forms a group. This group is called the group of quaternions, and is a 4-dimensional version of the complex numbers. Are any of the conditions above redundant?
Problem 4: Let be any nonempty set and consider the set . Show that has a natural group structure.
is the set of functions . Let and define the binary operation for all . Then is a group with identity such that for all and inverses for all .∎
Problem 5: Let be a group with two distinct elements and , both of order 2. Show that has a third element of order 2.
We consider first the case where . Then and is distinct from and . If , then and is distinct from and . ∎
Problem 6: Let be a group with one and only one element of order 2. Show that .
Since the product of two elements generally depends on the order in which we multiply them, the stated product is not necessarily well-defined. However, it works out in this case.
Since every element of appears once in the product, for every element , the inverse of must appear somewhere in the product. That, is, unless in which case is its own inverse by Theorem 14. Now, applying Corollary 13 to the product shows that its order is that same as the order of the product of all elements of order 2 in . But there is only one such element, , so the order of the product is 2. Since the only element in having order 2 is , the equality follows. ∎
We are about to witness a universal aspect of mathematics. That is, whenever we have any sort of structure, we ask ourselves: does it admit substructures? In the case of groups, the answer is yes, as we will immediately see.
Definition 1: Let be a group. Then, if is a subset of which is a group in its own right under t