(Revisited$_2$) Injectivity Relies on The Existence of an Onto Function Mapping Back to Its Preimage 
QUEST:

For any sets $X$ and $Y$, there exists an injective function $f:X\rightarrow Y$ if and only if there exists a surjective function $g:Y\rightarrow X$.


QUESTION$_1$:
How do you people approach this problem. I mean, what is running through your brain when you look at each of the above statements?

KNOWN:

$\dagger\hspace{.5cm}$If $f : X \rightarrow Y$ is injective, then there exists a function $g: Y \rightarrow X$ such that $g \circ f = 1_X$.
$\dagger\hspace{.5cm}$If $f:X \rightarrow Y$ is surjective, then there must exist a function $g:Y \rightarrow X$ such that $f \circ g = 1_Y$.


THOUGHTS:
http://en.wikipedia.org/wiki/Cantor–Bernstein–Schroeder_theorem

ATTEMPT$_{Q1}$: $\leftarrow$ This attempt is wrong, just so you know...
Since $f$ is an injection it is a bijection onto its image, and so there exists an inverse $h:f(X)\rightarrow X$. Now, let $x$ be an arbitrary element in $X$, and define $g:Y\rightarrow X$ by
$$g(y) =
\begin{cases}
h(y), & \text{if }y\in f(X) \\
x, & \text{otherwise }
\end{cases},$$
so $g$ is a bijection and therefore a surjection.

QUESTION$_2$:
Let $\precsim$ be a relation defined by
$$X\precsim Y~\iff~\exists~f:X\rightarrow Y~(1-1).$$
Let $\succsim$ be a relation defined by
$$X\succsim Y~\iff~\exists~f:X\rightarrow Y~(\text{onto}).$$
How are $\precsim$ and $\succsim$ related in the context of QUEST's proof?

ATTEMPT$_{Q2}$: $\leftarrow$ Maybe somebody will check this...
By the Cantor–Bernstein–Schroeder theorem, if $X\precsim Y$ and $Y\succsim X$, then $X\cong Y$, so we can define a relation $\leq$ on cardinalities as follows:
$$\lvert X \rvert \leq \lvert Y \rvert~~~\text{if}~~~X\precsim Y,$$
namely $\exists~f~\text{s.t.}~f:X\rightarrow Y~(1-1)$, which suggests that $\leq$ is anti-symmetric since
$$\lvert X \rvert \leq \lvert Y \rvert~\text{and}~\lvert Y \rvert \leq \lvert X \rvert \iff X\precsim Y~\text{and}~Y\precsim X,$$
if and only if there exists injective maps $f:X\rightarrow Y$ and $g:Y\rightarrow X$, so there exists also an injective map $h:X\rightarrow Y$, by C-B-S, and so $X\cong Y\iff \lvert X \rvert = \lvert Y \rvert$, where $\lvert * \rvert$ denotes cardinality.
 A: You already have all the ingredients in your question.
If there is an injective function $f\colon X\to Y$, then your fact 1 gives you a function $g\colon Y\to X$; is it what you're looking for?
If there is a surjective function $g\colon Y\to X$, then your fact 2 gives you a function $f\colon X\to Y$ such that $g\circ f=1_X$ (just reverse the role of $f$ and $g$ and of $X$ and $Y$); is it what you're looking for?

Complete solution. I accept your two facts as known, but stated in a slightly different way:


*

*Every injective function has a left inverse

*Every surjective function has a right inverse


Suppose there exists an injective function $f\colon X\to Y$. By fact 1, $f$ has a left inverse, that is, a function $g\colon Y\to X$ such that $g\circ f=1_X$. I claim that the function $g$ is surjective; indeed, if $x\in X$, we have
$$
x = g\circ f(x) = g(f(x)) = g(y)
$$
where $y=f(x)$.
Suppose conversely that there exists a surjective function $g\colon Y\to X$. By fact 2, $g$ has a right inverse, that is, a function $f\colon X\to Y$ such that $g\circ f=1_X$. I claim that the function $f$ is injective; indeed, if $f(x_1)=f(x_2)$, then
$$
x_1=g\circ f(x_1) = g(f(x_1))=g(f(x_2))=g\circ f(x_2)=x_2.
$$
A: Am I the only one who sees a mistake here?
Quote:
"By the Cantor–Bernstein–Schroeder theorem, if $X\precsim Y$ and $Y\succsim X$, then $X\cong Y$, so we can define a relation $\leq$ on cardinalities as follows:"
That's not the Cantor-Bernstein-Schroeder theorem. This is the CBS theorem:
If $X\precsim Y$ and $Y\precsim X$, then $X\cong Y$
where the original poster defined $X\precsim Y$ as there exists an injective function from X to Y. 
