elementary set theory - (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.

Answer

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:

1. Every injective function has a left inverse


2. 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.$$