BCA 21 / IMCA 21 / Mathematics SVT 21
ALGEBRAIC STRUCTURES
Abreviations used
N : represent set of natural numbers.
Z or I : represent set of +ve and –ve integers including zero.
Z+ : represent non-negative integers ie. +ve integers including zero.
Q : represent set of rational numbers.
R : represent set of real numbers.
C : represent set of complex numbers.
Zn = {0, 1, 2, 3, .............. n – 1} ie. Zn represent set of integers modulo n.
Q+ : represent set of +ve rational numbers.
z - {o} : represent set of integers except 0.
Q - {o} : represent set of rational numbers except zero.
R - {o} : set of real numbers except zero.
A set in general is denoted by S.
∀ : for all
∈ : belongs to
Binary Operation
If S is a non-empty set then a mapping (function) from S × S to S is defined as Binary Operation (in short B.O.) and denoted
by ∗ (read as star). ie. : S × S → S (Star maps S cross S to S)
Another Definition
If S is non-empty set then ∗ (star) is said to be a Binary operation if ∀ a, b ∈ S, a ∗ b ∈ S.
Examples
(1) on N + and × (ie addition & multiplication) are B.O.
2 + 3 = 5∈ N 2×3 = 6∈ N
(2) on Z, +, – & × are B.O.
4 + 5 ∈ Z , 3 − 4 = 1∈ Z , 4 − 3 = 1 ∈ Z , 5 × 6 = 30 ∈ Z
a
(3) On Q & R +, – & × are B.O. but ÷ is not a B.O. on Q & R Q for 0, ∉ Q & R but on Q - {o} & R - {o} ÷ is a B.O.
0
(4) on C, + and × are B.O.
( x1 + iy1 ) + ( x2 + iy 2 ) = ( x1 + x2 ) + i ( y1 + y 2 ) ∈ C
( x1 + iy1 ) + ( x2 + iy 2 ) = ( x1 x2 − y1 y 2 ) + i ( x1 y 2 + x2 y1 ) ∈ C
,22 KSOU Algebraic Structures
Definitions
(1) A non-empty set S with one or more binary operations is called an 'Algebraic Structure'.
(N, +), (Z, +, ×), (Q, +, ×) are all algebraic structures.
(2) Closure Law : A set S is said to be closed under a B.O. ∗ if ∀ a, b ∈ S, a ∗ b ∈ S.
(3) Associative Law : A B.O. ∗ is said to be associative on S if ∀ a, b, c ∈ S
(a ∗ b) ∗ c = a ∗ (b ∗ c)
(4) Commutative Law : A B.O. ∗ is said to be commutative on S if ∀ a, b ∈ S, a ∗ b = b ∗ a.
(5) Identity Law : An element e ∈ S satisfying
a ∗ e = a = e ∗ a. ∀ a ∈ S is called an identity element for the B.O. ∗ on S.
Examples
(i) + and × (addition and multiplication) are associative and commutative on N, Z, Q & R.
(ii) B.O. – (subtraction) is not associative & commutative.
(iii) 1 is an identity for B.O. × on N but + has no identity on N. Where as O is an identity on Z, Q and R for the B.O. +.
1 0
(iv) If S is a set of 2 × 2 matrices and B.O. is matrix multiplication then I = is an identity element.
0 1
Group
A non-empty set G together with a B.O. ∗ ie (G, ∗) is said to form a group if the following axioms are satisfied.
G1. Closure Law : ∀ a, b ∈ G, a ∗ b ∈ G
G2. Associative Law : ∀ a, b, c ∈ G, (a ∗ b) ∗ c = a ∗ (b ∗ c)
G3. Identity Law : There exists an element e ∈ G such that ∀ a ∈ G, a ∗ e = a = e ∗ a.
G4. Inverse : ∀ a ∈ G, there exists an element b such that a ∗ b = e = b ∗ a. This b is called inverse of a and usually denoted
as a–1
ie. a ∗ a–1 = e = a–1 ∗ a.
In addition to the above four axions if ∀ a, b ∈ G, a ∗ b = b ∗ a. Then (G, ∗) is called an 'abelian group' or 'commutative
group'.
Note (1) If for (G, ∗) only G1 is satisfied it is called a 'groupoid'.
(2) If for (G, ∗) G1 & G2 are satisfied it is called a 'semi-group'.
(3) If for (G, ∗) G1, G2 & G3 are satisfied it is called 'Monoid'.
Examples
(i) (N, +) is a groupoid and semigroup.
(ii) (N, ×) is a groupoid, semigroup and Monoid (identity for × is 1)
(iii) (Z, +) is a group (identity is O and a–1 = –a) ie. a + (–a) = 0 = –a + a.
Note :- Every group is a monoid but the converse is not true, (Z, +) is a group and also a monoid but (N, ×) is a monoid but
not a group.
, BCA 21 / IMCA 21 / Mathematics SVT 23
Properties of Groups
1. Cancellation laws are valid in a group
ie if (G , ∗) is a group then ∀ a, b, c ∈ G ,
(i) a ∗ b = a ∗ c ⇒ b = c (left cancellation law)
(ii ) b ∗ a = c ∗ a ⇒ b = c ( right cancellation law)
Proof :- a ∗ b = a ∗ c, as a ∈ G, a −1 ∈ G
∴ a −1 ∗ (a ∗ b) = a −1 ∗ (a ∗ c)
ie (a −1 ∗ a) ∗ b = (a −1 ∗ a) ∗ c
ie e ∗ b = e ∗ c where e is the identity.
⇒b=c
Similarly by considering
(b ∗ a) ∗ a −1 = (c ∗ a) ∗ a −1
we get b = c
2. In a group G, the equations a ∗ x = b and y ∗ a = b have unique solutions, ∀a, b ∈ G.
Proof :- a ∗ x = b
Operating on both sides by a–1
a −1 ∗ (a ∗ x) = a −1 ∗ b
ie (a −1 ∗ a) ∗ x = a −1 ∗ b
ie e ∗ x = a −1 ∗ b
∴ x = a −1 ∗ b
To prove that the solution is unique, let x1 & x2 be two solutions of a ∗ x = b.
ie a ∗ x1 = b & a ∗ x2 = b
⇒ a ∗ x1 = a ∗ x2
Operating on both sides by a–1
We get a −1 ∗ (a ∗ x1 ) = a −1 ∗ (a ∗ x2 )
ie (a −1 ∗ a ) ∗ x1 = (a −1 ∗ a) ∗ x2
ie e ∗ x1 = e ∗ x2
⇒ x1 = x2
∴ solution is unique.
3. In a group the identity element and inverse of an element are unique.
Proof :- To prove identity is unique. If possible let e1 & e2 are two identities then
∀a ∈ G, a ∗ e1 = a = e1 ∗ a (1)
& a ∗ e2 = a = e2 ∗ a (2)
From LHS of (1), a ∗ e1 = a = e2 ∗ a (using (2))
ie a ∗ e1 = e2 ∗ a = a ∗ e2 (using LHS of (2))
ALGEBRAIC STRUCTURES
Abreviations used
N : represent set of natural numbers.
Z or I : represent set of +ve and –ve integers including zero.
Z+ : represent non-negative integers ie. +ve integers including zero.
Q : represent set of rational numbers.
R : represent set of real numbers.
C : represent set of complex numbers.
Zn = {0, 1, 2, 3, .............. n – 1} ie. Zn represent set of integers modulo n.
Q+ : represent set of +ve rational numbers.
z - {o} : represent set of integers except 0.
Q - {o} : represent set of rational numbers except zero.
R - {o} : set of real numbers except zero.
A set in general is denoted by S.
∀ : for all
∈ : belongs to
Binary Operation
If S is a non-empty set then a mapping (function) from S × S to S is defined as Binary Operation (in short B.O.) and denoted
by ∗ (read as star). ie. : S × S → S (Star maps S cross S to S)
Another Definition
If S is non-empty set then ∗ (star) is said to be a Binary operation if ∀ a, b ∈ S, a ∗ b ∈ S.
Examples
(1) on N + and × (ie addition & multiplication) are B.O.
2 + 3 = 5∈ N 2×3 = 6∈ N
(2) on Z, +, – & × are B.O.
4 + 5 ∈ Z , 3 − 4 = 1∈ Z , 4 − 3 = 1 ∈ Z , 5 × 6 = 30 ∈ Z
a
(3) On Q & R +, – & × are B.O. but ÷ is not a B.O. on Q & R Q for 0, ∉ Q & R but on Q - {o} & R - {o} ÷ is a B.O.
0
(4) on C, + and × are B.O.
( x1 + iy1 ) + ( x2 + iy 2 ) = ( x1 + x2 ) + i ( y1 + y 2 ) ∈ C
( x1 + iy1 ) + ( x2 + iy 2 ) = ( x1 x2 − y1 y 2 ) + i ( x1 y 2 + x2 y1 ) ∈ C
,22 KSOU Algebraic Structures
Definitions
(1) A non-empty set S with one or more binary operations is called an 'Algebraic Structure'.
(N, +), (Z, +, ×), (Q, +, ×) are all algebraic structures.
(2) Closure Law : A set S is said to be closed under a B.O. ∗ if ∀ a, b ∈ S, a ∗ b ∈ S.
(3) Associative Law : A B.O. ∗ is said to be associative on S if ∀ a, b, c ∈ S
(a ∗ b) ∗ c = a ∗ (b ∗ c)
(4) Commutative Law : A B.O. ∗ is said to be commutative on S if ∀ a, b ∈ S, a ∗ b = b ∗ a.
(5) Identity Law : An element e ∈ S satisfying
a ∗ e = a = e ∗ a. ∀ a ∈ S is called an identity element for the B.O. ∗ on S.
Examples
(i) + and × (addition and multiplication) are associative and commutative on N, Z, Q & R.
(ii) B.O. – (subtraction) is not associative & commutative.
(iii) 1 is an identity for B.O. × on N but + has no identity on N. Where as O is an identity on Z, Q and R for the B.O. +.
1 0
(iv) If S is a set of 2 × 2 matrices and B.O. is matrix multiplication then I = is an identity element.
0 1
Group
A non-empty set G together with a B.O. ∗ ie (G, ∗) is said to form a group if the following axioms are satisfied.
G1. Closure Law : ∀ a, b ∈ G, a ∗ b ∈ G
G2. Associative Law : ∀ a, b, c ∈ G, (a ∗ b) ∗ c = a ∗ (b ∗ c)
G3. Identity Law : There exists an element e ∈ G such that ∀ a ∈ G, a ∗ e = a = e ∗ a.
G4. Inverse : ∀ a ∈ G, there exists an element b such that a ∗ b = e = b ∗ a. This b is called inverse of a and usually denoted
as a–1
ie. a ∗ a–1 = e = a–1 ∗ a.
In addition to the above four axions if ∀ a, b ∈ G, a ∗ b = b ∗ a. Then (G, ∗) is called an 'abelian group' or 'commutative
group'.
Note (1) If for (G, ∗) only G1 is satisfied it is called a 'groupoid'.
(2) If for (G, ∗) G1 & G2 are satisfied it is called a 'semi-group'.
(3) If for (G, ∗) G1, G2 & G3 are satisfied it is called 'Monoid'.
Examples
(i) (N, +) is a groupoid and semigroup.
(ii) (N, ×) is a groupoid, semigroup and Monoid (identity for × is 1)
(iii) (Z, +) is a group (identity is O and a–1 = –a) ie. a + (–a) = 0 = –a + a.
Note :- Every group is a monoid but the converse is not true, (Z, +) is a group and also a monoid but (N, ×) is a monoid but
not a group.
, BCA 21 / IMCA 21 / Mathematics SVT 23
Properties of Groups
1. Cancellation laws are valid in a group
ie if (G , ∗) is a group then ∀ a, b, c ∈ G ,
(i) a ∗ b = a ∗ c ⇒ b = c (left cancellation law)
(ii ) b ∗ a = c ∗ a ⇒ b = c ( right cancellation law)
Proof :- a ∗ b = a ∗ c, as a ∈ G, a −1 ∈ G
∴ a −1 ∗ (a ∗ b) = a −1 ∗ (a ∗ c)
ie (a −1 ∗ a) ∗ b = (a −1 ∗ a) ∗ c
ie e ∗ b = e ∗ c where e is the identity.
⇒b=c
Similarly by considering
(b ∗ a) ∗ a −1 = (c ∗ a) ∗ a −1
we get b = c
2. In a group G, the equations a ∗ x = b and y ∗ a = b have unique solutions, ∀a, b ∈ G.
Proof :- a ∗ x = b
Operating on both sides by a–1
a −1 ∗ (a ∗ x) = a −1 ∗ b
ie (a −1 ∗ a) ∗ x = a −1 ∗ b
ie e ∗ x = a −1 ∗ b
∴ x = a −1 ∗ b
To prove that the solution is unique, let x1 & x2 be two solutions of a ∗ x = b.
ie a ∗ x1 = b & a ∗ x2 = b
⇒ a ∗ x1 = a ∗ x2
Operating on both sides by a–1
We get a −1 ∗ (a ∗ x1 ) = a −1 ∗ (a ∗ x2 )
ie (a −1 ∗ a ) ∗ x1 = (a −1 ∗ a) ∗ x2
ie e ∗ x1 = e ∗ x2
⇒ x1 = x2
∴ solution is unique.
3. In a group the identity element and inverse of an element are unique.
Proof :- To prove identity is unique. If possible let e1 & e2 are two identities then
∀a ∈ G, a ∗ e1 = a = e1 ∗ a (1)
& a ∗ e2 = a = e2 ∗ a (2)
From LHS of (1), a ∗ e1 = a = e2 ∗ a (using (2))
ie a ∗ e1 = e2 ∗ a = a ∗ e2 (using LHS of (2))
