# free groups: $F_X\cong F_Y\Rightarrow|X|=|Y|$

I'm reading Grillet's Abstract Algebra. Let $F_X$ denote the free group on the set $X$. I noticed on wiki the claim $$F_X\cong\!\!F_Y\Leftrightarrow|X|=|Y|.$$ How can I prove the right implication (find a bijection $f:X\rightarrow Y$), i.e. that the rank is an invariant of free groups?

I am hoping for a simple and short proof, having all the tools of Grillet at hand. Rotman (Advanced Modern Algebra, p.305) proves it only for $|X|<\infty$, Bogopolski's (Introduction to Group Theory, p.55) proof seems (unnecessarily?) complicated, and Lyndon & Schupp's (Combinatorial Group Theory, p.1) proof I don't yet understand. It's the very first proposition in the book; in the proof, they say:

The subgroup $N$ of $F$ generated by all squares of elements in $F$ is normal, and $F/N$ is an elementary abelian $2$-group of rank $|X|$. (If $X$ is finite, $|F/N|=2^{|X|}$ finite; if $|X|$ is infinite, $|F/N|=|X|$). $\square$

Is $N:=\langle w^2;w\in F\rangle$? What is an abelian $2$-group? Elementary? What and how does the above quote really prove? I'm guessing a free abelian group on $X$ is $\langle X|[X,X]\rangle\cong\bigoplus\limits_{x\in X} \mathbb{Z}$?

Can an isomorphism $\varphi:F_X\rightarrow F_Y$ not preserve the length of words? At least one letter words?

-
Simpler, look at the abelianization of $F_X$ and $F_Y$, these are groups isomorphic to $\bigoplus_X \mathbb Z$ and $\bigoplus_Y \mathbb Z$, which have ranks $|X|$ and $|Y|$ respectively. So you reduce the problem to the abelian group case. I suspect your reference uses $\mathbb Z_2$ because they perceive the relation to vector spaces as simpler. – Ryan Budney Apr 26 '11 at 17:28
A 2-group is a $p$-group with $p = 2$. An abelian 2-group is essentially a product of some number (perhaps infinitely many) copies of the group $\mathbb{Z}/2\mathbb{Z}$. A free abelian group on $X$ is indeed $\bigoplus_{x \in X} \mathbb{Z}$. – Zhen Lin Apr 26 '11 at 17:29
See Pete L. Clark's comment at mathoverflow.net/questions/17152/… – Jonas Meyer Apr 26 '11 at 17:29
@Zhen Lin: A $2$-group is a group in which every element has order a power of $2$, so an abelian $2$-group is an abelian group that is a $2$-group. The cyclic group of order $4$ is an abelian $2$-group. What you describe ("essentially a product of some number of ocpies of $\mathbb{Z}/2\mathbb{Z}$") is an elementary abelian $2$-group. (An "elementary abelian $p$-group" is an abelian group in which $x^p=1$ for all $x$; assuming the Axiom of Choice, this is equivalent to being a direct sum of copies of $\mathbb{Z}/p\mathbb{Z}$). – Arturo Magidin Apr 26 '11 at 18:31

Yes, $N$ is the subgroup generated by all squares. $N$ is normal in $F$, because if $w^2$ is an element of the generating set for $N$, and $x\in F$, then $xw^2x^{-1} = (xwx^{-1})^2$ is also an element of $N$. So for every $x\in F$ we have $xNx^{-1}\subseteq N$, hence $N$ is normal.

When $p$ is a prime, an abelian $p$-group is simply an abelian group all of whose elements have order a power of $p$ (could be finite or infinite). An elementary abelian $p$-group is an abelian $p$-group in which every element satisfies $a^p = 1$ (and so, every element except for the identity is of order exactly $p$; this is with multiplicative notation, you would have $pa=0$ if you are using additive notation for your group). So the assertion is that $F/N$ is abelian, and the square of every element is the identity.

