GroupsPhilip J. ErdelskyNovember 7, 2002 |
Please e-mail comments, corrections and additions to the webmaster at pje@efgh.com.
A group is a set G and a binary operation with the following properties:
A set is said to be a group under a particular operation if the operation obeys these conditions. For example, the integers Z are a group under addition, but not under multiplication (because left inverses do not exist for most integers).
Associativity can easily be extended to operations on four or more elements. For example,
(ab)(cd) = a(b(cd)) = a((bc)d).
The operation is not necessarily commutative. However, we can prove that the operations in properties (2) and (3) are commutative, so that every left identity is also a right identity and every left inverse is also a right inverse.
Theorem 1.1. Every element in a group G commutes with its left inverse, i.e., aa^{ -1} = e for every a ∈ G.
Proof. Let (a^{ -1})^{ -1} be the left inverse of a^{ -1}. Then (a^{ -1})^{ -1}a^{ -1} = e.
Consider (a^{ -1})^{ -1}a^{ -1}aa^{ -1}. We associate it in two ways:
(a^{ -1})^{ -1}a^{ -1}aa^{ -1}= ((a^{ -1})^{ -1}a^{ -1})(aa^{ -1}) = e(aa^{ -1}) = aa^{ -1},
(a^{ -1})^{ -1}a^{ -1}aa^{ -1}= (a^{ -1})^{ -1}((a^{ -1}a)a^{ -1}) = (a^{ -1})^{ -1}(ea^{ -1}) = (a^{ -1})^{ -1}a^{ -1} = e,
and the desired result follows. █
Theorem 1.2. Every element in a group G commutes with the identity, i.e., ae = a for every a ∈ G.
Proof. This is easily proven by using associativity and the previous theorem:
ae = a(a^{ -1}a) = (aa^{ -1})a = ea = a.█
Since there is no difference between left and right identities and inverses, they are called simply identities and inverses.
Theorem 1.3. A group has only one identity and each element has only one inverse.
Proof. Let f be an identity. Then fe = e. But fe = f because the left identity e is also a right identity. Hence f=e.
Let b be an inverse for a. Then ba = e. Postmultiplying by a^{ -1} yields
(ba)a^{ -1} = ea^{ -1},█
b(aa^{ -1}) = a^{ -1},
be = a^{ -1},
b = a^{ -1}.
The identity is its own inverse. However, it may not be unique in this respect. For example, the set of all nonzero real numbers is a group under multiplication. The identity 1 is its own inverse, but so is -1.
If a group contains only a finite number of elements, the number of elements is called the order of the group.
Two groups G and H are isomorphic if there is one-to-one correspondence f : G ⟶ H which preserves the group operation, i.e., for every a and b ∈ G, f(ab) = f(a)f(b).
Such a function is called an isomorphism. Although an isomorphism is required to preserve only the group operation, it is fairly easy to prove that it also preserves the identity and inverses:
Of course, in f(e) = e, the first e refers to the identity of the first group, and the second e refers to the identity of the second group.
There are many examples of groups. The set of real numbers is a group under addition, but not under multiplication because zero has no inverse. The set {0, 1, ..., N-1} is a group under addition modulo N. The set of all permutations of a set is a group under composition. If the set has n elements, the group is called the symmetric group and is usually represented by S_{n}.
A subset H of a group G is called a subgroup if it is a group with the same binary operation, which is the case when
In any group, we can define an operation analogous to exponentiation in ordinary arithmetic. Let a be a group element and n a positive integer. Then define
a^{ n} = aaa...a (repeated n times),
a^{ 0} = e,
a^{ -n} = (a^{ n})^{ -1}.
It is easy to show that this operation obeys the following rules of exponentiation, where m and n are any integers:
a^{ m+n} = a^{ m}a^{ n},
a^{ mn} = (a^{ m})^{ n}
The set of all powers of a group element a is a subgroup called the subgroup generated by a.
Theorem 2.1. The subgroup generated by an element of a group is isomorphic to the integers Z under addition or to {0, 1, ..., r-1} under addition modulo r for some positive integer r, which is called the order of the element.
Proof. If the element is the identity, the result is obvious and its order is 1.
If the powers of a are all distinct, then H is isomorphic to Z, where the isomorphism f : Z ⟶ H is defined by
f(n) = a^{ n}.
If the powers of a are not all distinct, then let m and n be two integers with m < n and
a^{ m} = a^{ n}.
Then multiply by a^{ -m} to obtain:
e = a^{ n-m}.
Let r be the smallest positive integer such that
a^{ r} = e.
By the division algorithm, n = rq + s for any integer n, where 0 <= s < r. Hence
a^{ n} = a^{ rq}a^{ s} = (a^{ r})^{ q}a^{ s} = e^{ q}a^{ s} = a^{ s}.
Hence {e, a, a^{ 2}, ..., a^{ r-1}} constitute the entire subgroup. These elements are all distinct; assume, for purpose of contradiction, that
a^{ m} = a^{ n}
0 <= m < n < r.
Then
a^{ n-m} = e,
which is impossible because n-m is less than r.
It is fairly easy to show that {e, a, a^{ 2}, ..., a^{ r-1}} are a subgroup isomorphic to {0, 1, ..., r-1} under addition modulo r. █
For finite groups, the following theorem, called Lagrange's Theorem, gives a simple relation between the order of the group and the orders of its subgroups.
Theorem 2.2. The order of a subgroup of a finite group divides the order of the group.
Proof. Let H be a subgroup of the finite group G. For any a ∈ G, the coset of H with respect to a is {ax | x ∈ H}, which we shall call coset(a).
The union of all cosets is G, since every a ∈ G belongs to coset(a).
An element of coset(a) can be expressed as ax for only one value of x in H; for if ax = ay then a^{ -1}ax = a^{ -1}ay, ex = ey, and x = y. Therefore, every coset contains the same number of elements as H. (Notice that H itself is coset(e).)
Suppose coset(a) and coset(b) have an element in common. Then ax = by for some x and y ∈ H. Then any other element az ∈ coset(a) is also in coset(b) because
az = axx^{ -1}z = byx^{ -1}z
and yx^{ -1}z is in H. Similarly, every element of coset(b) is also in coset(a), and the two cosets are identical.
Hence the number of elements in G is the product of the number of elements in H (or any other coset) and the number of cosets. █
Corollary 2.3. The order of an element of a finite group divides the order of the group.
Corollary 2.4. If the order of a finite group is a prime number p, then the group is isomorphic to Z_{p}.
The classification of finite groups is a large and interesting topic in mathematics. Groups that are isomorphic to each other are not considered different, so we will often speak of isomorphic groups as the same. If groups with a particular property are all isomorphic to each other, we will speak of the group with that property.
A group isomorphic to Z_{n} (the integers {0, 1, ..., n-1} under addition modulo n) is called the cyclic group of order n, and it is often written as C_{n}.
It is clear that the only groups of order 1, 2 and 3 are C_{1}, C_{2} and C_{3}, respectively. More generally, if p is a prime number, then the only group of order p is C_{p}.
Consider the following operation on the cross product G ⨯ H of two groups:
(a,b)(c,d) = (ac, bd).
It is fairly easy to show that this is a group. If G and H are finite, G ⨯ H is also finite and its order is the product of the orders of G and H. Moreover, the order of an element (a,b) is the least common multiple of the orders of a and b.
There are at least two groups of order 4: C_{4} and C_{2} ⨯ C_{2}. These two groups are not isomorphic, because C_{4} has an element of order 4 and C_{2} ⨯ C_{2} does not. It can be shown that these are the only groups of order 4.
The symmetric group S_{n} of permutations of a set with n elements is a group of order n!. The set of all even permutations of such a set is a group of order n!/2 called an alternating group, and it is often written as A_{n}.
Permutation groups are especially important, because every group of order n is isomorphic to a subgroup of S_{n}. This is fairly easy to prove. Let a be an element of the group G. The function T_{a} : G ⟶ G defined by T_{a}(x) = ax is called a translation of the group. It is easily shown to be a permutation. The set of all such permutations is a group under composition, and the association of a with T_{a} is an isomorphism.
If the group operation is commutative (ab = ba for every a and b in the group), then the group is called a commutative group or an abelian group. The symbols for regular addition (which is commutative) are often used for a commutative group:
regular group notation | commutative group notation |
---|---|
ab | a+b |
e | 0 |
a^{ -1} | -a |
a^{ n} | na |
ab^{ -1} | a-b |
The integers are a commutative group under addition. The groups of order 1, 2, 3, 4 and 5 defined in the previous section are commutative. The smallest group which is not commutative is S_{3}, which has six elements.
Every cyclic group is commutative.
Theorem 4.1. If the orders of two elements of a commutative group are relatively prime, the order of their product is the product of their orders.
Proof. Let a and b be two elements of a commutative group with relatively prime orders r and s, respectively. Then the order of ab is the smallest positive integer m for which (ab)^{ m} = e, or equivalently a^{ m} = b^{ -m}.
Raise each side to the s-th power to obtain a^{ ms} = b^{ -ms} = (b^{ -s})^{ m} = e^{ m} = e. Hence r divides ms. Since r and s are relatively prime, r divides m. Similarly, s divides m. Since r and s are relatively prime, rs divides m. Since (ab)^{ rs} = a^{ rs} b^{ rs} = ee = e, m divides rs. and hence m = rs. █
Actually, it is not necessary that the entire group be commutative. It is sufficient that the two elements commute with each other.