On this page & study actions
Assessed progress
Sign in and complete the verified MCQs to track mastery.
Unit 3: Algebraic systems6 min read
Algebraic structures provide the foundational framework for analyzing symmetry, structural properties, and patterns in theoretical computer science, cryptography, and abstract algebra. This guide examines how smaller mathematical systems embed inside larger ones as subgroups, and how mappings known as homomorphisms allow us to compare different algebraic structures.
An algebraic system is defined as a non-empty set combined with one or more binary operations that map pairs of elements to the set itself. Formally, an algebraic system is represented as a tuple:
where is a non-empty set and , are binary operations.
Let be a non-empty set. A binary operator is said to be a binary operation (or a closed operation) on if:
Let be an algebraic system:
We can classify algebraic systems based on the axioms they satisfy. Two intermediate structures between a basic algebraic system and a group are semigroups and monoids.
[ Algebraic System ]
│ (requires Closure)
▼
[ Semigroup ]
│ (adds Associativity)
▼
[ Monoid ]
│ (adds Identity)
▼
[ Group ]
(adds Inverses)An algebraic system is a semigroup if:
Let be the set of positive odd integers, and let be standard multiplication.
Thus, is a semigroup.
Given a semigroup , a subset forms a subsemigroup if is closed under .
Consider the semigroup . The subset of positive even integers forms a subsemigroup because the sum of two even integers is always even.
If and are semigroups, then their Cartesian product is a semigroup under the component-wise operation defined by:
Let such that , , and .
a \star (b \star c) &= (a_1, a_2) \star ((b_1, b_2) \star (c_1, c_2)) \\ &= (a_1, a_2) \star (b_1 * c_1, b_2 * c_2) \\ &= (a_1 * (b_1 * c_1), a_2 * (b_2 * c_2)) \\ &= ((a_1 * b_1) * c_1, (a_2 * b_2) * c_2) \quad \text{(by associativity in } S_1, S_2\text{)} \\ &= (a_1 * b_1, a_2 * b_2) \star (c_1, c_2) \\ &= ((a_1, a_2) \star (b_1, b_2)) \star (c_1, c_2) \\ &= (a \star b) \star c \end{aligned}$$ Since $\star$ is closed and associative, $\langle S_1 \times S_2, \star \rangle$ is a semigroup. $\blacksquare$ ### Monoids An algebraic system $\langle A, * \rangle$ is a **monoid** if it is a semigroup and contains an identity element $e \in A$: 1. $*$ is closed. 2. $*$ is associative. 3. An identity $e \in A$ exists such that $a * e = e * a = a$ for all $a \in A$. #### Examples * $\langle \mathbb{N} \cup \{0\}, + \rangle$ is a monoid with identity element $0$. * $\langle \mathbb{N}, \cdot \rangle$ is a monoid with identity element $1$. ### Submonoids A subset $S \subseteq M$ of a monoid $\langle M, \circ \rangle$ is a **submonoid** of $\langle M, \circ \rangle$ if: 1. $S$ is closed under $\circ$. 2. The identity element $e$ of $M$ is in $S$. --- ## 3. Groups and Abelian Groups A **group** is a monoid that includes inverses for every element, providing a symmetric mathematical system. ### Group Definition An algebraic system $\langle G, * \rangle$ is a **group** if it satisfies four primary axioms: 1. **Closure**: $\forall a, b \in G, \; a * b \in G$. 2. **Associativity**: $\forall a, b, c \in G, \; (a * b) * c = a * (b * c)$. 3. **Identity**: $\exists e \in G$ such that $\forall a \in G, \; a * e = e * a = a$. 4. **Inverse**: $\forall a \in G, \; \exists a^{-1} \in G$ such that $a * a^{-1} = a^{-1} * a = e$. ### Abelian Groups A group $\langle G, * \rangle$ is **abelian** (or commutative) if the operation satisfies the commutativity axiom: $$\forall a, b \in G, \quad a * b = b * a$$ ```text [ Algebraic Structure Hierarchy ] ┌───────────────────────────────┐ │ Algebraic Systems │ │ ┌───────────────────────┐ │ │ │ Semigroups │ │ │ │ ┌───────────────┐ │ │ │ │ │ Monoids │ │ │ │ │ │ ┌───────────┐ │ │ │ │ │ │ Groups │ │ │ │ │ │ │ ┌───────┐ │ │ │ │ │ │ │Abelian│ │ │ │ │ │ │ └───────┘ │ │ │ │ │ └───────────┘ │ │ │ │ └───────────────┘ │ │ │ └───────────────────────┘ │ └───────────────────────────────┘ ``` --- ## 4. Key Theorems and Properties of Groups ### Theorem 1: Uniqueness of Identity In any group $\langle G, * \rangle$, the identity element is unique. #### Proof Suppose $e_1$ and $e_2$ are both identity elements in $G$. * Since $e_1$ is an identity: $e_1 * e_2 = e_2$ * Since $e_2$ is an identity: $e_1 * e_2 = e_1$ Equating the two yields $e_1 = e_2$. Thus, the identity element is unique. $\blacksquare$ ### Theorem 2: Uniqueness of Inverses In any group $\langle G, * \rangle$, the inverse of each element is unique. #### Proof Let $a \in G$, and let $b$ and $c$ be two inverses of $a$. Let $e$ be the identity in $G$. By the definition of an inverse: $$a * b = e \quad \text{and} \quad a * c = e$$ Equating them: $$a * b = a * c$$ Multiply both sides by the inverse $b$ on the left: $$b * (a * b) = b * (a * c)$$ Apply the associative property: $$(b * a) * b = (b * a) * c$$ Since $b$ is an inverse of $a$, we have $b * a = e$: $$e * b = e * c \implies b = c$$ Thus, the inverse is unique. $\blacksquare$ ### Theorem 3: Cancellation Laws In any group $\langle G, * \rangle$, the left and right cancellation laws hold: * **Left Cancellation**: $a * b = a * c \implies b = c$ * **Right Cancellation**: $b * a = c * a \implies b = c$ ### Theorem 4: Inverse of a Product (Socks-and-Shoes Property) For all $a, b$ in a group $\langle G, * \rangle$: $$(a * b)^{-1} = b^{-1} * a^{-1}$$ #### Proof We evaluate the product $(a * b) * (b^{-1} * a^{-1})$: $$\begin{aligned} (a * b) * (b^{-1} * a^{-1}) &= a * (b * b^{-1}) * a^{-1} \quad &\text{(by associativity)} \\ &= a * e * a^{-1} &\text{(by inverse property)} \\ &= a * a^{-1} &\text{(by identity property)} \\ &= e &\text{(by inverse property)} \end{aligned}$$ Similarly, $(b^{-1} * a^{-1}) * (a * b) = e$. Because inverses are unique, $(a * b)^{-1} = b^{-1} * a^{-1}$. $\blacksquare$ ### Theorem 5: Self-Inverse Property * If $a \in G$ satisfies $a * a = a$, then $a = e$. * If every element in a group is its own inverse ($a^{-1} = a$ for all $a \in G$), then the group is abelian. #### Proof (Every element is its own inverse implies Abelian) Let $a, b \in G$. Since every element is its own inverse, we have: $$a^{-1} = a, \quad b^{-1} = b, \quad \text{and} \quad (a * b)^{-1} = a * b$$ Using Theorem 4: $$(a * b)^{-1} = b^{-1} * a^{-1}$$ Substitute the self-inverse relations into the equation: $$a * b = b * a$$ Since this holds for all $a, b \in G$, the group $G$ is abelian. $\blacksquare$ ### Theorem 6: Commutative Squared Identity If $(a * b)^2 = a^2 * b^2$ for all $a, b$ in a group $\langle G, * \rangle$, then $G$ is abelian. #### Proof By definition: $$(a * b)^2 = (a * b) * (a * b) \quad \text{and} \quad a^2 * b^2 = a * a * b * b$$ Given that they are equal: $$a * (b * a) * b = a * (a * b) * b$$ By Left Cancellation (canceling $a$): $$(b * a) * b = (a * b) * b$$ By Right Cancellation (canceling $b$): $$b * a = a * b$$ Thus, $G$ is abelian. $\blacksquare$ --- ## 5. Finite Groups and Modulo Arithmetic Groups can be either finite or infinite. The size of a group is defined as its **order**. * **Order of a Group ($|G|$)**: The number of elements in group $G$. * **Order of an Element ($|a|$)**: For any $a \in G$, the smallest positive integer $n$ such that $a^n = e$. If no such integer exists, the element has infinite order. ### Addition Modulo $m$ ($\mathbb{Z}_m$) Let $m$ be a positive integer. For $a, b \in \{0, 1, \dots, m-1\}$, addition modulo $m$ ($+_m$) is defined as: $$a +_m b = (a + b) \pmod m$$ The algebraic system $\langle \mathbb{Z}_m, +_m \rangle$ is an abelian group of order $m$, where $\mathbb{Z}_m = \{0, 1, 2, \dots, m-1\}$. #### Cayley Table for $\langle \mathbb{Z}_4, +_4 \rangle$ The structure of finite groups can be visualized using a **Cayley table** (or composition table). Below is the table for $\langle \mathbb{Z}_4, +_4 \rangle$: | $+_4$ | 0 | 1 | 2 | 3 | | :---: | :-: | :-: | :-: | :-: | | **0** | 0 | 1 | 2 | 3 | | **1** | 1 | 2 | 3 | 0 | | **2** | 2 | 3 | 0 | 1 | | **3** | 3 | 0 | 1 | 2 | * **Closure**: Every element in the table belongs to $\{0, 1, 2, 3\}$. * **Identity**: $0$ acts as the identity element. * **Inverses**: * $0^{-1} = 0$ * $1^{-1} = 3$ (since $1 +_4 3 = 0$) * $2^{-1} = 2$ (since $2 +_4 2 = 0$) * $3^{-1} = 1$ (since $3 +_4 1 = 0$) ### Multiplication Modulo $p$ ($\mathbb{Z}_p^*$) Let $p$ be a prime number. The set of non-zero elements $\mathbb{Z}_p^* = \{1, 2, \dots, p-1\}$ forms an abelian group under multiplication modulo $p$ ($\times_p$). --- ## 6. Subgroups A **subgroup** is a group contained within a larger group. ### Formal Definition A non-empty subset $H$ of a group $\langle G, * \rangle$ is a **subgroup** of $G$ (denoted $H \le G$) if $\langle H, * \rangle$ itself satisfies all group axioms under the induced operation $*$. Every group $\langle G, * \rangle$ with $|G| \ge 2$ contains at least two subgroups: 1. **Trivial Subgroup**: $\{e\}$ 2. **Improper Subgroup**: $G$ itself Subgroups other than these are called **proper subgroups**. ### The Subgroup Criterion Theorems To determine if a subset $H \subseteq G$ is a subgroup, we do not need to verify all four group axioms. We can use simpler criteria. #### Theorem 7: Two-Step Subgroup Test A non-empty subset $H$ of a group $\langle G, * \rangle$ is a subgroup of $G$ if and only if: 1. $\forall a, b \in H \implies a * b \in H$ (Closed under the operation) 2. $\forall a \in H \implies a^{-1} \in H$ (Closed under inverses) #### Theorem 8: One-Step Subgroup Test A non-empty subset $H$ of a group $\langle G, * \rangle$ is a subgroup of $G$ if and only if: $$\forall a, b \in H \implies a * b^{-1} \in H$$ ##### Proof **Forward Direction ($\implies$)**: Assume $H \le G$. Let $a, b \in H$. Since $H$ is a group, $b^{-1} \in H$. By closure in $H$, $a * b^{-1} \in H$. **Backward Direction ($\impliedby$)**: Assume $H \subseteq G$ is non-empty and satisfies $a, b \in H \implies a * b^{-1} \in H$. 1. **Identity Element**: Since $H$ is non-empty, there exists some element $x \in H$. Applying the hypothesis with $a = x$ and $b = x$: $$x * x^{-1} \in H \implies e \in H$$ Thus, $H$ contains the identity element. 2. **Inverses**: Let $y \in H$. Since we know $e \in H$, let $a = e$ and $b = y$: $$e * y^{-1} \in H \implies y^{-1} \in H$$ Thus, every element in $H$ has its inverse in $H$. 3. **Closure**: Let $u, v \in H$. Since $v \in H$, its inverse $v^{-1} \in H$. Let $a = u$ and $b = v^{-1}$. Applying the hypothesis: $$u * (v^{-1})^{-1} \in H \implies u * v \in H$$ Thus, $H$ is closed under $*$. 4. **Associativity**: Since $H \subseteq G$, associativity holds in $H$ because it holds in the parent group $G$. Hence, $H$ is a subgroup of $G$. $\blacksquare$ --- ## 7. Homomorphisms and Isomorphisms Homomorphisms are functions that preserve structural relationships between different algebraic systems. ### Homomorphism Let $\langle G, * \rangle$ and $\langle H, \oplus \rangle$ be two groups. A function $f: G \to H$ is a **homomorphism** if: $$\forall a, b \in G, \quad f(a * b) = f(a) \oplus f(b)$$ ```text Group G Group H ┌───────────────┐ ┌───────────────┐ │ a * b │ ────────────────> │ f(a) ⊕ f(b) │ │ │ │ │ │ │ │ ▼ │ │ ▼ │ │ (a*b) │ ────────────────> │ f(a*b) │ └───────────────┘ Homomorphism └───────────────┘ f ``` This mapping allows us to perform an operation in the domain group $G$ and then map it to $H$, yielding the same result as mapping the elements to $H$ first and then performing the target operation. #### Example Consider the group of integers under addition $\langle \mathbb{Z}, + \rangle$ and the group of non-zero real numbers under multiplication $\langle \mathbb{R}^*, \cdot \rangle$. Let $f: \mathbb{Z} \to \mathbb{R}^*$ be defined by: $$f(n) = 2^n$$ We check if the mapping is a homomorphism: $$f(n + m) = 2^{n + m} = 2^n \cdot 2^m = f(n) \cdot f(m)$$ Because the operation is preserved, $f$ is a group homomorphism. ### Isomorphism A homomorphism $f: G \to H$ is an **isomorphism** if it is a **bijection** (both one-to-one and onto). If an isomorphism exists between $G$ and $H$, we say $G$ is isomorphic to $H$, denoted: $$G \cong H$$ Isomorphic groups are structurally identical; they differ only in the notation used for their elements and operations. --- ## 8. Summary * **Algebraic Systems** are built on set closure. Adding associativity gives a **semigroup**, adding a unique identity element gives a **monoid**, and adding unique inverses gives a **group**. * An **Abelian Group** is a group that also satisfies the commutative property. * The **uniqueness of identities and inverses**, alongside the **cancellation laws** and the relation $(a * b)^{-1} = b^{-1} * a^{-1}$, form the foundational mechanics of group operations. * **Subgroups** are subsets that form groups under the same operation. They can be verified using the single-step criterion: $a, b \in H \implies a * b^{-1} \in H$. * **Homomorphisms** are functions between groups that preserve the underlying algebraic operations, such that $f(a * b) = f(a) \oplus f(b)$. An **isomorphism** is a bijective homomorphism, indicating that two groups share the exact same algebraic structure.A non-empty set combined with one or more binary operations that are closed on the set.
A semigroup is a closed, associative algebraic system; a monoid is a semigroup that also possesses a unique identity element.
A monoid in which every element has a unique inverse under the specified binary operation.
A non-empty subset of a group that forms a group in its own right under the induced group operation.
A structure-preserving map between two algebraic systems that commutes with their respective binary operations.
Test your understanding with 5 questions
What is the order of the element $-i$ in the multiplicative group $G = \{1, -1, i, -i\}$?
Which of the following is a necessary and sufficient condition for a non-empty subset $H$ of a group $(G, *)$ to be a subgroup?
Consider the algebraic system $(\mathbb{Z}, *)$ where the binary operation is defined as $a * b = \max(a, b)$. Which algebraic structure does this represent?
Let $f: (G, *) \to (H, \oplus)$ be a group homomorphism. Which of the following properties is always true?
What is the inverse of the element $3$ in the group $(\mathbb{Z}_6, +_6)$ under addition modulo 6?
6 Modules
6 Modules