Free group

This article covers the mathematical term. See also: Free Group Bayreuth .

In mathematics , a group is called free if it contains a subset , so that each group element can be written in exactly one way as a (reduced) word of elements in and their inverses. The order of the factors is important here: If one demands that all elements of the group should commute, then one obtains the related but very different concept of the free Abelian group . ${\displaystyle S}$ ${\displaystyle S}$

Free groups play a universal role in group theory and allow each group to be represented by generators and relations. They also appear in algebraic topology , for example as a fundamental group of graphs (see Nielsen-Schreier theorem ) or of surfaces such as the dotted plane.

definition

A group is called free over a subset if each group element can be written in exactly one way as a product with factors , where for all , and exponents , where for all . ${\displaystyle F}$ ${\displaystyle S\subset F}$ ${\displaystyle a\in F}$ ${\displaystyle a=s_{1}^{e_{1}}s_{2}^{e_{2}}\cdots s_{n}^{e_{n}}}$ ${\displaystyle s_{1},s_{2},\dots ,s_{n}\in S}$ ${\displaystyle s_{i}\neq s_{i+1}}$ ${\displaystyle i}$ ${\displaystyle e_{1},e_{2},\dots ,e_{n}\in \mathbb {Z} }$ ${\displaystyle e_{i}\neq 0}$ ${\displaystyle i}$

Under the conditions mentioned, a reduced word is called over . Accordingly, there is free about if each element of can be clearly written over as a reduced word . The existence of such notation is the same as saying that a generating set of is. The uniqueness is synonymous with the fact that there are no algebraic relations between the elements of (except for the abbreviation relation valid in each group ) or that the neutral element of the group can be represented with the elements in reduced form exclusively as their empty product. Is freely as we also say, therefore, will free from generating . One then calls a free generating system or basis of the group . ${\displaystyle s_{1}^{e_{1}}s_{2}^{e_{2}}\cdots s_{n}^{e_{n}}}$ ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle uss^{-1}v=uv}$ ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle F}$

Universal property

A group is free over a subset if and only if it has the following universal property : If there is any mapping of the set into a group , then there is exactly one group homomorphism which continues, i.e. fulfills for all . ${\displaystyle F}$ ${\displaystyle S\subset F}$ ${\displaystyle f\colon S\to G}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle h\colon F\to G}$ ${\displaystyle f}$ ${\displaystyle h(s)=f(s)}$ ${\displaystyle s\in S}$

This universal mapping property is equivalent to the above definition. Either of the two characterizations can therefore be used as a definition of free groups, and both approaches can be found in the literature. The other characterization is then a consequence.

Examples

The group of whole numbers is free about . The universal imaging property here means: For every group and any element there is exactly one homomorphism with . This is given by for everyone . ${\displaystyle (\mathbb {Z} ,+)}$ ${\displaystyle S=\{1\}}$ ${\displaystyle G}$ ${\displaystyle g\in G}$ ${\displaystyle h\colon \mathbb {Z} \to G}$ ${\displaystyle h(1)=g}$ ${\displaystyle h(k)=g^{k}}$ ${\displaystyle k\in \mathbb {Z} }$

The cyclic group of order is not a free group. This is created by an element of order , and the relation prevents it from being free. One can think of it as the group of rotation of the regular corner in the plane, generated by a rotation about the angle . Each element can then be written as with , but this notation is not unambiguous because . ${\displaystyle C_{n}}$ ${\displaystyle n\geq 2}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle r^{n}=1}$ ${\displaystyle C_{n}}$ ${\displaystyle C_{n}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle 2\pi /n}$ ${\displaystyle r^{k}}$ ${\displaystyle k\in \mathbb {Z} }$ ${\displaystyle r^{k}=r^{k+n}}$

The Cartesian product with the component-wise addition is a free Abelian group over , but not a free group. In general, a free Abelian group over a set with more than one element is not a free group. ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$ ${\displaystyle \{(1,0),(0,1)\}}$ ${\displaystyle S}$

Let be the rotation of the around the x-axis by the angle and the rotation of the around the y-axis by the angle . Then the subgroup of the general linear group created by and is a free group over . Such a free rotation group over a two-element generating system appears in the proof of the Banach-Tarski paradox . ${\displaystyle \sigma }$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} (1,0,0)}$ ${\displaystyle \pi {\sqrt {2}}}$ ${\displaystyle \tau }$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} (0,1,0)}$ ${\displaystyle \pi {\sqrt {3}}}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle GL_{3}(\mathbb {R} )}$ ${\displaystyle S=\{\sigma ,\tau \}}$

