There exists an injection from $X$ to $Y$ if and only if there exists a surjection from $Y$ to $X$. Theorem. Let $X$ and $Y$ be sets with $X$ nonempty. Then (P) there exists an injection $f:X\rightarrow Y$ if and only if (Q) there exists a surjection $g:Y\rightarrow X$.
For the P $\implies$ Q part, I know you can get a surjection $Y\to X$ by mapping $y$ to $x$ if $y=f(x)$ for some $x\in X$ and mapping $y$ to some arbitrary $\alpha\in X$ if $y\in Y\setminus f(X)$. But I don't know about the Q $\implies$ P part.
Could someone give an elementary proof of the theorem?

This requires the axiom of choice. 
Suppose $g : Y \rightarrow X$ is surjective. Then $g^{-1}(x) \neq \emptyset$ for all $x \in X$. By the axiom of choice, there is a choice function $f$ such that for all $x$, $f(x) \in g^{-1}(x)$. $f(x)$ is then the desired injection $X \rightarrow Y$. 

Technically, let $\mathcal{A} = \{g^{-1}(x) : x \in X\}$. The choice function is actually a function $\mathcal{A} \rightarrow \bigcup \mathcal{A}$. But I leave it to you to compose it with the appropriate function to get the desired $f$. 
