1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Uh, forgive me if I'm missing something, but let's consider $\mathbb{N}$. It has cardinality $\beth_0$. The set of all functions from $\mathbb{N}$ to itself has cardinality $\beth_1$, I think. It is as least as large as $2^\mathbb{N}$ because we can consider the indicator functions on $\mathbb{N}$. I think. Again, sorry if I'm missing something obvious. $\endgroup$ Jun 24 at 1:59
  • $\begingroup$ @GregNisbet Holy crud, not sure what happened there - I think I was mixing two thoughts at once. It is true that the infinite case is simpler, but what I wrote was obviously garbage. Fixed! $\endgroup$ Jun 24 at 2:01
  • 1
    $\begingroup$ Oh I see. Finite sequences of compositions can't get us out of $\kappa$-land where $\kappa$ is the cardinality of our infinite base set. In other words, the free monoid on $\kappa$ has cardinality $\kappa$. $\endgroup$ Jun 24 at 2:03
  • $\begingroup$ In the second paragraph, I'm confused as to why we're talking about totality rather than invertibility. I think the functions in the interpretation of $M_n$ are all total, but the ones not in $S_n$ are not invertible. The "invertibility" reading makes intuitive sense to me; once we compose in an element without an inverse, invertibility is gone forever. $\endgroup$ Jun 24 at 2:12
  • $\begingroup$ @GregNisbet OK my brain might actually be melting. It's been a long day. $\endgroup$ Jun 24 at 2:13
0
$\begingroup$

The answer to the question in the title is negative for all finite integers $n$ greater than or equal to $4$.

Indeed, the symmetric group $\cal S_n$ is generated the $2$-element set $S = \{(1,2),(1,2,...,n)\}$ consisting of a transposition and a cyclic permutation. Moreover, the semigroup $\cal T_n$ of all transformations on $\{1, 2, \ldots, n\}$ can be generated by a $3$-element set consisting of $S$ and a transformation of rank $n-1$.

For the record, the semigroup $\cal PT_n$ of all partial transformations on $\{1, 2, \ldots, n\}$ can be generated by a $4$-element set.

A detailed study of these questions can be found in [1, Chapter 3].

[1] O. Ganyushkin and V. Mazorchuk, Classical finite transformation semigroups. An introduction. Algebra and Applications, 9. Springer-Verlag London, Ltd., London, 2009. xii+314 pp. ISBN: 978-1-84800-280-7

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.