Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
show 2 more comments

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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