Given any finite set $X$ the set $\mathcal{T}(X)=X^X$ of all functions from $X$ to $X$ clearly forms a monoid under composition. Now if we call any family of functions $\mathcal{F}\subseteq \mathcal{T}(X)$ a generating set of $\mathcal{T}(X)$ iff every function in $\mathcal{T}(X)$ can be expressed as a composition of functions in $\mathcal{F}$. Then how small can such a set $\mathcal{F}$ be while still generating every function in $\mathcal{T}(X)$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
11
The minimal number to generate the full transformation monoids is 3 maps. You must include a generating set for the symmetric group, which requires 2, and then you can add any idempotent function collapsing exactly two elements.
Here are hints.
Use double transitivity of the symmetric group to show you get all idempotents collapsing exactly two points.
Show using 1 you can get any map collapsing two elements. (This is overkill to show every non-permutation is a product of idempotents. Otherwise in step 1 get all maps collapsing just two points.)
Now do induction on the defect of $f$ (size of $|X|-|f(X)|$) to show you can get anything.
answered Oct 24, 2018 at 13:39
-
$\begingroup$ This can be found in virtually any book on finite semigroup including my book with John Rhodes the q-theory of finite semigroups. $\endgroup$ Commented Oct 24, 2018 at 13:40
-
$\begingroup$ It takes 3 maps all togethe to generate the full monoid. An n-cycle, a transposition and the map sending n to n-1 and fixing all other elements. I provided some hints. $\endgroup$ Commented Oct 24, 2018 at 13:45
-
$\begingroup$ Why is the $n$-cycle needed? It seems all you need is functions which move just one element, and then transpositions $\endgroup$ Commented Oct 24, 2018 at 13:47
-
$\begingroup$ To get 3 I can't use all transpositiins. The point is the monoid is generated by the symmetric group and any map collapsing exactly two elements and you can fix your favorite symmetric group generating set. $\endgroup$ Commented Oct 24, 2018 at 13:48
-
$\begingroup$ I think I get it. Is this result rather trivial then? Sorry I don't have any experience with this sorta stuff. $\endgroup$ Commented Oct 24, 2018 at 13:50