| Version 35 |
Version 34 |
| \PMlinkescapeword{alphabet} |
\PMlinkescapeword{alphabet} |
| \PMlinkescapeword{contraction} |
\PMlinkescapeword{contraction} |
| \PMlinkescapeword{contractions} |
\PMlinkescapeword{contractions} |
| \PMlinkescapeword{equivalent} |
\PMlinkescapeword{equivalent} |
| \PMlinkescapeword{generates} |
\PMlinkescapeword{generates} |
| \PMlinkescapeword{index} |
\PMlinkescapeword{index} |
| \PMlinkescapeword{inverse} |
\PMlinkescapeword{inverse} |
| \PMlinkescapeword{minimal} |
\PMlinkescapeword{minimal} |
| \PMlinkescapephrase{multiplicative group} |
|
| \PMlinkescapeword{order} |
\PMlinkescapeword{order} |
| \PMlinkescapeword{rank} |
\PMlinkescapeword{rank} |
| \PMlinkescapeword{ranks} |
\PMlinkescapeword{ranks} |
| \PMlinkescapeword{states} |
\PMlinkescapeword{states} |
| \PMlinkescapeword{structure} |
\PMlinkescapeword{structure} |
| \PMlinkescapeword{type} |
\PMlinkescapeword{type} |
|
|
| \section*{Definition} |
\section*{Definition} |
|
|
| If $F$ is a group with a subset $A$ such that for every group $G$ |
If $F$ is a group with a subset $A$ such that for every group $G$ |
| every function $\psi\colon A\to G$ extends to a unique \PMlinkname{homomorphism}{GroupHomomorphism} |
every function $\psi\colon A\to G$ extends to a unique \PMlinkname{homomorphism}{GroupHomomorphism} |
| $\phi\colon F\to G$, then $F$ is said to be a \emph{free group} of \emph{rank} $|A|$, |
$\phi\colon F\to G$, then $F$ is said to be a \emph{free group} of \emph{rank} $|A|$, |
| and we say that $A$ \emph{freely generates} $F$. |
and we say that $A$ \emph{freely generates} $F$. |
|
|
| \section*{Examples} |
\section*{Examples} |
|
|
| A group with only one element is a free group of rank $0$, freely generated by the empty set. |
A group with only one element is a free group of rank $0$, freely generated by the empty set. |
|
|
| The infinite cyclic group $\Z$ is a free group of rank $1$, freely generated by either $\{1\}$ or $\{-1\}$. |
The infinite cyclic group $\Z$ is a free group of rank $1$, freely generated by either $\{1\}$ or $\{-1\}$. |
|
|
| An example of a free group of rank $2$ is the multiplicative group of $2\times2$ integer matrices generated by |
An example of a free group of rank $2$ is the multiplicative group of $2\times2$ integer matrices generated by |
| \[ \left( \begin{array}{cc} |
\[ \left( \begin{array}{cc} |
| 1 & 2 \\ |
1 & 2 \\ |
| 0 & 1 \end{array} \right)\phantom{.}\] |
0 & 1 \end{array} \right)\phantom{.}\] |
| and |
and |
| \[ \left( \begin{array}{cc} |
\[ \left( \begin{array}{cc} |
| 1 & 0 \\ |
1 & 0 \\ |
| 2 & 1 \end{array} \right).\] |
2 & 1 \end{array} \right).\] |
|
|
| If $F$ is a free group freely generated by a set $A$, where $|A|>1$, then for distinct $a,b\in A$ the set $\{a^nb^n\mid 0<n\in\Z\}$ generates a free group of countably infinite rank. |
If $F$ is a free group freely generated by a set $A$, where $|A|>1$, then for distinct $a,b\in A$ the set $\{a^nb^n\mid 0<n\in\Z\}$ generates a free group of countably infinite rank. |
|
|
| \section*{Properties} |
\section*{Properties} |
|
|
| If a free group $F$ is freely generated by $A$, then $A$ is a minimal generating set for $F$, and no set of smaller cardinality than $A$ can generate $F$. |
If a free group $F$ is freely generated by $A$, then $A$ is a minimal generating set for $F$, and no set of smaller cardinality than $A$ can generate $F$. |
| It follows that if $F$ is freely generated by both $A$ and $B$, then $|A|=|B|$. So the rank of a free group is a well-defined concept, and free groups of different ranks are non-isomorphic. |
It follows that if $F$ is freely generated by both $A$ and $B$, then $|A|=|B|$. So the rank of a free group is a well-defined concept, and free groups of different ranks are non-isomorphic. |
|
|
| For every cardinal number $\kappa$ there is, up to isomorphism, exactly one free group of rank $\kappa$. |
For every cardinal number $\kappa$ there is, up to isomorphism, exactly one free group of rank $\kappa$. |
| The abelianization of a free group of rank $\kappa$ is a free abelian group of rank $\kappa$. |
The abelianization of a free group of rank $\kappa$ is a free abelian group of rank $\kappa$. |
|
|
| Every group is a homomorphic image of some free group. |
Every group is a homomorphic image of some free group. |
| More precisely, if $G$ is a group generated by a set of cardinality $\kappa$, then $G$ is a homomorphic image of every free group of rank $\kappa$ or more. |
More precisely, if $G$ is a group generated by a set of cardinality $\kappa$, then $G$ is a homomorphic image of every free group of rank $\kappa$ or more. |
|
|
| The \PMlinkname{Nielsen-Schreier Theorem}{NielsenSchreierTheorem} states that every \PMlinkname{subgroup}{Subgroup} of a free group is itself free. |
The \PMlinkname{Nielsen-Schreier Theorem}{NielsenSchreierTheorem} states that every \PMlinkname{subgroup}{Subgroup} of a free group is itself free. |
|
|
| \section*{Construction} |
\section*{Construction} |
|
|
| For any set $A$, the following construction gives a free group of rank $|A|$. |
For any set $A$, the following construction gives a free group of rank $|A|$. |
|
|
| Let $A$ be a set with elements $a_{i}$ for $i$ in some index set $I$. |
Let $A$ be a set with elements $a_{i}$ for $i$ in some index set $I$. |
| We refer to $A$ as an \emph{alphabet} and the elements of $A$ as \emph{letters}. |
We refer to $A$ as an \emph{alphabet} and the elements of $A$ as \emph{letters}. |
| A \emph{syllable} is a symbol of the form $a_{i}^n$ for $n \in \mathbb{Z}$. |
A \emph{syllable} is a symbol of the form $a_{i}^n$ for $n \in \mathbb{Z}$. |
| It is customary to write $a$ for $a^1$. Define a \emph{word} to be a finite sequence of syllables. For example, |
It is customary to write $a$ for $a^1$. Define a \emph{word} to be a finite sequence of syllables. For example, |
| $$ a_2^3a_1a_4^{-1}a_3^2a_2^{-3}$$ |
$$ a_2^3a_1a_4^{-1}a_3^2a_2^{-3}$$ |
| is a five-syllable word. Notice that there exists a unique \emph{empty word}, i.e., the word with no syllables, usually written simply as $1$. |
is a five-syllable word. Notice that there exists a unique \emph{empty word}, i.e., the word with no syllables, usually written simply as $1$. |
| Denote the set of all words formed from elements of $A$ by $\WA$. |
Denote the set of all words formed from elements of $A$ by $\WA$. |
|
|
| Define a binary operation, called the product, on $\WA$ by concatenation of words. To illustrate, if $a_2^{3}a_1$ and $a_1^{-1}a_3^{4}$ are elements of $\WA$ then their product is simply $a_2^{3}a_1a_1^{-1}a_3^{4}$. |
Define a binary operation, called the product, on $\WA$ by concatenation of words. To illustrate, if $a_2^{3}a_1$ and $a_1^{-1}a_3^{4}$ are elements of $\WA$ then their product is simply $a_2^{3}a_1a_1^{-1}a_3^{4}$. |
| This gives $\WA$ the structure of a monoid. |
This gives $\WA$ the structure of a monoid. |
| The empty word $1$ acts as a \PMlinkname{right and left identity}{LeftIdentityAndRightIdentity} in $\WA$, and is the only element which has an inverse. In order to give $\WA$ the structure of a group, two more ideas are needed. |
The empty word $1$ acts as a \PMlinkname{right and left identity}{LeftIdentityAndRightIdentity} in $\WA$, and is the only element which has an inverse. In order to give $\WA$ the structure of a group, two more ideas are needed. |
|
|
| If $v=u_1a_i^0u_2$ is a word where $u_1,u_2$ are also words and $a_i$ is some element of $A$, an \emph{elementary contraction of type I} replaces the occurrence of $a^0$ by $1$. Thus, after this type of contraction we get another word $w=u_1u_2$. If $v=u_1a_i^pa_i^qu_2$ is a word, an \emph{elementary contraction of type II} replaces the occurrence of $a_i^pa_i^q$ by $a_i^{p+q}$ which results in $w=u_1a_i^{p+q}u_2$. In either of these cases, we also say that $w$ is obtained from $v$ by an elementary contraction, or that $v$ is obtained from $w$ by an elementary expansion. |
If $v=u_1a_i^0u_2$ is a word where $u_1,u_2$ are also words and $a_i$ is some element of $A$, an \emph{elementary contraction of type I} replaces the occurrence of $a^0$ by $1$. Thus, after this type of contraction we get another word $w=u_1u_2$. If $v=u_1a_i^pa_i^qu_2$ is a word, an \emph{elementary contraction of type II} replaces the occurrence of $a_i^pa_i^q$ by $a_i^{p+q}$ which results in $w=u_1a_i^{p+q}u_2$. In either of these cases, we also say that $w$ is obtained from $v$ by an elementary contraction, or that $v$ is obtained from $w$ by an elementary expansion. |
|
|
| Call two words $u,v$ equivalent (denoted $u \sim v$) if one can be obtained from the other by a finite sequence of elementary contractions or expansions. This is an equivalence relation on $\WA$. Let $\FA$ be the set of equivalence classes of words in $\WA$. Then $\FA$ is group under the operation $$[u][v] = [uv]$$ |
Call two words $u,v$ equivalent (denoted $u \sim v$) if one can be obtained from the other by a finite sequence of elementary contractions or expansions. This is an equivalence relation on $\WA$. Let $\FA$ be the set of equivalence classes of words in $\WA$. Then $\FA$ is group under the operation $$[u][v] = [uv]$$ |
| where $[u] \in \FA$. The inverse $[u]^{-1}$ of an element $[u]$ is obtained by reversing the order of the syllables of $[u]$ and changing the sign of each syllable. For example, if $[u] = [a_1a_3^{2}]$, then $[u]^{-1} = [a_3^{-2}a_1^{-1}]$. |
where $[u] \in \FA$. The inverse $[u]^{-1}$ of an element $[u]$ is obtained by reversing the order of the syllables of $[u]$ and changing the sign of each syllable. For example, if $[u] = [a_1a_3^{2}]$, then $[u]^{-1} = [a_3^{-2}a_1^{-1}]$. |
|
|
| It can be shown that $\FA$ is a free group freely generated by the set $\{[x]\mid x\in A\}$. Moreover, a group is free if and only if it is isomorphic to $\FA$ for some set $A$. |
It can be shown that $\FA$ is a free group freely generated by the set $\{[x]\mid x\in A\}$. Moreover, a group is free if and only if it is isomorphic to $\FA$ for some set $A$. |
