Redshift Academy


Building Groups From Other Groups
---------------------------------

Quotient Groups
---------------

One way to build finite groups is to perform some 
kind operation involving smaller simpler groups.  
Before we go any further we need to discuss the 
idea of equivancy relations.

Equivalence Relations on Sets
-----------------------------

Basic idea:  If X is the set of all cars, and ~ is 
the equivalence relation "has the same color as", 
then one particular equivalence class consists of 
all green cars. X/~ could be naturally identified 
with the set of all car colors.

An equivalence relation, ~, from a set, S, to a 
set, T, is a subset of S x T.

An equivalence relation, ~, on a set, S, is a 
subset of S x S.

Where ~ is interpreted as 'equivalent to' and not
'approximately equal to'.

~ has to be reflexive, symmetric and transitive.  
That is, for s_i ∈ subset:

s_i ~ s_i - reflexive

s_i ~ s_j -> s_j ~ s_i - symmetric

s_i ~ s_j and s_i ~ s_k -> s_i ~ s_k - transitive

Equivalency Classes
-------------------

The equivalence class of an element a is denoted 
by [a] and is defined as the set:

[a] = {s ∈ S|s ~ a}

Non-overlapping (disjoint) equivalence classes 
form a partition of S where elements in the same
partition are related.

The set of all equivalence classes in S with 
respect to an equivalence relation ~ is denoted 
as S/~ and is called S modulo ~ (or the quotient 
set of S by ~).

Example 1:

ℤ is the set of all integers.  Let m ~ n i.f.f. 
m - n is divisble by 3 for any m,n ∈ ℤ.

Reflexive because m - m = 0 which is divisible by 3.

Symmetric because if m - n is divisible by 3 then
n - m = -(m - n) is also divisible by 3.

Transitive because m - n = 3a and n - p = 3b (a
and b are integers) so m - p = (m - n) + (n -p)
= 3(a + b).  Thus, m ~ p.

The equivalency classes are:

[0] = {0,3,6,...}

[1] = {1,4,7,...}

[2] = {2,5,8,...}

[3] = {3,6,9,...}

[4] = {4,7,10,...}

ℤ/~ = {[0],[1],[2],...}

Example 2:

{(1,1),(2,2),(3,3),(2,3),(3,2)}

Reflexive because (1,1), (2,2), (3,3) are present.

Symmetric because (2,3), (3,2) are present.

Transitive because (2,3), (3,2) -> (2,2) 

(3,2),(2,3) -> (3,3)

The equivalency classes are:                   

[1] = {1}

[2] = {2,3}

[3] = {3,2}

S/~ = {[1],[2]}

    = {{1},{2,3}}

Equivalence Relations on Groups
-------------------------------

Define a relation ~ on G by saying a ~ b if and 
only if there exists g ∈ G such that:

Multiplicative:  a = gbg^-1 

Additive: a = g + b + (-g)

Proof that ~ is an equivalence relation on G:

Reflexive:  a = eae^-1  

             a ~ a

Symmetric:  a = gbg^-1

            g^-1a = bg^-1

            g^-1ag = b

            g^-1a(g^-1)^-1 = b  x^-1 ∈ G

            Therefore a ~ b implies b ~ a

Tramsitive:  a = gbg^-1 and b = hch^-1

             a = g(hch^-1)g^-1

               = ghch^-1g^-1

               = ghc(gh)^-1  gh ∈ G
   
             Therefore a ~ c

a ~ b are said to be CONJUGATE and, therefore, 
conjugacy is an equivalence relation on a group.

[a] = {b ~ a|b ∈ G and b = gag^-1}

[a] is called the CONJUGACY CLASS.

Normal Subgroup
---------------

The conjugacy class containing e is a normal 
subgroup, if:

multiplicative:  gng^-1 ∈ N  for n ∈ N, g ∈ G

                 or,

                 gn = ng after multiplying g 
                         from the right

additive:  g + n + (-g) ∈ N for n ∈ N, g ∈ G

           or,

           g + n = n + g

Note that e = 1 in the multiplicative case and 
e = 0 in the additive case (i.e. 0^-1 is undefined).

In the multiplicative case if G is abelean then,

gg^-1n = n ∈ N

We can also look at the above in a reverse manner.
Let G be a group and N be subgroup of G.  To be a
subgroup N must contain the identity, e.  Then,

a ~ b is an equivalence relation if and only if:

Multiplicative case:  ab^-1 = e              

Additive case:  a + (-b) = e          

Where a, b ∈ G and e ∈ N

Proof:

Reflexive:  aa^-1 = e ∈ N 

             a ~ a

Symmetric:  (ab^-1)^-1 = e^-1

            (b^-1)^-1a^-1 = e^-1
            
            ba^-1 = e^-1

            b ~ a

Tramsitive:  ab^-1 = e and bc^-1 = e²

             (ab^-1)(bc^-1) = e²

             ac^-1 = e²

             a ~ c

