A generating set of cardinality $n$ in the free group $F_n$ is a free basis.

Poster jgon has presented notions that lie indeed at the heart of the matter. A slight variation in the arguments given above can be presented as follows:

Lemma. Let $G$ be a finitely generated group and $n \in \mathbb{N}^*$ arbitrary. Then the set of subgroups of $G$ of index $n$ is finite.

Proof: We shall write $\Sigma_{n}$ for the symmetric group of degree $n$; for natural numbers $r, s$ the notation $[r, s]$ refers to the interval induced by the natural order on $\mathbb{N}$; for $H \leqslant G$ we will use $(G/H)_{s}$ to denote the quotient of set $G$ by the left congruence modulo $H$.

Set $\mathscr{S}=\{H \leqslant G\ |\ |G:H|=n\}$ and for each $H \in \mathscr{S}$ introduce $\Phi_H=\{\varphi \in \mathrm{Isom}_{\mathrm{Ens}}((G/H)_{s}, [1,n])\ |\ \varphi(H)=1\}$; it is not difficult to see that $\Phi_{H} \neq \varnothing$ for every $H \in \mathscr{S}$, hence $$\prod_{H \in \mathscr{S}} \Phi_{H} \neq \varnothing$$ and we can thus fix a certain (yet arbitrary) $$\theta \in \prod_{H \in \mathscr{S}} \Phi_{H}$$

which is simply put a family of set-isomorphisms (i.e. mere bijections, that is what isomorphisms are in the category of sets) between the set of left congruence classes modulo each $H$ of index $n$ and the interval $[1, n]$, such that the class of $1_{G}$ (which is $H$ itself) is mapped to $1$.

For each $H \in \mathscr{S}$ there is a canonical left action of $G$ on $(G/H)_{s}$, which can be transported via the bijection $\theta_{H}$ to an action of $G$ on $[1, n]$, to be written as $\alpha_{H}$, whose associated morphism of permutation representation we will denote by $\rho_{H} \in \mathrm{Hom}_{\mathrm{Gr}} (G, \Sigma_{n})$. By construction, $\theta_{H}$ is an isomorphism between the left $G$-sets $(G/H)_{s}$ and $[1, n]$ (the latter given by $\alpha_{H}$ of course), hence $$H=\mathrm{Stab}_{\alpha_{H}} 1 \tag{1}$$ From this we infer that the mapping

$$\mathscr{S} \to \mathrm{Hom}_{\mathrm{Gr}}(G, \Sigma_n) \\ H \mapsto \rho_H \tag{2}$$

is injective (if $K, H \in \mathscr{S}$ are such that $\rho_{H}=\rho_{K}$, this is then equivalent to $\alpha_H=\alpha_K$ and relation (1) applies).

Fixing $S \subseteq G$ to be a finite generating set, one easily sees that the restriction mapping $$\mathrm{Hom}_{\mathrm{Gr}}(G, \Sigma_n) \to \mathrm{Hom}_{\mathrm{Ens}}(S, \Sigma_n) \\ f \mapsto f_{| S} \tag{3}$$ is also injective (two morphisms that agree on a generating system are equal). The injectivity of maps (2) and (3) means that $|\mathscr{S}| \leqslant |\mathrm{Hom}_{\mathrm{Ens}}(S, \Sigma_n)|=\left|\Sigma_n^S\right|=(n!)^{|S|}$; as $S$ is by hypothesis finite (more explicitly, by hypothesis such an $S$ certainly exists), then $(n!)^{|S|} \in \mathbb{N}$ and therefore equally $|\mathscr{S}| \in \mathbb{N}$, $\mathscr{S}$ being thus finite (the implicit set-theoretical conception being that natural numbers are precisely the finite cardinal numbers according to the Bourbaki presentation of Set Theory). $\Box$

For the sake of pure contemplation, may we also present an

