Algebraic Systems and Binary Operations

Algebraic structures provide a unified mathematical framework for studying sets equipped with operations that combine elements. This curriculum covers the progressive building blocks of abstract algebra, progressing from basic binary operations to semigroups, monoids, groups, and subgroups.

1. Fundamentals of Binary Operations and Algebraic Systems

To establish these algebraic structures, we begin with foundational sets:

$\mathbb{N} = \{1, 2, 3, \dots\}$ : Set of all natural numbers.
$\mathbb{Z} = \{0, \pm 1, \pm 2, \pm 3, \dots\}$ : Set of all integers.
$\mathbb{Q} = \{ \frac{p}{q} \mid p, q \in \mathbb{Z}, q \neq 0 \}$ : Set of all rational numbers.
$\mathbb{R}$ : Set of all real numbers.

Binary Operation

A binary operation $*$ on a non-empty set $A$ is a function $*: A \times A \to A$ . We say that the operation is closed on $A$ if:

a * b \in A \quad \forall a, b \in A \quad \text{(Closure Property)}

Example 1: The set $\mathbb{N}$ is closed under addition ( $+$ ) and multiplication ( $\cdot$ ) because the sum and product of any two natural numbers are also natural numbers.
Example 2: The set $\mathbb{N}$ is not closed under subtraction ( $-$ ) because $2 - 5 = -3 \notin \mathbb{N}$ , nor is it closed under division () because .

Algebraic System

An algebraic system (or algebraic structure) is a non-empty set $A$ together with one or more binary operations defined on it. It is formally written as an ordered tuple:

(A, *_1, *_2, \dots, *_n)

Examples: $(\mathbb{N}, +)$ , $(\mathbb{Z}, +, -)$ , and $(\mathbb{R}, +, \cdot, -)$ are all valid algebraic systems.

The hierarchy of algebraic structures based on the algebraic properties they satisfy is structured as follows:

text

       Algebraic Systems (Set + Binary Operation)
                  │
                  ▼
         Semigroups (Closed + Associative)
                  │
                  ▼
         Monoids (Semigroup + Identity)
                  │
                  ▼
         Groups (Monoid + Inverses)
                  │
                  ▼
       Abelian Groups (Group + Commutative)

2. Properties of Binary Operations

Let $*$ be a binary operation defined on a set $A$ .

Commutativity

The operation $*$ is commutative in $A$ if the order of operands does not affect the output:

a * b = b * a \quad \forall a, b \in A

Associativity

The operation $*$ is associative in $A$ if the grouping of operations does not alter the final result:

(a * b) * c = a * (b * c) \quad \forall a, b, c \in A

Identity Element

For an algebraic system $(A, *)$ , an element $e \in A$ is called the identity element of $A$ if:

a * e = e * a = a \quad \forall a \in A

Theorem: If an identity element exists in an algebraic system $(A, *)$ , it is unique.

Proof: Assume $e_1$ and $e_2$ are two distinct identity elements in $A$ . Since is an identity:

Inverse Element

Let $(A, *)$ be an algebraic system with unique identity $e$ . An element $b \in A$ is said to be the inverse of $a \in A$ if:

a * b = b * a = e

We denote the inverse of $a$ as $a^{-1}$ .

3. Semigroups and Monoids

We can now classify algebraic structures by layering these properties.

Semigroup

An algebraic system $(A, *)$ is a semigroup if it satisfies the following two axioms:

Closure: $*$ is a closed operation on $A$ ( $\forall a,b \in A, a * b \in A$ ).
Associativity: $*$ is associative on $A$ ().

Examples:
- $(\mathbb{N}, +)$ is a semigroup.
- $(\mathbb{N}, \cdot)$ is a semigroup.
- $(\mathbb{N}, -)$ is not a semigroup because subtraction is neither closed nor associative on $\mathbb{N}$ .

Subsemigroup

Consider a semigroup $(S, *)$ and let $T \subseteq S$ . The system $(T, *)$ is a subsemigroup of $(S, *)$ if $T$ is closed under the operation :

a, b \in T \implies a * b \in T

Example: Let $( \mathbb{N}, + )$ be a semigroup. Let $\mathbb{E} = \{2, 4, 6, \dots\}$ be the set of positive even integers. Since the sum of two even integers is always even, $(\mathbb{E}, +)$ is closed and therefore a subsemigroup of .