The equivalence class of e, is a normal subgroup N 
of G and the other equivalence classes are the cosets 
of N  It is important to note that cosets are not
subgroups.

In summary, the elements of any group may be 
partitioned into conjugacy classes.  Members of 
the same conjugacy class share many properties, 
and study of conjugacy classes of non-abelian 
groups reveals many important features of their 
structure.  For an abelian group, each conjugacy 
class is a set containing one element. 

Congruency Relations on Groups
------------------------------

An equivalence relation is just a relation which 
is reflexive, transitive, and symmetric.

A congruence relation is a little bit more than an
equivalence relation in that it respects some 
structure such as a group.  In this case we add 
the additional 2 axioms.

a₁ ≅ a₂ (mod n), b₁ ≅ b₂ (mod n)

Multiplicative:  a₁b₁ ≅ a₂b₂ (mod n)

Additive:  a₁ + b₁ ≅ a₂ + b₂ (mod n)

For all a₁, a₂, b₁, b₂ ∈ G.

Example:

a₁ = 1, a₂ = 4, b₁ = 2, b₂ = 5

1 ≅ 4 (mod 3) and 2 ≅ 5 (mod 3)

Therefore,

(1 + 2) ≅ (4 + 5) (mod 3) 

and,

(1 x 2) = (4 x 5) (mod 3)

Now that we have discussed equivalence relations
on groups we are in a position to discuss quotient
groups.  These best way to do this is to use an
example.

Example:

G = (ℤ,+)  ℤ = {0,1,-1,2,-2,3,-3,...}

N = 3ℤ = {3z|z ∈ ℤ}  

ℤ:
  --o---o---o---o---o---o---o---o---o---o---o---o---o--
   -6  -5  -4  -3  -2  -1   0   1   2   3   4   5   6

3ℤ:

  --o-----------o-----------o-----------o-----------o--
   -6          -3           0           3           6


1 + 3ℤ = {1 + x|x ∈ 3ℤ}:

  ------o-----------o-----------o-----------o----------
       -5          -2           1           4    

2 + 3ℤ = {2 + x|x ∈ 3ℤ}:

  ----------o-----------o-----------o-----------o------
           -4          -1           2           5   

and so on.

We can now pick a representative element from 
each coset and name the coset after it.
     
[0] = {0,3,6}

[1] = {1,4,7}

[2] = {2,5,8}

[0] contains the identity. Therefore, if we pick 
g = 2 and n = 1 we get:

2 + 1 + (-2) = 1

which proves that [0] is a normal subgroup.

In summary, in a quotient group, the equivalence 
class of the identity element is always a normal 
subgroup of the original group, and the other 
equivalence classes are the cosets of that normal 
subgroup.  Together they form a partition of G 
written as G/N, where G is the original group and 
N is the normal subgroup.   This is also written 
as G/~.

Direct Product of Groups
------------------------

The direct product is another way to build finite 
groups from smaller simpler groups.  Consider 
2 groups G and H.

The direct product is defined as:

G x H = A

In terms of elements this is:

(g₁,h₁) x (g₂,h₂) = (g₁◇g₂,h₁□h₂)

Where ◇ is the operation on G and □ is the 
operation on H.

The order of A is:

|A| =|G| x |H|

G and H do not have to be the same size.

This operation is the analogue of the Cartesian 
product of sets and is one of several important 
notions of direct product in mathematics. 

Example 1:

G = ℤ mod 2 under + = {0,1}

H = ℤ mod 2 under +

The elements are given by (not a Cayley table).

  |  0 | 1 
--+----+---
0 | 00 | 01 
--+----+---
1 | 10 | 11

The Cayley table is:

 +  | 00 | 11 | 10 | 01
----+----+----+----+----
 00 | 00 | 11 | 10 | 01
----+----+----+----+----
 11 | 11 | 00 | 01 | 10
----+----+----+----+----
 10 | 10 | 01 | 00 | 11
----+----+----+----+----
 01 | 01 | 10 | 11 | 00

It is important to recognize the mod of each 
group in caculating the table entries.  For 
example, the blue cell is:

