Generating set of a group

Last updated

The 5th roots of unity in the complex plane form a group under multiplication. Each non-identity element generates the group. One5Root.svg
The 5th roots of unity in the complex plane form a group under multiplication. Each non-identity element generates the group.

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination (under the group operation) of finitely many elements of the subset and their inverses.

Contents

In other words, if S is a subset of a group G, then S, the subgroup generated by S, is the smallest subgroup of G containing every element of S, which is equal to the intersection over all subgroups containing the elements of S; equivalently, S is the subgroup of all elements of G that can be expressed as the finite product of elements in S and their inverses. (Note that inverses are only needed if the group is infinite; in a finite group, the inverse of an element can be expressed as a power of that element.)

If G = S, then we say that SgeneratesG, and the elements in S are called generators or group generators. If S is the empty set, then S is the trivial group {e}, since we consider the empty product to be the identity.

When there is only a single element x in S, S is usually written as x. In this case, x is the cyclic subgroup of the powers of x, a cyclic group, and we say this group is generated by x. Equivalent to saying an element x generates a group is saying that x equals the entire group G. For finite groups, it is also equivalent to saying that x has order |G|.

If G is a topological group then a subset S of G is called a set of topological generators if S is dense in G, i.e. the closure of S is the whole group G.

Finitely generated group

If S is finite, then a group G = S is called finitely generated. The structure of finitely generated abelian groups in particular is easily described. Many theorems that are true for finitely generated groups fail for groups in general. It has been proven that if a finite group is generated by a subset S, then each group element may be expressed as a word from the alphabet S of length less than or equal to the order of the group.

Every finite group is finitely generated since G = G. The integers under addition are an example of an infinite group which is finitely generated by both 1 and −1, but the group of rationals under addition cannot be finitely generated. No uncountable group can be finitely generated. For example, the group of real numbers under addition, (R, +).

Different subsets of the same group can be generating subsets. For example, if p and q are integers with gcd(p, q) = 1, then {p, q} also generates the group of integers under addition by Bézout's identity.

While it is true that every quotient of a finitely generated group is finitely generated (the images of the generators in the quotient give a finite generating set), a subgroup of a finitely generated group need not be finitely generated. For example, let G be the free group in two generators, x and y (which is clearly finitely generated, since G = {x,y}), and let S be the subset consisting of all elements of G of the form ynxyn for n a natural number. S is isomorphic to the free group in countably infinitely many generators, and so cannot be finitely generated. However, every subgroup of a finitely generated abelian group is in itself finitely generated. In fact, more can be said: the class of all finitely generated groups is closed under extensions. To see this, take a generating set for the (finitely generated) normal subgroup and quotient. Then the generators for the normal subgroup, together with preimages of the generators for the quotient, generate the group.

Free group

The most general group generated by a set S is the group freely generated by S. Every group generated by S is isomorphic to a quotient of this group, a feature which is utilized in the expression of a group's presentation.

Frattini subgroup

An interesting companion topic is that of non-generators. An element x of the group G is a non-generator if every set S containing x that generates G, still generates G when x is removed from S. In the integers with addition, the only non-generator is 0. The set of all non-generators forms a subgroup of G, the Frattini subgroup.

Examples

The group of units U(Z9) is the group of all integers relatively prime to 9 under multiplication mod 9(U9 = {1, 2, 4, 5, 7, 8}). All arithmetic here is done modulo 9. Seven is not a generator of U(Z9), since

while 2 is, since:

On the other hand, for n > 2 the symmetric group of degree n is not cyclic, so it is not generated by any one element. However, it is generated by the two permutations (1 2) and (1 2 3 ... n). For example, for S3 we have (see permutation for an explanation of notation):

e = (1 2)(1 2)
(1 2) = (1 2)
(1 3) = (1 2)(1 2 3)
(2 3) = (1 2 3)(1 2)
(1 2 3) = (1 2 3)
(1 3 2) = (1 2)(1 2 3)(1 2)

