This is the first post of the Introduction to Abstract Algebra series. In the first post, we introduce the basic concepts in abstract algebra, starting from mappings, equivalent relations, partitions, and extending to groups and homomorphisms. We will also encounter an important theorem: the Lagrange’s theorem.

Preliminaries

Definition 1.1: Cartesian Product

• For two sets $A$ and $B$, there Cartesian product is $A \times B = \{(a, b) \mid a \in A, b \in B\}$.

Definition 1.2: Mapping

• A mapping $f$ from the set $A$ to the set $B$, denotes has $f: A \to B$, is an unambiguous association of an element in $A$ to an element in $B$. Note that $f \subseteq A \times B$.
• $A$ is the domain of $f$, $B$ is the codomain of $f$, $f(A) = \{f(a) \mid a \in A\}$ is the image/range of $f$.
• $f$ is onto/surjective if $f(A) = B$.
• $f$ is injective if $\forall a_1, a_2 \in A, a_1 \neq a_2, f(a_1) \implies f(a_1) \neq f(a_2)$.
• $f$ is bijective if $f$ is surjective and injective.

Definition 1.3: Equivalence Relation

• Given a set $A$, a relation $R$ is a subset of $A \times A$, i.e., $R \subseteq A \times A$. For $a_1, a_2 \in A$, if $(a_1, a_2) \in R$, put $a_1 \sim a_2$.
• $R$ is is an equivalence relation if:
  1. (reflexivity) $a \sim a, \forall a \in A$.
  2. (symmetry) $a \sim b \implies b \sim a, \forall a, b \in A$.
  3. (transitivity) $a \sim b, b \sim c \implies a \sim c, \forall a, b, c \in A$.
• For a set $A$ and an equivalence relation $\sim$ on $A$, $[a] = \{x \in A \mid x \sim a\}$ is an equivalence class. We define $A/\sim$ as the set of equivalence classes.

Example 1.1: Set $\mathbb Z/n\mathbb Z$

An equivalence relation on $\mathbb Z$ is $R = \{(a, b) \mid a, b \in \mathbb Z, a \equiv b \mod n\}$. This relation is called congruence modulo $n$. The $n-1$ equivalence classes induced by congruence modulo $n$, also referred to as congruence classes, form a set called $\mathbb Z/ n \mathbb Z$. For example, $\mathbb Z/ 2 \mathbb Z$ contains two congruence classess: $[0]$ and $[1]$.

Definition 1.4: Paritition

• Given a set $A$, a partition is a set of non-empty subsets $A_i \subseteq A$ such that:
  1. $\cup_i A_i = A$
  2. For $i \neq j$, $A_i \cap A_j \ = \emptyset$
• Lemma: An equivalence relation $A/\sim$ on $A$ is a partition of $A$.

Groups

A group is a set and a binary operation. Intuitively, a group is simply some elements and a rule that describes how they interact.

Definition 1.5: Group

• A group is a $(G, \circ)$ is a set $G$ and a binary operation $\circ: G \times G \to G$ that satisfies the following axioms:
  1. (associativity) $(a \circ b) \circ c = a \circ (b \circ c), \forall a, b, c \in G$.
  2. (identity) There exists an identity element $e \in G$ such that $e \circ a = a \circ e = a, \forall a \in G$.
  3. (inverse) For each element $a \in G$, there exists an inverse $a^{-1} \in G$ such that $a \circ a^{-1} = e$.

An equivalent statement of the three axioms is that a group is closed under multiplication and inverses. When the meaning is unambiguous, we often drop the binary operation and simply refers the group as $G$.

Applying the three axioms, we can easily show several useful properties below.

Properties 1.6: Basic Properties of a Group

• Given a group $G$:
  1. The identity element is unique.x
  2. Every element has a unique inverse.
  3. If $a \circ b = e$, then $b \circ a = e$.
  4. $(a \circ b)^{-1} = b^{-1} \circ a^{-1}$.
  5. $a^{-1^{-1}} = e$.

Definition 1.7: Abelian Group A $(G, \circ)$ is abelian if there for every two elements $a, b \in G$, $a \circ b = b \circ a$.

Definition 1.8: Order Given a group $G$ and a element $g \in G$, the order of $g$, denoted as $ord(g)$ or $|g|$, is the smallest $k \in \mathbb Z_{\geq 1}$ such that $g^k = e$ and $g^i \neq e$ for $i < k$, where $g^k$ here means applying the binary operation on $k$ copies of $g$. If such a $k$ does not exist, we say $g$ has infinite order.

Note that we also talk about the order of an group, which is the size of the underlying set.

Definition 1.9: Cyclic Group A group $G$ is cyclic if there exists a $g \in G$ such that $G = \{g^k \mid k \in \mathbb Z\}$. We call $g$ the generator of $G$. We say $g$ generates $G$ and write $G = \langle g \rangle$. Obviously, $ord(g) = |G|$.

Property 1.10: Properties of Cyclic Groups

Let $G$ be a finite cyclic group, $G = \langle x \rangle$ and $|G| = n$. Then,

