Foundations of Algebraic Structures, Relations & Modular Arithmetic

### 1. Cartesian Products and Binary Relations Let $A$ and $B$ be non-empty sets. The **Cartesian product** $A \times B$ is the set of all ordered pairs: $$A \times B = \{ (a, b) : a \in A, \; b \in B \}$$ A **binary relation** $R$ from $A$ to $B$ is a subset $R \subseteq A \times B$. When $A = B$, we say $R$ is a binary relation on $A$. If $(a, b) \in R$, we write $a \sim b$ or $a \, R \, b$. --- ### 2. Axioms of an Equivalence Relation > **Definition 1.1 (Equivalence Relation):** > A binary relation $\sim$ on a set $A$ is an **equivalence relation** if it satisfies the following three fundamental axioms for all elements $a, b, c \in A$: > 1. **Reflexivity:** $a \sim a, \quad \forall a \in A$. > 2. **Symmetry:** If $a \sim b$, then $b \sim a$. > 3. **Transitivity:** If $a \sim b$ and $b \sim c$, then $a \sim c$. #### Definition 1.2 (Equivalence Class): Let $\sim$ be an equivalence relation on set $A$. For any $a \in A$, the **equivalence class** of $a$, denoted by $[a]$ or $\text{cl}(a)$, is the set of all elements in $A$ related to $a$: $$[a] = \{ x \in A : x \sim a \}$$ Any element $x \in [a]$ is called a **representative** of the equivalence class $[a]$. --- ### 3. The Fundamental Theorem of Equivalence Relations A **partition** of a set $A$ is a collection $\mathcal{P} = \{A_i\}_{i \in I}$ of non-empty subsets of $A$ such that: 1. $A_i \cap A_j = \emptyset$ whenever $i \ne j$ (pairwise disjoint). 2. $\bigcup_{i \in I} A_i = A$ (exhaustive union). > **Theorem 1.1 (The Fundamental Theorem of Equivalence Relations):** > Let $A$ be a non-empty set. > 1. If $\sim$ is an equivalence relation on $A$, the set of all equivalence classes $A / \sim \;= \{ [a] : a \in A \}$ forms a partition of $A$. > 2. Conversely, every partition $\mathcal{P}$ of $A$ induces a unique equivalence relation $\sim$ on $A$ whose equivalence classes are precisely the cells of $\mathcal{P}$. #### Complete Proof of Part 1: - **Non-emptiness:** For every $a \in A$, by reflexivity $a \sim a$, so $a \in [a]$. Thus no equivalence class is empty: $[a] \ne \emptyset$. - **Exhaustive coverage:** Since $a \in [a]$ for all $a \in A$, we have: $$A = \bigcup_{a \in A} \{a\} \subseteq \bigcup_{a \in A} [a] \subseteq A \implies \bigcup_{a \in A} [a] = A$$ - **Pairwise disjointness:** Let $a, b \in A$. We must prove that either $[a] = [b]$ or $[a] \cap [b] = \emptyset$. Suppose $[a] \cap [b] \ne \emptyset$. Then there exists $z \in [a] \cap [b]$. By definition of equivalence class: $$z \in [a] \implies z \sim a \implies a \sim z \quad (\text{by symmetry})$$ $$z \in [b] \implies z \sim b$$ Now take any $x \in [a]$. Then $x \sim a$. Applying transitivity sequentially: $$x \sim a \text{ and } a \sim z \implies x \sim z$$ $$x \sim z \text{ and } z \sim b \implies x \sim b \implies x \in [b]$$ Hence $[a] \subseteq [b]$. By symmetrical reasoning, $[b] \subseteq [a]$. Therefore $[a] = [b]$. Consequently, distinct equivalence classes are strictly disjoint. $\blacksquare$