The fact that the square of every element of $F/N$ is the identity follows because every square is in $N$: if $fN\in F/N$, then $(fN)^2 = f^2N = 1N$. And the fact that $F/N$ is abelian now follows from the well-trod fact that a group in which the square of every element is the identity must be abelian (since $1 = (ab)^2 = a^2b^2$, so $abab=aabb$, hence $ba=ab$ by cancellation).

An elementary abelian $p$-group is always a vector space over $\mathbb{F}_p$, the field with $p$-elements: given $\alpha\in\mathbb{F}_p$, let $a\in\mathbb{Z}$ by any integer mapping to $\alpha$. Then, assuming your group is written additively, define $\alpha\cdot g$ as $\alpha\cdot g= ag$. Since $pg=0$, this is well defined and makes the abelian group into a vector space.

So here, you have that $F/N$ is an abelian $2$-group, and therefore is a vector space over the field of $2$-elements.

In fact, the images of the free generating set $X$ in $F/N$ form a basis for this vector space: since $X$ spans $F$, its images span $F/N$. And if you have a nontrivial linear combination between them, then it must be of the form $$\overline{x_1}+\cdots + \overline{x_n} = \mathbf{0}$$ where $\overline{g}$ is the image of $g\in F$ in the quotient, and $x_1,\ldots,x_n$ are pairwise distinct elements of $X$. But this means that $x_1\cdots x_n\in N$, that is, that it is the square of an element of $F$, and this is easily shown to be impossible.

So $F/N$ is a vector space over $\mathbb{F}_2$, and has a basis of cardinality $|X|$. How many elements does a vector space of dimension $\kappa$ over $\mathbb{F}_2$ have? If $\kappa$ is finite, then it has $2^{\kappa}$ elements. If $\kappa$ is infinite, then it has $\kappa$ elements. So if $X$ is infinite, then $|X|=|F/N|$.

Now suppose that $F_X$ and $F_Y$ are isomorphic. Then the isomorphism maps $N=\langle w^2\mid w\in F_X\rangle$ to $M=\langle z^2\mid z\in F_Y\rangle$, so we get that $F_X/N\cong F_Y/N$. If one of them is finite, then they both are; if one of them is infinite, then they both are. If both are finite, then the cardinality of $F_X/N$ is $2^|X|$, and the cardinality of $F_Y/N$ is $2^|Y|$, and since they are isomorphic groups, then $|X|=|Y|$. If they are both infinite, then $F_X/N$ has cardinality $|X|$, and $F_Y/N$ has cardinality $|Y|$, and since they are isomorphic their cardinalities are the same, so $|X|=|Y|$ as well. This proves the result.

There is a simpler way: the result holds for abelian free groups (tensor up to $\mathbb{Q}$ to reduce to the vector space $K$), and then show that $F_X^{\mathrm{ab}}$ is the free abelian group on $X$.

To answer final question: "word length" depends on the free basis. There is always a choice of basis for $F_Y$ that makes $\varphi$ preserve word length (simply take the basis $\varphi(X)$), but in general it need not. Take $X=\{x_1,x_2\}$, $Y=\{y_1,y_2\}$, and first map $F_X$ to $F_Y$ the obvious way ($x_1\mapsto y_1$, $x_2\mapsto y_2$), and then compose with a suitable inner automorphism of $F_Y$. For example, composing with conjugation by $y_1$ maps $x_1\mapsto y_1$ and $x_2\mapsto y_1y_2y_1^{-1}$. Composing with conjugation by $y_1y_2y_1^{-1}$ makes it even worse: \begin{align*} x_1 &\mapsto (y_1y_2y_1^{-1})y_1(y_1y_2^{-1}y_1^{-1}) = y_1y_2y_1y_2^{-1}y_1^{-1},\\ x_2 &\mapsto (y_1y_2y_1^{-1})y_2(y_1y_2^{-1}y_1^{-1}) = y_1y_2y_1^{-1}y_2y_1y_2^{-1}y_1^{-1}, \end{align*} mapping the two generators to words of length 5 and 7, respectively; of course, you can make it pretty much as bad as you want using this idea.

