written 7.4 years ago by | modified 2.4 years ago by |

**Mumbai University > Computer Engineering > Sem 3 > Discrete Structures**

**Marks:** 8 Marks

**Year:** May 2016

**1 Answer**

0

42kviews

Define group, monoid, semigroup.

written 7.4 years ago by | modified 2.4 years ago by |

**Mumbai University > Computer Engineering > Sem 3 > Discrete Structures**

**Marks:** 8 Marks

**Year:** May 2016

ADD COMMENT
EDIT

0

4.2kviews

written 7.4 years ago by | • modified 7.4 years ago |

- A group is a monoid with an inverse element. The inverse element (denoted by I) of a set S is an element such that (a 0 I) = (I 0 a) = a, for each element a ∈ S.
- So, a group holds four properties simultaneously –

- Closure,
- Associative,
- Identity element,
- inverse element.

- The order of a group G is the number of elements in G and the order of an element in a group is the least positive integer n such that an is the identity element of that group G.

**Examples**

- The set of N × N non-singular matrices form a group under matrix multiplication operation.
- The product of two N × N non-singular matrices is also an N × N non-singular matrix which holds closure property.
- Matrix multiplication itself is associative. Hence, associative property holds.
- The set of N × N non-singular matrices contains the identity matrix holding the identity element property.
- As all the matrices are non-singular they all have inverse elements which are also non-singular matrices. Hence, inverse property also holds.

**Monoid:**

If a semigroup {M, * } has an identity element with respect to the operation * , then {M, * } is called a *monoid*.

viz., if for any $a,b,c \in M$

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

and if there exists an element $e \in M$ such that for any $a \in M, e*a=a*e=a$, then the algebraic system {M, * } is called a monoid.

For example, if N is the set of natural numbers, then {N,+} and {N,X} are monoids with the identity elements 0 and 1 respectively.

The semigroups {E,+} and {E,X} are not monoids.

**Semigroup:**

If S is a nonempty set and * be a binary operation on S, then the algebraic system {S, * } is called a *semigroup* , if the operation * is associative.

viz., if for any $a,b,c \in S$,

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

Since the characteristic property of a binary operation on S is the closure property, it is not necessary to mention it explicity when algebraic systems are defined.

For example, if E is the set of positive even numbers, then {E, + } and {E, X} are semigroups.

ADD COMMENT
EDIT

Please log in to add an answer.