Abstract Algebra/Printable version

Abstract Algebra

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Abstract_Algebra

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.

Sets

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 $x$ and a set $A$, we can say either $x\in A$, that is, $x$ is contained in $A$, or $x\not \in A$, that is, $x$ is not contained in $A$. To state that multiple elements $a,b,c,\ldots ,n$ are contained in $A$, we write $a,b,c,\ldots ,n\in A$.

The axiom of extensionality

Using this notation and the symbol $\rightarrow$, which represents logical implication, we can restate the definition of equality for two sets $A$ and $B$ as follows:

$A=B$ if and only if $x\in A\rightarrow x\in B$ and $x\in B\rightarrow x\in A$.

This is known as the axiom of extensionality.

Comprehensive notation

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 $x$ with some property $Q(x)$ can be denoted by $\{x:Q(x)\}$. Similarly, the set of all elements $x$ of a set $A$ with some property $Q(x)$ can be denoted by $\{x\in A:Q(x)\}$. 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 $\mathbb {Z} =\{x:x{\text{ is an integer}}\}$, and the set of even integers can be written as $\{x\in \mathbb {Z} :x{\text{ is even}}\}$.

Set inclusion

For two sets $A$ and $B$, we define set inclusion as follows: $A$ is included in, or a subset of, $B$, if and only if every member of $A$ is a member of $B$. In other words,

$A\subseteq B\Leftrightarrow x\in A\rightarrow x\in B$

where the symbol $\subseteq$ denotes "is a subset of", and $\Leftrightarrow$ denotes "if and only if".

By the aforementioned axiom of extensionality, one finds that $A=B\Leftrightarrow A\subseteq B{\mbox{ and }}B\subseteq A$.

The empty set

One can define an empty set, written $\varnothing$, such that $\forall x(x\not \in \varnothing )$, where $\forall$ 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 inclusion

For two sets $A$ and $B$, we can define proper set inclusion as follows: $A$ is a proper subset of $B$ if and only if $A$ is a subset of $B$, and $A$ does not equal $B$. In other words, there is at least one member in $B$ not contained in $A$

$A\subset B\Leftrightarrow (A\subseteq B\land A\neq B)$,

where the symbol $\subset$ denotes "is a proper subset of" and the symbol $\land$ denotes logical and.

Cardinality of sets

The cardinality of a set $A$, denoted by $|A|$, can be said informally to be a measure of the number of elements in $A$. However, this description is only rigorously accurate for finite sets. To find the cardinality of infinite sets, more sophisticated tools are needed.

Set intersection

For sets $A$ and $B$, we define the intersection of $A$ and $B$ by the set $A\cap B$ which contains all elements which are common to both $A$ and $B$. Symbolically, this can be stated as follows:

$A\cap B=\{x\mid x\in A{\mbox{ and }}x\in B\}$.

Because every element of $A\cap B$ is an element of $A$ and an element of $B$, $A\cap B$ is, by the definition of set inclusion, a subset of $A$ and $B$.

If the sets $A$ and $B$ have no elements in common, they are said to be disjoint sets. This is equivalent to the statement that $A$ and $B$ are disjoint if $A\cap B=\emptyset$.

Set intersection is an associative and commutative operation; that is, for any sets $A$, $B$, and $C$, $(A\cap B)\cap C=A\cap (B\cap C)$ and $A\cap B=B\cap A$.

By the definition of intersection, one can find that $A\cap \emptyset =\emptyset$ and $A\cap A=A$. Furthermore, $A\subseteq B\Leftrightarrow A\cap B=A$.

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 $A_{i}$ are sets for every $i\in I$, we can denote the intersection of all $A_{i}$ by

$\bigcap _{i\in I}A_{i}=\{x\mid (\forall i\in I)x\in A_{i}\}$

In cases like this, $I$ is called an index set, and $A_{i}$ are said to be indexed by $I$.

In the case of $I=\{1,2,...,n\}$ one can either write $A_{1}\cap A_{2}\cap A_{3}\cap \cdots \cap A_{n}$ or

$\bigcap _{i=1}^{n}A_{i}$.

Set union

For sets $A$ and $B$, we define the union of $A$ and $B$ by the set $A\cup B$ which contains all elements which are in either $A$ or $B$ or both. Symbolically,

$A\cup B=\{x\mid x\in A{\mbox{ or }}x\in B\}$.

Since the union $A\cup B$ of sets $A$ and $B$ contains the elements of $A$ and $B$, $A\subseteq A\cup B$ and $B\subseteq A\cup B$.

Like set intersection, set union is an associative and commutative operation; for any sets $A$, $B$, and $C$, $(A\cup B)\cup C=A\cup (B\cup C)$ and $A\cup B=B\cup A$.

By the definition of union, one can find that $A\cup \emptyset =A\cup A=A$. Furthermore, $A\subseteq B\Leftrightarrow A\cup B=B$.

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 $A_{i}$ be sets for all $i\in I$. Then the union of all the $A_{i}$ is denoted by

$\bigcup _{i\in I}A_{i}=\{x\mid (\exists i\in I)x\in A_{i}\}$

(Where $\exists$ may be read as "there exists".)

For the union of a finite number of sets $A_{1},A_{2},A_{3},\ldots ,A_{n}$, that is, $I=\{1,2,...,n\}$ one can either write $A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n}$ or abbreviate this as

$\bigcup _{i=1}^{n}A_{i}$.

Distributive laws

Set union and set intersection are distributive with respect to each other. That is,

$A\cap (B\cup C)=(B\cup C)\cap A=(A\cap B)\cup (A\cap C)$ and

$A\cup (B\cap C)=(B\cap C)\cup A=(A\cup B)\cap (A\cup C)$.

Cartesian product

The Cartesian product of sets $A$ and $B$, denoted by $A\times B$, is the set of all ordered pairs which can be formed with the first object in the ordered pair being an element of $A$ and the second being an element of $B$. This can be expressed symbolically as

$A\times B=\{(x,y)\mid x\in A{\mbox{ and }}y\in B\}$.

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 $A,B,C,D$:

$(A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)$,

$(A\cup B)\times (C\cup D)=(A\times C)\cup (A\times D)\cup (B\times C)\cup (B\times D)$,

$A\times (B\cap C)=(A\times B)\cap (A\times C)$,

$A\times (B\cup C)=(A\times B)\cup (A\times C)$.

The Cartesian product of any set and the empty set yields the empty set; symbolically, for any set $A$, $A\times \emptyset =\emptyset \times A=\emptyset$.

The Cartesian product can easily be generalized to the n-ary Cartesian product, which is also denoted by $\times$. The n-ary Cartesian product forms ordered n-tuples from the elements of $n$ sets. Specifically, for sets $A_{1},A_{2},A_{3},\ldots ,A_{n}$,

