Show that there exist a set $R$ and functions $β : S → R$ and $γ : R → T$ such that $β$ is onto, $γ$ is one-to-one and $α = γβ.$

Let $S$ and $T$ be sets and $α : S → T$ a function. Show that there exist a set $R$ and functions $β : S → R$ and $γ : R → T$ such that $β$ is onto, $γ$ is one-to-one and $α = γβ.$

My proof:

Define $α : S → T$ via $\alpha(s)=t$. Assume that there exist a set $R$ and functions $β : S → R$ and $γ : R → T$. Since $\beta$ is onto, then for all $r\in R$, there is an element $s\in S$ such that $\beta(s)=r$. Also, by assuming problem $\gamma$ is one-to-one, so if $\gamma(r)=t$ and $\gamma(u)=t$ implies $r=u$. Thus $\gamma \beta(s)=\gamma(r)=t=\alpha(s)$ as desired.

Is my proof correct? I have a clear idea of why it works but I'm not very convinced of what I did.

Solution 1:

Your proof is doing it backwards to some extent. Define the set $R$ as some set which has $\big|R\big|=\big|\alpha(S)\big|$, i.e. $R$ is the same size as the range of $\alpha$. The easiest way to do this is to let $R=\alpha(S)$; note that this makes $R\subseteq T$ because $T$ is the codomain of $\alpha$.

We can define $\gamma:R\to T$ as the function $\gamma(r)=r$, which is well-defined because $R=\alpha(S)\subseteq T$. Clearly, $\gamma$ is injective because every distinct element in $R$ is mapped to itself (as an element of $T$). You can think of $\gamma$ as an identity map where the codomain is (possibly) larger than the domain.

Then, just define $\beta: S\to R$ as $s\mapsto \alpha(s)$. Remember that we defined $R=\alpha(S)$, and so $\beta$ is well-defined and it is clearly surjective as well. (The proof of this is left as an exercise for the reader.)

Your answer gets the general idea of what to do, but make sure you aren't "assuming" the requirements of the problem. We don't "assume" that $\gamma$ is one-to-one, we define $\gamma$ and then we show that it is one-to-one. It's a subtle distinction, but it's critically important to understanding the essence of the problem.