# 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 (disregarding trivial variations such as *st ^{-1}* =

*su*).

^{-1}ut^{-1}Note that the notion of free group is different from the notion free abelian group.

## Contents

## Examples

The group (**Z**,+) of integers is free; we can take *S* = {1}. A free group on a two-element subset *S* occurs in the proof of the Banach-Tarski paradox and is described there.

## Construction

If *S* is any set, there always exists a free group on *S*. This free group on *S* is essentially unique in the following sense: if *F*_{1} and *F*_{2} are two free groups on the set *S*, then *F*_{1} and *F*_{2} are isomorphic, and furthermore there exists precisely one group isomorphism *f* : *F*_{1} `->` *F*_{2} such that *f*(*s*) = *s* for all *s* in *S*.

This free group on *S* is denoted by F(*S*) and can be constructed as follows. For every *s* in *S*, we introduce a new symbol *s*^{-1}. We then form the set of all finite strings consisting of symbols of *S* and their inverses. Two such strings are considered equivalent if one arises from the other by replacing two adjacent symbols *ss ^{-1}* or

*s*by the empty string. This generates an equivalence relation on the set of strings; its quotient set is defined to be F(

^{-1}s*S*). Because the equivalence relation is compatible with string concatenation, F(

*S*) becomes a group with string concatenation as operation.

If *S* is the empty set, then F(*S*) is the trivial group consisting only of its identity element.

## Universal property

The free group on *S* is characterized by the following universal property: if *G* is any group and

*f*:*S*→*G*

is any function, then there exists a unique group homomorphism

*T*: F(*S*) →*G*

such that

*T*(*s*) =*f*(*s*)

for all *s* in *S*.

Free groups are thus instances of the more general concept of free objects in category theory. Like most universal constructions, they give rise to a pair of adjoint functors.

## Facts and theorems

Any group *G* is isomorphic to a quotient group of some free group F(*S*). If *S* can be chosen to be finite here, then *G* is called *finitely generated*.

If *F* is a free group on *S* and also on *T*, then *S* and *T* have the same cardinality. This cardinality is called the **rank** of the free group *F*.
For every cardinal number *k*, there is, up to isomorphism, exactly one free group of rank *k*.

If *S* has more than one element, then F(*S*) is not abelian, and in fact the center of F(*S*) is trivial (that is, consists only of the identity element).

A free group of finite rank *n* > 1 has an exponential growth rate of order 2*n* − 1.

Nielsen-Schreier theorem: Any subgroup of a free group is free.

A free group of rank *k* clearly has subgroups of every rank less than *k*.
Less obviously, a free group of rank greater than 1 has subgroups of all countable ranks.

## Tarski's Problems

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. Independently, a proof for both problems, and a proof of the first problem, have been announced (both in the affirmative). Neither has yet been judged correct and complete. For details, see the open problems at [1].