generating set of a group
   HOME

TheInfoList



OR:

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 , \mathbb/n\mathbb, 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 \mathbb N_0. The set is also a semigroup generator of the positive natural numbers \mathbb N_. 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 \mathbb Z, 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