Algebraic Structures

If there exists a system such that it consists of a non-empty set and one or more opera.
tions on that, set, then that system is called an algebraic system. It is generally denoted by
(A, op,, op, ...,op,), where A is a non-empty set and op,, op, .., op,, are operations on A.
An algebraic system is alsocalled an algebraic structure because the operations on the
set A define a structure on the elements of A..

N-ARY OPERATION
A function f: A xAx... A ’A is called an n-ary operation.

BINARY OPERATION
Consider a non-empty set A and a function f such that f: AxA ’A is called a binary
operation on A. If * is a binary operation on A, then it may be writteh as a * b.
A binary operation can be denoted by any of the symbols +, -, *, , A, O, V, A etc.
The value of the binary operation is denoted by placing the operator between the two
operands.
e.g., (i) The operation of addition is a binary operation on the set of natural numbers.
(iü) The operation of subtraction is a binary operation on set of
tion of subtraction is not a binary operation on the set of natural
integers. But, the opera
numbers because the subtrac
tion of two natural numbers may or may not be a natural number.
(iii) The operation of multiplication is a binary operation on the set of
set of integers and set of complex numbers. natural numbers,
(iv)The operation of set union is a binary operation on the set of
set. Similarly, the operation of set intersection is a binary subsets of a universal
universal set.
operation on the set of subsets of a

TABLES OF OPERATION

Consider a non empty finit¢ set A = la, ag, agy ., a,). A binary
described by means of table as shown in Fig. 1. operation on A can be

290
 ALGEBRA

a*a,

3
Fig. 1.
The empty in the jth row and kth column represent the element a *a,.
Example 1. Consider the set A=(1, 2, 3) and a binary operation *on the set Adefined by
a*b= 2a + 26.
Represent operation *as a table on A.
Sol. The table of the operation is shown in Fig. 2.
1 2 3

1 4 6
2. 6 8 10
3 10 12

Fig. 2.

PROPERTIES OF BINARY OPERATIONS

There are many properties of the binary operations which are as follows :
1. Closure Property. Consider a non-empty set Aand a binary operation * on A. Then
Ais closed under the operation *, if a * be A, where a and b are elements of A.
e.g., The operation of addition on the set of integers is a closed operation.
Example 2. Consider the set A= -1, 0, 1). Determine whether A is closed under (E)
addition (ü) multiplication.
Sol.(i) The sum of the elements is(- 1) +(-1) =-2 and 1 +1=2does not belongto A.
Hence A is not closed under addition.
(üi)The multiplication of every two elements of the set are
-1*0 =0; -1 *1 =-1; -1*-1l = 1
0*-1=0; 0*1 = 0; 0*0=0
1*-1=-1; 1%0 = 0; 1*1=1
Since, each multiplication belongs toAhence Aisclosed under multiplication.
Example 3. Consider the set A = (1, 3, 5, 7, 9, ...}, the set of odd +ve integers. Determine
whether Ais closed under (i) addition (iü) multiplication.
Sol. (i) The set Ais not closed under addition because the addition of two odd numbers
produces an even number which does not belong to A.
292 DISCRETE MATHEMATICS AND STRUCTUREO
(ii)The set Ais closed under the operation multiplication because the multiplication of
two odd numbers produces an odd number. So, for everya, be A, we have a*beA.
2. Associative [Link] non-empty set Aand a binary operation *on A
Then the operatioD *on Ais associative, if for every ab, c,e A, we have (a *b) *c =a* (6*
Example [Link] thebinary operation *on Q, the set of rational numbers,defined
by
a *b=a+b-ab a, be Q.
Determine whether * is associative.
Sol. Let us assume some elements a, b, c e Q, then by definition
(a * b) *c= (a +b- ab) *c= (a +b- ab) +c-(a +b- ab)c
=a+ b- ab + c- ca - bc + abc = a +b +c- ab - ac-bc +abc
Similarly, we have
a * (6 * c) = a + b+c- ab - ac - bc + abc
Therefore, (a * b) *c=a* (6 *c).
Hence * is associative.
3. Commutative Property. Consider a non-empty set A and a
binary operation * on A.
Then the operation * on Ais commutative, if for every a, b eA, we have a * b=b *a.
Example 5. Consider the binaryoperation * on Q, the set of rational numbers, defined
by
a *b=a + b a, be Q.
Determine whether * is commutative.
Sol. Let us assume some elements a, be Q, then by definition
a *b= a²+ b² =b*a
Hence is commutative.
*

Example 6. Consider the binary operation *and Q, the set of rational numbers defined
by
ab
a *b= a, be Q.
2
Determine whether * is (i)associative (iü) commutative.
Sol. (i)Let a, b e Q, then we have
ab
a *b= =b * a
Hence * is commutative.
(ii) Let a, b, c e Q, then by definition we
have
ab
C
'ab
abc
(a*b) *e= 2 4
abc
bc 2 abc
Similarly, a * (b * c) = a *
2 2 4
Therefore, a * (b * c) = a * (6 *c)
Hence, * is associative.
 [Link]

cation
A.
Q 6.' tion
4. Identity.
has an
Consider non-empty set Aand a binary
identity
a *e (right
a
property if there exists an element, e, inoperation
identity)=e * a(left identity) =a such
A
ae A.
293

* on A. Then the opera-

that

defune Theorem I. Proue that ef =e, wheree,' is a right identity and

binaryoperation.
Proof. We know that e, is a right identity.
e," is a left identity ofa

Hence, e" *ee"

...i)
Also, we know that e" is a left identity.
Hence, e ef =e
+ abe. From (i)and (ü), we have e =e,".
...(iz)

Thus, we can say that if e is a right identity of a binary