construction

For every amount there is a free group about . This can be constructed as follows. ${\displaystyle S}$ ${\displaystyle F(S)}$ ${\displaystyle S}$

In order to have an inverse for each element , we consider the set and define an involution through it . We identify with the help of the illustration . Let be the set of all words above the alphabet (cf. Kleen's envelope ). The concatenation of words then defines a link . This will on the free monoid over . To consider the equivalence relation generated by the elementary transformations is generated. Two words in so are exactly equivalent if they carried a finite sequence of inserting or removing sub-words form with overlap. We denote the set of equivalence classes with . The link on induces a well-defined link on the quotient set . After construction it becomes a free group . ${\displaystyle s\in S}$ ${\displaystyle s^{-1}}$ ${\displaystyle A=S\times \{\pm 1\}}$ ${\displaystyle {}^{-1}\colon A\to A}$ ${\displaystyle (s,\varepsilon )^{-1}=(s,-\varepsilon )}$ ${\displaystyle S}$ ${\displaystyle S\times \{+1\}}$ ${\displaystyle s\mapsto (s,+1)}$ ${\displaystyle M=A^{*}}$ ${\displaystyle A}$ ${\displaystyle \cdot \colon M\times M\to M}$ ${\displaystyle (M,\cdot )}$ ${\displaystyle A}$ ${\displaystyle M}$ ${\displaystyle uaa^{-1}v\equiv uv}$ ${\displaystyle M}$ ${\displaystyle aa^{-1}}$ ${\displaystyle a\in A}$ ${\displaystyle M/\equiv }$ ${\displaystyle F=F(S)}$ ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle \cdot \colon F\times F\to F}$ ${\displaystyle (F,\cdot )}$ ${\displaystyle S}$

The free group above is unique in the following sense: If and are two free groups above , then they are canonically isomorphic , that is, there is exactly one group isomorphism with the property for all . This uniqueness allows the free group to talk about. ${\displaystyle S}$ ${\displaystyle F_{1}}$ ${\displaystyle F_{2}}$ ${\displaystyle S}$ ${\displaystyle f\colon F_{1}\to F_{2}}$ ${\displaystyle f(s)=s}$ ${\displaystyle s\in S}$ ${\displaystyle S}$

If the set is empty , then is the one-element group consisting only of the neutral element . ${\displaystyle S}$ ${\displaystyle F(S)}$

Word problem

The word problem can be solved very easily in a free group . For every given word in the free generators , one finds an equivalent reduced word as follows : one summarizes neighboring equal generators until finally for all , and then removes superfluous entries to ensure for all . One arrives at a reduced word that represents the same group element, and this representation is unambiguous by definition. In this way, you can compare two elements of each other and determine whether they are the same or different. ${\displaystyle F=F(S)}$ ${\displaystyle s_{1}^{e_{1}}s_{2}^{e_{2}}\cdots s_{n}^{e_{n}}}$ ${\displaystyle S}$ ${\displaystyle s_{i}\neq s_{i+1}}$ ${\displaystyle i}$ ${\displaystyle e_{i}\neq 0}$ ${\displaystyle i}$ ${\displaystyle F}$

This comparison procedure assumes that there are no relations between the producers. In contrast to this, in a group given by generators and relations, the word problem is often difficult and generally not algorithmically solvable (Novikov and Boone's theorem).

rank

If a group is both free above and free above , then the sets and have the same cardinality . This is called the rank of the free group . According to the above construction there is exactly one free group of rank for every thickness apart from isomorphism . ${\displaystyle F}$ ${\displaystyle S}$ ${\displaystyle S'}$ ${\displaystyle S}$ ${\displaystyle S'}$ ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle n}$

In the literature it has become common to designate free groups of rank as non- Abelian free groups , because on the one hand the only Abelian free group and on the other hand many theorems that can be proven for the other free groups do not apply to the Abelian group . ${\displaystyle n\geq 2}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {Z} }$

There are several ways of proving that rank is uniquely determined. This is particularly easy for a free group over a set of finite thicknesses : Due to the universal mapping property of , the set of all group homomorphisms in the cyclic group consists of exactly elements. This is clearly defined by the group . ${\displaystyle F=F(S)}$ ${\displaystyle S}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle F}$ ${\displaystyle Hom(F,C_{2})}$ ${\displaystyle C_{2}}$ ${\displaystyle 2^{n}}$ ${\displaystyle n}$ ${\displaystyle F}$

