0
44kviews
Define group, monoid, semigroup.

Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: May 2016

1 Answer
0
4.3kviews
  • 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 –
  1. Closure,
  2. Associative,
  3. Identity element,
  4. 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.

Please log in to add an answer.