# Why do maximal-rank transformations of an infinite set $X$ generate the whole full transformation semigroup?

This question is a by-product of this one. I'm asking it because of this comment by Tara B.

I'll repeat the definitions. The full transformation semigroup $\mathscr T_X$ on a set $X$ is the semigroup of all functions from $X$ to $X$ with composition as the semigroup operation. $\mathscr J$ denotes the equivalence relation on $\mathscr T_X$ given by the formula $$(\phi\mathscr J \psi)\iff (\mathscr T_X\phi\mathscr T_X=\mathscr T_X\psi\mathscr T_X),$$ which means that two transformations are $\mathscr J$-related iff they generate the same two-sided ideal.

It's one of Green's relations, which are important in semigroup theory. It is a theorem that $$\mathscr J=\{(\phi,\psi)\,|\,\operatorname{rank}(\phi)=\operatorname{rank}(\psi)\},$$

where $\operatorname{rank}(\phi)$ denotes the carinality of the image of $\phi.$ By $J_\phi,$ we denote the $\mathscr J$-class of $\phi.$ Then we have $$J_{\operatorname{id}}=\{\phi\,|\,\operatorname{rank}(\phi)=\operatorname{card}(X)\}.$$

In the linked question I expressed my intuition that if $X$ is infinite, then every transformation of $X$ can be expressed as a composition of transformations in $J_{\operatorname{id}}.$ I couldn't prove it and this is what this question is about. How can I prove this fact? And can we give a more general statement? I believe we can. I'll give one more definition first.

For two $\mathscr J$-classes $J_\phi$ and $J_\psi,$ we say that $J_\phi\leq J_\psi$ iff the two-sided ideal generated by $\phi$ is contained in the two-sided ideal generated by $\psi.$

I think the following might be true. Let $X$ be any set and let $J$ be a $\mathscr J$-class in $\mathscr T_X.$ If either $X$ is infinite or $J\neq J_{\operatorname{id}},$ then for every $\phi\in\mathscr T_X,$ if $J_\phi\leq J,$ then $\phi$ is a composition of transformations in $J.$

-

Let $X$ be an infinite set and $\alpha\in {\mathscr T}_X$. Suppose $\alpha\notin J_{\operatorname{id}}$, since otherwise we are done. So $|X\alpha| < |X|$.

We can express $X$ as the disjoint union of sets $Y$ and $Z$ of the same cardinality of $X$, such that $X\alpha\subset Y$. Define $\beta,\gamma\in {\mathscr T}_X$ as follows: $\beta$ acts the same as $\alpha$ on $Y$, but as the identity on $Z$, while $\gamma$ acts as the identity on $Y$, and the same as $\alpha$ on $Z$. Then for $x\in Y$, we have $x\beta\gamma = x\alpha\gamma = x\alpha$ and for $x\in Z$, we have $x\beta\gamma = x\gamma = x\alpha$, so $\alpha = \beta\gamma$.

It's possible I might be missing something, because I'm not very used to uncountable cardinalities.

As for your more general statement, it sounds plausible, but I have no time to think about it right now. You might find that the same kind of idea works.

-
Thank you very much, what an elegant idea! –  user23211 Apr 3 '12 at 11:39
By the way, the more general statement is indeed true. Have you checked it? –  Tara B Apr 4 '12 at 22:25
I'm sorry for replying so late. I tried to check it and failed, and later forgot to reply. I haven't managed so far. By using your argument I only managed to prove that $J_{\phi}\leq J_{\psi}$ iff $\operatorname{rank}(\phi)\leq\operatorname{rank}(\psi)$. –  user23211 Apr 20 '12 at 21:40
That's okay; I'd forgotten about it! It's a while since I did this, so I'd have to look up what I did again. Let me know if you'd like me to. –  Tara B Apr 20 '12 at 21:46
Yes, of course! Thanks! –  user23211 Apr 20 '12 at 21:54

(I'm putting this as a separate answer because I don't want to spoil the brevity of the main answer. I hope that's okay.)

Some hints for proving the general statement:

For the finite case, it suffices to show $J_n\subseteq J_{n+1} J_{n+1}$ for $1\leq n\leq |X|-2$, where $J_i$ denotes the $\mathcal{J}$-class consisting of all transformations of rank $i$. This isn't hard, but I can give some more details later if you like.

Now suppose $X$ is infinite and $J_{\phi}\leq J_{\psi} =: J$. As you've already observed, this implies $\operatorname{rank}(\phi)\leq \operatorname{rank}(\psi)$. We might as well assume the inequality is strict, since otherwise $J_{\phi} = J$ and we're done. If $|X\psi|$ is finite, then we essentially use the argument for $X$ finite, so suppose $|X\psi|$ is infinite.

Partition $X$ into subsets $Y, Z, S$ such that $X\phi\subseteq Y$ and $|Y| = |Z| = |X\psi|$. Now define $\beta,\gamma\in J_{\psi}$ as follows: $\beta$ acts the same as $\phi$ on $Y\cup S$ and as the identity on $Z$, while $\gamma$ acts the same as $\phi$ on $Z$, as the identity on $Y$, and sends every element of $S$ to some fixed $y\in X$. Now, providing I didn't mistranscribe anything, it's easy to show that $|X\beta| = |X\gamma| = |X\psi|$, so $\beta,\gamma\in J$, and $\phi = \beta\gamma$.

-
Thanks! The only thing I think you mistranscribed is $X\cap S$ I think you meant $Y\cap S.$ I think I got it! :) When I was trying to do it I was having trouble with what to do with $S$ but now I see. :) –  user23211 Apr 24 '12 at 17:15
Yes, you're right. Although I definitely meant $\cup$, not $\cap$. =] I'm glad it makes sense to you. –  Tara B Apr 24 '12 at 17:53
OK, now it was my turn to make a typo. :) Sorry and thanks again! –  user23211 Apr 24 '12 at 18:15