identity or there is no left identity. operation then e is also a left
[Link] the binary operation *on I,, the set of positive integers defined by
ab
on A a *b=
2
Determine the identity for the binary operation %, ifexists.
fined Sol. Let us assume that e be a +ve integer number, then
e*a, aE I,
ea
= 1, e =2 ...E)
2

Similarly, a *e=a, a e I,
ae
Or e =2 ..(i|)
2
zed
Form (i) and (ii) for e=2, we have e*a=a*e=a
Therefore, 2 is the identity element for *,
5. Inverse. Consider a non-empty set A and a binary operation* on A. Then operation
uas tne inverse property if for each a e A, there exists an element b in A auch that
a *b (right inverse) =b*a (left inverse) =e, where bis called an inverse of a.
6. [Link] a non-empty set Aand a binary operation *on A. Then the
Operation *has the idempotent property, if for each ae A, we have
a *a =a a e A.

7. Distributivity. Consider a non-empty set Aand two binary operations *and +on A.
Then the operation *distributes over +, if for every a, b, ce A, we have
a *(b + c) =(a* b) + (a * c) [Left distributivity]
and
(6 + c) * a= (b * a) + (c * a) (Right distributivityl
[Link]. Consider a non-empty set A and a binary operation * on A. Then the
operation * has the cancellation property, if for every a, b, ce A, we have
[Left cancellationj
a * b a *c b=c
and
b*a = c*a b=c (Right cancellation
 294
DISCRETE MATHEMATICS AND STRUCTURES

SEMIGROUP
Let us consider, an algebraic system (A, *), where * is a binary operation on A. Then, the
system (A, *) is said to be a semi-group if it satisfies the following properties :
1. The operation * is aclosed operation on set A.
2. The operation *is an associative operation.
Example 8. Consider an algebraicsystem (A, *), where A = (1, 3, 5, 7, 9, ..], the set of all
positive
(A, *) isa
odd integers and *is abinary operation means multiplication. Determine whether
semi-group.
Sol. Closure property. The operation * is a closed operation because multiplication of
two +ve odd integers is a +ve odd number.
Associative property. The operation * is an associative operation on set A. Since for
every a, b, ce A, we have
(a * b) *c = a * (6 *c)
Hence, the algebraic system (A, *)is a semigroup.
Example 9, Consider the algebraicsystemn ((0, 1), *), where * is a multiplication opera
tion. Determine whether ({0, 1), *) isa semigroup.
Sol. Closure property. The operation * is a closed one on the given set
since
0 *0= 0;0 * =0;1*0 =0; 1 *1= 1.
Associative property. The operation * is associative since we have
(a * b) *c= a* (6 * c) a, b, c
Since, the algebraic system is closed and associative. Hence, it is a
semi-group.
Example 10. Let (A, *) be semi-group. Show that for a, b, c in A, ifa *c=c*a and
b*c=c *b, then (a * b) * c =c* (a * b).
Sol. Take L.H.S., we have
(a * b) *c a* (6 * c) [: * is associative]
a *(c * b)
[::6*c=c * b]
(a * c) * b
(: * is associativel
(c * a) * b
a *c =c * a
c* (a * b)
Which is equal to R.H.S. [: * is associative]
Hence, (a * b) *c=c* (a * b).

SUBSEMIGROUP
Consider a semigrOup (A, *) and let BçA. Then the
if the set B is closed under the operation *. system (B, *) is called a subsemigroup,
e.g., Consider a semigroup (N, +), where N is the
tion operation. The algebraie system (E, +)is a set of all natural numbers and + is an addi
+ve even integers. subsemigroup of (N, +), where E is a set of all
ALGEB
295
EREE SEMIGROUP
Consider a nonempty set A= \a,, any ...., a,).
Now A is the set of all finite sequences of
that can be formed from the alphabet of A. elements of A, iLe.. A* consists of all words
Tf . Band y are any elements of A*, then a .
(B.) = (a.B).Y.
Heree is a concatenation operation, which is an associative operation as
shown above.
Thus (A*, ") is a semigroup. This semigroup (A*, ) is called the free
ated by set A.
semigroup gener

PRODUCT OF SEMIGROUP

Theorem. If(S, ") and (S, are semigroups, then (S,xS, ") is asemigroup, where*
is defined by (s,, s,) *(8,", s,9 =(s, *s,, S' *s,).
[Link] semigroup S, x S, is closed under the operation*.
ASsociativity of *, Let a, b, ce Sx S,
So, a *(b *c) = (a, a) *(6, b,) (c c,)
= (a, a,) * (6,*,c b, * Co)
=(a, *,(6, *1 e), a, *, (b*, C)
= (a, *, b, ag *, b,) * (C, Cz)
= (a, a,) *(b,, b)) *(C, c,)
= (a * b) * C.
Since * is closed and associative. Hence S, x S, is a semigroup.

CONGRUENCE RELATION
a congruence relation if
An equivalence relation R on the semigroup (S, *) is called
aRa' and bRb'
’ (a * b) R (a' * b')
equivalence relation on I defined by
Example 11. Let (I, +) be a semigroup andR is an
aRb iff a=b(MOD 3). we have 3 divides
and b yield the same remainder when divided by 3, then
Sol. If a
3
a-bi.e., (a-b) -d.
(MOD 3) and c = d(MOD 3) then 3 divides a-b and 3 dividesc
Now, ifa=b ...(E)
Thus, we can write a-b= 3m ...(ü)
and c-d= 3n
Here m and n are same integer of 1.
Adding eqns. (i)and (ii), we have + n)
(a +)- (b + d) = 3(m
(a-b) + (e - d) = 3m + 3n or
Or a+c=b+d(MOD 3)

Thus, the relation is a congruence relation.