Mathematical Foundation of Computer Science

DHARM

ALGEBRAIC STRUCTURES 89

Left cosets and right cosets may or may not be equal. They are equal only for commuta-
tive groups, otherwise they are unequal.
For example, let I be the additive group of integers, i.e. (I, +) now take a subset of I is J
where J = 3I, so J = {......, – 6, – 3, 0, 3, 6, ....} [J ⊆ I]
Thus cosets of J in I generated by element 0, 1, 2 (∴0, 1, 2 ∈ I) are correspondingly
given as,
0 + J = { ......, – 6, – 3, 0, 3, 6, ....},
1 + J = {......, – 5, – 2, 1, 4, 7, ......},
2 + J = {......, – 4, – 1, 2, 5, 8, ......},
3 + J = {......, – 6, – 3, 0, 3, 6, ....} = 0 + J
4 + J = {......, – 5, – 2, 1, 4, 7, ......} = 1 + J
5 + J = {......, – 4, – 1, 2, 5, 8, ......} = 2 + J
6 + J = {......, – 6, – 3, 0, 3, 6, ......} = 0 + J
and so on, hence cosets,
0 + J = 3 + J = 6 + J = ...... = { ......, – 6, – 3, 0, 3, 6, ....}
1 + J = 4 + J = 7 + J = ..... = {......, – 5, – 2, 1, 4, 7, .....}
2 + J = 5 + J = 8 + J = ...... = {......, – 4, – 1, 2, 5, 8, ....}
From these cosets we can easily find the entire set I, i.e.,
I = (0 + J) ∪ (1 + J) ∪ (2 + J)
Therefore, cosets are the way of partitioning the entire set into smaller sets.

0+J 1+J
2+J
I
Fact
Let X is a group and Y is its subgroup then, number of distinct cosets of Y is called the index
of Y in X and is denoted by [X:Y], i.e.
[X : Y] = O(X)/O(Y) (index formula)
Immediate consequence of the above discussed index formula resulted a theorem known
as Lagrange theorem.
Lagrange Theorem
If Y is the subgroup of finite group X, then order of Y and index of Y in X divides the order of
the group X.
i.e., O(Y) is divisor of O(X), and [X: Y] is divisors of O(X).
Hints
Let order of group X is n, i.e., O(X) = n. Consider any element g in X. Let g be order m, then
Y = < g > = {g^0 , g^1 , g^2 , ........ , gm–1}, where g^0 = ê and gm = ê
Whence, the subgroup of X in particular the cyclic group generated by n, i.e.,
m = O(g) = O(Y) = O(< g >)
that concludes the theorem.