# Thread: Injection implied by Surjection

1. ## Injection implied by Surjection

Hey all, some help with the following proof would be appreciated:

Let A and B be sets. There exists an injection from A to B if and only if there exists a surjection from B to A.

Makes sense logically because this means no element of A is left out, but I'm not sure how to word it in a proof.

2. Originally Posted by jstarks44444
Let A and B be sets. There exists an injection from A to B if and only if there exists a surjection from B to A.
Leave out any nonsense about empty sets.
Say that $\displaystyle g:A\to B$ is injective.
We want to find a surjection $\displaystyle f:B\to A$.

The image set $\displaystyle g[A]\subseteq B.$ So for each $\displaystyle y\in B$ either $\displaystyle y\in g[A]\text{ or not}$.
Because $\displaystyle g$ is injective, if $\displaystyle y\in g[A]$ there is a unique $\displaystyle a_y\in A$ such that $\displaystyle g\left( {a_y } \right) = y$.
Now select any $\displaystyle b\in A$. Fix it.
We now define $\displaystyle f:B\to A$.
$\displaystyle f(z)=a_z\text{ if }z\in g[A]\text{, else }f(z)=b$.
That is a surjection. Prove it.

3. "if and only if" This means you have two implications. You did just one of them.

4. Originally Posted by veileen
"if and only if" This means you have two implications. You did just one of them.
Of course I did only one of them.
THIS IS NOT A HOMEWORK SERVICE!
I will not do complete questions.

What business is it of yours anyway?

5. Well, you said nothing about the second implication and jstarks44444 could think that is the whole proof.

"What business is it of yours anyway?" Uhm, what? o.o