Alternative proof: Given arbitrary set A we shall denote its symmetric group by $\Sigma(A)=\mathrm{Aut}_{\mathrm{Ens}}(A)$; for arbitrary sets $A, B$ and bijection $\varphi \in \mathrm{Isom}_{\mathrm{Ens}}(A, B)$ one can introduce the mapping $$\Sigma(\varphi): \Sigma(A) \to \Sigma(B)\\ \Sigma(\varphi)(\lambda)=\varphi \circ \lambda \circ \varphi^{-1}$$

The correspondence between these objects actually implements a functor (from $\mathrm{Iso(Ens)}$ to $\mathrm{Iso(Gr)}$, that is from the core of the category of sets to the corresponding core of the category of groups), so it is easy to infer that $\Sigma(\varphi) \in \mathrm{Isom}_{\mathrm{Gr}}(\Sigma(A), \Sigma(B))$.

For arbitrary $H \leqslant G$ let us denote the normal core of $H$ by $$H_G=\bigcap_{t \in G}tHt^{-1}$$ For the canonical left action of $G$ on the quotient $(G/H)_s$ we shall denote its associated morphism of permutation representation by $\rho_H \in \mathrm{Hom}_{\mathrm{Gr}}(G, \Sigma((G/H)_s))$ and notice that $\mathrm{Ker}(\rho_H)=H_G$. Employing the same notation as before for $\mathscr{S}$, fix an arbitrary $$\varphi \in \prod_{H \in \mathscr{S}} \mathrm{Isom}_{\mathrm{Ens}}((G/H)_s, [1, n])$$

(since cartesian products of nonempty sets are nonempty); finally, define $\theta_H=\Sigma(\varphi_H) \circ \rho_H$ and notice that $\theta_H \in \mathrm{Hom}_{\mathrm{Gr}}(G, \Sigma_n)$ and also that $\mathrm{Ker} \theta_H=H_G$. Also set $$K=\bigcap_{H \in \mathscr{S}} H_G$$

We denote the canonical projection of index $H$ on the direct product (direct power, even) $\Sigma_n^{\mathscr{S}}$ by $p_H$ and we refer to the universality property of direct products to infer the existence of a unique $$\psi \in \mathrm{Hom}_{\mathrm{Gr}}\left(G, \Sigma_n^{\mathscr{S}}\right)$$ such that $p_H \circ \psi=\theta_H$ for all $H \in \mathscr{S}$. It will thus be the case that $$\mathrm{Ker} \psi=\bigcap_{H \in \mathscr{S}} \mathrm{Ker} \theta_H=K$$

