Proof of Existence of a Free Group (one particular step in the process)

Question

I'm working through a lemma which is used to prove the existence of a free group on a set $S$.

The setting is this:

$S$ is a set, and $G$ is a group, and $f:S\to G$ is a map such that the image of $f$ generates $G$. That is, every element of $G$ can be written in the form $f(s_{1})^{e_1}\dots f(s_{n})^{e_n}$ where $s_{i}\in S$ and $e_{i} = \pm 1$.

The claim I am having difficulty verifying (which appears in a lemma) is this:

If $S$ is infinite, then the cardinality of $G$ is no larger than the cardinality of $S$.

To verify this, I would need an injection from $G$ to $S$, or a surjection from $S$ to $G$.

Intuitively, I think I see it, going from $S$ to $f(S)$ cannot increase the size, since $f$ is a function, and going from $f(S)$ to $G$ cannot get any larger since elements of $G$ can be mapped to finite sequences of elements of $f(S)$. But I can't seem to make this precise.

Answer 1

Let $A=f[S]$; clearly $|A|\le|S|$. Let $B=A\cup\{a^{-1}:a\in A\}$; then $|B|\le|S|+|S|=|S|$, since $S$ is infinite. Every member of $G$ is a product of finitely many elements of $B$, so $|G|$ is at most the number of finite tuples of elements of $B$. For each $n\in\Bbb N$ there are $|B|^n$ $n$-tuples of elements of $B$. $|B|^n\le|S|^n=|S|$, since $S$ is infinite. Finally,

$$\left|\bigcup_{n\in\Bbb N}B^n\right|\le|\Bbb N|\cdot|S|=\omega\cdot|S|=|S|\;,$$

the last step again following from the hypothesis that $S$ is infinite.

Answer 2

I think this lemma needs a slightly more sophisticated approach rather that trying to directly construct an injection or surjection in the appropriate direction. The important information is that the size of an infinite set $S$ is the same as the size of the set of finite sequences of elements of $S$. This follows from the fact that for an infinite set $S$ and every $n\in\mathbb N$, $S^n$ has the same size as $S$. This is due to Cantor.

The set of all finite sequences of elements of $S$ is $\bigcup_{i=0}^\infty S^n$. This is the union of countably many sets of the same size as $S$ (and one set with one element, $S^0$, which only contains the empty sequence of length $0$) and therefore also has the same size as $S$.

Similarly, the set of all finite sequences consisting of $-1$ and $1$ is countable.
Hence the set $P$ of all pairs $(x,y)$ where $x$ is a finite sequence of elements of $S$ and $y$ is a finite sequence consisting of $-1$ and $1$ of the same length has the same size as the infinite set $S$.

In your question you define a surjective function that assigns to each pair $(x,y)\in P$ an element of the group $G$.
Since $P$ has the same size as $S$, $G$ has cardinality not bigger than that of $S$.