$A_{1}\times A_{2}\times A_{3}\times \cdots \times A_{n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in A_{i}\}$.

This can be abbreviated as

$\prod _{i=1}^{n}A_{i}$.

In the n-ary Cartesian product, each $x_{i}$ is referred to as the $i$-th coordinate of $(x_{1},\ldots ,x_{n})$.

In the special case where all the factors are the same set $A$, we can generalize even further. Let $A^{\Omega }$ be the set of all functions $f\,:\,\Omega \rightarrow A$. Then, in analogy with the above, $A^{\Omega }$ is effectively the set of "$\Omega$-tuples" of elements in $A$, and for each such function $f$ and each $i\in \Omega$, we call $f(i)$ the $i$-th coordinate of $f$. As one might expect, in the simple case when $\Omega =\{1,2,...,n\}$ for an integer $n$, this construction is equivalent to $\prod _{i=1}^{n}A$, which we can abbreviate further as $A^{n}$. We also have the important case of $\Omega =\mathbb {N}$, giving rise to the set of all infinite sequences of elements of $A$, which we can denote by $A^{\infty }$. We will need this construction later, in particular when dealing with polynomial rings.

Disjoint union

Let $A$ and $B$ be any two sets. We then define their disjoint union, denoted $A\coprod B$ to be the following: First create copies $A^{\prime }$ and $B^{\prime }$ of $A$ and $B$ such that $A^{\prime }\cap B^{\prime }=\emptyset$. Then define $A\coprod B=A^{\prime }\cup B^{\prime }$. 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 $A\coprod B=(\{0\}\times A)\cup (\{1\}\times B)$.

Set difference

The set difference, or relative set complement, of sets $A$ and $B$, denoted by $A\setminus B$, is the set of elements contained in $A$ which are not contained in $B$. Symbolically,

$A\setminus B=\{x\mid x\in A{\mbox{ and }}x\not \in B\}$.

By the definition of set difference, $A\setminus B\subseteq A$.

The following identities hold for any sets $A,B,C$:

$A\setminus B=A\Leftrightarrow A\cap B=\emptyset$,

$A\setminus B=\emptyset \Leftrightarrow A\subseteq B$,

$A\setminus B=A\setminus C\Leftrightarrow A\cap B=A\cap C$,

$A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)$,

$A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$,

$A\setminus (B\setminus C)=(C\cap A)\cup (A\setminus B)$,

$A\setminus \emptyset =A$,

$A\setminus A=\emptyset$,

$\emptyset \setminus A=\emptyset$.

The set difference of two Cartesian products can be found as $(A\times B)\setminus (C\times D)=[A\times (B\setminus D)]\cup [(A\setminus C)\times B]$.

The universal set and set complements

We define some arbitrary set $U$ for which every set under consideration is a subset of $U$ 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 $A\subseteq U$, the complement of $A$ is given by $A^{C}=U\setminus A$. The following identities involving set complements hold true for any sets $A$ and $B$:

De Morgan's laws for sets:

$(A\cup B)^{C}=A^{C}\cap B^{C}$,

$(A\cap B)^{C}=A^{C}\cup B^{C}$,

Double complement law:

$A^{CC}=A$,

Complement properties:

$A\cup A^{C}=U$,

$A\cap A^{C}=\emptyset$,

$\emptyset ^{C}=U$,

$U^{C}=\emptyset$,

$A\subseteq B\rightarrow B^{C}\subseteq A^{C}$.

The set complement can be related to the set difference with the identities $A\setminus B=A\cap B^{C}$ and $(A\setminus B)^{C}=A^{C}\cup B$.

Symmetric difference

For sets $A$ and $B$, the symmetric set difference of $A$ and $B$, denoted by $A\bigtriangleup B$ or by $A\ominus B$, is the set of elements which are contained either in $A$ or in $B$ but not in both of them. Symbolically, it can be defined as

$A\bigtriangleup B=\{x:(x\in A)\oplus (x\in B)\}.$

More commonly, it is represented as

$A\bigtriangleup B=(A\setminus B)\cup (B\setminus A)$ or as

$A\bigtriangleup B=(A\cup B)\setminus (A\cap B)$.

The symmetric difference is commutative and associative so that $A\bigtriangleup B=B\bigtriangleup A$ and $(A\bigtriangleup B)\bigtriangleup C=A\bigtriangleup (B\bigtriangleup C)$. Every set is its own symmetric-difference inverse, and the empty set functions as an identity element for the symmetric difference, that is, $A\bigtriangleup A=\emptyset$ and $A\bigtriangleup \emptyset =A$. Furthermore, $A\bigtriangleup B=\emptyset$ if and only if $A=B$.

Set intersection is distributive over the symmetric difference operation. In other words, $A\cap (B\bigtriangleup C)=(A\cap B)\bigtriangleup (A\cap C)$.

The symmetric difference of two set complements is the same as the symmetric difference of the two sets: $A^{C}\bigtriangleup B^{C}=A\bigtriangleup B$.

Notation for specific 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: $\mathbb {N} _{0}=\{0,1,2,\ldots \}$ or $\mathbb {N} =\{0,1,2,\ldots \}$
Natural numbers without 0: $\mathbb {N} ^{*}=\{1,2,3,\ldots \}$
Integers: $\mathbb {Z} =\{0,\pm 1,\pm 2,\ldots \}$
Rational numbers: $\mathbb {Q} =\left\{{\frac {p}{q}}:p\in \mathbb {Z} {\mbox{ and }}q\in \mathbb {N} ^{*}\right\}$
Real numbers: $\mathbb {R}$
Complex numbers: $\mathbb {C}$

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 $\geq$ 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 $X$ and $Y$ so that, for a relation $R$, $R\subseteq X\times Y$. In this case, $X$ is referred to as the domain of the relation and $Y$ is referred to as its codomain. If an ordered pair $(x,y)$ is an element of $R$ (where, by the definition of $R$, $x\in X$ and $y\in Y$), then we say that $x$ is related to $y$ by $R$. We will use $R(x)$ to denote the set

$\{y\in Y:(x,y)\in R\}$.

In other words, $R(x)$ is used to denote the set of all elements in the codomain of $R$ to which some $x$ in the domain is related.

Equivalence relations

To denote that two elements $x$ and $y$ are related for a relation $R$ which is a subset of some Cartesian product $X\times X$, we will use an infix operator. We write $x\sim y$ for some $x,y\in X$ and $(x,y)\in R$.

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 $\geq$ operator, we know that for any two integers $m,n\in Z$ exactly one of $m\geq n$ or $n>m$ 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 $R\subseteq X\times X$ is reflexive if $a\sim a$ for all $a\in X$.
• Symmetry: A relation $R\subseteq X\times X$ is symmetric if ${a\sim b}\implies {b\sim a}$ for all $a,b\in X$.
• Transitivity: A relation $R\subseteq X\times X$ is transitive if ${{a\sim b}\wedge {b\sim c}}\implies {a\sim c}$ for all $a,b,c\in X$.

