Mathematical Foundation of Computer Science

DHARM

84 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

of closure property by operation + over K (since addition of two positive odd integers must be

an even positive integer that is not in the set K). Therefore, (J, +) is a sub semigroup of (I+, +),

or

(J, +) ⊆ (I+, +)

4.4 Complexes..........................................................................................................................

Let (X, ⊕) be a group, and Y ⊆ X then Y is called the complex of group (X, ⊕). For example,

consider X = {1, – 1, i, – i} and operation is usual multiplication ‘×’ then (X, ×) is a group. Now

{1, – 1}, {1, i}, {1, – i}, {– 1, i}, {– 1, – i}, and {i, – i} are subsets of X are called complexes of the

group (X, ×). Out of these complexes some complexes may form a group or may not form a

group under bounding operation ‘×’.

4.5 Product Semi Groups........................................................................................................

Let (X, ⊕), and (Y, ⊗) are two semigroups, define Z = X × Y such that the elements of Z are
ordered pair (x, y) where x ∈ X and y ∈ Y. Then (Z, #) is also a semigroup by assuming (a, b)
∈ Z and (c, d) ∈ Z i.e., (a, b) # (c, d) = (a ⊕ c, b ⊗ d). Hence, (Z, #) is called a product semigroup.
Consider an example, algebraic system (R+, ×) where × is usual multiplication operation
defines over the set of positive real numbers R+ forms a semigroup. Similarly (I, + 4 ) where + 4
is addition modulo 4 operation define over set of Integers forms a semigroup. Let S is the
direct product, i.e., S = R+ × I, then check whether (S, #) is a semigroup or not. Assume
ordered pairs (a, b) ∈ S and (c, d) ∈ S, where elements a, c belongs to R+, and elements b, d
belongs to I then
(a, b) # (c, d) = (a × c, b + 4 d)
Since operation × is closed in R+ and operation + 4 is closed in I, hence operation # is
closed. Also, since operation × and + 4 are associative hence # also holds associativity. Therefore,
direct product is a semigroup.

4.6 Permutation Groups..........................................................................................................

Let X be a group and p : X → X is a mapping to be permutation of X if p is bijective (one-one and
onto). Such groups are called permutation groups. Let X = {a, b, c,.....} be a set and let p
denotes a permutation of the elements of X; i.e., p : X → X is a bijective, then

p =

abc

pa pb pc

......

( ) ( ) ( )......

F

HG

I

KJ

is called permutation group, where image of the element of X is entered below the element.

For example, let X = {1, 2, 3} and suppose p(1) = 2, p(2) = 3, p(3) = 1 then we may represent p as,

p =

123

231

F

H

I

K or

132

213

F

H

I

K or

312

123

F

H

I
K
and so on. In general, a group of n-elements can have a total of n! permutations that is called
order of permutation and the degree of permutation is the number of the elements of the set
X. In the said example, the degree of permutation is 3 and the order of permutation is 6.
Let p 1 , p 2 , .......pn! are all possible permutations of a set of n elements then it is called
symmetric set of permutations. In the previous example {p 1 , p 2 , ...p 6 } are the symmetric set of
permutations that are shown below.