# Isomorphism of a semigroup S and (Aᴬ, ⋅).

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)$.

• 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! – Kyselejsyreček Feb 7 '15 at 19:16
• @Kyselejsyreček, you're welcome! – Andreas Caranti Feb 7 '15 at 20:14
• And concerning the notation I have used, you may want to check en.wikipedia.org/wiki/Currying – 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.

• 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. – Kyselejsyreček Feb 7 '15 at 19:27