## Facts about the transformation semigroup on a set

Let $X$ be a set and let $\mathsf{T}(X) = X^X$ be the transformation semigroup on $X$. Find the idempotents in $\mathsf{T}(X)$ as well as their respective maximal subgroups. Characterize the left and right zeros of $\mathsf{T}(X)$, and compute its kernel. Characterize the parital order on the idempotents. Prove that $\mathsf{T}(X)$ is regular.

We first recall some notation. If $f : X \rightarrow Y$ and $Z \subseteq X$, then $f|_Z : Z \rightarrow Y$ is the map given by $f|_Z(z) = f(z)$ (that is $f|_Z$ denotes the restriction of $f$ to $Z$). $\mathsf{id}_X$ denotes the identity map on $X$. The kernel of a set map $f : X \rightarrow Y$ is the relation on $X$ given by $(x,y) \in \mathsf{ker}\ f$ if and only if $f(x) = f(y)$; certainly $\mathsf{ker}\ f$ is an equivalence relation.

Lemma 1: $f : X \rightarrow X$ is idempotent if and only if $f|_{\mathsf{im}\ f} = \mathsf{id}_{\mathsf{im}\ f}$. Proof: $(\Rightarrow)$ Suppose $f$ is idempotent. That is, $f \circ f = f$. Now let $x \in \mathsf{im}\ f$, with $x = f(y)$. Now $f(x) = f(f(y))$ $= f^2(y) = f(y) = x$. So $f|_{\mathsf{im}\ f} = \mathsf{id}_{\mathsf{im}\ f}$. $(\Leftarrow)$ Suppose $f|_{\mathsf{im}\ f} = \mathsf{id}_{\mathsf{im}\ f}$. Now for all $x \in X$, we have $(f \circ f)(x) = f(f(x))$ $= f(x)$ since $f(x) \in \mathsf{im}\ f$. So $f^2 = f$. $\square$

In other words, a map $f : X \rightarrow X$ is idempotent if and only if it is the identity on its image. Now recall that the maximal subgroup $G_f$ with identity $f$ is precisely $G_f = \{g\ |\ fg = gf = g, gh = hg = f\ \mathrm{for\ some}\ h\}$. As we show in the next few lemmas, each of these equalities has a nice characterization in $\mathsf{T}(X)$.

Lemma 2a: Let $f,g : X \rightarrow X$ be functions with $f$ idempotent. Then $f \circ g = g$ if and only if $\mathsf{im}\ g \subseteq \mathsf{im}\ f$. Proof: $(\Rightarrow)$ Suppose $f \circ g = g$. Let $y \in \mathsf{im}\ g$, with $y = g(x)$. Now $y = g(x) = (f \circ g)(x)$ $= f(g(x))$, so that $y \in \mathsf{im}\ f$. $(\Leftarrow)$ Suppose $\mathsf{im}\ g \subseteq \mathsf{im}\ f$. Let $x \in X$. Then $(f \circ g)(x) = f(g(x))$ $= f|_{\mathsf{im}\ f}(g(x))$ $= g(x)$, using Lemma 1. So $f \circ g = g$. $\square$

Lemma 2b: Let $f,g : X \rightarrow X$ be functions with $f$ idempotent. Then $g \circ f = g$ if and only if $\mathsf{ker}\ f \subseteq \mathsf{ker}\ g$. Proof: $(\Rightarrow)$ Suppose $g \circ f = g$. If $(x,y) \in \mathsf{ker}\ f$, then $f(x) = f(y)$. So $g(f(x)) = g(f(y))$, so $(g \circ f)(x) = (g \circ f)(y)$, so that $g(x) = g(y)$. Thus $(x,y) \in \mathsf{ker}\ g$. $(\Leftarrow)$ Suppose $\mathsf{ker}\ f \subseteq \mathsf{ker}\ g$. Since $f$ is idempotent, for all $x \in X$, we have $(x,f(x)) \in \mathsf{ker}\ f$. So $(x,f(x)) \in \mathsf{ker}\ g$. Thus $g(x) = g(f(x))$ for all $x \in X$, and thus $g \circ f = g$. $\square$

