I am studying Nielsen & Chuang's book. In the appendix, they prove a little lemma that if a set $\langle g_1, g_2,...,g_l \rangle$ generates a group $G$, then the size of this set would at most $\log(|G|)$. A short proof is also presented there (screenshot attached).
I don't understand the part why $fg \notin \langle g_1, g_2,...,g_l \rangle$. Is there any other proof of this lemma? Or could you please explain this to me?
First of all note that they are assuming that $G$ is finite.
$f$, and hence $f^{-1}$, belongs to $H=<g_{1},...,g_{l}>$. Thus, if, by contradiction, $fg\in H$, then (since $H$ is a subgroup) $(f^{-1})(fg)$ belongs to $H$, that is, $g\in H$ (a contradiction).
What the proof says is that if you take and element $g_{l+1}\in G$ outside $H$, then any distinct $f_{1},f_{2}\in H$ give rise of a distinct elements $f_{1}g_{l+1},f_{2}g_{l+1}\notin H$ (why they distinct?) of $<H,g_{l+1}>=<g_{1},...,g_{l},g_{l+1}>$, which contains $H$. Consequently, $<H,g_{l+1}>$ is of order at least $2\cdot|H|$.
Conclusion. Start from any non-trivial element $g_{1}\in G$, and denote $H_{1}=<g_{1}>$ (if $G=1$ then $<\emptyset>=G$). If $H_{1}=G$ we are done. Else continue by induction to find a generating set $\{g_{1},...,g_{n}\}$ for $G$ such that $2^{n}\leq|G|$.