0
$\begingroup$

Let $F(S)$ be the free group generated by the set $S$ with $|S|=n$. I need to show that there is no generating set $T$ of $F(S)$ with $|T|<n$.


So far I noticed that if $|T|$ generated $F(S)$, then we could use a surjective map $\phi:S\to T$. Due to the universal property, this extends to a homomorphism $\phi:F(S)\to F(S)$ with nontrivial kernel. Then $F(S)=\langle \phi(S)\mid\ker \phi\rangle$.

When showing the existence of free groups, one gets that $F(S)=\langle S\mid\_ \ \rangle$. But I don't know how to show that this gives a contradiction.

$\endgroup$
  • $\begingroup$ Abelianize, tensor with $\otimes_{\mathbb{Z}}\mathbb{Q}$, and use your linear algebra. $\endgroup$ – user553213 Apr 21 '18 at 14:45
  • $\begingroup$ @deyore Shoudn't this be something which follows relatively easily from the definition? My course didn't even introduce tensor products so far. $\endgroup$ – user506844 Apr 21 '18 at 15:03
  • $\begingroup$ You are right. It is the same I said above, but let me use other language (which you can also compare to the answer below, which is the same thing). The idea is to first forget about the order of the letters in the words. This is just mapping to an Abelian group. The largest is the Abelianization. In the answer below they picked a vector space under addition. Once you have an Abelian group, you can see the words as linear combinations of the letters with integer coefficients. Then change the coefficients from the integers to a field. I replaced integers for rationals. In the answer below ... $\endgroup$ – user553213 Apr 21 '18 at 15:17
  • $\begingroup$ ... the coefficients became the field $\mathbb{Z}/2\mathbb{Z}$. Once you have done that, the problem reduces to the same question in a vector space, which you are familiar with. $\endgroup$ – user553213 Apr 21 '18 at 15:18
  • $\begingroup$ @deyore Why do I need to replac the coefficients? In the answer below why couldn't I map to $\mathbb Z^n$? $\endgroup$ – user506844 Apr 21 '18 at 15:38
1
$\begingroup$

At the risk of being accused of completely ignoring your approach, here is a solution that comes directly from the definition of a free group. In one of your comments, you said you were looking for a solution that comes directly from the definition. But even so, this is essentially the same solution as J.-E. Pin's, and as the solution suggested by by deyore in comments.

According to the definition of $F(S)$, for any group $G$, any map $S \to G$ extends uniquely to a homomorphism $F(S) \to G$. So there is a bijection between the set of maps $S \to G$ and the set of homomorphisms $F(S) \to G$.

So let $G$ be the cyclic group of order $2$. Then the number of maps from $S$ to $G$ is $2^{|S|}$. On the other hand, if $F(S)$ is generated by $T$, then any homomorphism from $F(S)$ to $G$ is uniquely determined by the images of the elements in $T$, and there are at most $2^{|T|}$ possible images, so $2^{|T|} \le 2^{|S|}$ and hence (since $S$ is finite), $|T| \le |S|$.

$\endgroup$
  • $\begingroup$ thx, i like that $\endgroup$ – user506844 Apr 21 '18 at 16:32
2
$\begingroup$

Hint. Let $F_n$ be a free group with $n$ generators $a_1, \ldots, a_n$. Let $h: F_n \to (\mathbb{Z}/2\mathbb{Z})^n$ be the map defined by $h(a_i) = (0, \ldots, 0, 1, 0, \ldots, 0)$, where the unique $1$ occurs in $i$-th position. Verify that $h$ extends uniquely to a surjective group morphism. Now suppose that $F_n$ admits $m < n$ generators $g_1, \ldots, g_m$. Then $h(g_1), \ldots, h(g_m)$ would generate $(\mathbb{Z}/2\mathbb{Z})^n$. Is that possible?

$\endgroup$
  • $\begingroup$ Why do you give me a hint which completely ignores my approach? $\endgroup$ – user506844 Apr 21 '18 at 15:13
  • 1
    $\begingroup$ @J.Doe oh dear, the sheer impertinence of J.-E.-Pin of providing you with a simple and elegant solution to your problem! I hope he apologizes ; ) $\endgroup$ – Olivier Bégassat Apr 21 '18 at 15:30
  • $\begingroup$ @OlivierBégassat I hope so too. This really annoys me. For some reason on this site the asker is to required to include his thoughts on the problem or the question will get tons of downvotes and closed. But then these thoughts get completely ignored. $\endgroup$ – user506844 Apr 21 '18 at 15:44
  • 2
    $\begingroup$ @J.Doe sounds awful. $\endgroup$ – Olivier Bégassat Apr 21 '18 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy