Group (mathematics)

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

Error creating thumbnail: convert: Non-conforming drawing primitive definition `ComicSansMS-Bold'''.

This picture illustrates how the hours on a clock form a group under modular addition.

In abstract algebra, a group is a set with a binary operation that satisfies certain axioms, detailed below. For example, the set of integers with addition is a group. The branch of mathematics which studies groups is called group theory.

Many of the structures investigated in mathematics turn out to be groups. These include familiar number systems, such as the integers, the rational numbers, the real numbers, and the complex numbers under addition, as well as the non-zero rationals, reals, and complex numbers, under multiplication. Other important examples are the group of non-singular matrices under multiplication and the group of invertible functions under composition. Group theory allows for the properties of such structures to be investigated in a general setting.

Group theory has extensive applications in mathematics, science, and engineering. Many algebraic structures such as fields and vector spaces may be defined concisely in terms of groups, and group theory provides an important tool for studying symmetry, since the symmetries of any object form a group. Groups are thus essential abstractions in branches of physics involving symmetry principles, such as relativity, quantum mechanics, and particle physics. Furthermore, their ability to represent geometric transformations finds applications in chemistry, computer graphics, and other fields.

History

Main article: Group theory#History

Explanation for Non-Mathematicians

In mathematics, groups are used in order to abstract away from calculating with concrete numbers (that is, in order to work with symbols instead of numbers). Correspondingly, a group consists of a set of abstract objects or symbols and of an "instruction for calculations" (an operation) that indicates how these objects are to be manipulated.

More precisely:

One speaks of a group whenever the following requirements are fulfilled of a set together with an operation that always combines two elements of this set, for example, a x b:

The combination of two elements of the set yields an element of the same set (Closure)
The bracketing is unimportant (Associativity): a × (b × c) = (a × b) × c
There is an element that does not cause anything to happen (Identity Element): a × 1 = 1 × a = a
Each element a has a "mirror image" (Inverse element) 1/a that has the property to yield the identity element when combined with a:

a × 1/a = 1/a × a = 1

Special case: If, in addition, one is also allowed to change the operands, that is if a × b = b × a holds (Commutativity), then we speak of an abelian (or commutative) group.

Examples of groups (all of these are also Abelian groups):

the integers $\Z$ with the addition operation "+" as binary operation and zero as identity element
the rational numbers $\Bbb Q$ without zero with multiplication "x" as binary operation and the number one as identity element. Zero has to be excluded because it does not have an inverse element. ("1/0" is undefined.)

The definition of groups is very general. This allows one to regard as groups not only sets of numbers with corresponding operations but also other abstract objects and symbols that fulfill the required properties, for example, polygons with their rotations and reflections. (See also: dihedral group)

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 second and third 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 in what the operation is.

Basic concepts in group theory

Order of groups and elements

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 aⁿ = e, where aⁿ is multiplication of a by itself n times (or other suitable composition depending on the group operator). If no such n exists, then the order of a is said to be infinity.

Subgroups

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.

If G is a finite group, then so is H. Further, the order of H divides the order of G (Lagrange's Theorem).

Abelian groups

A group G is said to be an abelian (or commutative) group if the operation is commutative, that is, for all a, b in G, a * b = b * a. A non-abelian group is a group that is not abelian. The term "abelian" is named after the mathematician Niels Abel.

Cyclic groups

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:

$G = \{ a^n \mid n \in \Z \}$

An additive cyclic group, with generator a:

$G' = \{ n \cdot a \mid n \in \Z \}$

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.

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 *, $\cdot$ , or the more general 'composition' symbol $\circ$ 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 (Z_n, +) and (F_n*, *), it is common to drop the parentheses and the operation, e.g. Z_{n</sup> and F_n*. 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 f₀.

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).

Examples of groups

Main article: Examples of groups

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, which forms a more complicated algebraic structure called a ring. (But, note that the integers with multiplications are not a group)

An abelian group: the nonzero integers under multiplication modulo P a prime

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.

Cyclic multiplicative groups

In the case of a cyclic multiplicative group G, all of the elements aⁿ of the group are generated by the set of all integer exponentiations of a primitive element of that group:

$G = \{ a^n \mid n \in \Z \pmod{m \in \Z} \}$

In this example if a is 2 and the operation is the mathematical multiplication operator, then G = ${..,2 - 2,2 - 1,2 0,2 1,2 2,2 3,..}$ = ${..,0.25,0.5,1,2,4,8,..}$ . 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.

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.

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.

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".

Image:Group diagram d6.svg

Cycle diagram for S₃. 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)²=ab and (ba)³=e, as well as the fact that (ab)²=ba and (ab)³=e The other "loops" are roots of unity so that, for example a²=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 S₃. It has order 6 (or 3 factorial), and is non-abelian (since, for example, ab ≠ ba). Since S₃ 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 S_N 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 S_N; this result is Cayley's theorem.

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:

$x b = e = x c$
$x b = x c$
$b x b = b x c$	(multiplying on the left by b)
$e b = e c$	(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 "a₁ * a₂ * ··· * a_n" 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)⁻¹ = b⁻¹ * a⁻¹.

Proof: We will demonstrate that (ab)(b^-1a^-1) = (b^-1a^-1)(ab) = e, as required by the definition of an inverse.

$(a b)(b - 1 a - 1)$	=	$a (b b - 1) a - 1$	(associativity)
	=	$a e a - 1$	(definition of inverse)
	=	$a a - 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.

Constructing new groups from given ones

Some possible ways to construct new groups from a set of given groups:

Subgroups: A subgroup H of a group G is 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 (g₁,h₁)(g₂,h₂) = (g₁*g₂,h₁•h₂) 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
(n₁, h₁) * (n₂, h₂) = (n₁ φ(h₁) (n₂), h₁ h₂)
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.

Proving that a set is a group

There are two main methods in proving that a set is a group:

Prove that the set is a subgroup of a group;
Prove that the set is a group using the definition.

The first method is generally referred to as the "subgroup test" and requires that you prove the following if trying to prove that H is a subgroup:

The set H is a non-empty subset of G (i.e. has the identity element inside)
H is closed under the same operation as G. (ab is in H and a^-1 is in H for all a,b in H)

The second method requires that you prove all the axioms and assumptions in the definition for a set G:

G is non-empty;
G is closed under the binary operation;
G is associative;
e is in G (usually follows from non-emptiness);
G consists of units.

For finite groups, one only needs to prove that a subset is non-empty and is closed under the ambient group's operation.

Generalizations

In abstract algebra, we get some related structures which are similar to groups by relaxing some of the axioms given at the top of the article.

If we eliminate the requirement that every element have an inverse, then we get a monoid.
If we additionally do not require an identity either, then we get a semigroup.
Alternatively, if we relax the requirement that the operation be associative while still requiring the possibility of division, then we get a loop.
If we additionally do not require an identity, then we get a quasigroup.
If we don't require any axioms of the binary operation at all, then we get a magma.

Groupoids, which are similar to groups except that the composition a * b need not be defined for all a and b, arise in the study of more involved kinds of symmetries, often in topological and analytical structures. They are special sorts of categories.

Supergroups and Hopf algebras are other generalizations.

Lie groups, algebraic groups and topological groups are examples of group objects: group-like structures sitting in a category other than the ordinary category of sets.

Abelian groups form the prototype for the concept of an abelian category, which has applications to vector spaces and beyond.

Formal group laws are certain formal power series which have properties much like a group operation.

References

External links

Group at MathWorld.
Group at PlanetMath.zh-classical:群 (代數)

nov:Grupe oc:Grop (matematicas)

Retrieved from "http://cryptodox.com/Group_%28mathematics%29"

Categories: Abstract algebra | Group theory | Symmetry | Binary operations

Navigation