Size of the image (rank) in $T_n$

Question

For $\alpha, \beta \in T_n$ (full transformation semigroup/monoid - set of all maps from $\{1,2,\ldots, n\}$ to itself), show that $|\text{Im}(\alpha\beta)| \leqslant |\text{Im}(\alpha)|$ and $|\text{Im}(\alpha\beta)| \leqslant |\text{Im}(\beta)|$.

How do you show this (apparently it's easy)?

Answer 1

If $k \in \operatorname{Im}(\alpha\beta) \subseteq \{1, \dots, n\}$, then there is some $i \in \{1, \dots, n\}$ such that $\alpha(\beta(i)) = k$.

This equation shows that $\alpha$ maps $\beta(i) \mapsto k$. In other words, $k \in \operatorname{Im}(\alpha)$, and so $\operatorname{Im}(\alpha\beta) \subseteq \operatorname{Im}(\alpha)$. Note that we only have equality $\operatorname{Im}(\alpha\beta) = \operatorname{Im}(\alpha)$ if $\beta$ is onto (hence bijective, as $\{1, \dots, n\}$ is finite).

For the second inequality, the correspondence $\operatorname{Im}(\alpha\beta) \to \operatorname{Im}(\beta), k \mapsto \beta(i)$, which involves arbitrarily choosing a preimage $i$, is injective. Why? Let $k, k' \in \operatorname{Im}(\alpha\beta)$ and choose $i, i' \in \{1, \dots, n\}$ such that $\alpha(\beta(i)) = k$ and $\alpha(\beta(i')) = k'$. If $\beta(i) = \beta(i')$, then by application of $\alpha$, it follows that $k = k'$. Note that we only have the bijection $\operatorname{Im}(\alpha\beta) \cong \operatorname{Im}(\beta)$ if $\alpha$ is one-to-one (hence bijective, as $\{1, \dots, n\}$ is finite).

Answer 2

I haven't read Sammy Black's proof in detail, but I think an answer consisting mainly of words might be more illuminating.

Let $X = \{1,\ldots,n\}$. Let $k = |\operatorname{Im}(\alpha)|$ and $m = |\operatorname{Im}(\beta)|$.

You didn't say whether your transformations are acting on the left or the right. I'll assume they act on the right.

To obtain $\operatorname{Im}(\alpha\beta)$, we act on $X$ first by $\alpha$ and then by $\beta$. Once we have acted by $\alpha$, we have $k$ points left to be acted on by $\beta$. Since $\beta$ is a function, this can produce at most $k$ points. But also, since $\beta$ maps the whole of $X$ to $m$ points, it certainly maps $\operatorname{Im}(\alpha)$ (which is a subset of $X$) to at most $m$ points.

So $|\operatorname{Im}(\alpha\beta)|$ is bounded above by both $k = |\operatorname{Im}(\alpha)|$ and $m = |\operatorname{Im}(\beta)|$.