### 1. Congruence Modulo $n$ Let $n$ be a positive integer ($n \in \mathbb{Z}^+$). > **Definition 1.3 (Congruence Modulo $n$):** > Two integers $a, b \in \mathbb{Z}$ are **congruent modulo $n$**, written: > $$a \equiv b \pmod n$$ > if $n$ divides their difference: $n \mid (a - b)$, or equivalently, there exists $k \in \mathbb{Z}$ such that $a - b = k n$. #### Proposition 1.1: Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$. - **Reflexivity:** $a - a = 0 = 0 \cdot n \implies a \equiv a \pmod n$. - **Symmetry:** If $a \equiv b \pmod n$, then $a - b = kn \implies b - a = (-k)n \implies b \equiv a \pmod n$. - **Transitivity:** If $a \equiv b \pmod n$ and $b \equiv c \pmod n$, then $a - b = kn$ and $b - c = jn$. Adding: $(a - b) + (b - c) = a - c = (k + j)n \implies a \equiv c \pmod n$. $\blacksquare$ --- ### 2. The Set of Residue Classes $\mathbb{Z}_n$ The equivalence classes are the **residue classes modulo $n$**: $$[a] = \{ x \in \mathbb{Z} : x \equiv a \pmod n \} = \{ a + kn : k \in \mathbb{Z} \}$$ By the Division Algorithm, for every $a \in \mathbb{Z}$ there exist unique $q, r \in \mathbb{Z}$ with $0 \le r < n$ such that $a = qn + r$. Hence, there are exactly $n$ distinct equivalence classes: $$\mathbb{Z}_n = \{ [0], [1], [2], \dots, [n-1] \}$$ #### Well-Defined Modular Operations: Define addition and multiplication on residue classes by: $$[a] + [b] = [a + b], \qquad [a] \cdot [b] = [a \cdot b]$$ *Proof of Well-Definedness:* Suppose $[a] = [a']$ and $[b] = [b']$. Then $a' = a + kn$ and $b' = b + jn$. Then: $$a' + b' = (a + b) + (k + j)n \equiv a + b \pmod n \implies [a' + b'] = [a + b]$$ $$a' b' = (a + kn)(b + jn) = ab + n(aj + bk + kjn) \equiv ab \pmod n \implies [a' b'] = [ab]$$ Thus, the operations are completely independent of class representatives! --- ### 3. Bézout's Identity & Modular Multiplicative Inverses > **Theorem 1.2 (Bézout's Identity):** > Let $a, b \in \mathbb{Z}$ with $\gcd(a, b) = d$. Then there exist integers $x, y \in \mathbb{Z}$ such that: > $$a x + b y = d$$ > **Theorem 1.3 (Existence of Modular Inverse):** > A residue class $[a] \in \mathbb{Z}_n$ possesses a multiplicative inverse $[a]^{-1} \in \mathbb{Z}_n$ such that $[a] \cdot [x] = [1]$ if and only if: > $$\gcd(a, n) = 1$$ #### Proof: $(\implies)$ If $[a][x] = [1]$, then $a x \equiv 1 \pmod n \implies a x - 1 = k n \implies a x - n k = 1$. Any divisor of both $a$ and $n$ must divide $a x - n k = 1$. Hence $\gcd(a, n) = 1$. $(\impliedby)$ If $\gcd(a, n) = 1$, by Bézout's Identity there exist integers $x, y \in \mathbb{Z}$ such that: $$a x + n y = 1 \implies a x - 1 = (-y) n \implies a x \equiv 1 \pmod n \implies [a][x] = [1]$$ Thus $[x]$ is the required modular inverse. $\blacksquare$ The set of all invertible elements forms the **Group of Units Modulo $n$**: $$U(n) = \mathbb{Z}_n^\times = \{ [a] \in \mathbb{Z}_n : \gcd(a, n) = 1 \}$$ with order given by **Euler's totient function**: $|U(n)| = \phi(n)$.

