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^-1ut^-1'').
A related but different notion is free abelian group.

Contents

History

Examples

Construction

Universal property

Facts and theorems

Free abelian group

Tarski's problems

References

See also

History

In 1882 Walther Dyck studied the concept of a free group, without naming the concept, in his paper ''Gruppentheoretische Studien'' which was published in the Mathematische Annalen. The term ''free group'' was introduced by Jakob Nielsen in 1924.

Examples

The group ('Z',+) of integers is free; we can take ''S'' = {1}. A free group on a two-element set ''S'' occurs in the proof of the Banach–Tarski paradox and is described there.
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.

Construction

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^-1s'' by the empty string. This generates an equivalence relation on the set of strings; its quotient set is defined to be F(''S''). One may prove, via induction on the length of strings, that the equivalence relation is compatible with string concatenation. It follows that F(''S'') becomes a group with string concatenation being the multiplication operation.
If ''S'' is the empty set, then F(''S'') is the trivial group consisting only of its identity element.

Universal property

An alternative definition of the free group on a set ''S'' is as follows:
Consider a pair (''F'', ''φ''), where ''F'' is a group and ''φ'': ''S'' → ''F'' is a function. ''F'' is said to be a 'free group on ''S'' with respect to ''φ'' ' if for any group ''G'' and any function ''ψ'': ''S'' → ''G'', there exists a unique homomorphism ''f'': ''F'' → ''G'' such that
:''f''(''φ''(''s'')) = ''ψ''(''s''), for all ''s'' in ''S''.
It follows readily from this definition that if (''F''₁, ''φ''₁) and (''F''₂, ''φ''₂) are two free groups on ''S'', then there exists a unique isomorphism ''f'': ''F''₁ → ''F''₂ such that
:''f''(''φ''₁(''s'')) = ''φ''₂(''s''), for all ''s'' in ''S''.
Therefore free groups on a set ''S'' are actually characterized, up to isomorphism, by the condition required in the definition. This property is called the universal property of free groups.
In this formulation, given a set ''S'', the existence of the free group on ''S'' is then shown by the construction from the preceding section. Thus one can take ''F'' = F(''S''), the equivalence classes of words, and ''φ'' to be the natural embedding of ''S'' into F(''S'').
The set ''S'', identified with its image ''φ''(''S''), is said to be a 'basis' of F(''S''). More generally, a subset ''S'' of a free group ''F'' is a basis of ''F'' if ''F'' is a free group on ''S'' with respect to the inclusion map. Bases of free groups are not unique in general.
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 which is left adjoint to the forgetful functor.

Facts and theorems

Some properties of free groups follow readily from the definition:
#Any group ''G'' is the homomorphic image of some free group F(''S''). Let ''S'' be a set of ''generators'' of ''G''. The natural map ''f'': F(''S'') → ''G'' is an epimorphism, which proves the claim. Equivalently, ''G'' is isomorphic to a quotient group of some free group F(''S''). The kernel of ''f'' is a set of ''relations'' in the presentation of ''G''. If ''S'' can be chosen to be finite here, then ''G'' is called 'finitely generated'.
#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.
#Two free groups F(''S'') and F(''T'') are isomorphic if and only if ''S'' and ''T'' have the same cardinality. This cardinality is called the 'rank' of the free group ''F''. Thus for every cardinal number ''k'', there is, up to isomorphism, exactly one free group of rank ''k''.
A few other related results are:
#''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.
#The commutator subgroup of a free group of rank ''k'' has infinite rank; for example for F(''a'',''b''), it is freely generated by the commutators [''a''^''m'', ''b''^''n''] for non-zero ''m'' and ''n''.
#The free group in two elements is SQ universal; the above follows as any SQ universal group has subgroups of all countable ranks.
#Any group that acts on a tree, freely and preserving the orientation, is a free group of countable rank (given by 1 plus the Euler characteristic of the quotient graph).
#The Cayley graph of a free group of finite rank is a tree on which the group acts freely, preserving the orientation.

Free abelian group

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 ''φ'': ''S'' → ''F'' 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 ''ψ'': ''S'' → ''G'', there exists a unique homomorphism ''f'': ''F'' → ''G'' such that
:''f''(''φ''(''s'')) = ''ψ''(''s''), for all ''s'' in ''S''.
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'')]. In other words, the free abelian group on ''S'' is the set of words that are distinguished only up to the order of letters.

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 open problem (08) at [1].

References

★ W. Magnus, A. Karrass and D. Solitar, "Combinatorial Group Theory", Dover (1976).

★ J.-P. Serre, ''Trees'', Springer (2003) (english translation of "arbres, amalgames, SL₂", 3rd edition, ''astérisque'' '46' (1983))

See also

★ Cayley graph

★ Generating set of a group

★ Presentation of a group

★ Free abelian group