# Elementary Set Theory proof regarding infinite and finite sets

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

• 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)? – 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.

• 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? – Diogo Bodas Jul 29 '16 at 3:14
• 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. – Pawel Jul 29 '16 at 16:06
• 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. – Pawel Jul 29 '16 at 16:10
• Now i understand, thank you again – 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.

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