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 …