GROUP THEORY - DISCRETE STRUCTURES
GROUP THEORY
INTRODUCTION
- To define general algebraic systems such as semigroups, monoids, and groups.
- And discuss some of their basic properties and concepts.
- Semigroups find their applications in computer arithmetic such as multiplication, theory of sequential machines and formal languages.
- Monoids are used in the study of syntactic analysis and formal languages.
- Group theory is useful in the design of fast adders and error-correcting codes.
ALGEBRAIC
SYSTEMS
Definition
- A system consisting of a non-empty set and one or more n-ary operations on the set is called an algebraic system.
- An algebraic system will be denoted by {S,f1,f2,….}, where S is the non-empty set and f1,f2,… are n-ary operations on S.
- We will mostly deal with algebraic systems, with n=1 and 2, containing one or two operations only. Though we will mostly deal with one algebraic system only, we may occasionally consider two or more systems which are of the same ‘type’ in some sense.
General
Properties of Algebraic Systems
Let
{S,*,⨁} be an
algebraic system, where * and ⨁
are binary operations on S.
1.Closure
Property
For
any a,b∈S,
a*b∈ S
Example
If
a,b∈Z,
a+b∈Z
and
a×b∈Z
where
+ and × are the operations of addition
and multiplication.
2.Associativity
For
any a,b,c∈S,
(a*b)*c = a*(b*c)
Example
If
a,b,c∈Z,
(a+b)+c
= a+(b+c) and
(a×b)×c
= a×(b×c)
3.Commutativity
For
any a,b ∈S,
a*b = b*a
Example
If
a,b∈Z,
a+b
= b+a and
a×b
= b×a
4.Identity
Element
There
exists a distinguished element e∈S, Such that for
any a∈S,
a*e = e*a = a
The
element e∈S is called the identity element of S
with respect to operation *.
Example
0
and 1 are the identity elements of Z with respect to the operations of addition
and multiplication respectively,
since,
for any a∈Z
a+0
= 0+a = a
a×1
= 1×a = a
5.Inverse
Element
For
each a∈S, there exists an element a-1∈S
such that
a*a-1 = a-1*a = e
The
element a-1∈S is called the inverse of a under the
operation *.
Example
For
each a∈Z, -a is the inverse of a under the
operation of addition, since,
a+(-a)
= (-a)+ a = 0
where
0 is the identity element of Z under addition.
6.Distributivity
For
any a,b,c∈S,
a*(b⨁c) = a*b⨁a*c
In
this case the operation * is said to be distributive over the operation ⨁.
Example
The
usual multiplication is distributive over addition, since
a×(b+c)
= a×b+a×c
7.Cancellation
Property
For
any a,b,c ∈S and a≠0,
a*b = a*c ⇒ b=c and
b*a = c*a ⇒ b=c
Example
Cancellation
property holds good for any a,b,c∈Z under addition
and multiplication.
8.Idempotent
Element
An
element a∈S is called an idempotent element with
respect to the operation *, if
a*a = a
Example
i)0∈Z
is an idempotent element under addition, since,
0+0
= 0
ii)0
and 1∈Z are idempotent elements under
multiplication, since,
0×0
= 0 and
1×1
= 1
9.Homomorphism
If
{X,•} and {Y,*} are two algebraic systems, where • and * are binary (n-ary)
operations, then a mapping
g: X→Y
is
called a homomorphism or simply morphism from {X,•} to {Y,*}, if for any x1,x2∈X,
g(x1•x2) = g(x1)*
g(x2)
If
a function g satisfying the above condition exists, then {Y,*} is called the
homomorphic image of { X,•}, even though g(X)⊆Y.
The
concepts of homomorphism holds good for algebraic systems with more than one
binary operations. Also more than one
homomorphic mapping is possible from one algebraic system to another.
9(a) Epimorphism
If
the homomorphism g: {X,•} → {Y,*} is onto, the g is called an
epimorphism.
9(b) Monomorphism
If
the homomorphism g: {X,•} → {Y,*} is one-to-one, then g is called a
monomorphism.
9(c) Isomorsphism
If
g: {X,•} → {Y,*} is one-to-one onto, then g is called an isomorphism. In this case the algebraic systems {X,•} and
{Y,*} are said to be isomorphic or to be of the
same type.
9(d)
Endomorphism
A
homomorphism g: {X,•} → {Y,*} is called an endomorphism, if Y⊆X.
9(e)
Automorphism
An
isomorphism g: {X,•} → {Y,*} is called an automorphism, Y=X.
10.Subalgebra
If
{X,•} is an algebraic system and Y is a non-empty set such that Y⊆X is closed under the operation •, then
{Y,•} is called a sub-algebraic system or a subalgebra of {X,•}.
Example
{Z+,×}
is a subalgebra of the algebra {Z,×}, where × is the multiplication operator.
11.Direct
Product
If
{X,•} and{Y,*} are two algebraic systems of the same type, then the algebraic
system {X×Y,⨁} is called the direct product of the algebras {X,•} and
{Y,*}, provided the operation ⨁
is defined for any x1,x2∈X and y1,y2∈Y
as
(x1,y1)⨁(x2,y2)
= { x1•x2, y1*y2 }
The
original algebraic systems are called the factor algebras of {X×Y,⨁}.
SEMIGROUPS AND MONOIDS
Definition of a
Semigroup
If
S is a non-empty set and * be a binary operation on S, then the algebraic
system {S,*} is called a semigroup, if it holds following two conditions
simultaneously
i.Closure
If for any a,b∈S,
a*b∈ S
ii.Associative
If for any a,b,c∈S,
(a*b)*c=a*(b*c)
Example
1.If
E is the set of positive even numbers, then {E,+} and {E,×} are semigroups.
2.The set S={1,2,3,…} with addition operation is
a semigroup.
Here closure property holds as for every
pair 1+2=3∈S
Associative property also holds for every
element (1+2)+3=1+(2+3)=5∈S
Definition of a
Monoid
If
a semigroup {M,*} has an identity element with respect to the operation *, then
{M,*} is called a monoid. So, a monoid
holds three properties simultaneously
i.Closure
If
for any a,b∈S,
a*b∈ S
ii.Associative
If
for any a,b,c∈S,
(a*b)*c=a*(b*c)
iii.Identity element
If
there exists an element e∈M such that for any a∈M,
e*a=a*e=a
then
the algebraic system {M,*} is called a monoid.
Example
1.If
N is the set of natural numbers, then {N,+} and {N,×} are monoids with the
identity elements 0 and 1 respectively.
2.The set S={1,2,3,…} with multiplication
operation is a monoid.
Here closure property holds as for every
pair 1×2=3∈S
Associative property holds for every
element (1×2)×3=1×(2×3)=6∈S
Identity property also holds for every element
HOMOMORPHISM OF
SEMIGROUPS AND MONOIDS
Definition of
Semigroups Homomorphism
If
{S,*} and {T,∆} are any two semigroups, then a mapping g: S→T such that, for
any two elements a,b ∈ S,
g(a*b) = g(a) ∆ g(b)
is
called a semigroup homomorphism.
As
defined in general algebraic system, a semigroup homomorphism is called a
semigroup epimorphism, semigroup monomorphism or semigroup isomorphism,
according as the mapping g is onto, one-to-one or one-to-one onto.
Definition of
Monoids Homomorphism
If
{M,*,eM } and {T,∆,eT } are any two monoids, where eM
and eT are identity elements of M and T with respect to the
corresponding binary operations * and ∆ respectively, then a mapping
g:
M→T such that, for any two elements a,b∈M,
g(a*b) = g(a)
∆ g(b) and
g(eM)
= eT
is
called a monoid homomorphism.
As before monoid epimorphism, monoid monomorphism and monoid isomorphism are defined.
SUBSEMIGROUPS
AND SUBMONOIDS
Definition of Subsemigroup
If
{S,*} is a semigroup and T⊆S is closed under the operation *, then
{T,*} is called a subsemigroup of {S,*}.
Example
If
the set E of all even non-negative integers, then {E,+} is a semigroup of the
semigroup {N,+}, where N is the set of natural numbers.
Definition of
Submonoids
If
{M,*,e} is a monoid and T⊆M is closed under the operations * and e∈T,
then {T,*,e} is called a submonoid of {M,*,e}.
Example
If
E is the set of all non-negative even integers, then {E,+,0} is a submonoid of
{N,+,0}, where N is the set of natural numbers.
GROUPS
Definition
If
G is a non-empty set and * is a binary operation of G, then the algebraic
system {G,*} is called a group if the following conditions are satisfied:
For
all a b,c ∈ G,
(a*b)*c=a*(b*c)
(Associativity)
There
exists an element e∈G such that, for any a∈G,
a*e=e*a=a (Existence of identity)
For
every a∈G, there exists
an element a-1∈G such that
a*
a-1 = a-1*a = e
(Existence of inverse)
Note: The algebraic system {S,*} is a semigroup, if
* is associative. If there exists an
identity element e ∈ S, then {S,*} is a monoid. Further if there exists an
inverse for each element of S, then {S,*} is a group.
Example
{Z,+} is a group under the usual addition.
Definitions
- When
G is finite, the numbers of elements of G is called the Order of G and denoted by
O(G)
or ।G।.
- If
the element a∈G, where G is a group with identity
element e, then the least positive integer m for which am = e is
called the order of the element a and
denoted as O(a).
- If no such integer exists, then a is of infinity order.
- A group {G,*}, in which the binary operation * is commutative is called a commutative group or abelian group.
Comments
Post a Comment