Characterize the elements of a semigroup of transformations on a set which generate trivial left and right principal ideals

Let X be a set and let \mathsf{T}(X) = X^X denote the semigroup of functions X \rightarrow X. Characterize the elements \alpha,\beta \in \mathsf{T}(X) such that \alpha \mathsf{T}(X) = \mathsf{T}(X) and \mathsf{T}(X) \beta = \mathsf{T}(X).


We begin with some lemmas about functions. Recall that a function \varphi : A \rightarrow B is called injective if for all x,y \in A, if \varphi(x) = \varphi(y) then x=y. It is called surjective if for every y \in B, there exists x \in A with \varphi(x) = y.

Lemma 1: Let \varphi : A \rightarrow B be a set function. Then the following are equivalent:

  1. \varphi is injective.
  2. For all suitable functions \alpha and \beta, if \varphi \circ \alpha = \varphi \circ \beta, then \alpha = \beta.
  3. If A \neq \emptyset, then there exists a function \psi : B \rightarrow A such that \psi \circ \varphi = \mathsf{id}_A.

Proof:

  • (1 \Rightarrow 3) We have \varphi : A \rightarrow B injective with A \neq \emptyset. Choose \alpha \in A. Note that for all y \in \mathsf{im}\ \varphi, the set \varphi^*(y) contains exactly one element; call this element x_y. Now define a function \psi : B \rightarrow A by

    \psi(y) = \left\{ \begin{array}{ll} x_y & \mathrm{if}\, y \in \mathsf{im}\ \varphi \\ \alpha & \mathrm{otherwise}. \end{array} \right.

    Clearly \psi is well defined and \psi \circ \varphi = \mathsf{id}_A.

  • (3 \Rightarrow 2) Suppose \psi exists. Then given \alpha and \beta,

    \begin{array}{rcl}  \varphi \circ \alpha = \varphi \circ \beta & \Rightarrow & \psi \circ (\varphi \circ \alpha) = \psi \circ (\varphi \circ \beta) \\ & \Rightarrow & (\psi \circ \varphi) \circ \alpha = (\psi \circ \varphi) \circ \beta \\ & \Rightarrow & \mathsf{id} \circ \alpha = \mathsf{id} \circ \beta \\ & \Rightarrow & \alpha = \beta. \end{array}
  • (2 \Rightarrow 1) Let x, y \in A such that \varphi(x) = \varphi(y). Now define maps \underline{x}, \underline{y} : \{\star\} \rightarrow A with \underline{x}(\star) = x and \underline{y}(\star) = y. Clearly \varphi \circ \underline{x} = \varphi \circ \underline{y}, and so \underline{x} = \underline{y}. Thus x=y. \square

Lemma 2: Let \varphi : A \rightarrow B be a set function. Then the following are equivalent.

  1. \varphi is surjective.
  2. For all suitable functions \alpha and \beta, if \alpha \circ \varphi = \beta \circ \varphi then \alpha = \beta.
  3. If A \neq \emptyset, then there exists a function \psi : B \rightarrow A such that \varphi \circ \psi = \mathsf{id}_B.

Proof:

  • (1 \Rightarrow 3) We have \varphi : A \rightarrow B with A \neq \emptyset. Since \varphi is surjective, \varphi^*(y) (the preimage of y) is nonempty for every y \in B. Let x_y be some element in this set. Then \psi : B \rightarrow A given by y \mapsto x_y is well defined, and clearly \varphi \circ \psi = \mathsf{id}_B.
  • (3 \Rightarrow 2) Suppose \psi exists. Then given \alpha and \beta,
    \begin{array}{rcl} \alpha \circ \varphi = \beta \circ \varphi & \Rightarrow & (\alpha \circ \varphi) \circ \psi = (\beta \circ \varphi) \circ \psi \\ & \Rightarrow & \alpha \circ (\varphi \circ \psi) = \beta \circ (\varphi \circ \psi) \\ & \Rightarrow & \alpha \circ \mathsf{id} = \beta \circ \mathsf{id} \\ & \Rightarrow & \alpha = \beta. \end{array}
  • (2 \Rightarrow 1) Consider the maps \alpha, \beta : B \rightarrow \{ \mathsf{true} , \mathsf{false} \} defined as follows:
    \begin{array}{l} \alpha(y) = \left\{ \begin{array}{ll} \mathsf{true} & \mathrm{if}\ y \in \mathsf{im}\ \varphi \\ \mathsf{false} & \mathrm{otherwise} \end{array} \right. \\ \beta(y) = \mathsf{true}. \end{array}

    Both \alpha and \beta are well defined, and clearly \varphi \circ \alpha = \varphi \circ \beta. Then \alpha = \beta, and so \alpha(y) = \mathsf{true} for all y \in B; hence y \in \mathsf{im}\ \varphi, and so \varphi is surjective. \square

We now claim the following: \alpha \mathsf{T}(X) = \mathsf{T}(X) if and only if \alpha is surjective and \mathsf{T}(X) \beta = \mathsf{T}(X) if and only if \beta is injective.

Suppose \alpha \mathsf{T}(X) = \mathsf{T}(X). In particular, there exists \beta such that \alpha \circ \beta = \mathsf{id}_X. By Lemma 2, \alpha is surjective. If \alpha is surjective, then there exists \beta \in \mathsf{T}(X) such that \alpha \circ \beta = \mathsf{id}. Now if \varphi \in \mathsf{T}(X), we have \varphi = \mathsf{id} \circ \varphi = \alpha \circ \beta \circ \varphi \in \alpha \mathsf{T}(X), so that \mathsf{T}(X) = \alpha \mathsf{T}(X). The proof for injective functions is analogous.

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: