38 g Theory of computer Science
Postulate 2: Associativity. If a, b, c are in S, then (a * b) * c = a * (b * c).
Postulate 3: Identity element. There exists a unique element (called the
identity element) e in S such that for any element x in S,
x * e = e * x = x.
Postulate 4: Inverse. For every element x in S there exists a unique element x'
in S such that x ' " x' = x' * x = e. The element x' is called the
inverse of x W.r.t. ".
Postulate 5: Commutativity. If a, b E S. then a * b = b * a.
It may be noted that a binary operation may satisfy none of the above five
postulates. For example, let S ={1. 2, 3, 4, ... }, and let the binary operation
be subtraction (i.e. a * b =a - b). The closure postulate is not satisfied since
2 - 3 =-1 eo S. Also, (2 - 3) - 4 =F 2 - (3 - 4), and so associativity is not
satisfied. As we cannot find a positive integer such that x - e = e - x =x, th t1
postulates 3 and 4 are not satisfied. Obviously, a - b =F b - a. Therefore,
commutativity is not satisfied.
Our interest lies in sets with a binary operation satisfying the postulates.
Defmitions (i) A set S with a binary operation * is called a semigroup if the
postulates 1 and 2 are satisfied.
(ii) A set S with a binary operation * is called a monoid if the postulates
1-3 are satisfied.
(iii) A set S with * is called a group if the postulates 1-4 are satisfied.
(iv) A semigroup (monoid or group) is called a commutative or an abelian
semigroup (monoid or group) if the postulate 5 is satisfied.
Figure 2.1 gives the relationship between semigroups, monoids, groups,
etc. where the numbers refer to the postulate number.
~ No operation
~tulates 1,2
r - - - - - ' - - - - ,
Semigroup
5
5
Fig. 2.1 Sets with one binary operation.
We interpret Fig. 2.1 as follows: A monoid satisfying postulate 4 is a group.
A group satisfying postulate 5 is an abelian group, etc.