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

  • $\begingroup$ Asaf can you tell me what to look up for more information on the last remark in your answer? When we say 'without the AC..' is that equivalent to saying if we accept the negation of 'AC'? $\endgroup$ – Prince M May 27 '17 at 4:38
  • $\begingroup$ Without AC just means without assuming AC. It may hold, or its negation may holds. The issue here is that the negation of AC is just that there is a family which does not admit a choice function. It tells you absolutely nothing constructive about that family. So for the most part, we talk about consistency results. Namely, something is consistent without choice, and on occasion we can say more (e.g. Zorn's lemma fails if AC fails). So what I mean is that it is consistent that the axiom of choice fails, and the Partition Principle fails. So it is not provable just from ZF. $\endgroup$ – Asaf Karagila May 27 '17 at 12:50

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.

  • $\begingroup$ Thank you for your answer. Could you explain why $Y_x=g^{-1}(\{x\})$? How do you know that $g^{-1}$ is well-defined? $\endgroup$ – ohmygoodness Sep 7 '12 at 18:26
  • $\begingroup$ @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. $\endgroup$ – William Sep 7 '12 at 18:29
  • $\begingroup$ 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. $\endgroup$ – ohmygoodness Sep 7 '12 at 18:50
  • $\begingroup$ @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. $\endgroup$ – André Nicolas Sep 7 '12 at 18:57
  • $\begingroup$ @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) $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.