Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

"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

share|improve this question

3 Answers 3

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.

share|improve this answer
    
I think this is the best way to answer this question. –  Vadim Feb 16 at 22:56
    
Thank you, @Vadim! –  Asaf Karagila Feb 16 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.