Editing Free group

{{Short description|Mathematics concept}}
{{Group theory sidebar |Discrete}}
[[Image:F2 Cayley Graph.png|right|thumb|Diagram showing the [[Cayley graph]] for the free group on two generators.  Each vertex represents an element of the free group, and each edge represents multiplication by ''a'' or ''b''.]]

In [[mathematics]], the '''free group''' ''F''<sub>''S''</sub> over a given set ''S'' consists of all [[Word (group theory)|words]] that can be built from members of ''S'', considering two words to be different unless their equality follows from the [[Group (mathematics)#Definition|group axioms]] (e.g. ''st'' = ''suu''<sup>−1</sup>''t'' but ''s'' ≠ ''t''<sup>−1</sup> for ''s'',''t'',''u'' ∈ ''S''). The members of ''S'' are called '''generators''' of ''F''<sub>''S''</sub>, and the number of generators is the '''rank''' of the free group.
An arbitrary [[group (mathematics)|group]] ''G'' is called '''free''' if it is [[group isomorphism|isomorphic]] to ''F''<sub>''S''</sub> 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''<sup>−1</sup>''t'').

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 [[Free group#Universal property|universal property]].

== History ==
Free groups first arose in the study of [[hyperbolic geometry]], as examples of [[Fuchsian group]]s (discrete groups acting by [[isometry|isometries]] on the [[Hyperbolic geometry|hyperbolic plane]]).  In an 1882 paper, [[Walther von Dyck]] pointed out that these groups have the simplest possible [[group presentation|presentations]].<ref>{{cite journal | last = von Dyck | first = Walther | author-link = Walther von Dyck | title = Gruppentheoretische Studien (Group-theoretical Studies) | journal = [[Mathematische Annalen]] | volume = 20 | issue = 1 | pages = 1–44 | year = 1882 | url = http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002246724&L=1 | doi = 10.1007/BF01443322 | s2cid = 179178038 | access-date = 2015-09-01 | archive-date = 2016-03-04 | archive-url = https://web.archive.org/web/20160304201754/http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002246724&L=1 | url-status = dead }}</ref> The algebraic study of free groups was initiated by [[Jakob Nielsen (mathematician)|Jakob Nielsen]] in 1924, who gave them their name and established many of their basic properties.<ref>{{cite journal|last=Nielsen|first=Jakob|author-link=Jakob Nielsen (mathematician)|year=1917|title=Die Isomorphismen der allgemeinen unendlichen Gruppe mit zwei Erzeugenden|url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002266873&L=1|journal=[[Mathematische Annalen]]|volume=78|issue=1|pages=385–397|doi=10.1007/BF01457113|jfm=46.0175.01|mr=1511907|s2cid=119726936|access-date=2015-09-01|archive-date=2016-03-05|archive-url=https://web.archive.org/web/20160305141749/http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002266873&L=1|url-status=dead}}
<!-- note the journal volume was published in 1964, but its JFM review and the text of the article use the date 1917---><!-- note the journal volume was published in 1964, but its JFM review and the text of the article use the date 1917.--></ref><ref>{{cite journal | last = Nielsen | first = Jakob | author-link = Jakob Nielsen (mathematician) | title = On calculation with noncommutative factors and its application to group theory. (Translated from Danish) | journal = The Mathematical Scientist | volume = 6 (1981) | issue = 2 | pages = 73–85 | year = 1921 }}</ref><ref>{{cite journal | last = Nielsen | first = Jakob | author-link = Jakob Nielsen (mathematician) | title = Die Isomorphismengruppe der freien Gruppen | journal = Mathematische Annalen | volume = 91 | issue = 3 | pages = 169–209 | year = 1924 | url = http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002269813&L=1 | doi = 10.1007/BF01556078 | s2cid = 122577302 | access-date = 2015-09-01 | archive-date = 2016-03-05 | archive-url = https://web.archive.org/web/20160305073827/http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002269813&L=1 | url-status = dead }}</ref> [[Max Dehn]] realized the connection with topology, and obtained the first proof of the full [[Nielsen–Schreier theorem]].<ref>See {{cite journal | last1 = Magnus | first1 = Wilhelm | author-link1 = Wilhelm Magnus | last2 = Moufang | first2 = Ruth | author-link2 = Ruth Moufang | title = Max Dehn zum Gedächtnis | journal = Mathematische Annalen | volume = 127 | issue = 1 | pages = 215–227 | year = 1954 | url = http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002283808&L=1 | doi = 10.1007/BF01361121 | s2cid = 119917209 | access-date = 2015-09-01 | archive-date = 2016-03-05 | archive-url = https://web.archive.org/web/20160305072926/http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=GDZPPN002283808&L=1 | url-status = dead }}</ref> [[Otto Schreier]] published an algebraic proof of this result in 1927,<ref>{{cite journal | last = Schreier | first = Otto | author-link = Otto Schreier | title = Die Untergruppen der freien Gruppen | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg | volume = 5 | year = 1928 | issue = 1 | pages = 161–183 | doi = 10.1007/BF02952517 | s2cid = 121888949 }}</ref> and [[Kurt Reidemeister]] included a comprehensive treatment of free groups in his 1932 book on [[combinatorial topology]].<ref>{{cite book | last = Reidemeister | first = Kurt | author-link = Kurt Reidemeister | title = Einführung in die kombinatorische Topologie | publisher = Wissenschaftliche Buchgesellschaft | date = 1972 |orig-date=1932 | location = Darmstadt}}</ref> Later on in the 1930s, [[Wilhelm Magnus]] discovered the connection between the [[lower central series]] of free groups and [[free Lie algebra]]s.

== Examples ==
The group ('''Z''',+) of [[integer]]s is free of rank 1; a generating set is ''S'' = {1}. The integers are also a [[free abelian group]], although all free groups of rank <math>\geq 2</math> 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''' ''F<sub>S</sub>'' 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''<sup>&minus;1</sup>, in a set ''S''<sup>&minus;1</sup>. Let ''T''&nbsp;=&nbsp;''S''&nbsp;∪&nbsp;''S''<sup>&minus;1</sup>, 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''&nbsp;=&nbsp;{''a'',&nbsp;''b'',&nbsp;''c''}, then ''T''&nbsp;=&nbsp;{''a'',&nbsp;''a''<sup>&minus;1</sup>,&nbsp;''b'',&nbsp;''b''<sup>&minus;1</sup>,&nbsp;''c'',&nbsp;''c''<sup>&minus;1</sup>}, and
:<math>a b^3 c^{-1} c a^{-1} c\,</math>
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,&nbsp;c<sup>&minus;1</sup> pair:
:<math>a b^3 c^{-1} c a^{-1} c\;\;\longrightarrow\;\;a b^3 \, a^{-1} c.</math>
A word that cannot be simplified further is called '''reduced'''.

The free group ''F<sub>S</sub>'' 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 reduced 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''<sup>&minus;1</sup>''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 ''F<sub>S</sub>'' is the [[Universal (mathematics)|universal]] group generated by the set ''S''.  This can be formalized by the following [[universal property]]: given any function {{mvar|f}} from ''S'' to a group ''G'', there exists a unique [[group homomorphism|homomorphism]] ''φ'':&nbsp;''F<sub>S</sub>''&nbsp;→&nbsp;''G'' making the following [[commutative diagram|diagram]] commute (where the unnamed mapping denotes the [[Inclusion map|inclusion]] from ''S'' into ''F<sub>S</sub>''):
[[Image:Free Group Universal.svg|center|100px]]
That is, homomorphisms ''F<sub>S</sub>''&nbsp;→&nbsp;''G'' are in one-to-one correspondence with functions ''S''&nbsp;→&nbsp;''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 ''F<sub>S</sub>'' as sending each symbol to a word consisting of that symbol. To construct ''φ'' for the given {{mvar|f}}, first note that ''φ'' sends the empty word to the identity of ''G'' and it has to agree with {{mvar|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 ''F<sub>S</sub>''.  The basis for a free group is not uniquely determined.

Being characterized by a universal property is the standard feature of [[free object]]s 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.

==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<sub>S</sub>''. Let ''S'' be a set of ''[[Generating set of a group|generators]]'' of ''G''. The natural map ''φ'': ''F<sub>S</sub>'' → ''G'' is an [[epimorphism]], which proves the claim. Equivalently, ''G'' is isomorphic to a [[quotient group]] of some free group ''F<sub>S</sub>''. If ''S'' can be chosen to be finite here, then ''G'' is called [[finitely generated group|finitely generated]]. The kernel Ker(''φ)'' is the set of all ''relations'' in the [[Presentation of a group|presentation]] of ''G''; if Ker(''φ)'' can be generated by the conjugates of finitely many elements of ''F'', then ''G'' is finitely presented.
#If ''S'' has more than one element, then ''F<sub>S</sub>'' is not [[abelian group|abelian]], and in fact the [[center of a group|center]] of ''F<sub>S</sub>'' is trivial (that is, consists only of the identity element).
#Two free groups ''F<sub>S</sub>'' and ''F<sub>T</sub>'' 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. Furthermore, if the free group ''F'' has rank ''n'' and the subgroup ''H'' has [[Index of a subgroup|index]] ''e'' in ''F'', then ''H'' is free of rank 1 + ''e''(''n–''1).
#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 [[commutator]]s [''a''<sup>''m''</sup>, ''b''<sup>''n''</sup>] 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. As a topological space (a one-dimensional [[simplicial complex]]), this Cayley graph Γ(''F'') is [[Contractible space|contractible]]. For a finitely presented group ''G,'' the natural homomorphism defined above, ''φ'' : ''F'' → ''G'', defines a [[Covering space|covering map]] of Cayley graphs ''φ*'' : Γ(''F'') → Γ(''G''), in fact a universal covering. Hence, the [[fundamental group]] of the Cayley graph Γ(''G'') is isomorphic to the kernel of ''φ'', the normal subgroup of relations among the generators of ''G''. The extreme case is when ''G'' = {''e''}, the trivial group, considered with as many generators as ''F'', all of them trivial; the Cayley graph Γ(''G'') is a bouquet of circles, and its fundamental group is ''F'' itself.
#Any subgroup of a free group, <math>H \subset F</math>, corresponds to a covering space of the bouquet of circles, namely to the [[Schreier coset graph]] of ''F''/''H''. This can be used to give a topological proof of the Nielsen-Schreier theorem above.
#The [[groupoid]] approach to these results, given in the work by P.J. Higgins below, is related to the use of [[covering space]]s above. 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 ==
{{further|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]]. {{harvtxt|Sela|2006}} answered the first question by showing that any two nonabelian free groups have the same first-order theory, and {{harvtxt|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 algebra]]s of any two non-abelian finitely generated free groups are isomorphic.

==See also==
* [[Generating set of a group]]
* [[Presentation of a group]]
* [[Nielsen transformation]], a factorization of elements of the [[automorphism group of a free group]]
* [[Normal form for free groups and free product of groups]]
* [[Free product]]

==Notes==
{{reflist}}

==References==
*{{Cite journal|last1=Kharlampovich|first1=Olga|last2=Myasnikov|first2=Alexei|title=Elementary theory of free non-abelian groups|journal=[[Journal of Algebra]]|volume=302|year=2006|issue=2|pages=451–552|doi=10.1016/j.jalgebra.2006.03.033|mr=2293770|doi-access=free}} 
*W. Magnus, A. Karrass and D. Solitar, "Combinatorial Group Theory", Dover (1976).
* P.J. Higgins, 1971, "Categories and Groupoids", van Nostrand, {New York}. Reprints in Theory and Applications of Categories, 7 (2005) pp 1–195.
*{{Cite journal
|last=Sela|first= Zlil | author-link=Zlil Sela 
|title=Diophantine geometry over groups. VI. The elementary theory of a free group. 
|journal=Geom. Funct. Anal. |volume=16 |year=2006|issue= 3|pages= 707–730|mr=2238945 |doi=10.1007/s00039-006-0565-8|s2cid= 123197664 }} 
*[[Jean-Pierre Serre|Serre, Jean-Pierre]], ''Trees'', Springer (2003) (English translation of "arbres, amalgames, SL<sub>2</sub>", 3rd edition, ''astérisque'' '''46''' (1983))
* P.J. Higgins, ''[http://doi.org/10.1112/jlms/s2-13.1.145 The fundamental groupoid of a graph of groups]'', [[Journal of the London Mathematical Society]] (2) '''13''' (1976), no. 1, 145–149.
* {{Cite book
 | last=Aluffi
 | first=Paolo
 | title=Algebra: Chapter 0
 | publisher=AMS Bookstore
 | year=2009
 | isbn=978-0-8218-4781-7
 | url=https://books.google.com/books?id=deWkZWYbyHQC&pg=PA70
 | page=70
 }}.
* {{Cite book
 | last=Grillet
 | first=Pierre Antoine
 | title=Abstract algebra
 | publisher=Springer
 | year=2007
 | isbn=978-0-387-71567-4
 | url=https://books.google.com/books?id=LJtyhu8-xYwC&pg=PA27
 | page=27
 }}.

{{DEFAULTSORT:Free Group}}
[[Category:Geometric group theory]]
[[Category:Combinatorial group theory]]
[[Category:Free algebraic structures]]
[[Category:Properties of groups]]