Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.

Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.

https://www.gyanodhan.com/video/7B4.%20GATE%20CSEIT/Discrete%20Mathematics%201/391.%20Day%2006-%20Discrete%20Mathematics%20for%20gate%20Computer%20Science%20-%20Examples%20based%20on%20semi%20group.mp4

Discrete Mathematics – Day 06: Semigroup in Discrete Mathematics (For GATE CSE)

 Introduction to Semigroup

A semigroup is an algebraic structure consisting of a set and an associative binary operation. It is one of the fundamental concepts in discrete mathematics, especially in abstract algebra and theoretical computer science.

Definition of Semigroup

A set $S$ with a binary operation $\ast$ is called a semigroup if it satisfies the following property:

Closure Property: If $a,b\in S$, then $a\ast b\in S$.
Associativity: For all $a,b,c\in S$, $(a\ast b)\ast c=a\ast (b\ast c)$.

Note: A semigroup does not necessarily have an identity element or inverses.

 Examples of Semigroup

Example 1: (Natural Numbers with Addition)

 Set: $S=\mathbb{N}=\{1,2,3,4,\dots \}$
 Operation: $+$ (Addition)

Closure: $a+b$ is always a natural number.
Associativity: $(a+b)+c=a+(b+c)$ always holds.

Conclusion: $(\mathbb{N},+)$ is a semigroup.

Example 2: (Non-zero Integers with Multiplication)

Set: S=Z∗={…,−3,−2,−1,1,2,3,… }S = \mathbb{Z}^* = \{ \dots, -3, -2, -1, 1, 2, 3, \dots\}S=Z∗={…,−3,−2,−1,1,2,3,…}
 Operation: $\times$ (Multiplication)

Closure: Multiplication of two integers is an integer.
Associativity: $(a\times b)\times c=a\times (b\times c)$.

Conclusion: (Z∗,×)(\mathbb{Z}^*, \times)(Z∗,×) is a semigroup.

Example 3: (Set of Matrices with Matrix Multiplication)

 Set: Mn(R)M_n(\mathbb{R})Mn​(R), the set of all $n\times n$ real matrices.
 Operation: Matrix Multiplication.

Closure: The product of two $n\times n$ matrices is an $n\times n$ matrix.
Associativity: Matrix multiplication follows the associative property.

Conclusion: (Mn(R),×)(M_n(\mathbb{R}), \times)(Mn​(R),×) forms a semigroup.

 Difference Between Semigroup and Monoid

Pro Tip: If a semigroup has an identity element, it becomes a monoid.

 GATE Questions Based on Semigroup

Q1: Which of the following is a semigroup but not a monoid?
A) $(\mathbb{Z},+)$
B) $(\mathbb{N},\times )$
C) (Mn(R),×)(M_n(\mathbb{R}), \times)(Mn​(R),×)
D) $(\mathbb{N},+)$

Answer: C (Matrix multiplication is associative but does not have an identity for all elements).

 Conclusion

 A semigroup is a set with an associative binary operation.
 It does not require an identity element.
 Common examples include natural numbers under addition and matrices under multiplication.
 Understanding semigroups helps in algebra, automata theory, and computer science applications.

 Want more GATE-level examples on semigroups? Let me know!

Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.

Discrete Mathematics for Computer Science

DISCRETE MATHEMATICS AND GRAPH THEORY

Title Discrete Mathematics Author Prof. Abhay Saxena ..

Here’s a quick and clear explanation of Semigroups in Discrete Mathematics (Day 06) with examples—especially useful for GATE Computer Science preparation:

---

Semigroup – Definition

A semigroup is a set equipped with a binary operation (like +, ×, etc.) that is:

1. Closed

2. Associative

A semigroup does not require an identity element or inverses (unlike a monoid or group).

---

Formal Definition

A *semigroup (S, ) satisfies:

• ∀ a, b ∈ S: a * b ∈ S (Closure)

• ∀ a, b, c ∈ S: (a * b) * c = a * (b * c) (Associativity)

---

Examples of Semigroups

Example 1:

Set: ℕ (Natural Numbers)
Operation: Addition (+)

• Closure: a + b ∈ ℕ

• Associativity: (a + b) + c = a + (b + c)
  So, (ℕ, +) is a semigroup

---

Example 2:

Set: {1, 2, 3}
Operation: Multiplication modulo 4

• Create a table for all a × b mod 4

• Check closure and associativity
  If both hold, it’s a semigroup.

---

Example 3:

String concatenation over set of characters

• Set: All strings over alphabet Σ = {a, b}

• Operation: Concatenation (e.g., “a” + “b” = “ab”)

• Closure: Concatenation of any two strings is a string

• Associativity: (“a” + “b”) + “c” = “a” + (“b” + “c”)
  So, this is a semigroup

---

Non-example:

Set of integers under subtraction (ℤ, -)

• (a – b) – c ≠ a – (b – c)
  Not associative → Not a semigroup

---

Would you like practice problems, GATE-style MCQs, or visual examples of semigroup tables?

Discrete Mathematics Day 06- Discrete Mathematics for gate Computer Science – Examples based on semi group.

ADVANCED DISCRETE MATHEMATICS MM-504 & 505 ( …

Discrete Mathematical Structures

Discrete Mathematics