Let be a set and let be the transformation semigroup on . Find the idempotents in as well as their respective maximal subgroups. Characterize the left and right zeros of , and compute its kernel. Characterize the parital order on the idempotents. Prove that is regular.

We first recall some notation. If and , then is the map given by (that is denotes the restriction of to ). denotes the identity map on . The kernel of a set map is the relation on given by if and only if ; certainly is an equivalence relation.

Lemma 1: is idempotent if and only if . Proof: Suppose is idempotent. That is, . Now let , with . Now . So . Suppose . Now for all , we have since . So .

In other words, a map is idempotent if and only if it is the identity on its image. Now recall that the maximal subgroup with identity is precisely . As we show in the next few lemmas, each of these equalities has a nice characterization in .

Lemma 2a: Let be functions with idempotent. Then if and only if . Proof: Suppose . Let , with . Now , so that . Suppose . Let . Then , using Lemma 1. So .

Lemma 2b: Let be functions with idempotent. Then if and only if . Proof: Suppose . If , then . So , so , so that . Thus . Suppose . Since is idempotent, for all , we have . So . Thus for all , and thus .

Lemma 3a: Let be functions with idempotent. Then there exists a function such that if and only if . Proof: Suppose for some function , and let . Now for some . Then , so that . Suppose . For each , define ; each is nonempty since . Let be a choice function that selects, given , an element of . (Use the Axiom of Choice.) That is, is an element such that . Then for all , we have (for some ). Thus .

Lemma 3b: Let be functions with idempotent. Then there exists a function such that if and only if . Proof: Suppose for some . If , then . So , so , and so . Thus . Suppose . For each , define if and otherwise. Now let be a choice function such that for each . Now let . We have , where . But then , so in fact . Thus .

By Lemmas 2 and 3, we see that if is idempotent, then .

We will now compute the isomorphism type of .

Lemma 4a: Let be idempotent and let . Then is a permutation of . Proof: Since , we have . (Surjective) Suppose ; then , with for some . Since , we have for some . So , and thus is surjective. (Injective) Let such that . Now , and we have and for some , so that . Since , we have , and since is idempotent, . So , and thus is injective.

Lemma 5a: The map given by is a surjective group homomorphism. Proof: Let . Let . Now , and . So . So . Now suppose . Certainly . Clearly . If , then , so . Thus . Since , we have . So is surjective.

Lemma 4b: Let be idempotent and let . Then the relation is a permutation of . Proof: Certainly is total. If , such that , then . Since , . So . Thus is well defined, with . Since is idempotent, we have for all . So for all . Since , we have for some , and thus . So . Thus is surjective. Now suppose and . Now , so that . So . Since , we have , and so . Thus is injective.

Lemma 5b: The map given by is an injective group homomorphism. Proof: Note that , so that . Thus is a group homomorphism. Now suppose . Then for all , we have , so that . Now , so that . Thus , and so is injective.

By the first isomorphism theorem for sets, we have , so that as groups. So we have as groups.

Lemma 6a: is a left zero if and only if there exists such that for all . Proof: Suppose is a constant function, with for all . Now if , we have for all ; so for all . Thus is a left zero. Suppose is a left zero. For each , let denote the constant function whose image is . Fix and let . Now for all , we have . So in fact is constant.

Lemma 6b: is a right zero if and only if . Proof: Suppose is a right zero. If and , then we have with . Let be any function such that . (For instance, a constant function.) But then , so that – a contradiction. Thus . Suppose . Then is trivial, so that every element (i.e. the only element) is a right zero.

By Lemma 6, we see that the left zeros in are precisely the constant functions, and that has no right zeros unless (in which case is trivial).

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

Lemma 7: Let be a semigroup. If is a left ideal and a left zero, then . Likewise, if is a right ideal and a right zero, then . Proof: If , we have .

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

Lemma 8: The set of constant functions on is a two-sided ideal in . Proof: Since the elements of are left zeros, is a right ideal. Now suppose is a constant function with image and a function. For all , we have ; so is constant. So is a two-sided ideal.

So the kernel of is the set of constant functions.

Lemma 9: Let be idempotent. Then if and only if and latex \mathsf{ker}\ f \subseteq \mathsf{ker}\ e$. Proof: Follows from Lemma 2.

Finally, we argue that is regular.

Let . Now define such that if and otherwise (use a choice function if you want). Now . By Lemma 2a, . By Lemma 3a, there exists such that . So , and thus is regular. So is regular.