Is the symmetric monoid always generated by a set of the same cardinality as the underlying set (set of least cardinality that it acts faithfully on)?
This seems to hold for finite symmetric monoids.
Does it hold for infinite symmetric monoids too?
For finite groups at least, the following holds.
Let $S_n$ be the symmetric group on $\{1 \cdots n\}$. $S_n$ is generated by the adjacent transpositions. Source. Let's call its set of generators $S(n)$.
Let $M_n$ be the "symmetric monoid" on $\{1 \cdots n\}$. $M_n$ is isomorphic to the family of functions on $\{ 1 \cdots n \}$. I'm not sure what you actually call this thing, maybe the complete monoid?
Anyway, I claim that the following generates $M_n$:
- $S(n)$, the generator of $S_n$.
- $f = (\lambda n \mathop. \max(1, n-1))$ -- the function that decreases the value of each $n$ by $1$ and applies a floor of $1$.
Call the above $M(n)$.
As proof, consider an arbitrary $\varphi \in M_n$.
Suppose $0$ elements are outside $\text{Im}(\varphi)$, then $\varphi$ is generated by $S(n)$ and thus $M(n)$.
Suppose $1$ element is outside $\text{Im}(\varphi)$, then exactly one element in the $\text{Im}(\varphi)$ has a preimage of size 2. We can use a permutation to make the preimage of this element occupy slots $1$ and $2$, combine them together using $f$, and then apply another permutation to fix up the image.
Similarly, in general, we can build each element $a$'s preimage by applying a permutation, invoking $f$ $n-1$ times (where $n$ is $|\text{Im}(a)|$), and then applying another permutation. Chaining these all together gives us $\varphi$. Since permutations are generated by $S(n)$, we are done.
Your proof is right. Re: your question, in fact the result is easier to resolve if the "base set" is infinite: if $X$ is infinite, the monoid of all functions $X\rightarrow X$ has size $2^{\vert X\vert}$ itself, and so cannot possibly be generated by any subset of size $\vert X\vert$ (the submonoid of a monoid $M$ generated by a set $U$ has cardinality $\le\max\{\vert U\vert,\aleph_0\}$).
As an aside, note that your generating set for $M_n$ is optimal in the following sharper sense than mere cardinality: if $X$ generates $M_n$ then the set of onto elements of $X$ must generate $S_n$ (since an element of $S_n$ can't have a non-onto function as a "composant"), and so $X$ must look like [generating set for $S_n$] + [at least one partial function]. Of course, finiteness of the base set is crucial here.