Mathematical Foundation of Computer Science

(Chris Devlin) #1
DHARM

ALGEBRAIC STRUCTURES 87

So, ê a–1 ∈ Y Y–1 ⊂ Y, thus a–1 ∈ Y.
Similarly, if a, b ∈ Y ⇒ b–1 ∈ Y and ab–1 ∈ Y;
So, (ab–1)–1 ∈ YY–1 ⊂ Y, i.e. a, b ∈ Y
Thus, a ∈ Y ⇒ a–1 ∈ Y and a, b ∈ Y ⇒a b ∈ Y, hence Y becomes a subgroup.

Example 4.8. Let Y and Z are two subgroups of X, then product of YZ is a subgroup of X if and
only of YZ = ZY.
Sol. Necessary Condition. Since, Y, Z, and YZ are subgroups of X, i.e.
Y < X, Z < X, and YZ < X
Therefore, Y–1 = Y, Z–1 = Z, (YZ)–1 = YZ,
But (YZ)–1 = Z–1Y–1, = ZY
Thus, ZY = YZ
(Sufficient condition) To claim YZ < X, from given Y < X, Z < X, and YZ = ZY
Since, we have Y^2 = Y = Y–1 and Z^2 = Z = Z–1
Assume S = YZ
Then, S^2 = (YZ) (YZ) = Y (ZY) Z = Y (YZ) Z (Commutivity)
= (YY) (ZZ)
= Y^2 Z^2
= YZ (∴ Y^2 Z^2 = YZ)
= S
also, S–1 = (YZ)–1 = Z–1 Y–1
= ZY
= YZ (∴ ZY = YZ)
= S
So, we have S^2 = S = S–1, therefore S is a subgroup of X, or YZ < X.


4.9 Cyclic Groups.....................................................................................................................


A group (X, x) is said to be cyclic group if ∀x ∈ X, there exists a, fixed element g such that, gn=x
for some integer n, where g is called generator of the cycle. Alternatively, a group X is said to
be cyclic with generator g if every element of X is in g, where g is of the form,
g^0 = e; g^1 = g; g^2 = g × g; .............; gn = g × g × g ......... × g (n times)
(where n ∈ I)
l Consider an example of group (X, ×), where X = {1, – 1, i, – i}. Since every element of
X is generated from one of the element ‘i’ of the set, i.e.,
i^4 = 1 ; i^2 = – 1; i^3 = i; i^4 = – i.
Since each element can be expressed in some power of i so i is one of the generator of
the cyclic group, hence,
g = [i]
Similarly, other element ‘– i’ also generates all the elements of the set X, hence other
generator, i.e., g = [– i], where -i is the inverse element of i.
Hence, we can say that if a is the generator of the cyclic group X then a–1 is also a
generator of X.
Therefore, g = [i] or [– i] are two generators of the cyclic group X.

Free download pdf