# Proof if there is an injective mapping between two infinite sets, a surjective mapping exists.

"Let $A$, $B$ be two infinite sets. Suppose that $f: A \to B$ is injective. Show that there exists a surjective map $g: B \to A$"

I am not sure how to go about this proof, I am trying to gather information to help me, and deduce as much as I can: . Since $f$ is injective we know that $|A| \leq |B|$.

. If g is surjective then $|A| \geq |B|$.

. Thus $|A| = |B|$ (For this to hold)

. This suggests that we cannot have one countable and one uncountable set.

. I would start by assuming by contradiction that no such surjective map exists. I am thinking perhaps by removing the elements $b$ from $B$ that are not mapped to from A we would have an injective map $g: A \to B\setminus\{b\}$. However this is as far as I have got, can someone tell me if I am on the right track and if so where to go from here, or if I have got the completely wrong train of thought? Thanks

-

You're going at it all wrong.

Consider the case $f\colon\Bbb N\to\Bbb R$ defined by $f(n)=n$. That is an injective function, but certainly not surjective. Can you think about a surjection from $\Bbb R$ onto $\Bbb N$? For example, $g(x)=\begin{cases} x&x\in\Bbb N\\ 0&x\notin\Bbb N\end{cases}$ is a surjection.

More generally, note that if $f\colon A\to B$ is injective, then $\{(f(a),a)\mid a\in A\}$ is a function from a subset of $B$ into $A$. What are the properties of this function, and how do you complete it to a function whose domain is $B$ itself -- that I am leaving to you to figure out.

-
I think this is the best way to answer this question. – Vadim Feb 16 '14 at 22:56
Thank you, @Vadim! – Asaf Karagila Feb 16 '14 at 22:58

Definition of $g$:

If $y=f(x)\in F(A)$, $g(y)=x$.

If $y\in B\backslash f(A)$, $g(y)=$ arbitrary.

The function is well-defined because $f$ is injective.

-

Let $B_1 = f(A), B_2 = B \setminus B_1$, $a_0 \in A$.

For $x \in B_1$, let $g(x)$ be the unique element $a \in A$ such that $f(a) = x$.

For $x \in B_2$, let $g(x) = a_0$.

Then $g(B) = A$.

-