One should note that in all three of these properties, we quantify across all elements of the set $X$.

Any relation $R\subseteq X\times X$ which exhibits the properties of reflexivity, symmetry and transitivity is called an equivalence relation on $X$. Two elements related by an equivalence relation are called equivalent under the equivalence relation. We write $a\sim _{R}b$ to denote that $a$ and $b$ are equivalent under $R$. If only one equivalence relation is under consideration, we can instead write simply $a\sim b$. As a notational convenience, we can simply say that $\sim$ is an equivalence relation on a set $X$ and let the rest be implied.

Example: For a fixed integer $p$, we define a relation $\sim _{p}$ on the set of integers such that $a\sim _{p}b$ if and only if $a-b=kp$ for some $k\in Z$. Prove that this defines an equivalence relation on the set of integers.

Proof:

• Reflexivity: For any $a\in X$, it follows immediately that $a-a=0=0p$, and thus $a\sim _{p}a$ for all $a\in G$.
• Symmetry: For any $a,b\in X$, assume that $a\sim _{p}b$. It must then be the case that $a-b=kp$ for some integer $k$, and $b-a=(-k)p$. Since $k$ is an integer, $-k$ must also be an integer. Thus, ${a\sim _{p}b}\implies {b\sim _{p}a}$ for all $a,b\in G$.
• Transitivity: For any $a,b,c\in X$, assume that $a\sim _{p}b$ and $b\sim _{p}c$. Then $a-b=k_{1}p$ and $b-c=k_{2}p$ for some integers $k_{1},k_{2}$. By adding these two equalities together, we get ${(a-b)+(b-c)=(k_{1}p)+(k_{2}p)}\Leftrightarrow {a-c=(k_{1}+k_{2})p}$, and thus $a\sim _{p}c$.

Q.E.D.

Remark. In elementary number theory we denote this relation $a\equiv b({\text{mod }}p)$ and say a is equivalent to b modulo p.

Equivalence classes

Let $\sim$ be an equivalence relation on $X$. Then, for any element $a\in X$ we define the equivalence class of $a$ as the subset $\left[a\right]\subseteq X$ given by

$\left[a\right]=\left\{b\in X|a\sim b\right\}$

Theorem: $b\in \left[a\right]\implies \left[b\right]=\left[a\right]$

Proof: Assume $b\in \left[a\right]$. Then by definition, $a\sim b$.

• We first prove that $\left[b\right]\subseteq \left[a\right]$. Let $p$ be an arbitrary element of $\left[b\right]$. Then $p\sim b$ by definition of the equivalence class, and $p\sim a$ by transitivity of equivalence relations. Thus, ${p\in \left[b\right]}\implies {p\in \left[a\right]}$ and $\left[b\right]\subseteq \left[a\right]$.
• We now prove that $\left[a\right]\subseteq \left[b\right]$ Let $q$ be an arbitrary element of $\left[a\right]$. Then, by definition $q\sim a$. By transitivity, $q\sim b$, so $q\in \left[b\right]$. Thus, ${q\in \left[a\right]}\implies {q\in \left[b\right]}$ and $\left[a\right]\subseteq \left[b\right]$.

As $\left[a\right]\subseteq \left[b\right]$ and as $\left[b\right]\subseteq \left[a\right]$, we have $\left[b\right]=\left[a\right]$.

Q.E.D.

Partitions of a set

A partition of a set $X$ is a disjoint family of sets $X_{i}$, $i\in I$, such that $\bigcup _{i\in I}X_{i}=X$.

Theorem: An equivalence relation $\sim$ on $X$ induces a unique partition of $X$, and likewise, a partition induces a unique equivalence relation on $X$, such that these are equivalent.

Proof: (Equivalence relation induces Partition): Let $P$ be the set of equivalence classes of $\sim$. Then, since $a\in [a]$ for each $a\in X$, $\cup P=X$. Furthermore, by the above theorem, this union is disjoint. Thus the set of equivalence relations of $\sim$ is a partition of $X$.

(Partition induces Equivalence relation): Let $X_{i}\,,\,i\in I$ be a partition of $X$. Then, define $\sim$ on $X$ such that $a\sim b$ if and only if both $a$ and $b$ are elements of the same $X_{i}$ for some $i\in I$. Reflexivity and symmetry of $\sim$ is immediate. For transitivity, if $a,b\in X_{i}$ and $b,c\in X_{i}$ for the same $i\in I$, we necessarily have $a,c\in X_{i}$, and transitivity follows. Thus, $\sim$ is an equivalence relation with $X_{i}\,,\,i\in I$ as the equivalence classes.

Lastly obtaining a partition $P$ from $\sim$ on $X$ and then obtaining an equivalence equation from $P$ obviously returns $\sim$ again, so $\sim$ and $P$ are equivalent structures.

Q.E.D.

Quotients

Let $\sim$ be an equivalence relation on a set $X$. Then, define the set $X/\sim$ as the set of all equivalence classes of $X$. 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

Definition

A function $\operatorname {f}$ is a triplet $(A,B,G)$ such that:

• $A$ is a set, called the domain of $\operatorname {f}$
• $B$ is a set, called the codomain of $\operatorname {f}$
• $G$ is a subset of $A\times B$, called the graph of $\operatorname {f}$

In addition the following two properties hold:

1. $\forall x\in A,\exists y\in B\mid (x,y)\in G$.
2. $\forall x\in A,y\in B,y'\in B{\mbox{, then }}(x,y)\in G{\mbox{ and }}(x,y')\in G\Rightarrow y=y'$.

$\forall x\in A$ we write $\operatorname {f} (x)$ for the unique $y\in B$ such that $(x,y)\in G$.

We say that $\operatorname {f}$ is a function from $A$ to $B$, which we write:

$\operatorname {f} :A\rightarrow B$

Example

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

$\operatorname {f} :\mathbb {R} \rightarrow \mathbb {R}$

$\operatorname {f} :x\mapsto x^{2}$

Remark

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 $\operatorname {f} (x)$ don't change, changing the domain or codomain changes the function.

Let's look at the following four functions.

The function:

$\operatorname {f_{1}} :\mathbb {R} \rightarrow \mathbb {R}$

$\operatorname {f_{1}} :x\mapsto x^{2}$

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

The function:

$\operatorname {f_{2}} :\mathbb {R} \rightarrow \mathbb {R} _{\geq 0}$

$\operatorname {f_{2}} :x\mapsto x^{2}$

