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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: