Sets
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
.
The axiom of extensionalityEdit
Using this notation and the symbol
, which represents logical implication, we can restate the definition of equality for two sets
and
as follows:
if and only if
and
.
This is known as the axiom of extensionality.
Comprehensive notationEdit
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
.
Set inclusionEdit
For two sets
and
, we define set inclusion as follows:
is included in, or a subset of,
, if and only if every member of
is a member of
. In other words,

where the symbol
denotes "is a subset of", and
denotes "if and only if".
By the aforementioned axiom of extensionality, one finds that
.
The empty setEdit
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.
Proper set inclusionEdit
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.
Cardinality of setsEdit
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.
Set intersectionEdit
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
.
In the case of
one can either write
or
.
Set unionEdit
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
.
Distributive lawsEdit
Set union and set intersection are distributive with respect to each other. That is,
and
.
Cartesian productEdit
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.
Disjoint unionEdit
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
.
Set differenceEdit
The set difference, or relative set complement, of sets
and
, denoted by
, is the set of elements contained in
which are not contained in
. Symbolically,
.
By the definition of set difference,
.
The following identities hold for any sets
:
,
,
,
,
,
,
,
,
.
The set difference of two Cartesian products can be found as
.
The universal set and set complementsEdit
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:
,
- Complement properties:
,
,
,
,
.
The set complement can be related to the set difference with the identities
and
.
Symmetric differenceEdit
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
or 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:
.
Notation for specific setsEdit
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: 
Integers: 
Rational numbers: 
Real numbers: 
Complex numbers:
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.
Equivalence relationsEdit
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.
Proof:
- 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
.
Q.E.D.
Remark. In elementary number theory we denote this relation
and say a is equivalent to b modulo p.
Equivalence classesEdit
Let
be an equivalence relation on
. Then, for any element
we define the equivalence class of
as the subset
given by
![\left[a\right]=\left\{b\in X|a\sim b\right\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25b76ff0a2e8dd26a7da129e97e071c71527b324)
Theorem:
Proof: Assume
. Then by definition,
.
- We first prove that
. Let
be an arbitrary element of
. Then
by definition of the equivalence class, and
by transitivity of equivalence relations. Thus,
and
.
- We now prove that
Let
be an arbitrary element of
. Then, by definition
. By transitivity,
, so
. Thus,
and
.
As
and as
, we have
.
Q.E.D.
Partitions of a setEdit
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.
Q.E.D.
QuotientsEdit
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.
Functions
DefinitionEdit
A function
is a triplet
such that:
is a set, called the domain of 
is a set, called the codomain of 
is a subset of
, called the graph of 
In addition the following two properties hold:
.
.
we write
for the unique
such that
.
We say that
is a function from
to
, which we write:

Let's consider the function from the reals to the reals which squares its argument. We could define it like this:


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.
The function:


is neither injective nor surjective (these terms will be defined later).
The function:


is not injective but surjective.
The function:


is injective but not surjective.
The function:


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.
Image and preimageEdit
For a set
, we write
for the set of subsets of
.
Let
. We will now define two related functions.
The image function:

The preimage function:

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).
We define
, which we call the image of
.
For any
, we call
the support of
.
Proposition: Let
. Then


Let's take again the function:


Let's consider the following examples:



Further definitionsEdit
Let
and
. We define
by
, which we call the composition of
and
.
Let
be a set. We define the identity function on A as

PropertiesEdit
Definition: A function
is injective if

Lemma: Consider a function
and suppose
. Then
is injective if and only if there exists a function
with
.
Proof:
:
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.
Q.E.D.
Definition: A function
is surjective if

Lemma: Consider a function
. Then
is surjective if and only if there exists a function
with
.
Proof:
:
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.
Q.E.D.
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
.
Proof:
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.
Q.E.D.
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 assumtion that
is an epimorphism. Consequentally,
is surjective. For the converse, assume
is surjective. Then the epimorphism property immediately follows.
Q.E.D.
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.
Universal propertiesEdit
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.
Binary Operations
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.
- Of the four arithmetic operations, addition, subtraction, multiplication, and division, which are associative? commutative and identity?
operation |
associative |
commutative
|
Addition |
yes |
yes
|
Multiplication |
yes |
yes
|
Subtraction |
No |
No
|
Division |
No |
No
|
Linear Algebra
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 presicely 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.
Number Theory
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.
The Peano postulates and the natural numbersEdit
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:
- Axiom 1.

- Axiom 2.

- Axiom 3.

- Axiom 4.

- Axiom 5.

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.

- Axiom 7.

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
.
MultiplicationEdit
Definition: We similarly define multiplication for the natural numbers recursively, again using two axioms:
- Axiom 8.