is not injective but surjective.

The function:

$\operatorname {f_{3}} :\mathbb {R} _{\geq 0}\rightarrow \mathbb {R}$

$\operatorname {f_{3}} :x\mapsto x^{2}$

is injective but not surjective.

The function:

$\operatorname {f_{4}} :\mathbb {R} _{\geq 0}\rightarrow \mathbb {R} _{\geq 0}$

$\operatorname {f_{4}} :x\mapsto x^{2}$

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 preimage

For a set $E$, we write ${\mathcal {P}}(E)$ for the set of subsets of $E$.

Let $\operatorname {f} :A\rightarrow B$. We will now define two related functions.

The image function:

$\operatorname {f} :{\mathcal {P}}(A)\rightarrow {\mathcal {P}}(B),S\subseteq A\mapsto \{\operatorname {f} (x)\mid x\in S\}$

The preimage function:

$\operatorname {f^{-1}} :{\mathcal {P}}(B)\rightarrow {\mathcal {P}}(A),T\subseteq B\mapsto \{x\in A\mid \operatorname {f} (x)\in T\}$

Note that the image and preimage are written respectively like $\operatorname {f}$ 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 $\operatorname {Im} _{\operatorname {f} }:=\operatorname {f} (A)$, which we call the image of $\operatorname {f}$.

For any $y\in B$, we call $\operatorname {f^{-1}} (\{y\})$ the support of $y$.

Proposition: Let $\operatorname {f} :A\rightarrow B$. Then

1. $\forall S\subseteq A,S\subseteq f^{-1}(f(S))$
2. $\forall T\subseteq B,f(f^{-1}(T))\subseteq T$

Example

Let's take again the function:

$\operatorname {f} :\mathbb {R} \rightarrow \mathbb {R}$

$\operatorname {f} :x\mapsto x^{2}$

Let's consider the following examples:

$\operatorname {f^{-1}} (\{4\})=\{-2,2\}$

$\operatorname {f^{-1}} (\mathbb {R} _{<0})=\emptyset$

$\operatorname {f} (\mathbb {R} _{\geq 0})=\mathbb {R} _{\geq 0}$

Further definitions

Let $\operatorname {f} :B\rightarrow C$ and $\operatorname {g} :A\rightarrow B$. We define $\operatorname {f} \circ \operatorname {g} :A\rightarrow C$ by $(\operatorname {f} \circ \operatorname {g} )(x):=\operatorname {f} (\operatorname {g} (x))$, which we call the composition of $\operatorname {f}$ and $\operatorname {g}$.

Let $A$ be a set. We define the identity function on A as

$\operatorname {id_{A}} :A\rightarrow A,x\mapsto x$

Properties

Definition: A function $\operatorname {f} :A\rightarrow B$ is injective if

$\forall x\in A,x'\in A,\operatorname {f} (x)=\operatorname {f} (x')\Rightarrow x=x'$

Lemma: Consider a function $\operatorname {f} :A\rightarrow B$ and suppose $A\neq \emptyset$. Then $\operatorname {f}$ is injective if and only if there exists a function $\operatorname {g} :B\rightarrow A$ with $\operatorname {g} \circ \operatorname {f} =\operatorname {id_{A}}$.
Proof:
$'\Rightarrow '$:
Suppose $\operatorname {f}$ is injective. As $A\neq \emptyset$ let's define $m$ as an arbitrary element of $A$. We can then define a suitable function $\operatorname {g} :B\rightarrow A$ as follows:

