Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: May 2016

• 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.