- Axiom 9.

Properties of additionEdit
We start by proving that addition is associative.
Theorem 1: Associativity of addition:
Proof: Base case: By axioms 6 and 7,
.
- By axiom 6,
.
- Inductive hypothesis: Suppose that, for
,
.
- Inductive step: By axiom 7,
.
- By the inductive hypothesis,
.
- By axiom 7,
.
- By axiom 7,
.
- By induction,
. QED.
Lemma 1:
Proof: Base case: 1+1=1+1.
- Inductive hypothesis: Suppose that, for
,
.
- Inductive step: By axiom 6,
.
- By the inductive hypothesis,
.
- By theorem 1,
.
- By axiom 6,
.
- By induction,
. QED.
Theorem 2: Commutativity of addition:
Proof: Base case: By lemma 1,
.
- Inductive hypothesis: Suppose that, for
,
.
- By axiom 6,
.
- By theorem 1,
.
- By the inductive hypothesis,
.
- By theorem 1,
.
- By lemma 1,
.
- By theorem 1,
.
- By axiom 6,
.
- By induction,
. QED.
Theorem 3:
.
Proof: Base case: Suppose
.
- By theorem 2,
.
- By axiom 6,
.
- By axiom 4,
.
- Inductive hypothesis: Suppose that, for
,
.
- Inductive step: Suppose
.
- By axiom 6,
.
- By theorem 2,
.
- By theorem 1,
.
- By the base case,
. Thus,
.
- By the inductive hypothesis,
.
- By induction,
. QED.
Properties of multiplicationEdit
Theorem 4: Left-distributivity of multiplication over addition:
.
Proof: Base case: By axioms 6 and 9,
.
- By axiom 8,
.
- Inductive hypothesis: Suppose that, for
,
.
- Inductive step: By axiom 7,
.
- By axiom 9,
.
- By the inductive hypothesis,
.
- By theorem 1,
.
- By axiom 9,
.
- By induction,
. QED.
Theorem 5:
.
Proof: Base case: By axiom 8, 1(1)=1.
- Inductive hypothesis: Suppose that, for
,
.
- Inductive step: By axiom 6,
.
- By theorem 4,
.
- By the base case,
.
- By the inductive hypothesis,
.
- By axiom 6,
.
- By induction,
. QED.
Theorem 6:
.
Proof: Base case: By axiom 8,
.
- By axiom 6,
.
- By axiom 8,
.
- Inductive hypothesis: Suppose that,
,
.
- Inductive step: By axiom 9,
.
- By the inductive hypothesis,
.
- By axiom 6,
.
- By theorem 1,
.
- By theorem 2,
.
- By theorem 1,

- By axiom 9,
.
- By theorem 1,
.
- By axiom 6,
.
- By induction,
. QED.
Theorem 7: Associativity of multiplication:
Proof: Base case: By axiom 8,
.
- Inductive hypothesis: Suppose that, for
,
.
- Inductive step: By axiom 9,
.
- By the inductive hypothesis,
.
- By theorem 4,
.
- By axiom 9,
.
- By induction,
. QED.
Theorem 8: Commutativity of multiplication:
.
Proof: Base case: By axiom 8 and theorem 5,
.
- Inductive hypothesis: Suppose that, for
,
.
- Inductive step: By axiom 9,
.
- By the inductive hypothesis,
.
- By theorem 6,
.
- By induction,
. QED.
Theorem 9: Right-distributivity of multiplication over addition:
.
Proof: By theorems 4 and 7,
.
- By theorem 7,
. QED.
The integersEdit
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.
Integer additionEdit
Definition: We define addition for the integers as follows:
![{\displaystyle \left[(a,b)\right]+\left[(c,d)\right]=\left[(a+c,b+d)\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/812c01093f785b1a4a8498d59f0a56f519a8aa36)
Using this definition and the properties for the natural numbers, one can prove that integer addition is both associative and commutative.
Integer multiplicationEdit
Definition: Multiplication for the integers, like addition, can be defined with a single axiom:
![{\displaystyle \left[(a,b)\right]\left[(c,d)\right]=\left[(ac+bd,ad+bc)\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f38fdd89ae78edac7e1dca425b610abad4921eb)
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.
Group Theory/Group
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
.
- (ii) There exists an element
such that
for all
.
The element
in (ii) is called an identity element of
.
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:
Corollary 7:
.
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.
Multiplication tablesEdit
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.
Problem 5: Let
be a group with two distinct elements
and
, both of order 2. Show that
has a third element of order 2.
Problem 6: Let
be a group with one and only one element
of order 2. Show that
.
Answer
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. ∎
Group Theory/Subgroup
SubgroupsEdit
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 