# Does a countable set generate a countable group?

Let $G$ be a group and let $A\subseteq G$ be infinite. Do $A$ and $\left< A\right>$ have the same cardinality?

## 3 Answers

Yes. Any element of $\langle A\rangle$ is a "word" in the alphabet $A\cup\{a^{-1}\mid a\in A\}$, which is again a set of size $|A|$. Any word is a finite string of symbols from this alphabet (but of course, different words may give the same element of $\langle A\rangle$), so $\langle A\rangle$ has size at most $|A|^{<\omega}$, which again is $|A|$. This gives $|A|$ as an upper bound. Of course, every element of $A$ is in this group, so it has size at least $|A|$, and equality follows.

This uses (some amount of) the axiom of choice, though. Without it, we cannot prove for an arbitrary infinite set $A$ that $|A|^{<\omega}=|A|$. Choice is not needed to prove this equality in concrete cases, such as if $|A|=|\mathbb N|$ or $|A|=|\mathbb R|$. There is however another, somewhat subtler, use of choice in the proof: Many different words may be equal, which is why a priori the number of words is just an upper bound, because this shows that $\langle A\rangle$ is a quotient of the set of words, under some equivalence relation. Without choice, a quotient of a set may even be larger than the set. I point this out here. (In that answer I link to a nice talk you may enjoy on this issue, by Mike Oliver.)

• This is a very nice answer. – Alexander Gruber Apr 9 '13 at 1:44

Let me give a proof of the statement in the title which has a different flavour from the other proofs. It certainly doesn't use choice, however it does use more group theory than the other answers (most notable, it uses the fact that subgroups of free groups are free).

Let $G$ be a countably-generated group, $G=\langle A\rangle$. We want to show that $G$ is countable. (I shall use "countable" to mean "infinite and countable", but it is difficult not to see how this result implies that finitely generated groups are countable also.)

To prove that $G$ is countable it suffices to prove that the free group on the generators $A$ is countable (can you see why this is?). This is a well-known result, and I shall give a relatively full proof. For more details, the book Combinatorial group theory by Magnus Karrass and Solitar will provide better detail/background. (There also exist topological proofs, but I do not know any good the references. Perhaps John Meier's book, or Pierre de la Harpe's?).

Write $F_{\infty}$ then for the free group on countably many generators.

Let $\langle a, b\rangle$ generate the free group on two generators.

Proposition: $H:=\langle a^{-i}ba^i, i\in\mathbb{Z}\rangle$ is free and infinitely generated, $H\cong F_{\infty}$.

This clearly proves the theorem.

Proof: As subgroups of free groups are free, $H$ is free. It therefore suffices to prove that the set $\{a^{-i}ba^i\}$ is a minimal generating set.

It is an important fact about free groups that if $\langle S\rangle=F$ and $F$ is $n$-generated then there exists an $n$-element subset of $S$ which generates $F$. Thus, if we can show that every element of $\{a^{-i}ba^i\}$ is needed to generate $H$ then we are done.

We shall write $W(x, y)$ to mean a word in $x$ and $y$. For example, if $W(x, y)=x^2y^2$ then $W(a^{-1}ba, a^{-2}ba^2)=(a^{-1}ba)^2(a^{-2}ba^2)^2=(a^{-1}b^2a)(a^{-2}b^2a^2)=a^{-1}b^2a^{-1}b^2a^2$.

The trick is to count the number of $b$-terms. Define the $b$-length of a word over $\{a^{-i}ba^i\}$ to be the number of $b$-terms in the word. For example, $b^2a^{-1}b^{-1}a$ has $b$-length $3$. You can think of it as taking the sum of the absolute values of the $b$-exponents: $|2|+|-1|=2+1=3$.

To see that every element of $\{a^{-i}ba^i\}$ is needed, suppose $g:=a^{-j}ba^j$ is not needed. However, $g$ is in $H$, so $g\in\langle a^{-i}ba^i; i\in\mathbb{N}\setminus\{j\} \rangle$=H. Note that the $b$-length of $g$ is one, while in general the $b$-length of $W(\{a^{-i}ba^i\})$ is simply the length of the word $W$. Thus, as $g$ has $b$-length one it is not in $\langle a^{-i}ba^i; i\in\mathbb{N}\setminus\{j\} \rangle$, a contradiction.

I rarely can be sure that my proofs are correct. However I can't say this trial is not correct:

Let $$C=A\cup A^{-1}\cup\{1\}$$

then $$\left< A\right>=\bigcup_{n\in \Bbb N}C^n$$ $$\Rightarrow|\left<A\right>|\le|\Bbb N||C|=|\Bbb N||A|=|A|$$ $$\Rightarrow |\left<A\right>|=|A|$$

• I am not sure what you mean by $|\mathbb N||C^n|$ in the previous to last line, since this depends on $n$ now while nothing else does. Maybe you meant $|\mathbb N|\sup_n|C^n|$, from which the argument can proceed now as written. – Andrés E. Caicedo Apr 9 '13 at 0:28
• thanks. $n$ is not needed. because $C$ is infinite, $C\times C\times C\times...\times C$ has the same size as $C$ (as $A$). So $C^n=CC...C$ has size $|C|$ too. now $sup_n |C^n|=sup_n |C|=|C|$. I think at most a countable version of Axiom of Choice is used. – user59671 Apr 9 '13 at 1:52