Skip to content
Home » Semigroups and monoids

Semigroups and monoids

Below is a clear, simple, and exam-oriented explanation of Semigroups and Monoids — perfect for BCA/MCA/Engineering/Discrete Mathematics or Abstract Algebra exams.

⭐ SEMIGROUPS AND MONOIDS

Semigroups and Monoids are algebraic structures based on a set and a binary operation defined on that set.
They are foundational in:

✔ Theoretical Computer Science
✔ Automata Theory
✔ Algebra
✔ Programming languages
✔ Cryptography
✔ Logic

⭐ 1. SEMIGROUPS

A semigroup is the simplest algebraic structure with an internal operation.

⭐ Definition of a Semigroup

A set ( S ) with a binary operation (*) is called a semigroup if:

1️⃣ Closure

For all ( a, b \in S ):

[
a * b \in S
]

2️⃣ Associativity

For all ( a, b, c \in S ):

[
(a * b) * c = a * (b * c)
]

⭐ No identity required, no inverses required.

So a semigroup is simply:

✔ Set + associative operation

⭐ Examples of Semigroups

✔ Example 1: Positive integers under addition

Set: ( \mathbb{Z}^{+} = {1,2,3,\ldots} )
Operation: +
Associative: yes
Identity: none (0 not included)

→ Semigroup

✔ Example 2: Strings under concatenation

Set: all strings over alphabet Σ
Operation: concatenation
Associative: yes

→ Semigroup
(Used in automata theory, language theory)

✔ Example 3: 2×2 matrices under multiplication

Associative: yes
Identity: exists but not necessary here
→ Semigroup

⭐ Not a Semigroup Example

Real numbers under subtraction:

[
(a – b) – c \neq a – (b – c)
]
Not associative → NOT a semigroup.

⭐ 2. MONOIDS

A monoid is a semigroup with an identity element.

⭐ Definition of a Monoid

A set ( M ) with operation (*) is a monoid if:

1️⃣ Closure

[
a * b \in M
]

2️⃣ Associativity

[
(a * b) * c = a * (b * c)
]

3️⃣ Identity Element

There exists ( e \in M ) such that for all ( a \in M ):

[
e * a = a * e = a
]

⭐ Examples of Monoids

✔ Example 1: Natural numbers under addition

Set: ( \mathbb{N} = {0,1,2,3,\ldots} )
Operation: +
Identity: 0

→ (ℕ, +) is a monoid

✔ Example 2: Strings under concatenation

Set: Σ*
Operation: concat
Identity: empty string ε
Because:

[
\varepsilon s = s\varepsilon = s
]

→ (Σ*, concatenation) is a monoid

(VERY important in automata theory)

✔ Example 3: Integers under multiplication

Set: ℤ
Operation: ×
Identity: 1

→ (ℤ, ×) is a monoid

⭐ Semigroup vs Monoid vs Group (Comparison)

StructureClosureAssociativeIdentityInverses
Semigroup✔✔✘✘
Monoid✔✔✔✘
Group✔✔✔✔

⭐ 3. Subsemigroups and Submonoids

✔ Subsemigroup

A non-empty subset ( H \subseteq S ) is a subsemigroup if:

  • closed under the operation

✔ Submonoid

A subset ( H \subseteq M ) is a submonoid if:

  • closed under the operation
  • contains the identity of M

⭐ 4. Applications of Semigroups and Monoids

✔ Automata Theory

  • Σ* under concatenation = monoid
  • Transition functions form a semigroup

✔ Computer Science

  • State machines
  • Functional programming
  • Formal languages

✔ Cryptography

Some cryptosystems use monoid actions.

✔ Programming Languages

  • Strings
  • Syntax trees
  • Regular expressions

✔ Mathematics / Algebra

  • Matrix multiplication = semigroup
  • Transformations = semigroup

⭐ Exam-Oriented Summary

Semigroup:

A set with closure + associativity.

Monoid:

Semigroup + identity element.

Examples:

  • (ℕ, +) monoid
  • (Σ*, concat) monoid
  • (ℤ+, +) semigroup
  • (Matrices, ×) semigroup

Comparison:

Monoid = semigroup with identity.
Group = monoid with inverses.