Lemma 3a: Let $f,g : X \rightarrow X$ be functions with $f$ idempotent. Then there exists a function $h : X \rightarrow X$ such that $g \circ h = f$ if and only if $\mathsf{im}\ f \subseteq \mathsf{im}\ g$. Proof: $(\Rightarrow)$ Suppose $g \circ h = f$ for some function $h$, and let $x \in \mathsf{im}\ f$. Now $x = f(y)$ for some $y$. Then $x = f(y) = g(h(y))$, so that $x \in \mathsf{im}\ g$. $(\Leftarrow)$ Suppose $\mathsf{im}\ f \subseteq \mathsf{im}\ g$. For each $x \in X$, define $A_x = \{y\ |\ g(y) = f(x)\}$; each $A_x$ is nonempty since $\mathsf{im}\ f \subseteq \mathsf{im}\ g$. Let $h : X \rightarrow X$ be a choice function that selects, given $x$, an element of $A_x$. (Use the Axiom of Choice.) That is, $h(x)$ is an element $y$ such that $g(y) = f(x)$. Then for all $x \in X$, we have $(g \circ h)(x) = g(h(x))$ $= g(y) = f(x)$ (for some $y$). Thus $g \circ h = f$.

Lemma 3b: Let $f,g : X \rightarrow X$ be functions with $f$ idempotent. Then there exists a function $h : X \rightarrow X$ such that $h \circ g = f$ if and only if $\mathsf{ker}\ g \subseteq \mathsf{ker}\ f$. Proof: $(\Rightarrow)$ Suppose $h \circ g = f$ for some $h$. If $(x,y) \in \mathsf{ker}\ g$, then $g(x) = g(y)$. So $h(g(x)) = h(g(y))$, so $(h \circ g)(x) = (h \circ g)(y)$, and so $f(x) = f(y)$. Thus $(x,y) \in \mathsf{ker}\ f$. $(\Leftarrow)$ Suppose $\mathsf{ker}\ g \subseteq \mathsf{ker}\ f$. For each $x \in X$, define $A_x = \{f(z)\ |\ g(z) = x\}$ if $x \in \mathsf{im}\ g$ and $X$ otherwise. Now let $h : X \rightarrow X$ be a choice function such that $h(x) \in A_x$ for each $x$. Now let $x \in X$. We have $(h \circ g)(x) = h(g(x)) = f(z)$, where $g(z) = g(x)$. But then $f(z) = f(x)$, so in fact $(h \circ g)(x) = f(x)$. Thus $h \circ g = f$. $\square$

By Lemmas 2 and 3, we see that if $f \in \mathsf{T}(X)$ is idempotent, then $G_f = \{g \ |\ \mathsf{im}\ g = \mathsf{im}\ f, \mathsf{ker}\ g = \mathsf{ker}\ f\}$.

We will now compute the isomorphism type of $G_f$.

Lemma 4a: Let $f \in \mathsf{T}(X)$ be idempotent and let $g \in G_f$. Then $g|_{\mathsf{im}\ f}$ is a permutation of $\mathsf{im}\ f$. Proof: Since $\mathsf{im}\ g = \mathsf{im}\ f$, we have $\mathsf{im}\ g|_{\mathsf{im}\ f} \subseteq \mathsf{im}\ f$. (Surjective) Suppose $y \in \mathsf{im}\ f$; then $y \in \mathsf{im}\ g$, with $y = g(x)$ for some $x \in X$. Since $g \circ f = g$, we have $y = g(f(w))$ for some $w \in X$. So $y \in \mathsf{im}\ g|_{\mathsf{im}\ f}$, and thus $g|_{\mathsf{im}\ f}$ is surjective. (Injective) Let $x,y \in \mathsf{im}\ f$ such that $g|_{\mathsf{im}\ f}(x) = g|_{\mathsf{im}\ f}(y)$. Now $g(x) = g(y)$, and we have $x = f(z)$ and $y = f(w)$ for some $z,w \in X$, so that $g(f(z)) = g(f(w))$. Since $\mathsf{ker}\ g \subseteq \mathsf{ker}\ f$, we have $f(f(z)) = f(f(w))$, and since $f$ is idempotent, $f(z) = f(w)$. So $x = y$, and thus $g|_{\mathsf{im}\ f}$ is injective. $\square$

