I have a set $P$ of permutations of size $s := |P|$.
By repeated application of those permutations I can generate $m$ permutations(or reach $m$ states?) that constitute the set $M$.
I am unable to generate the same $m$ permutations with any proper subset of $P$.
But I wonder if there is a subset $X$ of $M$ with $|x| < s$ that can generate $M$.
If we were talking about a vector space I could use the Steinitz exchange lemma to proof that there can be no base spanning the wholes space smaller than an existing base with linearly independent vectors. But things are quite different with a permutation group, e.g. the permutations do not commute. How can I prove that my "group base" is minimal?
Let $n\ge4$. The symmetric group $S_n$ is generated by the $(n-1)$-element set $P=\{(1\ 2),(1\ 3),\dots,(1\ n)\}$ and by no proper subset of $P$, but the $2$-element set $X=\{(1\ 2),(1\ 2\ 3\ \dots n)\}$ also generates $S_n$.