Ytukyg

Let $F_n$ be the free group on $n$ letters. Let $S={s_1,s_2,ldots,s_n}$ be a set of $n$ elements of $F_n$.
Is there any way to prove that $S$ is in fact a free basis for $F_n$ without using the Nielsen transformations?

Sure, $S$ induces a surjective map $phi: Fto 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 $Fto 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_iin T$ or $a_i^{-1}in T$.

We'll define a map from $g:Tto S_{n+1}$ which induces a map $G:Fto S_{n+1}$ which sends $w$ to a nonidentity permutation. For each $tin 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 $iin A_t$ and $sigma(j+1)=j$ for $jin B_t$. This is possible, since $i+1ne j$ for any $iin A_t$ and $jin 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$. $quadblacksquare$

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 $kerphi ne 1$. Then there exists $win kerphi$ with $wne 1$. Since $F$ is residually finite, there exists $alpha : Fto G$ with $G$ finite and $alpha (w)ne 1$. Then $alphacirc phi^n$ are pairwise distinct homomorphisms from $F$ to $G$ for all $nin 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 $alphacirc phi^n$ precisely when $n> i$. Thus the kernels of the maps $alphacircphi^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. $quadblacksquare$