Let $X$ a infinite set and $Y$ a finite set. Prove exists a function $f:X\rightarrow Y$ surjective and a function $g:Y\rightarrow X$ injective.

My work:

Let $f:X\rightarrow Y$ defined $f(x_i)=y_j$ such that $i\in [X]$ and $j\in[Y]$.

Go to prove $f$ is surjective.

Let $y_k\in Y$. As $f(x_i)=y_j$ with $x_i \in X$ and $y_i\in Y$ and $X$ is a infinite set. Then exists $x_k$ such that $f(x_k)=y_k$. In consequence $f$ is surjective.

Let $g:Y\rightarrow X$ defined $g(y_i)=x_j$ such that $i\in [Y]$ and $j\in[X]$. Let $y_1\,, y_2\in Y$ such that $g(y_1)=g(y_2)\implies x_1=x_2$. Here i'm stuck. Can someone help me?

  • 1
    $\begingroup$ For the "surjective" proof you will have to rule out the case where $Y$ is empty. I do not understand your use of subscripts and square brackets ... they are not needed. $\endgroup$ – GEdgar Mar 17 '18 at 14:57

You haven't actually defined a function at all - at least, not in any way that makes sense to a reader.

Hint: the way that I think best balances rigour and sensibleness-of-proof is to do it by induction on the size of the finite set.


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.