Lemma 5a: The map $\Psi : G_f \rightarrow \mathsf{Sym}(\mathsf{im}\ f)$ given by $g \mapsto g|_{\mathsf{im}\ f}$ is a surjective group homomorphism. Proof: Let $g,h \in G_f$. Let $x \in \mathsf{im}\ f$. Now $g|_{\mathsf{im}\ f}(x) = g(x) \in \mathsf{im}\ g = \mathsf{im}\ f$, and $h|_{\mathsf{im}\ f}(g(x)) = h(g(x))$ $= (h \circ g)(x)$ $= (h \circ g)|_{\mathsf{im}\ f}(x)$. So $h|_{\mathsf{im}\ f} \circ g|_{\mathsf{im}\ f} = (h \circ g)|_{\mathsf{im}\ f}$. So $\Psi(h \circ g) = \Psi(h) \circ \Psi(g)$. Now suppose $\sigma \in \mathsf{Sym}(\mathsf{im}\ f)$. Certainly $\mathsf{im}\ (\sigma \circ f) = \mathsf{im}\ f$. Clearly $\mathsf{ker}\ f \subseteq \mathsf{ker}\ (\sigma \circ f)$. If $(\sigma \circ f)(x) = (\sigma \circ f)(y)$, then $\sigma(f(x)) = \sigma(f(y))$, so $f(x) = f(y)$. Thus $\sigma \circ f \in G_f$. Since $f|_{\mathsf{im}\ f} = \mathsf{id}_{\mathsf{im}\ f}$, we have $\Psi(\sigma circ f) = \sigma$. So $\Psi$ is surjective. $\square$

Lemma 4b: Let $f \in \mathsf{T}(X)$ be idempotent and let $g \in G_f$. Then the relation $\overline{g} = \{([x]_{\mathsf{ker}\ f}, [g(x)]_{\mathsf{ker}\ f})\ |\ x \in X\}$ is a permutation of $X/\mathsf{ker}\ f$. Proof: Certainly $\overline{g}$ is total. If $([x]_{\mathsf{ker}\ f}, [g(x)]_{\mathsf{ker}\ f})$, $([x]_{\mathsf{ker}\ f}, [g(x)]_{\mathsf{ker}\ f}) \in \overline{g}$ such that $[x]_{\mathsf{ker}\ f} = [y]_{\mathsf{ker}\ f}$, then $f(x) = f(y)$. Since $\mathsf{ker}\ f \subseteq \mathsf{ker}\ g$, $g(x) = g(y)$. So $[g(x)]_{\mathsf{ker}\ f} = [g(y)]_{\mathsf{ker}\ f}$. Thus $\overline{g}$ is well defined, with $\overline{g}([x]) = [g(x)]$. Since $f$ is idempotent, we have $f(x) = f(f(x))$ for all $x \in X$. So $[x]_\mathsf{ker}\ f = [f(x)]_{\mathsf{ker}\ f}$ for all $x$. Since $\mathsf{im}\ f \subseteq \mathsf{im}\ g$, we have $f(x) = g(y)$ for some $y$, and thus $[x] = [g(y)]$. So $[x] = \overline{g}([y])$. Thus $\overline{g}$ is surjective. Now suppose $[x],[y] \in X/\mathsf{ker}\ f$ and $\overline{g}([x]) = \overline{g}([y])$. Now $[g(x)] = [g(y)]$, so that $(f \circ g)(x) = (f \circ g)(y)$. So $g(x) = g(y)$. Since $\mathsf{ker}\ g \subseteq \mathsf{ker}\ f$, we have $f(x) = f(y)$, and so $[x] = [y]$. Thus $\overline{g}$ is injective. $\square$

Lemma 5b: The map $\Phi : G_f \rightarrow \mathsf{Sym}(X/\mathsf{ker}\ f)$ given by $g \mapsto \overline{g}$ is an injective group homomorphism. Proof: Note that $\Phi(h \circ g)([x]) = [(h \circ g)(x)]$ $= [h(g(x))]$ $= \Phi(h)([g(x)])$ $= \Phi(h)(\Phi(g)([x]))$ $= (\Phi(h) \circ \Phi(g))([x])$, so that $\Phi(h) \circ \Phi(g) = \Phi(h \circ g)$. Thus $\Phi$ is a group homomorphism. Now suppose $\Phi(g) = \Phi(h)$. Then for all $x \in X$, we have $[g(x)] = [h(x)]$, so that $f(g(x)) = f(h(x))$. Now $(f \circ g)(x) = (f \circ h)(x)$, so that $g(x) = h(x)$. Thus $g = h$, and so $\Phi$ is injective. $\square$

