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?

Suppose that $g$ is a surjection from $Y$ to $X$. For every $x$ in $X$, let $Y_x$ be the set of all $y$ such that $g(y)=x$. So $Y_x=g^{-1}(\{x\})$: $Y_x$ is the preimage of $x$.  Since $g$ is a surjection, $Y_x$ is non-empty for every $x\in X$.
By the Axiom of Choice, there is a set $Y_c$ such that $Y_c\cap Y_x$ is a $1$-element set for every $x$. Informally, the set $Y_c$ chooses (simultaneously) an element $y_x$ from every $Y_x$. 
Define $f(x)$ by $f(x)=y_x$. Then $f$ is an injection from $X$ to $Y$. 
Remark: Fairly elementary, I guess, but definitely non-constructive. It can be shown that for general $X$, $Y$, and $g$, the result cannot be proved in ZF$. So we really cannot do better.  
