# (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.

• In my head I just think size. It has to be true. – Git Gud Jul 14 '13 at 21:43
• The words left-inverse and right-inverse dance through my mind until they collide with $f$ and $g$. And then in the debris I'm reminded of the Axiom of Choice. Btw, what do you mean with "each of the above" statements when I count only one statement above? – Hagen von Eitzen Jul 14 '13 at 21:44
• "Warning: Axiom of Choice may be necessary" (this is just what runs through my head looking at this problem, I don't know if it actually is or not) – Zev Chonoles Jul 14 '13 at 21:45
• "if": choice function for $g^{-1}(\{x\})$, "only if" - well, $X = \varnothing \neq Y$ provides a counterexample. But if we exclude empty sets, choose any $x \in X$ and extend $f^{-1}$ to all of $Y$. – Daniel Fischer Jul 14 '13 at 21:46
• Sort of a collection of cones with apexes the elements of $X$ and bases are subsets in $Y$ covering $Y$. – Stefan Hamcke Jul 14 '13 at 21:47

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

• What do you mean reverse the role? – Trancot Jul 14 '13 at 22:46
• @BarisaBarukh You can write fact 2 as "if $g\colon Y\to X$ is surjective, then there exists $f\colon X\to Y$ such that $g\circ f=1_X$". Sorry, I had the wrong order in the answer. – egreg Jul 14 '13 at 22:49
• I don't see how this all fits together. – Trancot Jul 14 '13 at 22:53
• These relations are related by implication, right? (SEE EDIT) – Trancot Jul 14 '13 at 23:48

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.