Showing that for all $f: X \to Y$ there exists $S, g: X \to S, h: S \to Y$ with $g$ injective and $h$ surjective such that $f = h \circ g$

Question

I want to show the claim in the title: That for all functions $f: X \to Y$ there exists some set $S$, some injective function $g: X \to S$, and some surjective function $h: S \to Y$ such that $f = h \circ g$.

So far, my line of thought is

• Maybe we can set $h$ to be the identity function (which is surjective). and $g$ to be $f$. However, this is not necessarily valid, as $f$ is not guaranteed to be injective.

Any ideas as to how to proceed?

$\ne$ Every function $f$ can be factored into $f = i \circ s$, with $i$ injective and $s$ surjective

Answer 1

I think you may have posed the question the wrong way around, but either way, this is true, but the factorisation is not that interesting, simply define

$S = (X\times \{0\}) \cup (Y\times \{1\})$

And then define

\begin{align} g:&X\to S\\ &x\mapsto (x,0) \end{align}

And then define

\begin{align} h:&S\to Y \\ h((a,n))& = \begin{cases} f(a) & \text{ if } n=0 \\ a & \text{ if }n= 1 \end{cases} \end{align}

I'll leave it to you to check that the conditions are satisfied

Answer 2

If $X$ is empty, then let $S=Y$ with $g=f$ and $h=\operatorname{id}_Y$. Then, $f=h \circ g$ with $g$ and $h$ being injective and surjective respectively.

Otherwise, let $S=X \times Y$ with $g(x)=(x,f(x))$ and $h(x,y)=y$. Then, again $f=h \circ g$ with $g$ and $h$ being injective and surjective respectively. Note that the surjectivity of $h$ requires $X$ to be nonempty.