Semi Groups

Definition

A semigroup is a non-empty set $S$ together with a binary operation $*$ such that:

1. Closure

• For every $a, b \in S$, the result $a * b$ is also in $S$.

2. Associativity

• For every $a, b, c \in S$, $$(a * b) * c = a * (b * c)$$

So, a semigroup is written as $(S, *)$, where the operation is associative.

Important notes about the definition

• A semigroup does not require an identity element.
• A semigroup does not require inverse elements.
• The operation can be addition, multiplication, composition, string concatenation, matrix multiplication, or any other associative binary operation.

Example

Let $S = \{1, 2, 3\}$ and define the operation $a * b = \max(a, b)$.

• Closure holds because the maximum of two elements of $S$ is still in $S$.
• Associativity holds because: $$\max(\max(a, b), c) = \max(a, \max(b, c))$$ Thus, $(S, \max)$ is a semigroup.

---

Main Content

1. Binary Operation and Closure

• A semigroup begins with a binary operation, meaning a rule that combines two elements of a set to produce one result.
• The result must always remain inside the same set, which is known as closure.

Explanation

If $S$ is a set and $*$ is a binary operation on $S$, then for every $a, b \in S$, the element $a * b$ must also belong to $S$. This is essential because if the result ever leaves the set, the structure is no longer properly defined as an algebraic system on that set.

Example 1: Addition on natural numbers

Let $S = \mathbb{N}$, the set of natural numbers, and operation be addition.

• $2 + 5 = 7 \in \mathbb{N}$
• $10 + 15 = 25 \in \mathbb{N}$

So closure holds.

Example 2: Multiplication on integers

Let $S = \mathbb{Z}$, the set of integers, and operation be multiplication.

• $3 \times (-4) = -12 \in \mathbb{Z}$
• $(-2) \times (-5) = 10 \in \mathbb{Z}$

Again, closure holds.

Non-example

Let $S = \mathbb{N}$ and operation be subtraction.

• $3 - 5 = -2$, which is not in $\mathbb{N}$

So subtraction is not closed on natural numbers, hence it cannot be a semigroup operation on $\mathbb{N}$.

---

2. Associative Property

• The most important condition for a semigroup is associativity.
• The way elements are grouped does not affect the final result.

Explanation

A binary operation $*$ is associative if for all $a, b, c \in S$: $$(a * b) * c = a * (b * c)$$ This property allows us to combine multiple elements without worrying about parentheses.

Example 1: Addition

For integers: $$(2 + 3) + 4 = 5 + 4 = 9$$ $$2 + (3 + 4) = 2 + 7 = 9$$ Thus, addition is associative.

Example 2: String concatenation

Let $a =$ "A", $b =$ "B", $c =$ "C".

• $(a \cdot b) \cdot c =$ "AB" + "C" = "ABC"
• $a \cdot (b \cdot c) =$ "A" + "BC" = "ABC"

So string concatenation is associative.

Non-example

Subtraction is not associative: $$(10 - 5) - 2 = 3$$ but $$10 - (5 - 2) = 7$$ Since these are not equal, subtraction is not associative.

Why associativity matters

• It makes repeated operations well-defined.
• It simplifies calculations.
• It allows the use of bracket-free expressions such as $a * b * c * d$.

---

3. Types, Examples, and Related Structures

• Semigroups may be classified into several useful forms depending on the operation and the presence of special elements.
• Semigroups are closely related to monoids and groups, but they are more general.

Common types of semigroups

a) Commutative semigroup

A semigroup is commutative if: $$a * b = b * a \quad \text{for all } a, b \in S$$ Example:

• $(\mathbb{Z}, +)$ is commutative because $a+b=b+a$

b) Monoid

A monoid is a semigroup with an identity element.

• Example: $(\mathbb{N}_0, +)$, where $0$ is the identity
• Here, $a + 0 = 0 + a = a$

c) Group

A group is a monoid in which every element has an inverse.

• Example: $(\mathbb{Z}, +)$ is a group because every integer $a$ has additive inverse $-a$

Thus, every group is a monoid and every monoid is a semigroup, but not every semigroup is a monoid or group.

Example of a semigroup that is not a monoid

Let $S = \{1, 2, 3\}$ with operation $\max$.

• It is associative and closed.
• But there is no identity element in the set that leaves every element unchanged under $\max$.

So it is a semigroup, but not a monoid.

Example of a semigroup in real life

Consider operations like:

• combining instructions in a program,
• concatenating words,
• composing functions,
• combining state transitions.

These are naturally associative and often form semigroups.

---

Working / Process

1. Identify the set

• Choose a non-empty set $S$, such as numbers, strings, matrices, or functions.

2. Define the operation

• Specify how two elements of the set are combined, for example addition, multiplication, concatenation, or composition.

3. Verify semigroup properties

• Check closure: the result stays in the set.
• Check associativity: $(a * b) * c = a * (b * c)$ for all elements.
• If both conditions hold, the structure is a semigroup.

Example process

Let $S = \{0, 1\}$ and define $a * b = a \lor b$ (logical OR).

• Step 1: Set is non-empty.
• Step 2: Operation is OR.
• Step 3:
• Closure: OR of 0 and 1 is still in $\{0,1\}$
• Associativity: $(a \lor b) \lor c = a \lor (b \lor c)$

Therefore, $(\{0,1\}, \lor)$ is a semigroup.

Visual intuition for associativity

For three elements $a, b, c$, associativity means the result is the same regardless of grouping:

(a * b) * c  =  a * (b * c)

This means:

• first combine $a$ and $b$, then combine with $c$, or
• first combine $b$ and $c$, then combine with $a$,

the outcome remains unchanged.

---

Advantages / Applications

• Semigroups provide a foundation for advanced algebraic structures such as monoids, groups, rings, and transformation algebras.
• They are widely used in computer science, especially in automata theory, formal languages, string processing, and compiler design.
• They help model composable processes, such as function composition, data transformations, and sequential operations in mathematics and engineering.

Additional applications

String concatenation

• words and sentences are built by combining smaller strings.

Function composition

• composing mappings is associative.

Finite state machines

• transitions can be studied using semigroup ideas.

Database and software workflows

• repeated combining of tasks or operations often follows semigroup-like rules.

Mathematical modeling

• many iterative systems are easier to study using semigroup theory.

---

Summary

• A semigroup is a non-empty set with a closed, associative binary operation.
• It is one of the simplest algebraic structures and is the basis for monoids and groups.
• Semigroups appear in many areas through operations like addition, multiplication, concatenation, and composition.
• Important terms to remember: semigroup, binary operation, closure, associativity, commutative semigroup, monoid, group.