1. For a positive integer $k$, $|x^k| = n/gcd(n,k)$. This implies that the generators of $G$ has an order coprime with $n$, so the number of generators of $G$ is $\phi(n)$, where again $\phi(n)$ is the Euler’s totient function.

2. Every subgroup of $G$ is cyclic. Suppose $H$ is a subgroup of $G$, and $a^m \in H$ is the element of smallest $m$ in $H$. Then for some $a^n \in H, a^n = a^{qm+r}$ for some integers $q, r\in \mathbb Z, r \leq m$. Then $a^r = a^{-qm+n} \in H$, but $m$ is the smallest order, so $r \geq m$. Thus, $r=m$, and $a^n = a^{qm}$, which means $H = \langle a^m \rangle$.

3. For a positive integer $k$, if $k \mid n$, there exists a subgroup of $G$ of order $k$ which is $\langle x^{n/k} \rangle$.

4. For a positive integer $k$, $\langle x^{k} \rangle = \langle x^{gcd(n,k)} \rangle$.

We will define several important groups.

Example 1.2: Group $\mathbb Z/n\mathbb Z$

Recall from Example 1.1 that $\mathbb Z/n \mathbb Z$ is a set of congruence classes modulo $n$. We will introduce the group $(\mathbb Z/n \mathbb Z, +)$. We define the binary operation $+$ for two congruent classes as: $[a]+[b] = [a+b]$, where the latter ”+” is our usual addition on numbers.

P.S. But to be more precise, the latter ”+” is not all separated form our new definitions. When $n=0$, we get back a group that is isomorphic (for now understand it as equivalent) to $\mathbb Z$ of integers.

You can check that this binary option is well-defined (unambiguous) and satisfies the above-mentioned axioms. For example, the identity element is clearly $[0]$. Also, $\mathbb Z/n \mathbb Z$ is cyclic, and $[1]$ is its generator.

Example 1.3: Group $(\mathbb Z/n\mathbb Z)^\times$

First, we define the set $(\mathbb Z/n\mathbb Z)^\times = \{[a] \in \mathbb Z/n\mathbb Z \mid gcd(a,n)=1\}$. In other words, $(\mathbb Z/n\mathbb Z)^\times$ contains the congruent classes that are coprime with $n$. We define the binary operation $\times$ as: $[a] \times [b] = [a \times b]$, where the latter ”$\times$” is our usual multiplication on numbers. It’s less trivial to show that $((\mathbb Z/n\mathbb Z)^\times, \times)$ is a group.

Property 1.11: The Euclidean Algorithm

Given $a, b \in \mathbb Z, \exists x, y \in \mathbb Z$, such that $xa + yb = gcd(a,b)$.

$Proof$. This can be proven by the Euclidean algorithm.

Lemma 1.12: Group $(\mathbb Z/n\mathbb Z)^\times$

$Proof$. It is straightforward to show that $(\mathbb Z/n\mathbb Z)^\times$ has the identity $[1]$ and satisfies associativity. We will show every element in $(\mathbb Z/n\mathbb Z)^\times$ has an inverse by Property 1.8.

For a $[k] \in (\mathbb Z/n\mathbb Z)^\times, gcd(k, n) = 1$, so there exists $x, y \in \mathbb Z$ such that $xk + yn = gcd(k,n) = 1$, or $[x] \times [k] = [1]$. So $[x] = [k]^{-1}$. Note that $|(\mathbb Z/n\mathbb Z)^\times| = \phi(n)$, where $\phi$ is the Euler’s totient function, which counts numbers lesser than $n$ that are coprime with $n$.

We will introduce other important groups like $S_n, A_n, D_{2n}, C_n$ later.

Homomorphisms and Isomorphisms

Homomorphisms are mappings from groups to groups.

Definition 1.13: Homomorphism

A homomorphism from a group $(G_1, \circ_1)$ to a group $(G_2, \circ_2)$ is a map $\phi: G_1 \to G_2$ such that $\phi(a \circ_1 b) = \phi(a) \circ_2 \phi(b)$.

$Proof$. By directly applying the definition of homomorphisms, we can show the following properties.

Property 1.14: Properties of Homomorphisms

Given a homomorphism $\phi: G_1 \to G_2$,

1. $\phi$ must send $e_1 \in G_1$ to $e_2 \in G_2$, where $e_1, e_2$ are identities.

2. $\phi(a^{-1})$ = $\phi(a)^{-1}$

Definition 1.15: Isomorphisms

An isomorphism from a group $(G_1, \circ_1)$ to a group $(G_2, \circ_2)$ is a bijective homomorphism $\phi: G_1 \to G_2$. We say $G_1$ and $G_2$ are isomorphic, denoted as $G_1 \cong G_2$.

Property 1.16: Properties of Isomorphisms

Given an isomorphism $\phi: G_1 \to G_2$,

1. |G_1| = |G_2|.

2. $G_1 \text{ is cyclic} \iff G_2 \text{ is cyclic}$.