If we abbreviate $G/K=G'$ and denote the canonical surjection attached to the quotient of $G$ modulo $K$ by $\sigma \in \mathrm{Hom}_{\mathrm{Gr}}(G, G')$, the fundamental (iso)morphism theorem for groups tells us that there exists a unique $\gamma \in \mathrm{Hom}_{\mathrm{Gr}}\left(G', \Sigma_n^{\mathscr{S}}\right)$ such that $\psi=\gamma \circ \sigma$, and this unique morphism is furthermore injective. As $G'$ is the quotient of a finitely generated group, it itself is finitely generated and thus isomorphic (via $\gamma$) to a finitely generated subgroup of $\Sigma_n^{\mathscr{S}}$.

Let us also recall the following version of the correspondence theorem: in general, for an arbitrary surjective morphism $f \in \mathrm{Hom}_{\mathrm{Gr}}(F, F')$, by considering sets $\mathscr{S}=\{E \leqslant F\ |\ E \geqslant \mathrm{Ker}f \wedge |F:E|=n\}$ respectively $\mathscr{T}=\{H \leqslant F'\ |\ |F':H|=n\}$ and mappings $$\Phi: \mathscr{S} \to \mathscr{T} \\ \Phi(E)=f(E)$$ together with $$\Psi: \mathscr{T} \to \mathscr{S} \\ \Psi(H)=f^{-1}(H)$$

not only are these maps correctly defined but they are mutual inverses (in fact they are isomorphisms of ordered sets, when ordering both $\mathscr{S}$ and $\mathscr{T}$ with inclusion). In our particular case, considering surjection $\sigma$, any subgroup of index $n$ in $G$ automatically includes the kernel of $\sigma$ by construction, so by the correspondence theorem we can infer that $|\mathscr{S}|=|\mathscr{S'}|$, where $\mathscr{S'}=\{H \leqslant G'\ |\ |G':H|=n\}$.

In other words, we have reduced the claim on subgroups of $G$ to the analogous one for $G'$, and in order to prove this latter claim it will suffice to show that $G'$ is finite. This will be achieved as long as we can establish the next auxiliary result, interesting in and of itself, which we will prove independently. $\Box$

Auxiliary Lemma: let $F$ be a finite group and $\Lambda$ an arbitrary set. Then any finitely generated subgroup $G \leqslant F^{\Lambda}$ is finite.

Proof: For arbitrary set $A$, let us write $\mathscr{Eq}(A)$ for the set of all equivalence relations on $A$ and $\Delta_A$ for the diagonal of $A$ (the relation of equality on $A$); for arbitrary $R \in \mathscr{Eq}(A)$ let us denote the canonical surjection attached to $R$ by $\sigma_R \in \mathrm{Hom}_{\mathrm{Ens}}(A, A/R)$. If $f \in \mathrm{Hom}_{\mathrm{Ens}}(A, B)$ let $\mathrm{E}_f=(f \times f)^{-1}(\Delta_B)$ denote the canonical equivalence induced by $f$.

We shall say that $R$ is a finite equivalence if the quotient set $A/R$ is finite; we go on to remark that if $I$ is a finite and nonempty index set and $R \in \mathscr{Eq}(A)^I$ is a family of finite equivalences, then $$\bigcap_{i \in I} R_i \in \mathscr{Eq}(A)$$ is also finite (finite nonempty intersections of finite equivalences are again finite equivalences): if $\tau_i=\sigma_{R_i}$ for all $i \in I$ and $$p_i: \prod_{j \in I} A/R_j \to A/R_i$$ is the canonical projection of index $i$ of the cartesian product, then by the universality property there will exist a unique $$\rho: A \to \prod_{i \in I} A/R_i$$ such that $p_i \circ \rho=\tau_i$ for all $i \in I$. By construction, we have $$\mathrm{E}_{\rho}=\bigcap_{i \in I} \mathrm{E}_{\tau_i}=\bigcap_{i \in I} R_i=S$$

(the last equality serving as the definition of object $S$) and by the fundamental (iso)morphism theorem for sets we infer the existence of a unique map $$\varphi: A/S \to \prod_{i \in I} A/R_i$$ such that $\rho=\varphi \circ \sigma_S$, map which is necessarily injective. Hence, owing to this injectivity we can claim that $$|A/S| \leqslant \left|\prod_{i \in I} A/R_i \right|=\prod_{i \in I} |A/R_i|$$

As finite products of finite cardinals (i.e. natural numbers) are finite cardinals and cardinals less or equal to finite ones are themselves finite, it follows that $S$ is also a finite equivalence, justifying our claim.

Having completed preparations, we move on to the core of the problem and define for each $x \in F^{\Lambda}$ the equivalence $\Gamma_x \in \mathscr{Eq}(\Lambda)$ given by $$\lambda \Gamma_x \mu \Longleftrightarrow x_{\lambda}=x_{\mu}$$

It is immediate to notice that $\Gamma_x$ occurs as the canonical equivalence induced by the map

$$\Lambda \to F \\ \lambda \mapsto x_{\lambda}$$

map which induces an injective quotient map $\Lambda/{\Gamma_x} \to F$; as $F$ is finite by hypothesis, we gather that $\Gamma_x$ is a finite equivalence.

Next, fix a certain (yet arbitrary) finite nonempty generating system $S \subseteq G$, the existence of which is guaranteed by hypothesis and define $$\Delta=\bigcap_{s \in S} \Gamma_s$$

a finite equivalence as we have explained above. Let us remark the properties

$$\Gamma_x \cap \Gamma_y \subseteq \Gamma_{xy} \tag{1}$$ $$\Gamma_x=\Gamma_{x^{-1}} \tag{2}$$ $$\Gamma_{1_{F^{\Lambda}}}=\Lambda \times \Lambda \tag{3}$$

valid for all $x, y \in F^{\Lambda}$. Upon introducing subset $$E=\{x \in F^{\Lambda}\ |\ \Delta \subseteq \Gamma_x \}$$ then by relation (3) $E$ is nonempty (it contains the unit), by (1) it is multiplicatively stable and by (2) it is closed with respect to inverses, which in other words means that $E \leqslant F^{\Lambda}$.

Let us note that by definition $S \subseteq E$, hence $G=\langle S \rangle \leqslant E$; therefore, to prove our claim it will suffice to show that $E$ is finite. To this end, we fix a certain complete and independent system of representatives for $\Delta$ in $\Lambda$, say $M$; as $|M|=|\Lambda/{\Delta}|$ and $\Delta$ is a finite equivalence, $M$ is a finite set. Let

$$p_M: F^{\Lambda} \to F^{M} \\ p_M(x)=x_{|M}=(x_{\lambda})_{\lambda \in M}$$

denote the morphism of restriction to $M$ (its construction is also justified by the universality property of direct products) and $f=(p_M)_{|E} \in \mathrm{Hom}_{\mathrm{Gr}}\left(E, F^M\right)$ the restriction of this morphism to $E$. As $F$ and $M$ are both finite, it will suffice to establish the injectivity of $f$ in order to conclude the finiteness of $E$.

Let $u \in \mathrm{Ker}f$ and $\lambda \in \Lambda$ be arbitrary; there must exist a (unique!) $\mu \in M$ such that $\lambda \Delta \mu$, and by definition of $E$, as $u \in E$ it follows that $\lambda \Gamma_u \mu$, in other words that $u_{\lambda}=u_{\mu}$; however, since $f(u)=u_{|M}=(1_F)_{\mu \in M}$ we conclude that $u_{\lambda}=1_F$ for any index $\lambda \in \Lambda$, whence $u=1_{F^{\Lambda}}$ and thus $\mathrm{Ker}f$ is trivial. $\Box$

As a remark, this lemma can easily be generalised to monoids: in an arbitrary direct power of a finite monoid, any finitely generated submonoid is finite.

Theorem. If group $G$ is finitely generated and residually finite then it is Hopfian (i.e. any surjective endomorphism is an automorphism).

Proof: Let $f \in \mathrm{End}_{\mathrm{Gr}}(G)$ be surjective and set $$\hat{f}, \check{f}: \mathscr{P}(G) \to \mathscr{P}(G) \\ \hat{f}(X)=f(X)\\ \check{f}(X)=f^{-1}(X)$$ The surjectivity entails that $\hat{f} \circ \check{f}=\mathbf{1}_{\mathscr{P}(G)}$, and thus $\check{f}$ is injective.

It is an elementary fact (universality properties of quotient maps in the category of sets) that for any $H \leqslant G$ $f$ induces a canonical bijection between the quotient sets $(G/f^{-1}(H))_s$ and $(G/H)_{s}$ (this is where the assumption of surjectivity is again indispensable). Therefore, if in continuity with the above notation for arbitrary $n \in \mathbb{N}$ we introduce $\mathscr{S}_n=\{H \leqslant G\ |\ |G:H|=n|\}$ we then have that $\check{f}(\mathscr{S}_n) \subseteq \mathscr{S}_n$; the lemma above tells us that $\mathscr{S}_n$ is finite which together with this inclusion and the injectivity of $\check{f}$ suffice to establish the equality $$\check{f}(\mathscr{S}_n)=\mathscr{S}_n \tag{1}$$

Furthermore, note that for any $H \leqslant G$ we have $\mathrm{Ker}f \leqslant f^{-1}(H)$ so in particular for any $n \in \mathbb{N}$ such that $\mathscr{S}_n \neq \varnothing$ it is the case that $$\mathrm{Ker}f \leqslant \bigcap_{H \in \mathscr{S}_n}\ f^{-1}(H)=\bigcap_{H \in \mathscr{S}_n}\ \check{f}(H)=\bigcap \mathscr{S}_n \tag{2}$$ (the axiomatic system I guide myself by does not allow for empty intersections).

Introducing $M=\{n \in \mathbb{N}\ |\ \mathscr{S}_n \neq \varnothing\}$ (about which we note that $1 \in M$) and $$\mathscr{T}=\bigcup_{n \in \mathbb{N}}\ \mathscr{S}_n=\bigcup_{n \in M} \mathscr{S}_n$$

the residual finiteness property can be expressed as

$$\{1_G\}=\bigcap \mathscr{T}=\bigcap_{n \in M} \bigcap \mathscr{S}_n \tag{3}$$

Relation (2) means that $\mathrm{Ker}f \leqslant \bigcap \mathscr{S}_n$ for any $n \in M$, thus by (3) $\mathrm{Ker}f \leqslant \{1_G\}$ and $f$ is injective. $\Box$

Sure, $S$ induces a surjective map $\phi: F\to F$, defined by sending a free basis to $S$. To show $S$ is a free basis for $F$, it therefore suffices to show that any surjective map $F\to F$ is in fact an isomorphism.

This is essentially the statement that finitely generated free groups are Hopfian.

I'll essentially copy over the proofs needed to arrive at this conclusion given on the groupprops wiki. None of them use Nielsen transformations, or anything similar. They are what I'd consider "algebraic" rather than "combinatorial."

Lemma. Free groups are residually finite, i.e. for any nonidentity element, there is a finite index normal subgroup not containing that element, or in other words, there for any nonidentity element from the group to a finite group which is not the identity on that element.

Proof:

Let $F$ be the free group, with some free basis $T$. Let $w=a_na_{n-1}\cdots a_2a_1$ be a nonidentity reduced word, with $a_i\in T$ or $a_i^{-1}\in T$.

We'll define a map from $g:T\to S_{n+1}$ which induces a map $G:F\to S_{n+1}$ which sends $w$ to a nonidentity permutation. For each $t\in T$, let $A_t=\{i : t=a_i\}$ and $B_t=\{j : t=a_j^{-1}\}$. Now for each $t$, if $A_t=B_t=\varnothing$, define $f(t)=1$. Otherwise, if one of $A_t$ or $B_t$ is nonempty, choose a permutation $\sigma$ such that $\sigma(i)=i+1$ for $i\in A_t$ and $\sigma(j+1)=j$ for $j\in B_t$. This is possible, since $i+1\ne j$ for any $i\in A_t$ and $j\in B_t$, since that would mean that the word wasn't reduced, and any partial injection can be extended to a bijection. Then observe that $G(w)$ sends $1$ to $n$ by construction. Thus $G$ is not the identity on $w$. $\quad\blacksquare$

Now we can prove that finitely generated free groups are Hopfian, i.e. that any surjective endomorphism is an automorphism. In fact this proof shows that any finitely generated, residually finite group is Hopfian.

Proof:

Let $F$ be a finitely generated, residually finite group. Let $\phi : F \to F$ be a surjective endomorphism. Assume for contradiction that $\ker\phi \ne 1$. Then there exists $w\in \ker\phi$ with $w\ne 1$. Since $F$ is residually finite, there exists $\alpha : F\to G$ with $G$ finite and $\alpha (w)\ne 1$. Then $\alpha\circ \phi^n$ are pairwise distinct homomorphisms from $F$ to $G$ for all $n\in \Bbb{N}$, since if we let $w_i$ be elements such that $\phi^i(w_i)=w$ using the surjectivity of $\phi$, then we have that $w_i$ is in the kernel of $\alpha\circ \phi^n$ precisely when $n> i$. Thus the kernels of the maps $\alpha\circ\phi^n$ are all distinct.

However, since $G$ is finite and $F$ is finitely generated, if $F$ has a generating set with $m$ elements, there are at most $m^{|G|}$ homomorphisms from $F$ to $G$. Contradiction. $\quad\blacksquare$