### 1. Binary Operations and Algebraic Structures Let $S$ be a non-empty set. > **Definition 1.4 (Binary Operation):** > A **binary operation** $*$ on $S$ is a function $*: S \times S \to S$. > That is, for every ordered pair $(a, b) \in S \times S$, $*$ assigns a unique element $a * b \in S$. > This property is termed **Closure**: $\forall a, b \in S, \; a * b \in S$. #### Hierarchy of Algebraic Structures: 1. **Magma / Groupoid:** A set $S$ equipped with a closed binary operation $*$. 2. **Semigroup:** A magma $(S, *)$ that satisfies **Associativity**: $$\forall a, b, c \in S, \quad (a * b) * c = a * (b * c)$$ 3. **Monoid:** A semigroup $(S, *)$ possessing an **Identity Element** $e \in S$: $$\forall a \in S, \quad a * e = e * a = a$$ --- ### 2. The Axiomatic Definition of a Group A group is the foundational algebraic structure of modern symmetry and mathematical physics. > **Definition 1.5 (Group):** > A **group** is an ordered pair $(G, *)$ consisting of a non-empty set $G$ and a binary operation $*$ on $G$ that satisfies the following four **Group Axioms**: > 1. **Closure ($G_1$):** > $$\forall a, b \in G, \quad a * b \in G$$ > 2. **Associativity ($G_2$):** > $$\forall a, b, c \in G, \quad (a * b) * c = a * (b * c)$$ > 3. **Identity Element ($G_3$):** > There exists an element $e \in G$ such that: > $$\forall a \in G, \quad a * e = e * a = a$$ > 4. **Inverse Element ($G_4$):** > For every element $a \in G$, there exists an element $a^{-1} \in G$ such that: > $$a * a^{-1} = a^{-1} * a = e$$ #### Definition 1.6 (Abelian / Commutative Group): A group $(G, *)$ is called **Abelian** (named in honor of Niels Henrik Abel) if the binary operation satisfies commutativity: $$\forall a, b \in G, \quad a * b = b * a$$ If there exist elements $x, y \in G$ such that $x * y \ne y * x$, the group is **Non-Abelian**.

### 1. Uniqueness Theorems While the group axioms state the existence of an identity and inverses, their uniqueness is a mathematical consequence of the axioms. > **Theorem 1.4 (Uniqueness of the Identity Element):** > In any group $(G, *)$, the identity element is unique. #### Proof: Suppose $e$ and $e'$ are both identity elements in $G$. Since $e$ is an identity: $e * e' = e'$. Since $e'$ is an identity: $e * e' = e$. Therefore: $$e = e * e' = e'$$ Thus, there can be only one identity element. $\blacksquare$ --- > **Theorem 1.5 (Uniqueness of Inverse Elements):** > In any group $(G, *)$, every element $a \in G$ possesses a unique inverse $a^{-1}$. #### Proof: Suppose $b$ and $c$ are both inverses of $a$. Then: $$a * b = b * a = e \quad \text{and} \quad a * c = c * a = e$$ Using associativity: $$b = b * e = b * (a * c) = (b * a) * c = e * c = c$$ Hence $b = c$. The inverse is strictly unique. $\blacksquare$ --- ### 2. The Cancellation Laws > **Theorem 1.6 (Cancellation Laws):** > In any group $(G, *)$, for all $a, b, c \in G$: > 1. **Left Cancellation:** If $a * b = a * c$, then $b = c$. > 2. **Right Cancellation:** If $b * a = c * a$, then $b = c$. #### Proof of Left Cancellation: Since $a \in G$, its inverse $a^{-1}$ exists. Multiply both sides on the left by $a^{-1}$: $$a^{-1} * (a * b) = a^{-1} * (a * c)$$ By associativity: $$(a^{-1} * a) * b = (a^{-1} * a) * c$$ $$e * b = e * c \implies b = c \quad \blacksquare$$ --- ### 3. The Shoes-and-Socks Property and Involutions > **Theorem 1.7 (Inverse of Products):** > For any elements $a, b \in G$: > $$(a * b)^{-1} = b^{-1} * a^{-1}$$ #### Proof: We verify that multiplying $(a * b)$ by $(b^{-1} * a^{-1})$ yields the identity $e$: $$(a * b) * (b^{-1} * a^{-1}) = a * (b * b^{-1}) * a^{-1} = a * e * a^{-1} = a * a^{-1} = e$$ Similarly, on the left: $$(b^{-1} * a^{-1}) * (a * b) = b^{-1} * (a^{-1} * a) * b = b^{-1} * e * b = b^{-1} * b = e$$ By uniqueness of the inverse, $(a * b)^{-1} = b^{-1} * a^{-1}$. $\blacksquare$ *(Physical analogy: You put on socks then shoes ($a * b$); to reverse the process, you must remove shoes then socks ($b^{-1} * a^{-1}$)!)* #### Proposition 1.2 (Double Inverse Law): For every $a \in G$: $$(a^{-1})^{-1} = a$$