World Library  
Flag as Inappropriate
Email this Article

Generating set of a group

Article Id: WHEBN0000099945
Reproduction Date:

Title: Generating set of a group  
Author: World Heritage Encyclopedia
Language: English
Subject: Grushko theorem, Cayley graph, Ping-pong lemma, Commutator subgroup, Quasi-isometry
Collection: Group Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Generating set of a group

In abstract algebra, a generating set of a group is a subset such that every element of the group can be expressed as the 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 〈S〉, the subgroup generated by S, is the smallest subgroup of G containing every element of S, meaning 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.

If G = 〈S〉, then we say S generates G; 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|.

Contents

  • Finitely generated group 1
  • Free group 2
  • Frattini subgroup 3
  • Examples 4
  • See also 5
  • References 6
  • External links 7

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(pq) = 1, then {pq} 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 (simply take the images of the generators in the quotient), 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. Since 〈S〉 is clearly isomorphic to the free group in countably infinite number of generators, it 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

\{7^i \mod{9}\ |\ i \in \mathbb{N}\} = \{7,4,1\}.

while 2 is, since:

\{2^i \mod{9}\ |\ i \in \mathbb{N}\} = \{2,4,8,7,5,1\}.

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:

e = (1 2)(1 2)
(1 2) = (1 2)
(2 3) = (1 2)(1 2 3)
(1 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).

See also

References

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.