In general, the free group can be made Abelian, and the factor group thus obtained is free Abelian in rank . This rank corresponds to the dimension of the vector space over a body (for example ) and is thus clearly defined by the group . ${\displaystyle F=F(S)}$ ${\displaystyle F_{ab}=F/[F,F]}$ ${\displaystyle |S|}$ ${\displaystyle F_{ab}\otimes K}$ ${\displaystyle K}$ ${\displaystyle K=\mathbb {Q} }$ ${\displaystyle F}$

Change of base and automorphisms

A free group of rank has an infinite number of bases. Each automorphism maps one base to a new base . Conversely exists for each two such bases and precisely an automorphism with . This already suggests that even if the free groups themselves are fairly easy to understand, their automorphism groups are highly complex and interesting. ${\displaystyle F}$ ${\displaystyle r\geq 2}$ ${\displaystyle h\colon F\to F}$ ${\displaystyle B=(b_{1},\dots ,b_{r})}$ ${\displaystyle B'=(h(b_{1}),\dots ,h(b_{r}))}$ ${\displaystyle B}$ ${\displaystyle B'}$ ${\displaystyle h\colon F\to F}$ ${\displaystyle h(B)=B'}$

Subgroups

Each subgroup of a free group is free, according to the phrase of Nielsen-Schreier (named after Jakob Nielsen and Otto Schreier ).

A free group of rank obviously has a subgroup of rank for every thickness . In the case there are even subgroups of countably infinite rank ( Nielsen-Schreier theorem ). This amazing property is in contrast to free Abelian groups (where the rank of a subgroup is at most as great as the rank of the whole group) or vector spaces over a body (where the dimension of a subspace is never greater than the dimension of the whole space). ${\displaystyle n}$ ${\displaystyle m\geq n}$ ${\displaystyle m}$ ${\displaystyle n\geq 2}$

Other properties

The Cayley graph of the free group over the generators ${\displaystyle a,b}$

The properties of free groups in the non-Abelian case (for rank ) are very different from the Abelian case (for rank or ). The latter are, so to speak, two exceptions to the generic case: ${\displaystyle \geq 2}$ ${\displaystyle 0}$ ${\displaystyle 1}$

• The free group of rank is the trivial group consisting only of the neutral element. ${\displaystyle 0}$
• The free group of rank is the infinitely cyclical group and thus Abelian . ${\displaystyle 1}$ ${\displaystyle (\mathbb {Z} ,+)}$
• A free group of rank is not Abelian and its center consists only of the neutral element. ${\displaystyle \geq 2}$

The disgrace of the free group of rank is the free Abelian group of rank , isomorphic to . ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle \mathbb {Z} ^{r}}$

If a free group is of rank , then the commutator subgroup is free of countably infinite rank. In the simplest case, for the free group on producers , is freely generated by the commutators with . ${\displaystyle F}$ ${\displaystyle \geq 2}$ ${\displaystyle F'=[F,F]}$ ${\displaystyle F=F(a,b)}$ ${\displaystyle a,b}$ ${\displaystyle F'}$ ${\displaystyle [a^{m},b^{n}]}$ ${\displaystyle m,n\in \mathbb {Z} \setminus \{0\}}$

Every free group is torsion-free, that is, it contains no non-trivial elements of finite order.

The Cayley graph of a free group is a tree , and operates on it freely and true to orientation. The reverse is true: If a group operates freely and true to orientation on a tree, then it is a free group. ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle G}$

If a free group is of rank , then every generating system has at least elements. If a generating system has exactly elements, then it is free. ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle S\subset F}$ ${\displaystyle n}$ ${\displaystyle S\subset F}$ ${\displaystyle n}$

Applications

Group theory

In group theory, free groups serve to represent a given group by means of generators and relations. For this, be a generating system of the group . (For example one can always take. Mostly one chooses as small as possible. If a finite set can be chosen, then one calls a finitely generated group .) The group homomorphism , which continues the mapping on , is then surjective. The kernel describes the algebraic relations that apply between the generators from in . The factor group is then isomorphic to the given group . ${\displaystyle G}$ ${\displaystyle S\subset G}$ ${\displaystyle G}$ ${\displaystyle S=G}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle h\colon F(S)\to G}$ ${\displaystyle S\hookrightarrow G}$ ${\displaystyle F(S)}$ ${\displaystyle R=\ker(h)}$ ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle F(S)/R}$ ${\displaystyle G}$