-
@Arturo Magidin: excellent post. I am especially interested in the part "There is a simpler way". What do you mean by "tensor up to $\mathbb{Q}$ to reduce to the vector space $K$"? I checked Grillet, and the result indeed holds for abelian free groups, since they are free $\mathbb{Z}$-modules. – Leon Apr 26 '11 at 19:18
Is this the correct proof?: $F_X\cong\!\!F_Y$ $\Rightarrow$ $\mathrm{Ab}(F_X)\!=\!\bigoplus_{x\in X}\mathbb{Z}\cong \mathrm{Ab}(F_Y)=\bigoplus_{y\in Y}\mathbb{Z}$ $\Rightarrow$ $|X|=|Y|$? Seems a bit too easy. What did you mean by "show that $F^{ab}_X$ is the free abelian group on X"? Isn't this by definition? – Leon Apr 26 '11 at 19:25
@Leon Lampret: For that proof, you first need to show that the result holds free abelian groups (the implication from $\oplus_{x\in X}\mathbb{Z}\cong \oplus_{y\in Y}\mathbb{Z}$ to $|X|=|Y|$ needs to be proven, it's not immediate; it can be done by going to a quotient which is a vector space, or tensoring up with $\mathbb{Q}$ to get a vector space, and invoking the result for vector spaces). As to showing $F_X^{\rm ab}$ is free on $X$, that means proving that $F_X^{\rm ab}\cong \oplus_{x\in X}\mathbb{Z}$. This could be your definition of "free abelian group", but there are many such. – Arturo Magidin Apr 26 '11 at 20:14
OK, since "free modules over commutative rings have equipolent bases" is already a proposition in Grillet, I'm almost done. But just out of curiosity, what did you mean by tensor up with $\mathbb{Q}$? What do we get with $(\bigoplus_{x\in X}\mathbb{Z})\otimes_\mathbb{Z}\mathbb{Q}$? – Leon Apr 26 '11 at 20:21
@Leon: Tensor products distribute over direct sums (e.g. Prop XVI.2.1 in Lang), and $\mathbb{Z}\otimes_{\mathbb{Z}}\mathbb{Q}\cong\mathbb{Q}$, so you get $\oplus_{x\in X}\mathbb{Q}$, which is a vector space over $\mathbb{Q}$ of dimension $|X|$. – Arturo Magidin Apr 26 '11 at 20:23

The first part of your question is relatively easy to get. say f is the homomorphism between the two free groups then you need to deduce that f induce a bijection (as a function not a homomorphism) between elements of X and a free (no obvious combinations) set of Fy (which of the same cardinality as Y) let us suppose that f(X) is not a free set in Fy i.e there are a1,a2,..ak in (f(X) and f(X)^(-1)) such that a1a2..ak=1 by f-1 you will end up having a relation in Fx which is supposed to be free so you have |Y|<|X| the rest follows..

-
Suppose $F$ is the free group on $x$ and $y$, and $G$ is the free group on $a$ and $b$. Let $f\colon F\to G$ be given by mapping $x$ to $a$ and $y$ to $ab$. Then $f$ does not induce a bijection between the elements of $X=\{x,y\}$ and those of $Y=\{a,b\}$. But $f$ is an isomorphism of free groups, as is easy to verify. – Arturo Magidin Apr 26 '11 at 17:31
@Arturo Magidin If I understand correctly, this answers the last part of my question: isomorphisms $F_X\rightarrow F_Y$ need not preserve the length of words, not even one letter ones. Hmm, trying to prove at the moment, that your $f$ is indeed an isomorphism... – Leon Apr 26 '11 at 17:34
to arturo in your example f is not an isomorphism because you can't get b :) – El Moro Apr 26 '11 at 17:36
@Leon this is a skeched proof of the right implication – El Moro Apr 26 '11 at 17:39
@El Moro: What makes you think you can't get $b$? $b = a^{-1}(ab) = f(x^{-1}y)$. – Arturo Magidin Apr 26 '11 at 17:43