free group

TheInfoList

for the free group on two generators would look like. Each vertex represents an element of the free group, and each edge represents multiplication by ''a'' or ''b''. In
mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It has no generally ...
, the free group ''F''''S'' over a given set ''S'' consists of all
words In linguistics, a word of a spoken language can be defined as the smallest sequence of phonemes that can be uttered in isolation with semantic, objective or pragmatics, practical meaning (linguistics), meaning. In many languages, words also corres ...
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''−1''t'', but ''s'' ≠ ''t''−1 for ''s'',''t'',''u'' ∈ ''S''). The members of ''S'' are called generators of ''F''''S'', and the number of generators is the rank of the free group. An arbitrary
group A group is a number A number is a mathematical object used to counting, count, measurement, measure, and nominal number, label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with ...
''G'' is called free if it is
isomorphic In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
to ''F''''S'' for some
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are u ...

''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''−1''t''). A related but different notion is a
free abelian group In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
; both notions are particular instances of a
free objectIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
from
universal algebraUniversal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular Group (mathematics), groups as t ...
. As such, free groups are defined by their
universal property In category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labelled d ...
.

# History

Free groups first arose in the study of
hyperbolic geometry In mathematics, hyperbolic geometry (also called Lobachevskian geometry or János Bolyai, Bolyai–Nikolai Lobachevsky, Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any ...
, as examples of
Fuchsian group In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...
s (discrete groups acting by
isometries In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
on the
hyperbolic plane In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
). In an 1882 paper,
Walther von Dyck Walther Franz Anton von Dyck (6 December 1856 – 5 November 1934), born Dyck and later von, ennobled, was a Germany, German mathematician. He is credited with being the first to define a mathematical group (mathematics), group, in the modern sens ...
pointed out that these groups have the simplest possible
presentations Introduction A presentation conveys information from a speaker to an audience. Presentations are typically demonstrations, introduction, lecture, or speech meant to inform, persuade,inspire, motivate, build goodwill, or present a new idea/produc ...
. 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. Max Dehn realized the connection with topology, and obtained the first proof of the full Nielsen–Schreier theorem. Otto Schreier published an algebraic proof of this result in 1927, and Kurt Reidemeister included a comprehensive treatment of free groups in his 1932 book on combinatorial topology. Later on in the 1930s, Wilhelm Magnus discovered the connection between the lower central series of free groups and free Lie algebras.

# Examples

The group (Z,+) of integers is free of rank 1; a generating set is ''S'' = . The integers are also a
free abelian group In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, although all free groups of rank $\geq 2$ are non-abelian. A free group on a two-element set ''S'' occurs in the proof of the Banach–Tarski paradox and is described there. 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 circles, 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

The free group ''FS'' with free generating set ''S'' can be constructed as follows. ''S'' is a set of symbols, and we suppose for every ''s'' in ''S'' there is a corresponding "inverse" symbol, ''s''−1, in a set ''S''−1. Let ''T'' = ''S'' ∪ ''S''−1, and define a word (group theory), word in ''S'' to be any written product of elements of ''T''. That is, a word in ''S'' is an element of the monoid generated by ''T''. The empty word is the word with no symbols at all. For example, if ''S'' = , then ''T'' = , and :$a b^3 c^ c a^ c\,$ is a word in ''S''. If an element of ''S'' lies immediately next to its inverse, the word may be simplified by omitting the c, c−1 pair: :$a b^3 c^ c a^ c\;\;\longrightarrow\;\;a b^3 \, a^ c.$ A word that cannot be simplified further is called reduced. 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 Conjugacy class, 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''−1''abcb'' 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''.

# Universal property

The free group ''FS'' is the Universal (mathematics), universal group generated by the set ''S''. This can be formalized by the following universal property: given any function from ''S'' to a group ''G'', there exists a unique group homomorphism, homomorphism ''φ'': ''FS'' → ''G'' making the following commutative diagram, diagram commute (where the unnamed mapping denotes the Inclusion map, inclusion from ''S'' into ''FS''): Image:Free Group Universal.svg, center, 100px That is, homomorphisms ''FS'' → ''G'' are in one-to-one correspondence with functions ''S'' → ''G''. For a non-free group, the presence of group presentation, 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 , first note that ''φ'' sends the empty word to the identity of ''G'' and it has to agree with 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 objectIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
s in
universal algebraUniversal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular Group (mathematics), groups as t ...
. 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.

# 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 ''Generating set of a group, 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 ''φ'' is a set of ''relations'' in the Presentation of a group, 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 group, abelian, and in fact the center of a group, center of F(''S'') is trivial (that is, consists only of the identity element). #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 free group of finite rank ''n'' > 1 has an exponential growth, exponential growth rate (group theory), growth rate of order 2''n'' − 1. A few other related results are: #The Nielsen–Schreier theorem: Every 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 (''nonabelian!'') free group of rank at least 2 has subgroups of all countable set, countable ranks. #The commutator subgroup of a free group of rank ''k'' > 1 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 Group action (mathematics), acts on a tree, free action, freely and preserving the oriented graph, orientation, is a free group of countable rank (given by 1 plus the Euler characteristic of the Group action (mathematics), quotient graph theory, graph). #The Cayley graph of a free group of finite rank, with respect to a free generating set, is a tree (graph theory), tree on which the group acts freely, preserving the orientation. #The groupoid approach to these results, given in the work by P.J. Higgins below, is kind of extracted from an approach using covering spaces. It allows more powerful results, for example on Grushko's theorem, and a normal form for the fundamental groupoid of a graph of groups. In this approach there is considerable use of free groupoids on a directed graph. # Grushko's theorem has the consequence that if a subset ''B'' of a free group ''F'' on ''n'' elements generates ''F'' and has ''n'' elements, then ''B'' generates ''F'' freely.

# 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'')], 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.

# Tarski's problems

Around 1945, Alfred Tarski asked whether the free groups on two or more generators have the same model theory, first-order theory, and whether this theory is decidability (logic), decidable. answered the first question by showing that any two nonabelian free groups have the same first-order theory, and 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.