3. $G_1 \text{ is abelian} \iff G_2 \text{ is abelian}$.

4. If $g_1 \in G_1$ has order $k$, $ord(\phi(g_1)) = k$.

Moreover,

5. Any two cyclic groups of the same order are isomorphic. Just send the generator of one group to the generator of the other group.

The Lagrange’s Theorem

Definition 1.17: Subgroup Given a group $(G, \circ)$, $(H, \circ)$ is a subgroup of $(G, \circ)$ if $(H, \circ)$ is a well-defined group and $H \subseteq G$ is a subset. $\{e\}$ and $G$ are trivial subgroups of $G$, where $\{e\}$ is the identity. Again, we simply say $H$ is a subgroup of $G$ when there are no confusions on the binary operator.

Theorem 1.18: The Lagrange’s theorem

If $G$ is a finite group, and $H \subset G$ is a subgroup. Then $|H| \mid |G|$.

Corollary: If $G$ is a finite group, and $a \in G$. Then $ord(a) \mid |G|$. This is by observing that $a$ generates a subgroup $H = \langle a \rangle$ which is of size $ord(a)$.

Corollary 1.19: The Fermat’s little theorem

If $p$ is a prime integer, $a$ is any integer, then $a^p \equiv a \mod p$.

$Proof$. We prove the Fermat’s little theorem by applying Lagrange’s Theorem to $(\mathbb Z/p\mathbb Z)^\times$, where $p$ is a prime. We have that $|(\mathbb Z/p\mathbb Z)^\times| = p-1$, so by the Lagrange’s Theorem, for $[a] \in (\mathbb Z/p\mathbb Z)^\times, ord([a]) \mid p-1$. Thus, we have $[a]^{p-1} = [1] \implies [a]^{p} = [a]$, or $a^p \equiv a \mod p$.

Corollary: In general, for $n \in \mathbb Z_{\geq 1}, [a] \in (\mathbb Z/n\mathbb Z)^\times, [a]^{\phi(n)} = [1]$.

Corollary 1.20: Prime Order Groups Are Cyclic

$Proof$. Given a group $G$ of order $p$, where $p$ is a prime, for an $a \in G$, $ord(a) \mid p$, so $ord(a) = 1 \text{ or } p$. Since the identity is unique, we have $p-1$ generators.

Now we will prove the Lagrange’s theorem by defining cosets.

Definition 1.21: Coset

Given a group $G, H \subset G$ is a subgroup. Define an equivalence relation on $G$ by $\forall g_1, g_2 \in G, g_1 \sim g_2 \iff g_1H = g_2H$. Here for $g \in G, gH = \{gh \mid h \in H\}$. We call $gH$ a left coset of $G$. Then $G/\sim$ is the set of the equivalence classes, or the set of the left cosets. (Similarly, $Hg$ is a right coset).

$Proof$. By straightforwardly showing $\sim$ is indeed an equivalence relation, we already have that $G/\sim$, or the set of cosets, is a partition of $G$. But to make the idea more transparent, we will show this directly.

1. We first note that every $g \in G$ lies in some left coset. Namely, $g \in gH$.
2. We then note that $g_1H = g_2H \iff g_2^{-1}g_1 H = H \iff g_2^{-1}g_1 \in H \iff g_2^{-1}g_1 = h \text{ for some } h \in H \iff g_1 = g_2 h$. The second $\iff$ can be shown by assuming that $g_2^{-1}g_1 \notin G$ and noting that $g_2^{-1}g_1 \circ e = g_2^{-1}g_1 \notin G \implies g_2^{-1}g_1H \neq H$, a contradiction. This easy to prove property, $gH = H \iff g \in H$, is a very useful property. Thus, if two left cosets $g_1H$ intersects with $g_2H$ at some element $g_3$, then $g_1H = g_3H$ and $g_2H = g_3H$, so $g_1H = g_2H$ and they are the same left coset.

$Proof$. Finally, we prove the Lagrange’s theorem by defining an isomorphism. Given a group $G$, a subgroup $H \subseteq G$ and any $g \in G$, define the mapping $\phi: H \to gH$ as $\phi(h) = gh$. The mapping is clearly well-defined. It is injective since $gh_1 = gh_2 \iff h_1 = h_2$. It is surjective since by definition, every element of $gH$ is $gh$ for some $h \in H$. Since $H \cong gH$, $|H| = |gH|$. Thus we show that every left coset has the same cardinality as $H$. Since $G/\sim$, the set of left cosets, is a partition of $G$, we have that $|H| \mid |G|$.

Definition 1.22: Index

Given a group $G, H \subset G$ is a subgroup, $|G|/|H|$, the number of left cosets, is the index of $H$ in $G$, denoted as $[G:H]$.

References

[1] Siegel, Kyler. MATH GU4041 Introduction to Modern Algebra I. Department of Mathematics, Columbia University. 2019.

[2] Dummit, David and Foote, Richard. Abstract Algebra. Third Edition. John Wiley and Sons, Inc. 2004.