Semigroups and Subsemigroups

Algebraic structures form the mathematical bedrock of computer science, modern algebra, and cryptographic systems. In this guide, we will analyze the properties of binary operations, define algebraic systems, and thoroughly investigate semigroups and subsemigroups alongside their structural properties.

1. Introduction to Algebraic Systems and Binary Operations

To build complex algebraic systems, we must first establish the behavior of sets under various operations.

Binary Operations

A binary operator $*$ is a binary operation (or closed operation) on a non-empty set $A$ if it maps any two elements of $A$ to an element within $A$ . This is known as the closure property:

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

Example 1: The set of natural numbers $\mathbb{N} = \{1, 2, 3, \dots\}$ is closed under addition ( $+$ ) and multiplication ( $\cdot$ ). For any $a, b \in \mathbb{N}$ , we have:

Algebraic Systems

An algebraic system is defined as a non-empty set $A$ equipped with one or more binary operations. It is denoted as:

$(A, *, \oplus, \dots)$

Common examples of algebraic systems include:

$(\mathbb{N}, +)$
$(\mathbb{Z}, +, -)$ where $\mathbb{Z}$ represents all integers.
$(\mathbb{R}, +, \cdot, -)$ where represents all real numbers.

Structural Properties of Binary Operations

Let $(A, *)$ be an algebraic system.

Commutativity: The operation $*$ is commutative in $A$ if: $a * b = b * a \quad \forall a, b \in A$
Associativity: The operation $*$ is associative in if:

2. Foundations of Semigroups

A semigroup is one of the simplest yet most useful algebraic structures.

Definition

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

Closure: The binary operation $*$ is closed on $S$ . $a * b \in S \quad \forall a, b \in S$
Associativity: The operation $*$ is associative for all elements in .

text

       +------------------------------------+
       |          Algebraic System          |
       |             (S, *)                 |
       +-----------------+------------------+
                         |
                         | Must satisfy:
                         v
       +-----------------+------------------+
       | 1. Closure:     a * b ∈ S          |
       | 2. Associativity:                  |
       |    (a * b) * c = a * (b * c)       |
       +-----------------+------------------+
                         |
                         v
       +-----------------+------------------+
       |             SEMIGROUP              |
       +------------------------------------+

Key Semigroup Examples and Non-Examples

1. $(\mathbb{N}, +)$ and $(\mathbb{N}, \cdot)$

Addition ( $+$ ): The sum of any two natural numbers is a natural number (Closure). Addition is associative: $(a+b)+c = a+(b+c)$ . Thus, $(\mathbb{N}, +)$ is a semigroup.

2. $(\mathbb{N}, -)$ (Non-Example)

The system $(\mathbb{N}, -)$ is not a semigroup because:

It is not closed (e.g., $1 - 2 = -1 \notin \mathbb{N}$ ).
It is not associative: $(5 - 3) - 1 = 2 - 1 = 1$ Clearly, .

3. Positive Odd Integers under Multiplication

Let $A = \{1, 3, 5, 7, 9, \dots\}$ be the set of positive odd integers, with $*$ representing standard multiplication.

Closure: Let $a = 2k_1 + 1$ and $b = 2k_2 + 1$ (where ). Because is of the form , the product is always positive and odd. Hence, is closed on .

3. Subsemigroups

When a subset of a semigroup inherits the semigroup properties under the same operation, it forms a subsemigroup.

Definition

Consider a semigroup $(S, *)$ and let $T \subseteq S$ be a non-empty subset. The system $(T, *)$ is called a subsemigroup of $(S, *)$ if and only if the set is under the binary operation :

$t_1 * t_2 \in T \quad \forall t_1, t_2 \in T$

Since the operation $*$ is already associative over the entire parent set $S$ , it is guaranteed to be associative over any subset $T \subseteq S$ . Thus, closure is the only property that must be verified.

Concrete Examples

1. Positive Even Integers under Addition

Let $(\mathbb{N}, +)$ be the parent semigroup of natural numbers. Let $E = \{2, 4, 6, 8, \dots\}$ be the set of positive even integers.

Closure: The sum of any two even numbers is always even: $(2k_1) + (2k_2) = 2(k_1 + k_2) \in E \quad \forall 2k_1, 2k_2 \in E$

text

 Semigroup (N, +)
  +-----------------------------------------+
  |  1,  3,  5,  7,  9,  ...                |
  |                                         |
  |  Subsemigroup (E, +)                    |
  |   +---------------------------------+   |
  |   |  2,  4,  6,  8,  10,  ...       |   |
  |   |                                 |   |
  |   |  Closed: Even + Even = Even     |   |
  |   +---------------------------------+   |
  +-----------------------------------------+

2. Positive Odd Integers under Addition (Non-Example)

Let $(\mathbb{N}, +)$ be the parent semigroup. Let $O = \{1, 3, 5, 7, \dots\}$ be the set of positive odd integers.

Closure Failure: Adding two odd integers results in an even integer: $3 + 5 = 8 \notin O$
Conclusion: $(O, +)$ is not a subsemigroup of $(\mathbb{N}, +)$ .

4. Cartesian Products of Semigroups

We can combine existing semigroups to construct higher-dimensional algebraic structures.

Theorem

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

