Jump to content

Nielsen–Schreier theorem

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by MystBot (talk | contribs) at 20:31, 5 December 2011 (r2.7.1) (Robot: Adding fr:Théorème de Nielsen-Schreier). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In group theory, a branch of mathematics, the Nielsen–Schreier theorem is the statement that every subgroup of a free group is itself free.[1][2][3] It is named after Jakob Nielsen and Otto Schreier.

Statement of the theorem

A free group may be defined from a group presentation consisting of a set of generators and the empty set of relations (equations that the generators satisfy). That is, it is the unique group in which every element is a product of some sequence of generators and their inverses, and in which there are no equations between group elements that do not follow in a trivial way from the equations gg−1 describing the relation between a generator and its inverse. The elements of a free group may be described as all of the possible reduced words formed by sequences of generators and their inverse that have no adjacent pair of a generator and the inverse of the same generator.

The Nielsen–Schreier theorem states that if G is a subgroup of a free group, then G is itself isomorphic to a free group. That is, there exists a subset S of elements of G such that every element in S is a product of members of S and their inverses, and such that S satisfies no nontrivial relations.

Example

Let G be the free group with two generators, a and b, and let E be the subgroup consisting of all reduced words that are products of evenly many generators or their inverses. Then E is itself generated by the six elements p = aa, q = ab, r = ab−1, s = ba, t = ba−1, and u = bb. A factorization of any reduced word in E into these generators and their inverses may be constructed simply by taking consecutive pairs of symbols in the reduced word. However, this is not a free presentation of E because it satisfies the relations p = qr−1 = rq−1 and s = tu−1 = ut−1. Instead, E is generated as a free group by the three elements p = aa, q = ab, and s = ba. Any factorization of a word into a product of generators from the six-element generating set {p, q, r, s, t, u} can be transformed into a product of generators from this smaller set by replacing r with ps−1, replacing t with sp−1, and replacing u with sp−1q. There are no additional relations satisfied by these three generators, so E is the free group generated by p, q, and s.[4] The Nielsen–Scheier theorem states that this example is not a coincidence: like E, every subgroup of a free group can be generated as a free group, possibly with a larger set of generators.

Proof

It is possible to prove the Nielsen–Scheier theorem using topology.[1] A free group G on a set of generators is the fundamental group of a bouquet of circles, a topological graph with a single vertex and with an edge for each generator.[5] Any subgroup H of the fundamental group is itself a fundamental group of a covering space of the bouquet, a (possibly infinite) topological Schreier coset graph that has one vertex for each coset of the subgroup.[6] And in any topological graph, it is possible to shrink the edges of a spanning tree of the graph, producing a bouquet of circles that has the same fundamental group H. Since H is the fundamental group of a bouquet of circles, it is itself free.[5]

According to Schreier's subgroup lemma, a set of generators for a free presentation of H may be constructed from cycles in the covering graph formed by concatenating a spanning tree path from a base point (the coset of the identity) to one of the cosets, a single non-tree edge, and an inverse spanning tree path from the other endpoint of the edge back to the base point.[7]

Axiomatic foundations

Although several different proofs of the Nielsen–Schreier theorem are known, they all depend on the axiom of choice. In the proof based on fundamental groups of bouquets, for instance, the axiom of choice appears in the guise of the statement that every connected graph has a spanning tree. The use of this axiom is necessary, as there exist models of Zermelo–Fraenkel set theory in which the axiom of choice and the Nielsen–Schreier theorem are both false. The Nielsen–Schreier theorem in turn implies a weaker version of the axiom of choice, for finite sets.[8]

History

The Nielsen–Schreier theorem is a non-abelian analogue of an older result of Richard Dedekind, that every subgroup of a free abelian group is free abelian.[3]

Jakob Nielsen (1921) originally proved a restricted form of the theorem, stating that any finitely-generated subgroup of a free group is free. His proof involves performing a sequence of Nielsen transformations on the subgroup's generating set that reduce their length (as reduced words in the free group from which they are drawn).[1][9] Otto Schreier proved the Nielsen–Schreier theorem in its full generality in his 1926 habilitation thesis, Die Untergruppen der freien Gruppe, also published in 1927 in Abh. math. Sem. Hamburg. Univ.[10][11]

The topological proof based on fundamental groups of bouquets of circles is due to Reinhold Baer and Friedrich Levi (1936). Another topological proof, based on the Bass–Serre theory of group actions on trees, was published by Jean-Pierre Serre (1970).[12]

Notes

  1. ^ a b c Stillwell (1993), Section 2.2.4, The Nielsen–Schreier Theorem, pp. 103–104.
  2. ^ {{citation}}: Empty citation (help), Corollary 2.9, p. 95.
  3. ^ a b Johnson (1980), Section 2, The Nielsen–Schreier Theorem, pp. 9–23.
  4. ^ Johnson (1997), ex. 15, p. 12.
  5. ^ a b Stillwell (1993), Section 2.1.8, Freeness of the Generators, p. 97.
  6. ^ Stillwell (1993), Section 2.2.2, The Subgroup Property, pp. 100–101.
  7. ^ Stillwell (1993), Section 2.2.6, Schreier Transversals, pp. 105–106.
  8. ^ Läuchli (1962); Howard (1985).
  9. ^ {{citation}}: Empty citation (help), Section 3.2, A Reduction Process, pp. 121–140.
  10. ^ O'Connor, John J.; Robertson, Edmund F., "Nielsen–Schreier theorem", MacTutor History of Mathematics Archive, University of St Andrews {{citation}}: Unknown parameter |name= ignored (help)
  11. ^ Hansen, Vagn Lundsgaard (1986), Jakob Nielsen, Collected Mathematical Papers: 1913-1932, Birkhäuser, p. 117, ISBN 9780817631406.
  12. ^ Rotman (1995), The Nielsen–Schreier Theorem, pp. 383–387.

References

  • Baer, Reinhold; Levi, Friedrich (1936), "Freie Produkte und ihre Untergruppen", Compositio Math., 3: 391–398.
  • Howard, Paul E. (1985), "Subgroups of a free group and the axiom of choice", The Journal of Symbolic Logic, 50 (2): 458–467, doi:10.2307/2274234, MR 0793126.
  • Johnson, D. L. (1980), Topics in the Theory of Group Presentations, London Mathematical Society lecture note series, vol. 42, Cambridge University Press, ISBN 9780521231084.
  • Johnson, D. L. (1997), Presentations of Groups, London Mathematical Society student texts, vol. 15 (2nd ed.), Cambridge University Press, ISBN 9780521585422.
  • Läuchli, Hans (1962), "Auswahlaxiom in der Algebra", Commentarii Mathematici Helvetici, 37: 1–18, MR 0143705.
  • Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (1976), Combinatorial Group Theory (2nd revised ed.), Dover Publications.
  • Nielsen, Jakob (1921), "Om regning med ikke-kommutative faktorer og dens anvendelse i gruppeteorien", Math. Tidsskrift B, (in Danish), 1921: 78–94, JFM 48.0123.03{{citation}}: CS1 maint: extra punctuation (link).
  • Rotman, Joseph J. (1995), An Introduction to the Theory of Groups, Graduate Texts in Mathematics, vol. 148 (4th ed.), Springer-Verlag, ISBN 9780387942858.
  • Serre, J.-P. (1970), Groupes Discretes, Extrait de I'Annuaire du College de France, Paris{{citation}}: CS1 maint: location missing publisher (link).
  • Stillwell, John (1993), Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, vol. 72 (2nd ed.), Springer-Verlag.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Nielsen–Schreier_theorem&oldid=464269186"