Algebraic topology

Free groups also appear in algebraic topology, for example as fundamental groups of graphs or surfaces like the dotted plane:

• The fundamental group of every connected graph is free. This fact can be used for a topological proof of the Nielsen-Schreier theorem .

• The fundamental group of the -fold dotted level is a free group of rank . A basis can be given geometrically by homotopy classes of paths, one running around the point . (The space is homotopy equivalent to a graph, see the previous example.) ${\displaystyle n}$ ${\displaystyle X=\mathbb {R} ^{2}\setminus \{p_{1},\dots ,p_{n}\}}$ ${\displaystyle n}$ ${\displaystyle x_{1},\dots ,x_{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle X}$

• Likewise, the fundamental group of a bounded compact surface is free from gender with boundary components, namely from rank . ( However, there is a relation for unrestricted areas of gender and the fundamental group is not free.) ${\displaystyle g\geq 0}$ ${\displaystyle b\geq 1}$ ${\displaystyle 2g+b-1}$ ${\displaystyle g\geq 1}$

First level logic and Tarski's questions

Around 1945, logician Alfred Tarski asked two questions that have become famous over the years and are notorious for their difficulty:

• Do all free groups of rank have the same elementary theory? In other words, do all the sentences that can be formulated in the logic of the first order match for these groups? ${\displaystyle n\geq 2}$

• Are these elementary theories decidable?

Both questions were solved in 2006: Zlil Sela showed that all free groups of rank have the same elementary theory and Olga Kharlampovich and Alexei Myasnikov were also able to show that this theory is decidable. ${\displaystyle n\geq 2}$

history

As early as 1882, Walther von Dyck pointed out that free groups have the simplest possible presentations, namely those without any relation. However, the systematic study of free groups was not started until the 1920s by Jakob Nielsen , who gave free groups their current name and proved many of their basic properties, in particular the Nielsen-Schreier theorem. Otto Schreier proved this theorem in full generality in 1927. Max Dehn recognized the relationship to algebraic topology and was the first to give a topological proof of Nielsen-Schreier's theorem. Kurt Reidemeister presented this development in his textbook on combinatorial topology in 1932. In the 1930s, Wilhelm Magnus developed the relationship between the descending central series of free groups and free Lie algebras .

Individual evidence

1. ^ Zlil Sela : Diophantine geometry over groups VI: The elementary theory of a free group. In: Geometric & Functional Analysis. GAFA. Vol. 16, No. 3, 2006, pp. 707-730, doi : 10.1007 / s00039-006-0565-8 .
2. ↑ Olga Kharlampovich , Alexei Myasnikov: Elementary theory of free non-abelian groups. In: Journal of Algebra. Vol. 302, No. 2, 2006, pp. 451-552, doi : 10.1016 / j.jalgebra.2006.03.033 , digital version (PDF; 7786.39 kB) .
3. ^ Walther von Dyck : Group theoretical studies. In: Mathematical Annals . Vol. 20, No. 1, 1882, pp. 1-44, doi : 10.1007 / BF01443322 .
4. ↑ Otto Schreier : The subgroups of the free groups. In: Treatises from the Mathematical Seminar of the University of Hamburg. Vol. 5, 1927, pp. 161-183, doi : 10.1007 / BF02952517 .
5. ↑ See Wilhelm Magnus , Ruth Moufang : Max Dehn zum Gedächtnis. In: Mathematical Annals. Vol. 127, No. 1, 1954, pp. 215-227, doi : 10.1007 / BF01361121 .
6. ↑ Kurt Reidemeister : Introduction to combinatorial topology (= Die Wissenschaft. Collection of scientific and mathematical monographs. Vol. 86, ZDB -ID 538216-6 ). Vieweg, Braunschweig 1932 (Unchanged reprint. Ibid 1951; Unchanged reprographic reprint of the 1951 edition. Ibid 1972, ISBN 3-534-06007-5 ).

literature

• Roger C. Lyndon, Paul E. Schupp: Combinatorial Group Theory (= Results of Mathematics and their Frontier Areas. A Series of Modern Surveys in Mathematics. Vol. 89). Springer, Berlin et al. 1977, ISBN 3-540-07642-5 .