Infinite groups can also have finite generating sets. The additive group of integers has 1 as a generating set. The element 2 is not a generating set, as the odd numbers will be missing. The two-element subset {3, 5} is a generating set, since (5) + 3 + 3 = 1 (in fact, any pair of coprime numbers is, as a consequence of Bézout's identity).

The dihedral group of order n is generated by the set {r, s}, where r represents rotation by π/n and s is any reflection about a line of symmetry. [1]

The cyclic group of order n, , and the nth roots of unity are all generated by a single element (in fact, these groups are isomorphic to one another). [2]

A presentation of a group is defined as a set of generators and a collection of relations between them, so any of the examples listed on that page contain examples of generating sets. [3]

Semigroups and monoids

If G is a semigroup or a monoid, one can still use the notion of a generating set S of G. S is a semigroup/monoid generating set of G if G is the least semigroup/monoid containing S.

The definitions of generating set of a group using finite sums, given above, must be slightly modified when one deals with semigroups or monoid. Indeed, this definition should not use the notion of inverse operation anymore. The set S is said to be a semigroup generating set of G if each element of G is a finite sum of elements of S. Similarly, a set S is said to be a monoid generating set of G if each non-zero element of G is a finite sum of elements of S.

For example {1} is a monoid generator of the set of non-negative natural numbers . The set {1} is also a semigroup generator of the positive natural numbers . However, the integer 0 can not be expressed as a (non-empty) sum of 1's, thus {1} is not a semigroup generator of the non-negative natural numbers.

Similarly, while {1} is a group generator of the set of relative integers , {1} is not a monoid generator of the set of relative integers. Indeed, the integer -1 can not be expressed as a finite sum of 1's.

See also

Notes

  1. Dummit, David S.; Foote, Richard M. (2004). Abstract algebra (3rd ed.). Wiley. p. 25. ISBN   9780471452348. OCLC   248917264.
  2. Dummit & Foote 2004 , p. 54
  3. Dummit & Foote 2004 , p. 26

Related Research Articles

Abelian group Commutative group (mathematics)

In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after early 19th century mathematician Niels Henrik Abel.

Quotient group

A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure. For example, the cyclic group of addition modulo n can be obtained from the group of integers under addition by identifying elements that differ by a multiple of n and defining a group structure that operates on each such class as a single entity. It is part of the mathematical field known as group theory.

Integral domain Commutative ring with no zero divisors other than zero

In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural setting for studying divisibility. In an integral domain, every nonzero element a has the cancellation property, that is, if a ≠ 0, an equality ab = ac implies b = c.

Group (mathematics) Algebraic structure with one binary operation

In mathematics, a group is a set equipped with an operation that combines any two elements to form a third element while being associative as well as having an identity element and inverse elements. These three conditions, called group axioms, hold for number systems and many other mathematical structures. For example, the integers together with the addition operation form a group. The formulation of the axioms is, however, detached from the concrete nature of the group and its operation. This allows one to handle entities of very different mathematical origins in a flexible way, while retaining essential structural aspects of many objects in abstract algebra and beyond. The ubiquity of groups in numerous areas—both within and outside mathematics—makes them a central organizing principle of contemporary mathematics.

Monoid Algebraic structure with an associative operation and an identity element

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element.

Semigroup

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

Subgroup Subset of a group that forms a group itself

In group theory, a branch of mathematics, given a group G under a binary operation ∗, a subset H of G is called a subgroup of G if H also forms a group under the operation ∗. More precisely, H is a subgroup of G if the restriction of ∗ to H × H is a group operation on H. This is usually denoted HG, read as "H is a subgroup of G".

In algebra, the kernel of a homomorphism is generally the inverse image of 0. An important special case is the kernel of a linear map. The kernel of a matrix, also called the null space, is the kernel of the linear map defined by the matrix.

In mathematics, a presentation is one method of specifying a group. A presentation of a group G comprises a set S of generators—so that every element of the group can be written as a product of powers of some of these generators—and a set R of relations among those generators. We then say G has presentation

In mathematics, in particular abstract algebra, a graded ring is a ring such that the underlying additive group is a direct sum of abelian groups such that . The index set is usually the set of nonnegative integers or the set of integers, but can be any monoid. The direct sum decomposition is usually referred to as gradation or grading.

In mathematics, a free abelian group or free Z-module is an abelian group with a basis, or, equivalently, a free module over the integers. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subset such that every element of the group can be uniquely expressed as a linear combination of basis elements with integer coefficients. For instance, the integers with addition form a free abelian group with basis {1}. Free abelian groups have properties which make them similar to vector spaces. They have applications in algebraic topology, where they are used to define chain groups, and in algebraic geometry, where they are used to define divisors. Integer lattices also form examples of free abelian groups, and lattice theory studies free abelian subgroups of real vector spaces.

Glossary of group theory

A group is a set together with an associative operation which admits an identity element and such that every element has an inverse.

Ring theory is the branch of mathematics in which rings are studied: that is, structures supporting both an addition and a multiplication operation. This is a glossary of some terms of the subject.

In the branch of abstract algebra known as ring theory, a unit of a ring is any element that has a multiplicative inverse in : an element such that

Order (group theory)

In group theory, a branch of mathematics, the order of a group is its cardinality, that is, the number of elements in its set. If the group is seen multiplicatively, the order of an elementa of a group, sometimes also called the period length or period of a, is the smallest positive integer m such that am = e, where e denotes the identity element of the group, and am denotes the product of m copies of a. If no such m exists, a is said to have infinite order.

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A. The free semigroup on A is the subsemigroup of A containing all elements except the empty string. It is usually denoted A+.

Finitely generated group

In algebra, a finitely generated group is a group G that has some finite generating set S so that every element of G can be written as the combination of finitely many elements of the finite set S and of inverses of such elements.

In mathematics, the Grothendieck group construction constructs an abelian group from a commutative monoid M in the most universal way, in the sense that any abelian group containing a homomorphic image of M will also contain a homomorphic image of the Grothendieck group of M. The Grothendieck group construction takes its name from a specific case in category theory, introduced by Alexander Grothendieck in his proof of the Grothendieck–Riemann–Roch theorem, which resulted in the development of K-theory. This specific case is the monoid of isomorphism classes of objects of an abelian category, with the direct sum as its operation.

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some morphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra.

In computer science, more precisely in automata theory, a rational set of a monoid is an element of the minimal class of subsets of this monoid that contains all finite subsets and is closed under union, product and Kleene star. Rational sets are useful in automata theory, formal languages and algebra.

References