[edit] Definition
A group (G, *) is a set G with a binary operation * that satisfies the following four axioms:
Closure: For all a, b in G, the result of a * b is also in G.
Associativity: For all a, b and c in G, (a * b) * c = a * (b * c).
Identity element: There exists an element e in G such that for all a in G, e * a = a * e = a.
Inverse element: For each a in G, there exists an element b in G such that a * b = b * a = e, where e is an identity element.
Some texts omit the explicit requirement of closure, since the closure of the group follows from the definition of a binary operation.
Using the identity element property, it can be shown that a group has exactly one identity element. See the proof below.
The inverse of an element can also be shown to be unique, and the left- and right-inverses of an element are the same. Some definitions are thus slightly more narrow, substituting the third and fourth axioms with the concept of a "left (or right) identity element" and a "left (or right) inverse element."
A group (G, *) is often denoted simply G where there is no ambiguity as to what the operation is.
[edit] Basic concepts in group theory
[edit] Order of groups and elements
Main article: Order (group theory)
The order of a group G, usually denoted by G or occasionally by o(G), is the number of elements in the set G. If the order is not finite, then the group is an infinite group, denoted G = ∞.
The order of an element a in a group G is the least positive integer n such that an = e, where an represents , i.e. multiplication of a by itself n times. If no such n exists, then the order of a is said to be infinity.
[edit] Subgroups
Main article: Subgroup
A set H is a subgroup of a group G if it is a subset of G and a group using the operation defined on G. In other words, H is a subgroup of (G, *) if the restriction of * to H is a group operation on H.
A necessary and sufficient condition for a subset H of a group G to be a subgroup is that g−1h ∈ H for all g, h ∈ H. (See subgroup test.)
If G is a finite group, then so is H. Further, the order of H divides the order of G (Lagrange's Theorem).
The powers of any element a and their inverses (that is, a0 = e, a, a2, a3, a4, …, a−1, a−2, a−3, a−4, …) always form a subgroup of the larger group. It is said that a generates that subgroup.
[edit] Cyclic groups
Main article: Cyclic group
A cyclic group is a group whose elements may be generated by successive composition of the operation defining the group being applied to a single element of that group. This single element is called the generator or primitive element of the group.
A multiplicative cyclic group in which G is the group, and a is the generator:
An additive cyclic group, with generator a:
If successive composition of the operation defining the group is applied to a non-primitive element of the group, a cyclic subgroup is generated. The order of the cyclic subgroup divides the order of the group. Thus, if the order of a group is prime, all of its elements, except the identity, are primitive elements of the group.
It is important to note that a group contains all of the cyclic subgroups generated by each of the elements in the group. However, a group constructed from cyclic subgroups is itself not necessarily a cyclic group. For example, a Klein group is not a cyclic group even though it is constructed from two copies of the cyclic group of order 2.
[edit] Abelian groups
Main article: Abelian group
A group G is said to be abelian, or commutative, if the operation satisfies the commutative law. That is, for all a and b in G, a * b = b * a. If not, the group is called non-abelian or non-commutative. The name "abelian" comes from the Norwegian mathematician Niels Abel.
[edit] Notation for groups
Groups can use different notation depending on the context and the group operation.
Additive groups use + to denote addition, and the minus sign - to denote inverses. For example, a + (-a) = 0 in Z.
Multiplicative groups use *, , or the more general 'composition' symbol to denote multiplication, and the superscript -1 to denote inverses. For example, a*a-1 = 1. It is very common to drop the * and just write aa-1 instead.
Function groups use • to denote function composition, and the superscript -1 to denote inverses. For example, g • g-1 = e. It is very common to drop the • and just write gg-1 instead.
Omitting a symbol for an operation is generally acceptable, and leaves it to the reader to know the context and the group operation.
When defining groups, it is standard notation to use parentheses in defining the group and its operation. For example, (H, +) denotes that the set H is a group under addition. For groups like (Zn, +) and (Fn*, *), it is common to drop the parentheses and the operation, e.g. Zn and Fn*. It is also correct to refer to a group by its set identifier, e.g. H or , or to define the group in set-builder notation.
The identity element e is sometimes known as the "neutral element," and is sometimes denoted by some other symbol, depending on the group:
In multiplicative groups, the identity element can be denoted by 1.
In invertible matrix groups, the identity element is usually denoted by I.
In additive groups, the identity element may be denoted by 0.
In function groups, the identity element is usually denoted by f0.
If S is a subset of G and x an element of G, then, in multiplicative notation, xS is the set of all products {xs : s in S}; similarly the notation Sx = {sx : s in S}; and for two subsets S and T of G, we write ST for {st : s in S, t in T}. In additive notation, we write x + S, S + x, and S + T for the respective sets (see cosets).
[edit] Examples of groups
Main articles: Examples of groups and List of small groups
[edit] Trivial group
A trivial group is a group consisting of a single element. All such groups are isomorphic so one often speaks of the trivial group. The single element of the trivial group, variously labeled e, 1, or 0, is the identity element. The group operation is e + e = e.
[edit] An abelian group: the integers under addition
A familiar group is the group of integers under addition. Let Z be the set of integers, {..., −4, −3, −2, −1, 0, 1, 2, 3, 4, ...}, and let the symbol "+" indicate the operation of addition. Then (Z,+) is a group.
Proof:
Closure: If a and b are integers then a + b is an integer.
Associativity: If a, b, and c are integers, then (a + b) + c = a + (b + c).
Identity element: 0 is an integer and for any integer a, 0 + a = a + 0 = a.
Inverse elements: If a is an integer, then the integer −a satisfies the inverse rules: a + (−a) = (−a) + a = 0.
This group is also abelian because a + b = b + a.
If we extend this example further by considering the integers with both addition and multiplication, it forms a more complicated algebraic structure called a ring. (But, note that the integers with multiplications are not a group.)
[edit] An abelian group: the nonzero integers under multiplication modulo P a prime
Main article: Multiplicative group of integers modulo n
The nonzero integers under multiplication modulo p a prime form a group. The only non-trivial group property to prove is that each element has an inverse. Let a be a nonzero integer not equal to one. Any nonzero integer that p divides equals zero under multiplication mod p. a*a cannot equal a or p will divide a. If a*a equals one, we have found the inverse and we are done. If a*a does not equal one, then a*a*a cannot equal a or a*a or again p will divide a. Continuing in this manner we can construct a*a*a...a up to p-2 times. If we have reached this far, a*a*a...a p-1 times will equal one as there are no more numbers that a*a*a..*a p-1 times can equal.
[edit] Cyclic multiplicative groups
In the case of a cyclic multiplicative group G, all of the elements an of the group are generated by the set of all integer exponentiations of a primitive element of that group:
In this example if a is 2 and the operation is the mathematical multiplication operator, then
The modulo m may bind the group into a finite set with a non-fractional set of elements, since the inverse (and x − 2 , etc.) would be within the set.
[edit] Not a group: the integers under multiplication
On the other hand, if we consider the integers with the operation of multiplication, denoted by "·", then (Z,·) is not a group. It satisfies most of the axioms, but fails to have inverses:
Closure: If a and b are integers then a · b is an integer.
Associativity: If a, b, and c are integers, then (a · b) · c = a · (b · c).
Identity element: 1 is an integer and for any integer a, 1 · a = a · 1 = a.
However, it is not true that whenever a is an integer, there is an integer b such that ab = ba = 1. For example, a = 2 is an integer, but the only solution to the equation ab = 1 in this case is b = 1/2. We cannot choose b = 1/2 because 1/2 is not an integer. (Inverse element fails)
Since not every element of (Z,·) has an inverse, (Z,·) is not a group. It is, however, a commutative monoid, which is a similar structure to a group but does not require inverse elements.
[edit] An abelian group: the nonzero rational numbers under multiplication
Consider the set of rational numbers Q, the set of all fractions of integers a/b, where a and b are integers and b is nonzero, and the operation multiplication, denoted by "·". Since the rational number 0 does not have a multiplicative inverse, (Q,·), like (Z,·), is not a group.
However, if we instead use the set of all nonzero rational numbers Q \ {0}, then (Q \ {0},·) does form an abelian group.
Closure, Associativity, and Identity element axioms are easy to check and follow because of the properties of integers.
Inverse elements: The inverse of a/b is b/a and it satisfies the axiom.
We don't lose closure by removing zero, because the product of two nonzero rationals is never zero. Just as the integers form a ring, the rational numbers form the algebraic structure of a field, allowing the operations of addition, subtraction, multiplication and division.
[edit] A finite nonabelian group: permutations of a set
This example is taken from the larger article on the Dihedral group of order 6
For a more concrete example of a group, consider three colored blocks (red, green, and blue), initially placed in the order RGB. Let a be the action "swap the first block and the second block", and let b be the action "swap the second block and the third block".
Cycle diagram for S3. A loop specifies a series of powers of any element connected to the identity element (1). For example, the e-ba-ab loop reflects the fact that (ba)2=ab and (ba)3=e, as well as the fact that (ab)2=ba and (ab)3=e The other "loops" are roots of unity so that, for example a2=e.
In multiplicative form, we traditionally write xy for the combined action "first do y, then do x"; so that ab is the action RGB → RBG → BRG, i.e., "take the last block and move it to the front". If we write e for "leave the blocks as they are" (the identity action), then we can write the six permutations of the set of three blocks as the following actions:
e : RGB → RGB
a : RGB → GRB
b : RGB → RBG
ab : RGB → BRG
ba : RGB → GBR
aba : RGB → BGR
Note that the action aa has the effect RGB → GRB → RGB, leaving the blocks as they were; so we can write aa = e. Similarly,
bb = e,
(aba)(aba) = e, and
(ab)(ba) = (ba)(ab) = e;
so each of the above actions has an inverse.
By inspection, we can also determine associativity and closure; note for example that
(ab)a = a(ba) = aba, and
(ba)b = b(ab) = bab.
This group is called the symmetric group on 3 letters, or S3. It has order 6 (or 3 factorial), and is non-abelian (since, for example, ab ≠ ba). Since S3 is built up from the basic actions a and b, we say that the set {a,b} generates it.
More generally, we can define a symmetric group from all the permutations of N objects. This group is denoted by SN and has order N factorial.
One of the reasons that permutation groups are important is that every finite group can be expressed as a subgroup of a symmetric group SN; this result is Cayley's theorem.
[edit] Simple theorems
A group has exactly one identity element.
Proof: Suppose both e and f are identity elements. Then, by the definition of identity, fe = ef = e and also ef = fe = f. But then e = f.
Therefore the identity element is unique.
Every element has exactly one inverse.
Proof: Suppose both b and c are inverses of x. Then, by the definition of an inverse, xb = bx = e and xc = cx = e. But then:
xb = e = xc
xb = xc
bxb = bxc
(multiplying on the left by b)
eb = ec
(using bx = e)
b = c
(neutral element axiom)
Therefore the inverse is unique.
The first two properties actually follow from associative binary operations defined on a set. Given a binary operation on a set, there is at most one identity and at most one inverse for any element.
You can perform division in groups; that is, given elements a and b of the group G, there is exactly one solution x in G to the equation x * a = b and exactly one solution y in G to the equation a * y = b.
The expression "a1 * a2 * ··· * an" is unambiguous, because the result will be the same no matter where we place parentheses.
(Socks and shoes) The inverse of a product is the product of the inverses in the opposite order: (a * b)−1 = b−1 * a−1.
Proof: We will demonstrate that (ab)(b-1a-1) = (b-1a-1)(ab) = e, as required by the definition of an inverse.
(ab)(b − 1a − 1)
=
a(bb − 1)a − 1
(associativity)
=
aea − 1
(definition of inverse)
=
aa − 1
(definition of neutral element)
=
e
(definition of inverse)
And similarly for the other direction.
These and other basic facts that hold for all individual groups form the field of elementary group theory.
[edit] Constructing new groups from given ones
Some possible ways to construct new groups from a set of given groups:
Subgroups: The closure, under the group operation and inversion, of any nonempty subset of a group is also a group.
Quotient group: Given a group G and a normal subgroup N, the quotient group is the set of cosets of G/N together with the operation (gN)(hN)=ghN.
Direct product: If (G,*) and (H,•) are groups, then the set G×H together with the operation (g1,h1)(g2,h2) = (g1*g2,h1•h2) is a group. The direct product can also be defined with any number of terms, finite or infinite, by using the Cartesian product and defining the operation coordinate-wise.
Semidirect product: If N and H are groups and φ : H → Aut(N) is a group homomorphism, then the semidirect product of N and H with respect to φ is the group (N × H, *), with * defined as
(n1, h1) * (n2, h2) = (n1 φ(h1) (n2), h1 h2)
Direct external sum: The direct external sum of a family of groups is the subgroup of the product constituted by elements that have a finite number of non-identity coordinates. If the family is finite the direct sum and the product are equivalent.
