If $X$ is an infinite set, then $|X|=|F(X)|$, where $F(X)$ is the free group on $X$

Question

I am struggling to prove that for an infinite set $|X|=|F(X)|$, where $F(X)$ is the free group on $X$.

I can see the obvious injection $X \to F(X)$ but struggling to see the converse. Any help would be much appreciated!

Answer 1

You need to assume that for an infinite set $X$, $|X|=|X\times X|$. But in fact, the assertion that this holds for any infinite set is equivalent to the Axiom of Choice, which is a theorem of Tarski's; this is what Asaf notes in comments regarding how you need the Axiom of Choice to establish this.

From that assumption it is clear that for every positive integer $n$, $|X^n|=|X|$.

Now, the elements of $F(X)$ are reduced finite sequences of elements of $X$ and their formal inverses (no element appears next to its formal inverse); there are $2|X|=|X|$ one-letter words (the factor of $2$ to account for formal inverses). There are at most $2|X|\times 2|X| = |X|^2 = |X|$ two-letter reduced words (because some combinations will include cancellations). Omitting the factors of $2$ from here on, since they don't matter, there are at most $|X|^3=|X|$ three-letter reduced worlds; etc. For each $n$, there are at most $|X|^n = |X|$ $n$-letter reduced words, since $X$ is infinite. Thus, $F(X)$ contains at most this many elements: $$|X| + |X|^2 + |X|^3 + \cdots = \aleph_0|X| = \max\{\aleph_0,|X|\} = |X|,$$ because $X$ is infinite, so $\aleph_0\leq |X|$.

Thus, $|F(X)|\leq |X|$, and applying Cantor-Bernstein you can conclude that $|F(X)|=|X|$.