Wikipedia / Generating set of a group
Wikipedia / Generating set of a 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.
, the , is the smallest subgroup 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.)
generates are called generators or group generators is the trivial group, since we consider the empty product to be the identity.
is the cyclic subgroup, a cyclic group. For finite groups has order.
A group may need an infinite number of generators. For example, the additive group of rational numbers 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.
is a topological group is called a set of topological generators is dense, i.e. the closure.
Finitely generated group
is called finitely generated. The structure of finitely generated abelian groups of length less than or equal to the order of the group.
. 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.
are integers with 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 be the free group for some natural number 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.
Examples
The multiplicative group of integers modulo 9, , is the group of all integers relatively prime to9 under multiplication . The element 7 is not a generator of
The symmetric group Sn of degree n is not generated by any one element (is not cyclic) when n>2. However, in these cases Sn can always be generated by two permutations: in cycle notation, the transposition (1 2) and the cycle form a generating set. For example, the 6 elements of S3 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 have finite generating sets. The additive group of integers has1 as a generating set. The element2 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 numbers is, as a consequence of Bézout's identity).
The dihedral group 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 groupth roots of unity are all generated by a single element (in fact, these groups are isomorphic to one another).
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.
Free group
is the group freely generated 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, the Frattini subgroup.
Semigroups and monoids
.
For example, {1} is a monoid generator of the set of natural numbers. However, the integer 0 can not be expressed as a (non-empty) sum of 1s, thus {1} is not a semigroup generator of the natural numbers.
Similarly, while {1} is a group generator of the set of integers, {1} 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 for related meanings in other structures