
In
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathematics), fields, module (mathe ...
, a generating set of a group is a
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
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.
In other words, if ''S'' is a subset of a group ''G'', then , the ''subgroup generated by S'', is the smallest
subgroup
In group theory, a branch of mathematics, given a group (mathematics), 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, ...
of ''G'' containing every element of ''S'', which is equal to the intersection over all subgroups containing the elements of ''S''; equivalently, 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'' = , then we say that ''S'' ''generates'' ''G'', and the elements in ''S'' are called ''generators'' or ''group generators''. If ''S'' is the empty set, then is the
trivial group
In mathematics, a trivial group or zero group is a Group (mathematics), 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 is the identity element ...
, since we consider the empty product to be the identity.
When there is only a single element ''x'' in ''S'', is usually written as . In this case, is the ''cyclic subgroup'' of the powers of ''x'', a
cyclic group
In group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathemati ...
, and we say this group is generated by ''x''. Equivalent to saying an element ''x'' generates a group is saying that equals the entire group ''G''. For
finite group
Finite is the opposite of Infinity, infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected ...
s, it is also equivalent to saying that ''x'' has
order , ''G'', .
A group may need an infinite number of generators. For example the additive group of
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
s Q is not finitely generated. It is generated by the inverses of all the integers, but any finite number of these generators can be removed from the generating set without it ceasing to be a generating set. In a case like this, all the elements in a generating set are nevertheless "non-generating elements", as are in fact all the elements of the whole group − see
#Frattini subgroup below.
If ''G'' is a
topological group
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
then a subset ''S'' of ''G'' is called a set of ''topological generators'' if is dense in ''G'', i.e. the
closure of is the whole group ''G''.
Finitely generated group
If ''S'' is finite, then a group 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 . The
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of ...
s 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 , then also generates the group of integers under addition by
Bézout's identity.
While it is true that every
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division (mathematics), division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to a ...
of a finitely generated group is finitely generated (the images of the generators in the quotient give a finite generating set), a
subgroup
In group theory, a branch of mathematics, given a group (mathematics), 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, ...
of a finitely generated group need not be finitely generated. For example, let ''G'' be the
free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all Word (group theory), words that can be built from members of ''S'', considering two words to be different unless their equality follows from the Group (mathematics) ...
in two generators, ''x'' and ''y'' (which is clearly finitely generated, since ''G'' = ), and let ''S'' be the subset consisting of all elements of ''G'' of the form ''y''
''n''''xy''
−''n'' for ''n'' a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
. is
isomorphic
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
to the free group in countably infinitely many generators, and so cannot be finitely generated. However, every subgroup of a finitely generated
abelian group
In mathematics, an abelian group, also called a commutative group, is a group (mathematics), group in which the result of applying the group Operation (mathematics), operation to two group elements does not depend on the order in which they are w ...
is in itself finitely generated. In fact, more can be said: the class of all finitely generated groups is closed under
extensions
Extension, extend or extended may refer to:
Mathematics
Logic or set theory
* Axiom of extensionality
* Extensible cardinal
* Extension (model theory)
* Extension (predicate logic), the set of tuples of values that satisfy the predicate
* Exte ...
. To see this, take a generating set for the (finitely generated)
normal subgroup
In abstract algebra, a normal subgroup (also known as an invariant subgroup or self-conjugate subgroup) is a subgroup that is invariant under inner automorphism, conjugation by members of the Group (mathematics), group of which it is a part. In o ...
and quotient. Then the generators for the normal subgroup, together with preimages of the generators for the quotient, generate the group.
Examples
* The
multiplicative group of integers modulo 9, , is the group of all integers
relatively prime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to 9 under multiplication . Note that 7 is not a generator of , since
while 2 is, since
* On the other hand, ''S''
n, the
symmetric group
In abstract algebra, the symmetric group defined over any set (mathematics), set is the group (mathematics), group whose Element (mathematics), elements are all the bijections from the set to itself, and whose group operation is the function c ...
of degree ''n'', is not generated by any one element (is not
cyclic) when ''n'' > 2. However, in these cases ''S''
n can always be generated by two permutations which are written in
cycle notation as (1 2) and . For example, the 6 elements of ''S''
3 can be generated from the two generators, (1 2) and (1 2 3), as shown by the right hand side of the following equations (composition is left-to-right):
:''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 is a generating set, since (in fact, any pair of
coprime
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
numbers is, as a consequence of
Bézout's identity).
* The
dihedral group
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
of an
n-gon (which has
order ) is generated by the set , where represents rotation by and is any reflection across a line of symmetry.
* The
cyclic group
In group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathemati ...
of order ,
, and the
th roots of unity
In mathematics, a root of unity, occasionally called a Abraham de Moivre, de Moivre number, is any complex number that yields 1 when exponentiation, raised to some positive integer power . Roots of unity are used in many branches of mathematic ...
are all generated by a single element (in fact, these groups are
isomorphic
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
to one another).
* A
presentation of a group
In mathematics, a presentation is one method of specifying a group (mathematics), group. A presentation of a group ''G'' comprises a set ''S'' of generating set of a group, generators—so that every element of the group can be written as a produ ...
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.
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
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
to a
quotient
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division (mathematics), division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to a ...
of this group, a feature which is utilized in the expression of a group's
presentation
A presentation conveys information from a speaker to an audience. Presentations are typically demonstrations, introduction, lecture, or speech meant to inform, persuade, inspire, motivate, build goodwill, or present a new idea/product. Presen ...
.
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.
Semigroups and monoids
If ''G'' is a
semigroup
In mathematics, a semigroup is an algebraic structure
In mathematics, an algebraic structure consists of a nonempty Set (mathematics), set ''A'' (called the underlying set, carrier set or domain), a collection of operation (mathematics), opera ...
or a
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ar ...
, 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 smallest 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 monoids. 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 is a monoid generator of the set of non-negative
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s
. The set is also a semigroup generator of the positive natural numbers
. However, the integer 0 can not be expressed as a (non-empty) sum of 1s, thus is not a semigroup generator of the non-negative natural numbers.
Similarly, while is a group generator of the set of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of ...
s
, is not a monoid generator of the set of integers. Indeed, the integer −1 cannot be expressed as a finite sum of 1s.
See also
*
Generating set
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
for related meanings in other structures
*
Presentation of a group
In mathematics, a presentation is one method of specifying a group (mathematics), group. A presentation of a group ''G'' comprises a set ''S'' of generating set of a group, generators—so that every element of the group can be written as a produ ...
*
Primitive element (finite field)
In field theory (mathematics), field theory, a primitive element of a finite field is a generating set of a group, generator of the group of units, multiplicative group of the field. In other words, is called a primitive element if it is a primi ...
*
Cayley graph
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
Notes
References
*
*
External links
*{{mathworld , urlname=GroupGenerators , title=Group generators
Group theory