(1,0) x (1,0) = ((1 + 1),(0 + 0) = (2,0)

However, 2 (mod 2) = 0

If we let 1 = 11, 0 = 00, 1 = 10 and 2 = 01  
we get:

 + | 0 | 1 | 2 | 3
---+---+---+---+----
 0 | 0 | 1 | 2 | 3
---+---+---+---+----
 1 | 1 | 0 | 3 | 2
---+---+---+---+----
 2 | 2 | 3 | 0 | 1
---+---+---+---+----
 3 | 3 | 2 | 1 | 0

This is the Klein 4 group. Therefore Z₂  x Z₂ 
is isomorphic to the Klein 4 group.

Example 2:

G = ℤ₂ under +

H = ℤ₃ under + = {0,1,2}

The elements are given by (not a Cayley table).

  |  0 |  1 |  2
--+----+----+---
0 | 00 | 01 | 02
--+----+----+---
1 | 10 | 11 | 12

The Cayley table is:

  + | 00 | 11 | 02 | 10 | 01 | 12
----+----+----+----+----+----+----
 00 | 00 | 11 | 02 | 10 | 01 | 12
----+----+----+----+----+----+----
 11 | 11 | 02 | 10 | 01 | 12 | 00     
----+----+----+----+----+----+----
 02 | 02 | 10 | 01 | 12 | 00 | 11     
----+----+----+----+----+----+----
 10 | 10 | 01 | 12 | 00 | 11 | 02     
----+----+----+----+----+----+----
 01 | 01 | 12 | 00 | 11 | 02 | 10     
----+----+----+----+----+----+----
 12 | 12 | 00 | 11 | 02 | 10 | 01

Again, it is important recognize the mod 
of each group in caculating the table entries.  
For example, the blue cell is

(1,2) x (1,2) = ((1 + 1),(2 + 2) = (2,4)

The first number is subject to mod 2 and the 
second number is subject to mod 3. Therefore:

(2,4) -> (0,1)

Let 0 = 00, 1 = 11, 2 = 02, 3 = 10, 4 = 01 and 
5 = 12.  This leads to:

 + | 0 | 1 | 2 | 3 | 4 | 5 
---+---+---+---+---+---+---
 0 | 0 | 1 | 2 | 3 | 4 | 5 
---+---+---+---+---+---+---
 1 | 1 | 2 | 3 | 4 | 5 | 0 
---+---+---+---+---+---+---
 2 | 2 | 3 | 4 | 5 | 0 | 1  
---+---+---+---+---+---+---
 3 | 3 | 4 | 5 | 0 | 1 | 2 
---+---+---+---+---+---+---
 4 | 4 | 5 | 0 | 1 | 2 | 3 
---+---+---+---+---+---+---
 5 | 5 | 0 | 1 | 2 | 3 | 4 

This is the ℤ mod 6 group.  There Z mod 2 x Z mod 3 
is isomorphic to the Z mod 6 group.

If each group is an abelian group, as is the case
here, then we can refer to G x H as G ⊕ H.  
However, this is simply a matter of notation - the 
concepts are always the same regardless of whether 
we use additive or multiplicative notation.  Since 
both G and H in the above case are abelian we can 
also write:

G x H ≡ G ⊕ H

Example 3:

G = ℤ₂ under +

H = {1,-1,i,-i) under x

The elements are given by (not a Cayley table).

    |  1  |   -1 |   i |   -i
----+-----+------+-----+------
  0 | 0,1 | 0,-1 | 0,i | 0,-i    
----+-----+------+-----+------
  1 | 1,1 | 1,-1 | 1,i | 1,-i    

The Cayley table is:

   x  | 0,1  | 0,-1 | 0,i  | 0,-i | 1,1  | 1,-1 | 1,i  | 1,-i 
------+------+------+------+------+------+------+------+------
 0,1  | 0,1  | 0,-1 | 0,i  | 0,-i | 1,1  | 1,-1 | 1,i  | 1,-i
------+------+------+------+------+------+------+------+------
 0,-1 | 0,-1 | 0,1  | 0,-i | 0,i  | 1,-1 | 1,1  | 1,-i | 1,i
------+------+------+------+------+------+------+------+------
 0,i  | 0,i  | 0,-i | 0,-1 | 0,1  | 1,i  | 1,-i | 1,-1 | 1,1
------+------+------+------+------+------+------+------+------
 0,-i | 0,-i | 0,i  | 0,1  | 0,-1 | 1,-i | 1,i  | 1,1  | 1,-1
------+------+------+------+------+------+------+------+------
 1,1  | 1,1  | 1,-1 | 1,i  | 1,-i | 0,1  | 0,-1 | 0,i  | 0,-1
------+------+------+------+------+------+------+------+------
 0,-i | 0,-i | 0,i  | 0,1  | 0,-i | 1,-i | 1,i  | 1,1  | 1,-1
------+------+------+------+------+------+------+------+------
 1,1  | 1,1  | 1,-1 | 1,i  | 1,-i | 0,1  | 0,-1 | 0,i  | 0,-1
------+------+------+------+------+------+------+------+------
 1,-1 | 1,-1 | 1,1  | 1,-i | 1,i  | 0,-1 | 0,1  | 0,-i | 0,i
------+------+------+------+------+------+------+------+------
 1,i  | 1,i  | 1,-i | 1,-1 | 1,1  | 0,i  | 0,-i | 0,-1 | 0,1
------+------+------+------+------+------+------+------+------
 1,-i | 1,-i | 1,i  | 1,1  | 1,-1 | 0,-i | 0,i  | 0,1  | 0,-1
------+------+------+------+------+------+------+------+------

This time H has no mod so only the first entry
is involved.