$\operatorname {g} (y):=\left\{{\begin{array}{ll}{\mbox{the unique }}x\in A\mid \operatorname {f} (x)=y&{\text{, if }}y\in \operatorname {Im} _{\operatorname {f} }\\m&{\text{, else}}\\\end{array}}\right.$

It is now easy to verify that $\operatorname {g} \circ \operatorname {f} =\operatorname {id_{A}}$.
$'\Leftarrow '$:
Suppose there is a function $\operatorname {g} :B\rightarrow A$ with $\operatorname {g} \circ \operatorname {f} =\operatorname {id_{A}}$. Then $\forall x,x'\in A,\operatorname {f} (x)=\operatorname {f} (x')\Rightarrow \operatorname {g} (\operatorname {f} (x))=\operatorname {g} (\operatorname {f} (x'))\Rightarrow x=x'$. $\operatorname {f}$ is thus injective.
Q.E.D.

Definition: A function $\operatorname {f} :A\rightarrow B$ is surjective if

$\forall y\in B,\exists x\in A\mid \operatorname {f} (x)=y$

Lemma: Consider a function $\operatorname {f} :A\rightarrow B$. Then $\operatorname {f}$ is surjective if and only if there exists a function $\operatorname {g} :B\rightarrow A$ with $\operatorname {f} \circ \operatorname {g} =\operatorname {id_{B}}$.
Proof:
$'\Rightarrow '$:
Suppose $\operatorname {f}$ is surjective. We can define a suitable function $\operatorname {g} :B\rightarrow A$ as follows:

$\operatorname {g} (y):={\mbox{an }}x\in A\mid \operatorname {f} (x)=y$

It is now easy to verify that $\operatorname {f} \circ \operatorname {g} =\operatorname {id_{B}}$.
$'\Leftarrow '$:
Suppose there is a function $\operatorname {g} :B\rightarrow A$ with $\operatorname {f} \circ \operatorname {g} =\operatorname {id_{B}}$. Then $\forall y\in B{\mbox{, let }}x:=\operatorname {g} (y)$. Then $\operatorname {f} (x)=\operatorname {f} (\operatorname {g} (y))=y$. $\operatorname {f}$ is thus surjective.
Q.E.D.

Definition: A function $\operatorname {f} :A\rightarrow B$ is bijective if it is both injective and surjective.

Lemma: A function $\operatorname {f} :A\rightarrow B$ is bijective if and only if there exists a function $\operatorname {g} :B\rightarrow A$ with $\operatorname {g} \circ \operatorname {f} =\operatorname {id_{A}}$ and $\operatorname {f} \circ \operatorname {g} =\operatorname {id_{B}}$. Furthermore it can be shown that such a $\operatorname {g}$ is unique. We write it $\operatorname {f^{-1}} :B\rightarrow A$ and call it the inverse of $\operatorname {f}$.
Proof:
Left as an exercise.

Proposition: Consider a function $\operatorname {f} :A\rightarrow B$. Then

1. $f$ is injective iff $\forall S\subseteq A,f^{-1}(f(S))=S$
2. $f$ is surjective iff $\forall T\subseteq B,f(f^{-1}(T))=T$
3. $f$ is bijective iff the image and preimage of $f$ are inverse of each other

Example: If $A$ and $B$ are sets such that $B\subseteq A$, there exists an obviously injective function $i\,:\,B\rightarrow A$, called the inclusion $B\subseteq A$, such that $i(b)=b$ for all $b\in B$.

Example: If $\sim$ is an equivalence relation on a set $X$, there is an obviously surjective function $\pi \,:\,X\rightarrow X/\sim$, called the canonical projection onto $X/\sim$, such that $\pi (x)=[x]$ for all $x\in X$.

Theorem: Define the equivalence relation $\sim$ on $A$ such that $a\sim b$ if and only if $f(a)=f(b)$. Then, if $f:A\rightarrow B$ is any function, $f$ decomposes into the composition

$A{\stackrel {\pi }{\longrightarrow }}A/\sim {\stackrel {\tilde {f}}{\longrightarrow }}\mathrm {im} f{\stackrel {i}{\longrightarrow }}B$

where $\pi$ is the canonical projection, $i$ is the inclusion $\mathrm {im} \,f\subseteq B$, and ${\tilde {f}}$ is the bijection ${\tilde {f}}([a])=f(a)$ for all $a\in A$.

Proof: The definition of ${\tilde {f}}$ immediately implies that $f=i\circ {\tilde {f}}\circ \pi$, so we only have to prove that ${\tilde {f}}$ is well defined and a bijection. Let $a,a^{\prime }\in A$. Then $[a]=[a^{\prime }]\,\Rightarrow \,a\sim a^{\prime }\,\Rightarrow \,f(a)=f(a^{\prime })$. This shows that the value of ${\tilde {f}}([a])$ is independent of the representative chosen from $[a]$, and so it is well-defined.

For injectivity, we have ${\tilde {f}}([a])={\tilde {f}}([a^{\prime }])\,\Rightarrow \,f(a)=f(a^{\prime })\,\Rightarrow \,[a]=[a^{\prime }]$, so ${\tilde {f}}$ is injective.

For surjectivity, let $b\in \mathrm {im} \,f$. Then there exists an $a\in A$ such that $f(a)=b$, and so ${\tilde {f}}([a])=b$ by definition of ${\tilde {f}}$. Since $b$ is arbitrary in $\mathrm {im} \,f$, this proves that ${\tilde {f}}$ is surjective.

Q.E.D.

Definition: Given a function $f\,:\,X\rightarrow Y$, $f$ is a

(i) Monomorphism if given any two functions $g,h\,:\,W\rightarrow X$ such that $f\circ g=f\circ h$, then $g=h$.

(ii) Epimorphism if given any two functions $g,h\,:\,Y\rightarrow Z$ such that $g\circ f=h\circ f$, then $g=h$.

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 $f\,:\,B\rightarrow C$ be a monomorphism. Then, for any two functions $g,h\,:\,A\rightarrow B$, $f(g(a))=f(h(a))\,\Rightarrow \,g(a)=h(a)$ for all $a\in A$. This is the definition if injectivity. For the converse, if $f$ is injective, it has a left inverse $f^{\prime }$. Thus, if $f(g(a))=f(h(a))$ for all $a\in A$, compose with $f^{\prime }$ on the left side to obtain $g(a)=h(a)$, such that $f$ is a monomorphism.

(ii) Let $f\,:\,A\rightarrow B$ be an epimorphism. Then, for any two functions $g,h\,:\,B\rightarrow C$, $g(f(a))=h(f(a))\,\Rightarrow \,g(b)=h(b)$ for all $a\in A$ and $b\in B$. Assume $\mathrm {im} f\neq B$, that is, that $f$ is not surjective. Then there exists at least one $b\in B$ not in $\mathrm {im} \,f$. For this $b$ choose two functions $g,h$ which coincide on $\mathrm {im} \,f$ but disagree on $\{b\}$. However, we still have $g(f(a))=h(f(a))$ for all $a\in A$. This violates our assumption that $f$ is an epimorphism. Consequentally, $f$ is surjective. For the converse, assume $f$ 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 $A$ and $B$, we have the canonical projections $\pi _{A}\,:\,A\times B\rightarrow A$ sending $(a,b)$ to $a$, and $\pi _{B}\,:\,A\times B\rightarrow B$ sending $(a,b)$ to $b$. These maps are obviously surjective.

In addition, we have the natural inclusions $i_{A}\,:\,A\rightarrow A\coprod B$ and $i_{B}\,:\,B\rightarrow A\coprod B$ which are obviously injective as stated above.

Universal properties

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 $A,B,C$ be any sets.

(i) Let $f\,:\,C\rightarrow A$ and $g\,:\,C\rightarrow B$. Then there exists a unique function $u\,:\,C\rightarrow A\times B$ such that $f=\pi _{A}\circ u$ and $g=\pi _{B}\circ u$ are simultaneously satisfied. $u$ is sometimes denoted $f\times g$.

(ii) Let $f\,:\,A\rightarrow C$ and $g\,:\,B\rightarrow C$. Then there exists a unique function $u\,:\,A\coprod B\rightarrow C$ such that $f=u\circ i_{A}$ and $g=u\circ i_{B}$ are simultaneously satifsied.

The canonical projections onto quotients also satisfy a universal property.

Theorem: Define the equivalence relation $\sim$ on $X$ and let $f\,:\,X\rightarrow Y$ be any function such that $a\sim b\,\Rightarrow \,f(a)=f(b)$ for all $a,b\in X$. Then there exists a unique function ${\bar {f}}\,:\,X/\sim \rightarrow Y$ such that $f={\bar {f}}\circ \pi$, where $\pi \,:\,X\rightarrow X/\sim$ is the canonical projection.

Binary Operations

A binary operation on a set $A$ is a function $*:A\times A\rightarrow A$. For $a,b\in A$, we usually write $*(a,b)$ as $a*b$. The property that $a*b\in A$ for all $a,b\in A$ 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. $1/2$ is not an integer, so the integers are not closed under division.

To indicate that a set $A$ has a binary operation $*$ defined on it, we can compactly write $(A,*)$. 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 $A$ is associative if for all $a,b,c\in A$, $(a*b)*c=a*(b*c)$.

Example: Addition of integers is associative: $(1+2)+3=6=1+(2+3)$. Notice however, that subtraction is not associative. Indeed, $2=1-(2-3)\neq (1-2)-3=-4$.

Definition: A binary operation $*$ on $A$ is commutative is for all $a,b\in A$, $a*b=b*a$.

Example: Multiplication of rational numbers is commutative: ${\frac {a}{b}}\cdot {\frac {c}{d}}={\frac {ac}{bd}}={\frac {ca}{bd}}={\frac {c}{d}}\cdot {\frac {a}{b}}$. Notice that division is not commutative: $2\div 3={\frac {2}{3}}$ while $3\div 2={\frac {3}{2}}$. Notice also that commutativity of multiplication depends on the fact that multiplication of integers is commutative as well.

Exercise

• Of the four arithmetic operations, addition, subtraction, multiplication, and division, which are associative? commutative and identity?

Answer

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 $V$ and $W$ with bases $B$ and $C$ and dimensions $n$ and $m$, respectively, a linear map $f\,:\,V\to W$ corresponds to a unique $m\times n$ 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 $f(\alpha x+\beta y)=\alpha f(x)+\beta f(y)$, 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 $V$ is isomorphic to $\mathbb {F} ^{n}$ for some field $\mathbb {F}$ and some $n\in \mathbb {N}$, called the dimension of $V$. Specifying such an isomorphism is equivalent to choosing a basis for $V$. Thus, any linear map between vector spaces $f\,:\,V\to W$ with dimensions $n$ and $m$ and given bases $\phi$ and $\psi$ induces a unique linear map $[f]_{\phi }^{\psi }\,:\,\mathbb {R} ^{n}\to \mathbb {R} ^{m}$. These maps are precisely the $m\times n$ matrices, and the matrix in question is called the matrix representation of $f$ relative to the bases $\phi ,\psi$.

Remark: The idea of identifying a basis of a vector space with an isomorphism to $\mathbb {F} ^{n}$ 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 numbers

Definition: Using the undefined notions "1" and "successor" (denoted by $'$), we define the set of natural numbers without zero $\mathbb {N} ^{*}$, hereafter referred to simply as the natural numbers, with the following axioms, which we call the Peano postulates:

Axiom 1. $\exists 1(1\in \mathbb {N} ^{*}).$

Axiom 2. $\forall a(a\in \mathbb {N} ^{*}\implies \exists b(b=a')).$

Axiom 3. $\lnot \exists a(a'=1).$

Axiom 4. $\forall a\in \mathbb {N} ^{*}(\forall b\in \mathbb {N} ^{*}(a'=b'\implies a=b)).$

Axiom 5. $\forall A\subseteq \mathbb {N} ^{*}((1\in A)\land \forall a\in A(a'\in A)\implies A=\mathbb {N} ^{*}).$

We can prove theorems for natural numbers using mathematical induction as a consequence of the fifth Peano Postulate.

Addition

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. $\forall a\in \mathbb {N} ^{*}(a+1=a').$

Axiom 7. $\forall a\in \mathbb {N} ^{*}(\forall b\in \mathbb {N} ^{*}(a+b'=(a+b)')).$

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 $a,b,c,\ldots ,n$ in $\mathbb {N} ^{*}$.

Multiplication

Definition: We similarly define multiplication for the natural numbers recursively, again using two axioms:

Axiom 8. $a(1)=a.$

Axiom 9. $ab'=ab+a.$

Properties of addition

We start by proving that addition is associative.

Theorem 1: Associativity of addition: $(a+b)+c=a+(b+c).$

Proof: Base case: By axioms 6 and 7, $a+(b+1)=(a+b)'$.

By axiom 6, $a+(b+1)=(a+b)+1$.

Inductive hypothesis: Suppose that, for $k'>1$, $(a+b)+k=a+(b+k)$.

Inductive step: By axiom 7, $(a+b)+k'=\left[(a+b)+k\right]'$.

By the inductive hypothesis, $(a+b)+k'=\left[a+(b+k)\right]'$.

By axiom 7, $(a+b)+k'=a+(b+k)'$.

By axiom 7, $(a+b)+k'=a+(b+k')$.

By induction, $(a+b)+c=a+(b+c)$. QED.

Lemma 1: $a+1=1+a.$

Proof: Base case: 1+1=1+1.

Inductive hypothesis: Suppose that, for $k'>1$, $k+1=1+k$.

Inductive step: By axiom 6, $k'+1=(k+1)+1$.

By the inductive hypothesis, $k'+1=(1+k)+1$.

By theorem 1, $k'+1=1+(k+1)$.

By axiom 6, $k'+1=1+k'$.

By induction, $a+1=1+a$. QED.

Theorem 2: Commutativity of addition: $a+b=b+a.$

Proof: Base case: By lemma 1, $a+1=1+a$.

Inductive hypothesis: Suppose that, for $k'>1$, $a+k=k+a$.

By axiom 6, $a+k'=a+(k+1)$.

By theorem 1, $a+k'=(a+k)+1$.

By the inductive hypothesis, $a+k'=(k+a)+1$.

By theorem 1, $a+k'=k+(a+1)$.

By lemma 1, $a+k'=k+(1+a)$.

By theorem 1, $a+k'=(k+1)+a$.

By axiom 6, $a+k'=k'+a$.

By induction, $a+b=b+a$. QED.

Theorem 3: $a+b=a+c\implies b=c$.

Proof: Base case: Suppose $1+b=1+c$.

By theorem 2, $b+1=c+1$.

By axiom 6, $b'=c'$.

By axiom 4, $b=c$.

Inductive hypothesis: Suppose that, for $k'>1$, $k+b=k+c\implies b=c$.

Inductive step: Suppose $k'+b=k'+c$.

By axiom 6, $(k+1)+b=(k+1)+c$.

By theorem 2, $(1+k)+b=(1+k)+c$.

By theorem 1, $1+(k+b)=1+(k+c)$.

By the base case, $k+b=k+c$. Thus, $k'+b=k'+c\implies k+b=k+c$.

By the inductive hypothesis, $k'+b=k'+c\implies b=c$.

By induction, $a+b=a+c\implies b=c$. QED.

Properties of multiplication

Theorem 4: Left-distributivity of multiplication over addition: $a(b+c)=ab+ac$.

Proof: Base case: By axioms 6 and 9, $a(b+1)=ab+a$.

By axiom 8, $a(b+1)=ab+a(1)$.

Inductive hypothesis: Suppose that, for $k'>1$, $a(b+k)=ab+ak$.

Inductive step: By axiom 7, $a(b+k')=a(b+k)'$.

By axiom 9, $a(b+k')=a(b+k)+a$.

By the inductive hypothesis, $a(b+k')=(ab+ak)+a$.

By theorem 1, $a(b+k')=ab+(ak+a)$.

By axiom 9, $a(b+k')=ab+ak'$.

By induction, $a(b+c)=ab+ac$. QED.

Theorem 5: $1a=a$.

Proof: Base case: By axiom 8, 1(1)=1.

Inductive hypothesis: Suppose that, for $k'>1$, $1k=k$.

Inductive step: By axiom 6, $1k'=1(k+1)$.

By theorem 4, $1k'=1k+1(1)$.

By the base case, $1k'=1k+1$.

By the inductive hypothesis, $1k'=k+1$.

By axiom 6, $1k'=k'$.

By induction, $1a=a$. QED.

Theorem 6: $a'b=ab+b$.

Proof: Base case: By axiom 8, $a'(1)=a'$.

By axiom 6, $a'(1)=a+1$.

By axiom 8, $a'(1)=a(1)+1$.

Inductive hypothesis: Suppose that, $k'>1$, $a'k=ak+k$.

Inductive step: By axiom 9, $a'k'=a'k+a'$.

By the inductive hypothesis, $a'k'=ak+k+a'$.

By axiom 6, $a'k'=ak+k+(a+1)$.

By theorem 1, $a'k'=ak+(k+a)+1$.

By theorem 2, $a'k'=ak+(a+k)+1$.

By theorem 1, $a'k'=ak+a+k+1$

By axiom 9, $a'k'=ak'+k+1$.

By theorem 1, $a'k'=ak'+(k+1)$.

By axiom 6, $a'k'=ak'+k'$.

By induction, $a'b=ab+b$. QED.

Theorem 7: Associativity of multiplication: $(ab)c=a(bc).$

Proof: Base case: By axiom 8, $ab(1)=ab=a\left[b(1)\right]$.

Inductive hypothesis: Suppose that, for $k'>1$, $(ab)k=a(bk)$.

Inductive step: By axiom 9, $(ab)k'=(ab)k+ab$.

By the inductive hypothesis, $(ab)k'=a(bk)+ab$.

By theorem 4, $(ab)k'=a(bk+b)$.

By axiom 9, $(ab)k'=a(bk')$.

By induction, $(ab)c=a(bc)$. QED.

Theorem 8: Commutativity of multiplication: $ab=ba$.

Proof: Base case: By axiom 8 and theorem 5, $a(1)=a=1a$.

Inductive hypothesis: Suppose that, for $k'>1$, $ak=ka$.

Inductive step: By axiom 9, $ak'=ak+a$.

By the inductive hypothesis, $ak'=ka+a$.

By theorem 6, $ak'=k'a$.

By induction, $ab=ba$. QED.

Theorem 9: Right-distributivity of multiplication over addition: $(a+b)c=ac+bc$.

Proof: By theorems 4 and 7, $(a+b)c=ca+cb$.

By theorem 7, $(a+b)c=ac+bc$. QED.

The integers

The set of integers $\mathbb {Z}$ 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

$(a,b)\equiv (c,d)\Leftrightarrow a+d=c+b.$

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 addition

Definition: We define addition for the integers as follows:

$\left[(a,b)\right]+\left[(c,d)\right]=\left[(a+c,b+d)\right].$

Using this definition and the properties for the natural numbers, one can prove that integer addition is both associative and commutative.

Integer multiplication

Definition: Multiplication for the integers, like addition, can be defined with a single axiom:

$\left[(a,b)\right]\left[(c,d)\right]=\left[(ac+bd,ad+bc)\right].$

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.

Monoids

Definition 1: A monoid is a binary structure $(M,*)$ satisfying the following properties:

(i) $(a*b)*c=a*(b*c)$ for all $a,b,c\in M$. This is defined as associativity.

(ii) There exists an identity element $e\in M$ such that $a*e=a=e*a$ for all $a\in M$.

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 $M$ is unique.

Proof: Assume $e$ and $e^{\prime }$ are both identity elements of $M$. Then both satisfy condition (ii) in the definition above. In particular, $e=e*e^{\prime }=e^{\prime }$, proving the theorem. ∎

This theorem will turn out to be of fundamental importance later when we define groups.

Theorem 3: If $a_{1},a_{2},\ldots ,a_{n}$ are elements of $M$ for some $n\in \mathbb {N}$, then the product $a_{1}*a_{2}*\cdots *a_{n}$ is unambiguous.

Proof: We can prove this by induction. The cases for $n=1$ and $n=2$ are trivially true. Assume that the statement is true for all $n<k$. For $n=k$, the product $a_{1}*\cdots *a_{k}$, inserting parentheses, can be "partitioned" into $(a_{1}*\cdots *a_{i})*(a_{i+1}*\cdots *a_{k})$. Both parts of the product have a number of elements less than $k$ and are thus unambiguous. The same is true if we consider a different "partition", $(a_{1}*\cdots *a_{j})*(a_{j+1}*\cdots *a_{k})$, where $j>i$. Thus, we can unambiguously compute the products $(a_{1}*\cdots *a_{i})$, $(a_{i+1}*\cdots *a_{j})$, and $(a_{j+1}*\cdots *a_{k})$, and rewrite the two "partitions" as $b_{1}*(b_{2}*b_{3})$ and $(b_{1}*b_{2})*b_{3}$. 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.

Groups

Definition 4: A group is a monoid $(G,*)$ that also satisfies the property

(iii) For each $a\in G$, there exists an element $a^{\prime }\in G$ such that $a*a^{\prime }=a^{\prime }*a=e$.

Such an element $a^{\prime }$ is called an inverse of $a$. When the operation on the group is understood, we will conveniently refer to $(G,*)$ as $G$. 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, $a*b\equiv ab$.

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 $a\in G$, let $b$ be a right-inverse of $a$, and let $c$ be a right-inverse of $b$. Then, $a=a(bc)=(ab)c=c$. Thus, any right-inverse is also a left-inverse, or $ab=ba$. A similar argument can be made for left-inverses.

Theorem 6: The inverse of any element is unique.

Proof: Let $g\in G$ and let $g^{\prime }$ and $g^{\prime \prime }$ be inverses of $g$. Then, $g^{\prime }=g^{\prime }*e=g^{\prime }*g*g^{\prime \prime }=e*g^{\prime \prime }=g^{\prime \prime }$. ∎

Thus, we can speak of the inverse of an element, and we will denote this element by $a^{-1}$. We also observe this nice property:

Corollary 7: $(a^{-1})^{-1}=a$.

Proof: This follows immediately since $a*a^{-1}=a^{-1}*a=e$.

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 $G$ be a group and $a,b\in G$. Then $(a*b)^{-1}=b^{-1}*a^{-1}$.

Proof: The result follows by direct computation: $(a*b)*(b^{-1}*a^{-1})=a*b*b^{-1}*a^{-1}=a*e*a^{-1}=a*a^{-1}=e$. ∎

Theorem 9: Let $a,b,c\in G$. Then, $a*b=a*c$ if and only if $b=c$. Also, $a*c=b*c$ if and only if $a=b$.

Proof: We will prove the first assertion. The second is identical. Assume $a*b=a*c$. Then, multiply on the left by $a^{-1}$ to obtain $b=c$. Secondly, assume $b=c$. Then, multiply on the left by $a$ to obtain $a*b=a*c$. ∎

Theorem 10: The equation $a*x=b$ has a unique solution in $G$ for any $a,b\in G$.

Proof: We must show existence and uniqueness. For existence, observe that $x=a^{-1}*b$ is a solution in $G$. For uniqueness, multiply both sides of the equation on the left by $a^{-1}$ to show that this is the only solution. ∎

Notation: Let $G$ be a group and $a\in G$. We will often encounter a situation where we have a product $\underbrace {a*a*\cdots *a} _{\mathrm {n\,terms} }$. For these situations, we introduce the shorthand notation $a^{n}=\underbrace {a*a*\cdots *a} _{\mathrm {n\,terms} }$ if $n$ is positive, and $a^{n}=\underbrace {a^{-1}*a^{-1}*\cdots *a^{-1}} _{\mathrm {|n|\,terms} }$ if $n$ is negative. Under these rules, it is straightforward to show $g^{n}*g^{m}=g^{n+m}$ and $(a^{n})^{-1}=a^{-n}$ and $a^{0}=e$ for all $a\in G$.

Definition 11: (i) The order of a group $G$, denoted $|G|$ or $o(G)$, is the number of elements of $G$ if $G$ is finite. Otherwise $|G|$ is said to be infinite.

(ii) The order of an element of $g\in G$, similarly denoted $|g|$ or $o(g)$, is defined as the lowest positive integer $n$ such that $g^{n}=e$ if such an integer exists. Otherwise $|g|$ is said to be infinite.

Theorem 12: Let $G$ be a group and $a,b\in G$. Then $|ab|=|ba|$.

Proof: Let the order of $ab$ be $n$. Then, $(ab)^{n}=abab...ab=e$, $n$ being the smallest positive integer such that this is true. Now, multiply by $b$ on the left and $a$ on the right to obtain $(ba)^{n+1}=ba$ implying $(ba)^{n}=e$. Thus, we have shown that $|ba|\leq |ab|$. A similar argument in the other direction shows that $|ab|\leq |ba|$. Thus, we must have $|ab|=|ba|$, proving the theorem. ∎

Corollary 13: Let $G$ be a group with $a,b\in G$. Then, $|aba^{-1}|=|b|$.

Proof: By Theorem 12, we have that $|aba^{-1}|=|ba^{-1}a|=|be|=|b|$. ∎

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 $g$ have order 2 in the group $G$. Then, $g^{2}=gg=e$, so by definition, $g^{-1}=g$. Now, assume $g^{-1}=g$ and $g\neq e$. Then $e=gg^{-1}=gg=g^{2}$. Since $g\neq e$, 2 is the smallest positive integer satisfying this property, so $g$ has order 2. ∎

Definition 15: Let $G$ be a group such that for all $a,b\in G$, $ab=ba$. Then, $G$ 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 $a^{n}$ with $na$. In such cases, we only need to keep track of the fact that $n$ is an integer while $a$ 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 $G$ be a group. A subset $S\subseteq G$ is called a generating set for $G$ if every element in $G$ can be written in terms of elements in $S$. We write $G=\langle S\rangle =\{s_{1}^{e_{1}}\ldots s_{m}^{e_{m}}\mid s_{i}\in S,e_{i}\in \{1,-1\}\}$.

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 tables

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 $K_{4}$. The multiplication table is structured such that $g*h$ is represented by the element in the "$(g,h)$-position", that is, in the intersection of the $g$-row and the $h$-column.

${\begin{array}{c|cccc}*&e&a&b&c\\\hline e&e&a&b&c\\a&a&e&c&b\\b&b&c&e&a\\c&c&b&a&e\end{array}}$

This next group is for the group of integers under addition modulo 4, called $\mathbb {Z} _{4}$. We will learn more about this group later.

${\begin{array}{c|cccc}+&0&1&2&3\\\hline 0&0&1&2&3\\1&1&2&3&0\\2&2&3&0&1\\3&3&0&1&2\end{array}}$

We can clearly see that $K_{4}$ and $\mathbb {Z} _{4}$ 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 $k\in G$ appeared twice in some row of the multiplication table for $G$. Then there would exist $g,h,h^{\prime }\in G$ such that $gh=gh^{\prime }$, implying $h=h^{\prime }$ and contradicting the assumption of $k$ appearing twice. We state this as a theorem:

Theorem 17: Let $G$ be a group and $a\in G$. Then $aG=\{a*g\mid g\in G\}=G$.

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.

Problems

Problem 1: Show that $M_{n}(\mathbb {R} )$, the set of $n\times n$ matrices with real entries, forms a group under the operation of matrix addition.

Problem 2: Let $V,W$ be vector spaces and $\mathrm {Hom} (V,W)$ be the set of linear maps from $V$ to $W$. Show that $\mathrm {Hom} (V,W)$ forms an abelian group by defining $(f+g)(v)=f(v)+g(v)$.

Problem 3: Let $\mathbb {H}$ be generated by the elements $i,j,k,m$ such that $i^{2}=j^{2}=k^{2}=m$, $m^{2}=e$ and $ij=mji=k$. Show that $\mathbb {H}$ 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 $S$ be any nonempty set and consider the set $G^{S}$. Show that $G^{S}$ has a natural group structure.

Answer

$G^{S}$ is the set of functions $f\,:\,S\rightarrow G$. Let $f_{1},f_{2}\in G^{S}$ and define the binary operation $(f_{1}*f_{2})(x)=f_{1}(x)f_{2}(x)$ for all $x\in S$. Then $G^{S}$ is a group with identity $0$ such that $0(x)=e$ for all $x\in X$ and inverses $f^{-1}(x)=f(x)^{-1}$ for all $f\in G^{S},x\in X$.∎

Problem 5: Let $G$ be a group with two distinct elements $a$ and $b$, both of order 2. Show that $G$ has a third element of order 2.

Answer

We consider first the case where $ab=ba$. Then $(ab)^{2}=abab=aabb=e$ and $ab$ is distinct from $e,a$ and $b$. If $ab\neq ba$, then $(aba^{-1})^{2}=abaa^{-1}ba^{-1}=abba^{-1}=e$ and $aba^{-1}$ is distinct from $e,a$ and $b$. ∎

Problem 6: Let $G$ be a group with one and only one element $f$ of order 2. Show that $\prod _{g\in G}g=f$.

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 $G$ appears once in the product, for every element $g\in G$, the inverse of $g$ must appear somewhere in the product. That, is, unless $|g|=2$ in which case $g$ 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 $G$. But there is only one such element, $f$, so the order of the product is 2. Since the only element in $G$ having order 2 is $f$, the equality follows. ∎

Group Theory/Subgroup

Subgroups

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 $G$ be a group. Then, if $H\subseteq G$ is a subset of $G$ which is a group in its own right under t