Theorem: Product Semigroups

If $(S_1, *_1)$ and $(S_2, *_2)$ are semigroups, then their Cartesian product is a semigroup under the component-wise operation defined by:

(s_1', s_2') * (s_1'', s_2'') = (s_1' *_1 s_1'', \ s_2' *_2 s_2'')

Proof:

Closure: Since $S_1$ is closed under $*_1$ , $s_1' *_1 s_1'' \in S_1$ . Since is closed under , . Thus, .

Monoid

An algebraic system $(A, *)$ is a monoid if it satisfies three axioms:

Closure: $\forall a,b \in A, a*b \in A$ .
Associativity: $\forall a,b,c \in A, (a*b)*c = a*(b*c)$ .

Example 1: Show that $(\mathbb{N}, \cdot)$ $(N, \cdot)$ is a monoid.
- Closure: Product of two natural numbers is a natural number.
- Associativity: Multiplication is associative over $\mathbb{N}$ .
- Identity: $1 \in \mathbb{N}$ serves as the identity element because $a \cdot 1 = 1 \cdot a = a$ for all .

Submonoid

Let $(M, *)$ be a monoid with identity element $e$ . A subset $S \subseteq M$ is a submonoid of $M$ if and only if:

$S$ is closed under the operation $*$ .
The identity element $e$ of $M$ belongs to $S$ ( $e \in S$ ).

4. Special Algebraic Systems

Clock Algebra $\langle M, T \rangle$

Let $M = \{1, 2, \dots, m\}$ . Let $T$ be a unary operation on $M$ given by:

\begin{aligned} T(j) &= j + 1 \quad \text{for } j \neq m \\ T(m) &= 1 \end{aligned}

The element $1 \in M$ acts as a generator of the algebra. By repeatedly applying the unary operator $T$ starting from $1$ , we can generate the entire set $M$ :

text

 1 ──T──► 2 ──T──► 3 ──T──► ... ──T──► m ──T──► 1

Composition Monoid $\langle F, \circ \rangle$

Let $X = \{1, 2, 3, 4\}$ , and let $f: X \to X$ be defined by the set of ordered pairs:

f = \{\langle 1,2 \rangle, \langle 2,3 \rangle, \langle 3,4 \rangle, \langle 4,1 \rangle\}

We can form composite functions by composing $f$ with itself:

$f^2 = f \circ f = \{\langle 1,3 \rangle, \langle 2,4 \rangle, \langle 3,1 \rangle, \langle 4,2 \rangle\}$

The collection of functions $F = \{f^0, f, f^2, f^3\}$ under the binary operation of function composition $\circ$ forms an algebraic system .

5. Groups and Abelian Groups

Group

An algebraic system $(G, *)$ is a group if it satisfies the following four conditions:

Closure: $a * b \in G \quad \forall a, b \in G$ .
Associativity: $(a * b) * c = a * (b * c) \quad \forall a, b, c \in G$ .

Abelian Group

A group $(G, *)$ is called Abelian (or commutative) if the operation satisfies the commutative law:

a * b = b * a \quad \forall a, b \in G

Classic Examples of Groups

Integer Addition Group $(\mathbb{Z}, +)$

Show that $(\mathbb{Z}, +)$ is an Abelian group.

Closure: The sum of any two integers $a + b \in \mathbb{Z}$ .
Associativity: Integer addition is associative: $(a + b) + c = a + (b + c)$ .

Hence, $(\mathbb{Z}, +)$ is an Abelian group.

Non-Zero Real Multiplication Group $(\mathbb{R}^*, \cdot)$

Let $\mathbb{R}^*$ be the set of all non-zero real numbers.

Closure: The product of two non-zero reals is a non-zero real ( $a \cdot b \in \mathbb{R}^*$ ).
Associativity: Real multiplication is associative: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ .

Hence, $(\mathbb{R}^*, \cdot)$ is an Abelian group.

Note: The entire set of real numbers $\mathbb{R}$ under multiplication $(\mathbb{R}, \cdot)$ is not a group because the element $0 \in \mathbb{R}$ has no multiplicative inverse ( $1/0$ is undefined).

Positive Rational Scaling Group $(\mathbb{Q}^+, *)$

