I would like to ask you for help with proving the following theorem from our textbook:

Any semigroup is isomorphic to a subsemigroup of ($A^A, \cdot$) for a suitable set A.

The theorem is then proved somewhat briefly for me, claiming that:

Let (S, $\cdot$) be a semigroup. For a $\in$ G, let $\rho_a: S \to S$ be a function defined as $\rho_a(x) = a \cdot x$ for any x $\in$ S. Then $\rho$ is an injective function from (S, $\cdot$) to ($S^S, \circ$). To prove that $\rho$ is an isomorphism: (...)

In a recommended literature borrowed from our university's library, I could only find a very similar theorem saying thet for every group G, $\rho: G \to Sym(G)$ is an injective homomorphism. This is proved by saying that $\rho_a: G \to G$ is a bijective function as implied by the law of reduction ($a \cdot b = a \cdot c \implies b = c$) proved for groups using the inverse of a which doesn't have to exist in a semigroup.

I am, however, very confused by the relation of $\rho_a$ as a function of x $\in$ G and $\rho(a) = \rho_a(x), a \in G$. Could please anyone explain thoroughly how do they relate to each other forming $\rho: G \to Sym(G)$ from $\rho_a: G \to G$ and prove that the original theorem from our textbook concerning semigroups was right or wrong?

Thank you.


A semigroup is not assumed to have an identity. So if $S$ does not have an indentity, the first step is to find a semigroup with identity, that is a monoid, $(A, \cdot, 1)$ and an injective homomorphism $\varphi : S \to A$. This is relatively easy. Form the disjoint union $A = S \cup \{ 1 \}$, and define products in the obvious way. Clearly $\varphi(s) = s$.

So now you have a monoid $(A, \cdot, 1)$. Consider, as per your textbook, the monoid $(A^{A}, \circ, 1)$ of maps from $A$ to $A$ under composition, $1$ being the identity map here. Consider the map $$ \rho : A \to A^{A}, \qquad a \mapsto (x \mapsto a x). $$

This is injective, as shown in another answer: if $\rho(a) = \rho(b)$, then $$a = a \cdot 1 = \rho(a)(1) = \rho(b)(1) = b \cdot 1 = b.$$

And then you have for all $x \in A$ $$ \rho(ab)(x) = (ab) x = a (b x) = \rho(a) (bx) = \rho(a) (\rho(b)(x)) = \rho(a) \circ \rho(b)(x), $$ so $$\rho(ab) = \rho(a) \circ \rho(b),$$ that is, $\rho$ is a homomorphism.

Note that your book writes $\rho_{a} = \rho(a)$.

  • $\begingroup$ Wow, this was a perfect proof, thank you very much! Especially the notion that a maps to a map and your writing of $\rho$ as $\rho(a)(x)$ helped me a lot. Thank you once again! $\endgroup$ – Kyselejsyreček Feb 7 '15 at 19:16
  • $\begingroup$ @Kyselejsyreček, you're welcome! $\endgroup$ – Andreas Caranti Feb 7 '15 at 20:14
  • $\begingroup$ And concerning the notation I have used, you may want to check en.wikipedia.org/wiki/Currying $\endgroup$ – Andreas Caranti Feb 7 '15 at 20:17

If your definition of a semigroup includes the existence of a unit 1, then the following argument should work:

If $a,b \in S$ and $\rho_a = \rho_b$, then in particular $a = \rho_a(1) = \rho_b(1) = b$, i.e. the map $\rho$ is injective.

You do not need that $\rho_a$ is a bijection. The map $\rho$ is defined as a map from $S$ to $S^S$, the latter being all functions from $S$ to itself (they do not need to be bijective).

Note also that $S^S$ is not a group.

  • $\begingroup$ Thank you for your explanation which was useful for me. The definition of semigroup doesn't imply the existence of a neutral element of course. But this is not a limiting fact in this case as shown by Mr. Andreas Caranti. $\endgroup$ – Kyselejsyreček Feb 7 '15 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.