To prove that $(S_1 \times S_2, *)$ is a semigroup, we must prove both closure and associativity for the operation $*$ .

Part 1: Closure

Let $a, b \in S_1 \times S_2$ . By definition of the Cartesian product: $a = (a_1, a_2) \quad \text{where } a_1 \in S_1, a_2 \in S_2$

Applying the product operation: $a * b = (a_1, a_2) * (b_1, b_2) = (a_1 *_1 b_1, a_2 *_2 b_2)$

Since $S_1$ is a semigroup, it is closed under $*_1$ ; hence, $(a_1 *_1 b_1) \in S_1$ . Since is a semigroup, it is closed under ; hence, .

Because both components belong to their respective sets, we have: $(a_1 *_1 b_1, a_2 *_2 b_2) \in S_1 \times S_2$

Thus, the operation $*$ is closed on $S_1 \times S_2$ .

Part 2: Associativity

Let $a, b, c \in S_1 \times S_2$ , such that: $a = (a_{1}, a_{2}), b = (b_{1}, b_{2}),$

We must show that $a * (b * c) = (a * b) * c$ . Let us expand the left-hand side (LHS):

$a * (b * c) = (a_1, a_2) * \big((b_1, b_2) * (c_1, c_2)\big)$

Since $S_1$ and $S_2$ are semigroups, their individual operations $*_1$ and $*_2$ are associative. Therefore, we can rewrite the components:

$a_1 *_1 (b_1 *_1 c_1) = (a_1 *_1 b_1) *_1 c_1$

Substituting these back into the tuple yields:

$= \big((a_1 *_1 b_1) *_1 c_1, \; (a_2 *_2 b_2) *_2 c_2\big)$

The LHS equals the RHS, proving associativity.

Since both closure and associativity hold, $(S_1 \times S_2, *)$ is a semigroup. $\blacksquare$

To contextualize semigroups, we look at where they sit in the hierarchy of algebraic systems.

text

       +------------------------------------------------+
       |               Algebraic Systems                |
       |  +------------------------------------------+  |
       |  |                Semigroups                |  |
       |  |  +------------------------------------+  |  |
       |  |  |              Monoids               |  |  |
       |  |  |  +------------------------------+  |  |  |
       |  |  |  |            Groups            |  |  |  |
       |  |  |  |  +------------------------+  |  |  |  |
       |  |  |  |  |     Abelian Groups     |  |  |  |  |
       |  |  |  |  +------------------------+  |  |  |  |
       |  |  |  +------------------------------+  |  |  |
       |  |  +------------------------------------+  |  |
       |  +------------------------------------------+  |
       +------------------------------------------------+

Monoids

A semigroup $(M, *)$ that contains an identity element $e \in M$ is called a monoid.

Example 1: $(\mathbb{N}, +)$ where $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ is a monoid. The identity element is $0$ since $a + 0 = 0 + a = a$ .

Submonoids

Let $(M, \circ)$ be a monoid and let $S \subseteq M$ . Then $(S, \circ)$ is a submonoid of $(M, \circ)$ if and only if:

$S$ is closed under the operation $\circ$ .
The identity element $e$ of $(M, \circ)$ satisfies $e \in S$ .

Modulo Congruence Systems: $\langle \mathbb{Z}_4, +_4 \rangle$

Let $\mathbb{Z}_4 = \{[0], [1], [2], [3]\}$ with addition modulo $4$ ( $+_4$ ). This operation is defined as:

$[i] +_4 [j] = [(i + j) \pmod 4]$

This system is an algebraic structure represented by the following Cayley table:

| $+_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 |

This system is closed and associative, making it a semigroup. It also has identity $0$ (making it a monoid) and inverse elements for each entry (making it a group).

Clock Algebra

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

$T(j) = j + 1$ for $j \neq m$
$T(j) = 1$ for

The element $1 \in M$ acts as a generator of the algebra.

Summary

An algebraic system $(A, *)$ consists of a non-empty set and a closed binary operation.
A semigroup is an algebraic system with closure and associativity.
A subsemigroup is a non-empty subset of a semigroup that is closed under the same binary operation.
The Cartesian product of two semigroups $(S_1 \times S_2, *)$ is proven to be a semigroup under component-wise operations.

Assessed progress

Semigroups and Subsemigroups

Semigroups and Subsemigroups

1. Introduction to Algebraic Systems and Binary Operations

Binary Operations

Algebraic Systems

Structural Properties of Binary Operations

2. Foundations of Semigroups

Definition

Key Semigroup Examples and Non-Examples

1. $(\mathbb{N}, +)$ and $(\mathbb{N}, \cdot)$

2. $(\mathbb{N}, -)$ (Non-Example)

3. Positive Odd Integers under Multiplication

3. Subsemigroups

Definition

Concrete Examples

1. Positive Even Integers under Addition

2. Positive Odd Integers under Addition (Non-Example)

4. Cartesian Products of Semigroups

Theorem

Proof

Part 1: Closure

Part 2: Associativity

Monoids

Submonoids

Modulo Congruence Systems: $\langle \mathbb{Z}_4, +_4 \rangle$

Clock Algebra

Summary

Key Concepts

Algebraic System

Semigroup

Subsemigroup

Associativity

Cartesian Product Semigroup

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures