This is Exercise 1.16 of Howie's Fundamentals of Semigroup Theory.
The Details.
Definition 1: Let $A$ and $B$ be sets. A relation $\rho$ from $A$ to $B$ is a subset of $A\times B$. Define $$a\rho=\{b\in B\mid (a, b)\in \rho\}$$ for each $a\in A$.
Definition 2: If $S$ and $T$ are semigroups, then $\mu\subseteq S\times T$ is a relational morphism from $S$ to $T$ if $$\begin{align} (\forall a\in S)\, a\mu&\ne \emptyset\tag{RM1}\\ (\forall a,b\in S)\, (a\mu)(b\mu)&\subseteq (ab)\mu.\tag{RM2} \end{align}$$ Further, we say $\mu$ is injective if $$(\forall a, b\in S)\, a\mu\cap b\mu\ne \emptyset\implies a\mu=b\mu.\tag{RM3}$$
The first part of the exercise asks the reader to show
Lemma 1: Every relational morphism $\mu\subseteq S\times T$ is a subsemigroup of the direct product $S\times T$.
Proof: If $s\mu t$ and $s'\mu t'$, then $$tt'\in\{\sigma\sigma'\mid s\mu\sigma, s'\mu\sigma'\}\stackrel{(RM2)}{\subseteq}(ss')\mu\left(\stackrel{(RM1)}{\ne}\emptyset\right)$$ so $ss'\mu tt'$. The result follows.$\square$
Definition 3: We say $S$ divides $T$, written $S\preccurlyeq T$, if there exists a subsemigroup $U$ of $T$ and a morphism $\psi$ from $U$ onto $S$.
The Question.
Show that $S\preccurlyeq T$ if and only if there exists an injective relational morphism from $S$ to $T$.
My Attempt.
I've given this several hours of my (admittedly divided) attention and I'm still stuck. It really should be easy.
Suppose $\mu\subseteq S\times T$ is an injective relational morphism. Basically, I've looked at $\operatorname{im} \mu=\{b\in T\mid \exists s\in S, a\mu b\}$ as the subsemigroup of $T$ I need. I've poked $\operatorname{ker} \mu=\mu\circ\mu^{-1}=\{(a, b)\in S\times S\mid a\mu=b\mu\}$ a bit, hoping for some answers. My notes are a mess.
Please help :)
You can use the following steps. By Lemma 1, $\mu$ is a subsemigroup of $S \times T$. Let $\alpha: \mu \to S$ and $\beta: \mu \to T$ be the induced projections. Note that $\alpha$ is surjective by (RM1). Furthermore $\mu = \beta \circ \alpha^{-1}$ (as relations). This is called the canonical factorization of $\mu$
Hint. The key step is to prove that $\mu$ is injective if and only if $\beta$ is injective. By the way, this is a frequent trick when studying relational morphisms: $\mu$ and $\beta$ often share the same properties.
Once you have proved the hint, the rest follows easily. If $S$ divides $T$, there exists a semigroup $R$, a surjective morphism $\alpha: R \to S$ and an injective morphism $\beta: R \to T$. Then $\alpha^{-1}$ is an injective relational morphism and thus $\tau = \beta \circ \alpha^{-1}$ is an injective relational morphism from $S$ into $T$. Conversely, let $\mu$ be an injective relational morphism from $S$ into $T$ and let $S \enspace{\buildrel{\alpha^{-1}} \over \longrightarrow} \enspace R \enspace{\buildrel{\beta} \over\longrightarrow}\enspace T$ be its canonical factorisation. Since $\beta$ is injective and $\alpha$ is surjective, $S$ divides $T$.