In group theory

Group theory

In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...

, a branch of mathematics, the Nielsen–Schreier theorem is the statement that every subgroup

Subgroup

In group theory, given a 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, H is a subgroup of G if the restriction of * to H x H is a group operation on H...

 of a free group

Free group

In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...

 is itself free. It is named after Jakob Nielsen

Jakob Nielsen (mathematician)

Jakob Nielsen was a Danish mathematician known for his work on automorphisms of surfaces. He was born in the village Mjels on the island of Als in North Schleswig, in modern day Denmark. His mother died when he was 3, and in 1900 he went to live with his aunt and was enrolled in the Realgymnasium...

 and Otto Schreier

Otto Schreier

Otto Schreier was an Austrian mathematician who made major contributions in combinatorial group theory and in the topology of Lie groups. He studied mathematics at the University of Vienna and obtained his doctorate in 1923, under the supervision of Philipp Furtwängler...

.

Statement of the theorem

A free group may be defined from a group presentation

Presentation of a group

In mathematics, one method of defining a group is by a presentation. One specifies a set S of generators so that every element of the group can be written as a product of powers of some of these generators, and a set R of relations among those generators...

 consisting of a set of generators

Generating set of a group

In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...

 and the empty set

Empty set

In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

 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 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 is a subgroup of a free group, then is itself isomorphic

Group isomorphism

In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. If there exists an isomorphism between two groups, then the groups are called isomorphic...

 to a free group. That is, there exists a subset of elements of such that every element in is a product of members of and their inverses, and such that satisfies no nontrivial relations.

Example

Let be the free group with two generators, and , and let be the subgroup consisting of all reduced words that are products of evenly many generators or their inverses. Then is itself generated by the six elements , , , , , and . A factorization of any reduced word in 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 because it satisfies the relations and . Instead, is generated as a free group by the three elements , , and . Any factorization of a word into a product of generators from the six-element generating set } can be transformed into a product of generators from this smaller set by replacing with , replacing with , and replacing with . There are no additional relations satisfied by these three generators, so is the free group generated by , , and . The Nielsen–Scheier theorem states that this example is not a coincidence: like , 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

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

. A free group on a set of generators is the fundamental group

Fundamental group

In mathematics, more specifically algebraic topology, the fundamental group is a group associated to any given pointed topological space that provides a way of determining when two paths, starting and ending at a fixed base point, can be continuously deformed into each other...

 of a bouquet of circles, a topological graph with a single vertex and with an edge for each generator. Any subgroup 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

Coset

In mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, thenA coset is a left or right coset of some subgroup in G...

 of the subgroup. And in any topological graph, it is possible to shrink the edges of a spanning tree

Spanning tree

Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...

 of the graph, producing a bouquet of circles that has the same fundamental group . Since is the fundamental group of a bouquet of circles, it is itself free.

According to Schreier's subgroup lemma

Schreier's subgroup lemma

Schreier's subgroup lemma is a theorem in group theory used in the Schreier–Sims algorithm and also for finding a presentation of a subgroup.-Definition:Suppose H is a subgroup of G, which is finitely generated with generating set S, that is, G = ....

, a set of generators for a free presentation of may be constructed from cycles

Cycle (graph theory)

In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...

 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.

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

Zermelo–Fraenkel set theory

In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...

 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.

History

The Nielsen–Schreier theorem is a non-abelian

Nonabelian group

In mathematics, a non-abelian group, also sometimes called a non-commutative group, is a group in which there are at least two elements a and b of G such that a * b ≠ b * a...

 analogue of an older result of Richard Dedekind

Richard Dedekind

Julius Wilhelm Richard Dedekind was a German mathematician who did important work in abstract algebra , algebraic number theory and the foundations of the real numbers.-Life:...

, that every subgroup of a free abelian group

Free abelian group

In abstract algebra, a free abelian group is an abelian group that has a "basis" in the sense that every element of the group can be written in one and only one way as a finite linear combination of elements of the basis, with integer coefficients. Hence, free abelian groups over a basis B are...

 is free abelian

Abelian group

In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...

.

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 transformation

Nielsen transformation

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, Nielsen transformations, named after Jakob Nielsen, are certain automorphisms of a free group which are a non-commutative analogue of row reduction and one of the main tools used in studying free groups,...

s on the subgroup's generating set that reduce their length (as reduced words in the free group from which they are drawn). Otto Schreier proved the Nielsen–Schreier theorem in its full generality in his 1926 habilitation

Habilitation

Habilitation is the highest academic qualification a scholar can achieve by his or her own pursuit in several European and Asian countries. Earned after obtaining a research doctorate, such as a PhD, habilitation requires the candidate to write a professorial thesis based on independent...

 thesis

Thesis

A dissertation or thesis is a document submitted in support of candidature for an academic degree or professional qualification presenting the author's research and findings...

, Die Untergruppen der freien Gruppe, also published in 1927 in Abh. math. Sem. Hamburg. Univ.

The topological proof based on fundamental groups of bouquets of circles is due to . Another topological proof, based on the Bass–Serre theory

Bass–Serre theory

Bass–Serre theory is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees...

 of group action

Group action

In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...

s on trees

Real tree

A real tree, or an \mathbb R-tree, is a metric space such thatfor any x, y in M there is a unique arc from x to y and this arc is a geodesic segment. Here by an arc from x to y we mean the image in M of a topological embedding f from an interval [a,b] to M such that f=x and f=y...

, was published by .