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?
 A: 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.  
A: 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$. 
A: There is no really elementary proof, since this is in fact independent of the "constructive" part of the usual axioms of set theory.
However, if one has a basic understanding of the axiom of choice, then one can easily construct the injection. The axiom of choice says that if we have a family of non-empty sets then we can choose exactly one element from each set in our family.
Suppose that $g\colon Y\to X$ is a surjection then for every $x\in X$ there is some $y\in Y$ such that $g(y)=x$. I.e., the set $\{y\in Y\mid g(y)=x\}$ is non-empty.
Now consider the family $\Bigg\{\{y\in Y\mid g(y)=x\}\ \Bigg|\ x\in X\Bigg\}$, by the above sentence this is a family of non-empty sets, and using the axiom of choice we can choose exactly one element from every set. Let $y_x$ be the chosen element from $\{y\in Y\mid g(y)=x\}$. Let us see that the function $f(x)=y_x$ is injective.
Suppose that $y_{x}=y_{x'}$, in particular this means that both $y_{x}$ and $y_{x'}$ belong to the same set $\{y\in Y\mid g(y)=x\}$ and this means that $x= g(y_{x}) = g(y_{x'}) =x'$, as wanted.

Some remarks:
The above proof uses the full power of the axiom of choice, we in fact construct an inverse to the injection $g$. However, we are only required to construct an injection from $X$ into $Y$, which need not be an inverse of $g$ -- this is known as The Partition Principle:

If there exists a surjection from $Y$ onto $X$ then there exists an injection from $X$ into $Y$

It is still open whether or not the partition principle implies the axiom of choice, so it might be possible with a bit less than the whole axiom of choice.
However the axiom of choice is definitely needed. Without the axiom of choice it is consistent that there exist two sets $X$ and $Y$ such that $Y$ has both an injection into $X$ and a surjection onto $X$, but there is no injection from $X$ into $Y$.
