Ingroup theory, a branch of mathematics, theNielsen–Schreier theorem states that everysubgroup of afree group is itself free.^[1][2][3] It is named afterJakob Nielsen andOtto Schreier.

A free group may be defined from agroup presentation consisting of aset of generators with no relations. That is, every element is a product of some sequence of generators and their inverses, but these elements do not obey any equations except those trivially following fromgg⁻¹ = 1. The elements of a free group may be described as all possiblereduced words, thosestrings of generators and their inverses in which no generator is adjacent to its own inverse. Two reduced words may be multiplied byconcatenating them and then removing any generator-inverse pairs that result from the concatenation.

TheNielsen–Schreier theorem states that ifH is a subgroup of a free groupG, thenH is itselfisomorphic to a free group. That is, there exists a setS of elements which generateH, with no nontrivial relations among the elements ofS.

TheNielsen–Schreier formula, orSchreier index formula, quantifies the result in the case where the subgroup has finite index: ifG is a free group of rankn (free onn generators), andH is a subgroup of finiteindex [G :H] =e, thenH is free of rank${\displaystyle 1+e(n-1)}$.^[4]

LetG be the free group with two generators${\displaystyle a,b}$, and letH be the subgroup consisting of all reduced words of even length (products of an even number of letters${\displaystyle a,b,a^{-1},b^{-1}}$). ThenH is generated by its six elements${\displaystyle p=aa,q=ab,r=ba,s=bb,t=a{b}^{-1},u=a^{-1}b.}$ A factorization of any reduced word inH into these generators and their inverses may be constructed simply by taking consecutive pairs of letters in the reduced word. However, this is not a free presentation ofH because the last three generators can be written in terms of the first three as${\displaystyle s=r{p}^{-1}q,t=p{r}^{-1},u=p^{-1}q}$. Rather,H is generated as a free group by the three elements${\displaystyle p=aa,q=ab,r=ba,}$ which have no relations among them; or instead by several other triples of the six generators.^[5] Further,G is free onn = 2 generators,H has indexe = [G :H] = 2 inG, andH is free on 1 +e(n–1) = 3 generators. The Nielsen–Schreier theorem states that likeH, every subgroup of a free group can be generated as a free group, and if the index ofH is finite, its rank is given by the index formula.

A short proof of the Nielsen–Schreier theorem uses thealgebraic topology offundamental groups andcovering spaces.^[1] A free groupG on a set of generators is the fundamental group of abouquet of circles, atopological graphX with a single vertex and with a loop-edge for each generator.^[6] Any subgroupH of the fundamental group is itself the fundamental group of a connected covering spaceY →X. The spaceY is a (possibly infinite) topological graph, theSchreier coset graph having one vertex for eachcoset inG/H.^[7] In any connected topological graph, it is possible to shrink the edges of aspanning tree of the graph, producing a bouquet of circles that has thesame fundamental groupH. SinceH is the fundamental group of a bouquet of circles, it is itself free.^[6]

The rank ofH can be computed using two properties ofEuler characteristic that follow immediately from its definition. The first property is that the Euler characteristic of abouquet ofs circles is1 - s. The second property ismultiplicativity in covering spaces: IfY is a degree-d cover ofX, then

${\displaystyle \chi (Y)=d\cdot \chi (X)}$.

Now supposeH is a subgroup of the free groupG, with index[G:H] = e. The previous part of the proof shows thatH is a free group; letr denote the rank ofH. Applying the two properties of Euler characteristic for the covering graphY corresponding toH gives the following:

${\displaystyle \chi (Y)=1-r}$

and

${\displaystyle \chi (Y)=e\cdot \chi (X)=e(1-n).}$

Combining these equations, we obtain${\displaystyle r=1-e(1-n)=1+e(n-1).}$

This proof appears inMay'sConcise Course.^[8]An equivalent proof usinghomology and the firstBetti number ofY is due toReinhold Baer and Friedrich Levi (1936).The original proof by Schreier forms the Schreier graph in a different way as a quotient of theCayley graph ofG modulo the action ofH.^[9]

According toSchreier's subgroup lemma, a set of generators for a free presentation ofH may be constructed fromcycles 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.^[10][9]

Although several different proofs of the Nielsen–Schreier theorem are known, they all depend on theaxiom 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 ofZermelo–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.^[11][12]

The Nielsen–Schreier theorem is anon-abelian analogue of an older result ofRichard Dedekind, that every subgroup of afree abelian group is freeabelian.^[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 ofNielsen transformations on the subgroup's generating set that reduce their length (as reduced words in the free group from which they are drawn).^[1][13] Otto Schreier proved the Nielsen–Schreier theorem in its full generality in his 1926habilitationthesis,Die Untergruppen der freien Gruppe, also published in 1927 inAbh. math. Sem. Hamburg. Univ.^[14][15]

The topological proof based on fundamental groups of bouquets of circles is due toReinhold Baer and Friedrich Levi (1936). Another topological proof, based on theBass–Serre theory ofgroup actions ontrees, was published byJean-Pierre Serre (1970).^[16]

• Fundamental theorem of cyclic groups, a similar result forcyclic groups that in the infinite case may be seen as a special case of the Nielsen–Schreier theorem
• Kurosh subgroup theorem

• Baer, Reinhold;Levi, Friedrich (1936), "Freie Produkte und ihre Untergruppen",Compositio Mathematica,3:391–398.
• Fried, Michael D.;Jarden, Moshe (2008),Field arithmetic, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge, vol. 11 (3rd ed.),Springer-Verlag, p. 70,ISBN 978-3-540-77269-9,Zbl 1145.12001.
• 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,JSTOR 2274234,MR 0793126,S2CID 33535673.
• Johnson, D. L. (1980),Topics in the Theory of Group Presentations, London Mathematical Society lecture note series, vol. 42, Cambridge University Press,ISBN 978-0-521-23108-4.
• Johnson, D. L. (1997),Presentations of Groups, London Mathematical Society student texts, vol. 15 (2nd ed.), Cambridge University Press,ISBN 978-0-521-58542-2.
• Läuchli, Hans (1962), "Auswahlaxiom in der Algebra",Commentarii Mathematici Helvetici,37:1–18,doi:10.1007/bf02566957,hdl:20.500.11850/131689,MR 0143705,S2CID 186223589.
• 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.
• Rotman, Joseph J. (1995),An Introduction to the Theory of Groups, Graduate Texts in Mathematics, vol. 148 (4th ed.), Springer-Verlag,ISBN 978-0-387-94285-8.
• Serre, J.-P. (1970),Groupes Discretes, Extrait de I'Annuaire du College de France, Paris{{citation}}: CS1 maint: location missing publisher (link).
• Serre, J.-P. (1980),Trees, Springer-Verlag,ISBN 3-540-10103-9.
• Stillwell, John (1993),Classical Topology and Combinatorial Group Theory, Graduate Texts in Mathematics, vol. 72 (2nd ed.), Springer-Verlag.

• Properties of groups
• Axiom of choice
• Theorems in algebra
• Theorems in group theory

• Articles with short description
• Short description matches Wikidata
• CS1 Danish-language sources (da)
• CS1 maint: location missing publisher