By the first isomorphism theorem for sets, we have $X/\mathsf{ker}\ f \cong \mathsf{im}\ f$, so that $\mathsf{Sym}(X/\mathsf{ker}\ f) \cong \mathsf{Sym}(\mathsf{im}\ f)$ as groups. So we have $G_f \cong \mathsf{Sym}(X/\mathsf{ker}\ f) \cong \mathsf{Sym}(\mathsf{im}\ f)$ as groups.

Lemma 6a: $\lambda \in \mathsf{T}(X)$ is a left zero if and only if there exists $c \in X$ such that $\lambda(x) = c$ for all $x \in X$. Proof: $(\Leftarrow)$ Suppose $\lambda$ is a constant function, with $\lambda(x) = c$ for all $x$. Now if $f \in \mathsf{T}(X)$, we have $(\lambda \circ f)(x) = \lambda(f(x)) = c = \lambda(x)$ for all $x$; so $\lambda \circ f = \lambda$ for all $f$. Thus $\lambda$ is a left zero. $(\Rightarrow)$ Suppose $\lambda$ is a left zero. For each $x \in X$, let $f_x$ denote the constant function whose image is $x$. Fix $x \in X$ and let $c = \lambda(x)$. Now for all $y \in X$, we have $\lambda(y) = \lambda(f_y(x))$ $= (\lambda \circ f_y)(x)$ $= \lambda(x)$ $= c$. So in fact $\lambda = f_c$ is constant. $\square$

Lemma 6b: $\rho \in \mathsf{T}(X)$ is a right zero if and only if $|X| = 1$. Proof: $(\Rightarrow)$ Suppose $\rho$ is a right zero. If $|X| \geq 2$ and $x \in X$, then we have $y \in X$ with $y \neq \rho(x)$. Let $f$ be any function such that $f(\rho(x)) = y$. (For instance, a constant function.) But then $(f \circ \rho)(x) \neq \rho(x)$, so that $f \circ \rho \neq \rho$– a contradiction. Thus $|X| = 1$. $(\Leftarrow)$ Suppose $|X| = 1$. Then $\mathsf{T}(X)$ is trivial, so that every element (i.e. the only element) is a right zero. $\square$

By Lemma 6, we see that the left zeros in $\mathsf{T}(X)$ are precisely the constant functions, and that $\mathsf{T}(X)$ has no right zeros unless $|X| = 1$ (in which case $\mathsf{T}(X)$ is trivial).

Recall that the kernel of a semigroup is the intersection of all its ideals.

Lemma 7: Let $S$ be a semigroup. If $L \subseteq S$ is a left ideal and $\ell \in S$ a left zero, then $\ell \in L$. Likewise, if $R$ is a right ideal and $r$ a right zero, then $r \in R$. Proof: If $s \in L$, we have $\ell s = \ell \in L$. $\square$

By Lemma 7, every ideal (being also a left ideal) contains the set $C$ of constant functions. We claim also that $C$ is an ideal.

Lemma 8: The set $C$ of constant functions on $X$ is a two-sided ideal in $\mathsf{T}(X)$. Proof: Since the elements of $C$ are left zeros, $C$ is a right ideal. Now suppose $f_c$ is a constant function with image $c$ and $g$ a function. For all $x$, we have $(g \circ f)(x) = g(f(x))$ $= g(c)$; so $g \circ f_c = f_{g(c)}$ is constant. So $C$ is a two-sided ideal. $\square$

So the kernel of $\mathsf{T}(X)$ is the set of constant functions.

Lemma 9: Let $e,f \in \mathsf{T}(X)$ be idempotent. Then $e = e \circ f = f \circ e$ if and only if $\mathsf{im}\ e \subseteq \mathsf{im}\ f$ and latex \mathsf{ker}\ f \subseteq \mathsf{ker}\ e\$. Proof: Follows from Lemma 2. $\square$

Finally, we argue that $\mathsf{T}(X)$ is regular.

Let $g \in \mathbb{T}(X)$. Now define $f \in \mathsf{T}(X)$ such that $f(x) = x$ if $x \in \mathsf{im}\ g$ and $f(x) \in \mathsf{im}\ g$ otherwise (use a choice function if you want). Now $\mathsf{im}\ f = \mathsf{im}\ g$. By Lemma 2a, $f \circ g = g$. By Lemma 3a, there exists $a$ such that $g \circ a = f$. So $g \circ a \circ g = g$, and thus $g$ is regular. So $\mathsf{T}(X)$ is regular.