Let $A = \mathbb{Q}^+$ (positive rational numbers) and let $*$ be defined by $a * b = \frac{ab}{2}$ .

Closure: Since $a, b$ are positive rationals, $\frac{ab}{2}$ is also a positive rational.
Associativity:
$(a * b) * c = \left(\frac{ab}{2}\right) * c = \frac{\left(\frac{ab}{2}\right)c}{2} = \frac{abc}{4}$

Hence, $(\mathbb{Q}^+, *)$ is an Abelian group.

6. Mathematical Theorems of Group Theory

For any group $(G, *)$ , the following fundamental properties hold:

Theorem: Uniqueness of Inverses

The inverse of any element $a \in G$ is unique.

Proof: Let $b$ and $c$ be two inverse elements of $a$ . By the definition of an inverse:

$a * b = e \quad \text{and} \quad a * c = e$

Since , we apply the left cancellation law (multiplying by the inverse of on the left):

Theorem: Cancellation Laws

In any group $(G, *)$ , left and right cancellation laws hold:

Left Cancellation: $a * b = a * c \implies b = c$
Right Cancellation: $b * a = c * a \implies b = c$

Proof (Left Cancellation): Since $G$ is a group, $a^{-1}$ exists for all $a \in G$ .
$\begin{aligned} a * b = a * c & ⟹ a^{- 1} * (a * b) = a^{- 1} * (a * c) \end{aligned}$

Theorem: Inverse of a Product (Socks-and-Shoes)

For any $a, b \in G$ , $(a * b)^{-1} = b^{-1} * a^{-1}$ .

