# 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?

-

There is no really elementary proof, since this is in fact independent of the "constructive" part of the usually 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$.

-

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. - Thank you for your answer. Could you explain why$Y_x=g^{-1}(\{x\})$? How do you know that$g^{-1}$is well-defined? – ohmygoodness Sep 7 '12 at 18:26 @user39561$Y_x = g^{-1}(\{x\})$by definition.$g^{-1}(\{x\})$is always well-defined; however, it may be empty. Using surjectivity, you can show that$g^{-1}(\{x\})$is not empty because everything has a preimage. Now since$g^{-1}(\{x\})$is not empty, you now apply the axiom of choice. – William Sep 7 '12 at 18:29 So, for example, suppose$Y=\{a,b\}$and$X=\{z\}$. then there exists a surjection$g:Y\rightarrow X$. Wouldn't$(z,a)\in g^{-1}$and$(z,b)\in g^{-1}$? Forgive me if I'm being dense. – ohmygoodness Sep 7 '12 at 18:50 @user39561: We would have$g^{-1}(\{z\})=\{a,b\}$. Then in the proof we pick an element of$\{a,b\}$and send$z$to that. – André Nicolas Sep 7 '12 at 18:57 @user39561: You're quite right that$(z,a),(z,b)\in g^{-1}$. The kicker, here, is that$g^{-1}$is denoting a relation (set of ordered pairs), and not a function. Both$g$and$g^{-1}$are relations, but only$g$is a function. When we say$g^{-1}(\{z\})$, we are speaking of the image of the set$\{z\}$under the relation$g^{-1}$. This isn't the same as saying$\{g^{-1}(z)\}$--as you pointed out,$g^{-1}$isn't well-defined. (cont'd) – Cameron Buie Sep 7 '12 at 18:59 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\$.

-