Free group

In mathematics, the free group FS over a given set S consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms (e.g. st = suu−1t, but st−1 for s,t,uS). The members of S are called generators of FS, and the number of generators is the rank of the free group. An arbitrary group G is called free if it is isomorphic to FS for some subset S of G, that is, if there is a subset S of G such that every element of G can be written in exactly one way as a product of finitely many elements of S and their inverses (disregarding trivial variations such as st = suu−1t).

A related but different notion is a free abelian group; both notions are particular instances of a free object from universal algebra. As such, free groups are defined by their universal property.

Free groups first arose in the study of hyperbolic geometry, as examples of Fuchsian groups (discrete groups acting by isometries on the hyperbolic plane). In an 1882 paper, Walther von Dyck pointed out that these groups have the simplest possible presentations.[1] The algebraic study of free groups was initiated by Jakob Nielsen in 1924, who gave them their name and established many of their basic properties.[2][3][4] Max Dehn realized the connection with topology, and obtained the first proof of the full Nielsen–Schreier theorem.[5] Otto Schreier published an algebraic proof of this result in 1927,[6] and Kurt Reidemeister included a comprehensive treatment of free groups in his 1932 book on combinatorial topology.[7] Later on in the 1930s, Wilhelm Magnus discovered the connection between the lower central series of free groups and free Lie algebras.

On the other hand, any nontrivial finite group cannot be free, since the elements of a free generating set of a free group have infinite order.

In algebraic topology, the fundamental group of a bouquet of k circles (a set of k loops having only one point in common) is the free group on a set of k elements.

If an element of S lies immediately next to its inverse, the word may be simplified by omitting the c, c−1 pair:

The free group FS is defined to be the group of all reduced words in S, with concatenation of words (followed by reduction if necessary) as group operation. The identity is the empty word.

A word is called cyclically reduced if its first and last letter are not inverse to each other. Every word is conjugate to a cyclically reduced word, and a cyclically reduced conjugate of a cyclically reduced word is a cyclic permutation of the letters in the word. For instance b−1abcb is not cyclically reduced, but is conjugate to abc, which is cyclically reduced. The only cyclically reduced conjugates of abc are abc, bca, and cab.

The free group FS is the universal group generated by the set S. This can be formalized by the following universal property: given any function f from S to a group G, there exists a unique homomorphism φFS → G making the following diagram commute (where the unnamed mapping denotes the inclusion from S into FS):

That is, homomorphisms FS → G are in one-to-one correspondence with functions S → G. For a non-free group, the presence of relations would restrict the possible images of the generators under a homomorphism.

To see how this relates to the constructive definition, think of the mapping from S to FS as sending each symbol to a word consisting of that symbol. To construct φ for the given f, first note that φ sends the empty word to the identity of G and it has to agree with f on the elements of S. For the remaining words (consisting of more than one symbol), φ can be uniquely extended, since it is a homomorphism, i.e., φ(ab) = φ(a) φ(b).

The above property characterizes free groups up to isomorphism, and is sometimes used as an alternative definition. It is known as the universal property of free groups, and the generating set S is called a basis for FS. The basis for a free group is not uniquely determined.

Being characterized by a universal property is the standard feature of free objects in universal algebra. In the language of category theory, the construction of the free group (similar to most constructions of free objects) is a functor from the category of sets to the category of groups. This functor is left adjoint to the forgetful functor from groups to sets.

The free abelian group on a set S is defined via its universal property in the analogous way, with obvious modifications: Consider a pair (F, φ), where F is an abelian group and φ: SF is a function. F is said to be the free abelian group on S with respect to φ if for any abelian group G and any function ψ: SG, there exists a unique homomorphism f: FG such that

The free abelian group on S can be explicitly identified as the free group F(S) modulo the subgroup generated by its commutators, [F(S), F(S)], i.e. its abelianisation. In other words, the free abelian group on S is the set of words that are distinguished only up to the order of letters. The rank of a free group can therefore also be defined as the rank of its abelianisation as a free abelian group.

Around 1945, Alfred Tarski asked whether the free groups on two or more generators have the same first-order theory, and whether this theory is decidable. Sela (2006) answered the first question by showing that any two nonabelian free groups have the same first-order theory, and Kharlampovich & Myasnikov (2006) answered both questions, showing that this theory is decidable.

A similar unsolved (as of 2011) question in free probability theory asks whether the von Neumann group algebras of any two non-abelian finitely generated free groups are isomorphic.