Proof: Let us compute the product of $(a * b)$ and $(b^{-1} * a^{-1})$ :
$\begin{aligned} ( \end{aligned}$

Theorem: Self-Inverse Implies Commutativity

If every element of a group $G$ is its own inverse (i.e., $a = a^{-1}$ for all $a \in G$ ), then $G$ must be Abelian.

Proof: Let $a, b \in G$ . Since every element is its own inverse, we have:

$a = a^{-1}, \quad b = b^{-1}, \quad \text{and} \quad (a * b) = (a * b)^{-1}$

Theorem: Square Condition for Commutativity

In a group $(G, *)$ , if $(a * b)^2 = a^2 * b^2$ for all , then is an Abelian group.

Proof: Note that $x^2 = x * x$ . Given:

$(a * b)^2 = a^2 * b^2 \implies (a * b) * (a * b) = (a * a) * (b * b)$

7. Finite Groups and Cayley Tables

The order of a group $G$ , denoted by $|G|$ or $o(G)$ , is the number of elements in the set $G$ . If the order is finite, the group is called a finite group. We can visualize finite groups using Cayley Tables (composition tables).

Example 1: $G = \{1, -1\}$ under multiplication

The composition table is:

| $\cdot$ | $1$ | $-1$ | | :--- | :--- | :--- | | $1$ | $1$ | $-1$ | | $-1$ | $-1$ | |

Closure: All entries are elements of $G$ .
Identity: $1$ is the identity element.
Inverses: $1^{-1} = 1$ , and $(-1)^{-1} = -1$ .

Example 2: $G = \{1, \omega, \omega^2\}$ (Cube Roots of Unity)

Here, $\omega^3 = 1$ and $1 + \omega + \omega^2 = 0$ . The composition table under multiplication is:

| $\cdot$ | $1$ | $\omega$ | $\omega^2$ | | :--- | :--- | :--- | :--- | | $1$ | $1$ | $\omega$ | | | | | | | | | | | |

Identity: $1$
Inverses: $1^{-1} = 1$ , $\omega^{-1} = \omega^2$ , and .

Example 3: $G = \{1, -1, i, -i\}$ (Fourth Roots of Unity)

The composition table under multiplication ( $i^2 = -1$ ) is:

| $\cdot$ | $1$ | $-1$ | $i$ | $-i$ | | :--- | :--- | :--- | :--- | :--- | | $1$ | $1$ | $-1$ | | | | | | | | | | | | | | | | | | | | |

Identity: $1$
Inverses: $1^{-1} = 1$ , $(-1)^{-1} = -1$ , , and .

8. Modulo Arithmetic Systems

Modulo operations offer a way to construct finite groups over integers.

Addition Modulo $m$ ( $+_m$ )

For a positive integer $m$ and any $a, b \in \mathbb{Z}$ :

a +_m b = (a + b) \pmod m

This represents the remainder $r$ ( $0 \le r < m$ ) obtained when $a+b$ is divided by $m$ .

Multiplication Modulo $p$ ( $\times_p$ )

For a positive integer $p$ and any $a, b \in \mathbb{Z}$ :

a \times_p b = (ab) \pmod p

This represents the remainder $r$ ( $0 \le r < p$ ) obtained when the product $ab$ is divided by $p$ .

Example 1: Additive Group $\langle \mathbb{Z}_6, +_6 \rangle$

Let $G = \{0, 1, 2, 3, 4, 5\}$ under $+_6$ .

| $+_6$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

Identity: $0$
Inverses:
- $0^{-1} = 0$
- $1^{-1} = 5$ (since $1 +_6 5 = 0$ )

Example 2: Multiplicative Group $\langle \mathbb{Z}_7^*, \times_7 \rangle$

Let $G = \{1, 2, 3, 4, 5, 6\}$ under multiplication modulo $7$ .

| $\times_7$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

Identity: $1$
Inverses: $1^{-1}=1$ , $2^{-1}=4$ , $3^{-1}=5$ , , , and .

General Modulo Rules:

The set $\mathbb{Z}_m = \{0, 1, 2, \dots, m-1\}$ forms an Abelian group under addition modulo $m$ .

The set forms an Abelian group under multiplication modulo if and only if is a .

9. Subgroups, Order of Elements, and Morphisms

Subgroup

Let $(G, *)$ be a group. A non-empty subset $H \subseteq G$ is called a subgroup of $G$ if $(H, *)$ itself forms a group.

For any group $G$ , $\{e\}$ and $G$ are subgroups. These are called trivial (or improper) subgroups. All other subgroups are called proper subgroups.

Theorem: Necessary and Sufficient Subgroup Condition

A non-empty subset $H$ of a group $G$ is a subgroup of $G$ if and only if:

a, b \in H \implies a * b^{-1} \in H

Proof:

$(\implies)$ Direct Direction: If $H$ is a subgroup, it forms a group under $*$ . Since $b \in H$ , its inverse $b^{-1} \in H$ . Since is closed under , and .

Order of an Element

Let $a$ be an element of a group $(G, *)$ . The order of $a$ is the smallest positive integer $n$ such that:

a^n = \underbrace{a * a * \dots * a}_{n \text{ times}} = e

If no such finite integer $n$ exists, the element is said to have infinite order.

Example: In the multiplicative group $G = \{1, -1, i, -i\}$ $G = {1, - 1, i, - i}$ with identity $e = 1$ $e = 1$ :
- $\text{order}(1) = 1$ because .

Homomorphisms and Isomorphisms

Homomorphism

Let $(G, *)$ and $(G', \oplus)$ be two groups. A function $f: G \to G'$ is called a if it preserves the group operation:

f(a * b) = f(a) \oplus f(b) \quad \forall a, b \in G

text

       G (with operation *)             G' (with operation ⊕)
     ┌──────────────────────┐         ┌──────────────────────┐
     │      a  ,  b         │   f     │   f(a)  ,  f(b)      │
     │                      ├────────►│                      │
     │      a * b           │         │   f(a) ⊕ f(b)        │
     └──────────────────────┘         └──────────────────────┘
                 ▲                                ▲
                 └────────── preserves ───────────┘

Isomorphism

If a homomorphism $f: G \to G'$ is also a bijection (both one-to-one and onto), then $f$ is called an isomorphism. Under these conditions, the groups $G$ and $G'$ are structurally identical, denoted as .

Summary

An algebraic system is a set paired with one or more closed operations.
Semigroups represent associative closed structures, while monoids add a unique identity element.
A group requires closure, associativity, a unique identity, and unique inverses for every element. If commutativity holds, it is an Abelian group.
Subgroups are subsets that form groups on their own. The single-step check $a * b^{-1} \in H$ is a clean way to prove a subset is a subgroup.
Modulo arithmetic allows us to construct finite fields and cyclic groups, where $\mathbb{Z}_p^*$ forms a multiplicative group if and only if is prime.

Assessed progress

Algebraic Systems and Binary Operations

Key Concepts

Binary Operation

Semigroup and Monoid

Group

Abelian Group

Subgroup

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures