Suppose $X$ is an infinite set and $Y$ is a finite set. Show that exists a surjective function $f:X\rightarrow Y$ and an injective function $g:Y\rightarrow X$.

  • 1
    $\begingroup$ Hint: Select as many elements from $X$ as $Y$ has elements, and set up a bijection. Can you see how to extend that to a surjection $X\to Y$ (in the first case)/an injection$Y\to X$ (in the second case)? $\endgroup$ – celtschk Jul 28 '16 at 23:28

Assume $Y$ is non empty (otherwise, statement is not true). Since $|Y|$ is finite, let $|Y|=n$ for some $n \in \{1,2,...\}$. Thus, $Y=\{a_1,a_2,...,a_n\}$ Then select $n$ distinct elements from $X$ (you can do that since $X$ is infinite). Call these elements $b_1, b_2,...,b_n$. Then set $f: X \rightarrow Y$ to be $$f(b_1)=a_1$$ $$f(b_2)=a_2$$ $$...$$ $$f(b_n)=a_n$$ and set $f(x)=a_1$ for all other $x \in X$. Then this function is surjective.

To find an injective function, set $g: Y \rightarrow X$ to be $$g(a_1)=b_1$$ $$f(a_2)=b_2$$ $$...$$ $$f(a_n)=b_n$$ By choice of $b_1,...,b_n$, this function is injective.

  • $\begingroup$ Thank you, it makes sense, but as im stil learning set theory, im not sure when i can just select n distinct elements from an infinite set for example. Is the axiom of choice enabling me to do it? If so, how can i be sure that all bn's bn's are distinct? $\endgroup$ – Diogo Bodas Jul 29 '16 at 3:14
  • $\begingroup$ Imagine an infinite set $X$. It consists of infinitely many elements, is that correct? Thus, there are infinitely many distinct elements in it. Another way of thinking about it is that if $X$ DID NOT have infinitely many distinct elements, then it would have only finitely many elements. $\endgroup$ – Pawel Jul 29 '16 at 16:06
  • $\begingroup$ Let's say you want $n$ distinct elements. Choose one element from the set. Call it $b_1$. Then there exists some other element in the set $X$ different from $b_1$ (if it was not the case, then $X$ would consist of only one element, a contradiction). Call that element $b_2$. Then there exist some other element, call it $b_3$ that is different from $b_1$ and $b_2$ (if such an element did not exist, then $X$ would consist of only 2 elements, a contradiction). Continue this way to obtain a set of $n$ distinct elements. $\endgroup$ – Pawel Jul 29 '16 at 16:10
  • $\begingroup$ Now i understand, thank you again $\endgroup$ – Diogo Bodas Jul 29 '16 at 16:30

You can do it by induction on $|Y|$; however a key word is missing in the statement, that is, $Y$ must be non empty.

If $|Y|=1$, the result is obvious.

Suppose $|Y|=n+1$ and that you're able to find a surjection $X\to Z$ when $|Z|=n$. Let $a\in X$ and $b\in Y$; then $Y'=Y\setminus\{b\}$ has $|Y'|=n$ and $X'=X\setminus\{a\}$ is infinite. By the induction hypothesis there is a surjective function $f'\colon X'\to Y'$. Extend $f'$ to a function $f\colon X\to Y$ by $f(a)=b$.

Finally, every surjection $f\colon X\to Y$ admits a function $g\colon Y\to X$ such that $f\circ g(y)=y$ for all $y\in Y$. Prove that $g$ is injective.

  • $\begingroup$ Thank you!! $g$ is injective because it has a left inverse,$f$, right? $\endgroup$ – Diogo Bodas Jul 29 '16 at 15:54
  • $\begingroup$ @DiogoBodas Yes: the right inverse of surjection has a left inverse, so it is injective. $\endgroup$ – egreg Jul 29 '16 at 15:56

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.