"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
Best Answer
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.