Equivalence between an injection and a surjection

[mtayab1994]

Homework Statement

Let A and B be two sets.

Homework Equations

Prove that there exists a injection from A to B if and only if there exists a surjection from B to A

The Attempt at a Solution

I did one implication which is we suppose that f: B→A is a surjection.
Then by definition of a surjection: $$\forall a\in A,\exists b\in B/f(b)=a$$
Then for each a in A we consider the nonempty set $$f^{-1}(a)$$
and I let an arbitrary b in $$f^{-1}(a)$$ and then I defined the function:

g: A→B so we get g(a)=b for our choice of b in $$f^{-1}(a)$$ and this is injective, because f was a function that we established earlier so if we take b1 in $$f^{-1}(a_{1})$$
and b2 in $$f^{-1}(a_{2})$$ then it's simple to see that b1≠b2, but if they were equal then by definition:

a1=f(b1)=f(b2)=a2. So therefore g is injective. Is this correct so far?

 

[LCKurtz]

Homework Statement

Let A and B be two sets.

Homework Equations

Prove that there exists a injection from A to B if and only if there exists a surjection from B to A

Supose A = {1,2,3}, B = {1,2,3,4,5}. Then f(n) = n for n = 1,2,3 is an injection form A to B. But there is no surjection from B to A.

[Edit, added later]: You can safely ignore this post as noted below.

 

[Mandelbroth]

Supose A = {1,2,3}, B = {1,2,3,4,5}. Then f(n) = n for n = 1,2,3 is an injection form A to B. But there is no surjection from B to A.

Really?

Maybe I'm misunderstanding. Let $g:B\to A, x\mapsto\left\{\begin{matrix} 1 & \text{if } x\in\{1,4,5\} \\ 2 & \text{if } x=2 \\ 3 & \text{if } x=3\end{matrix}\right.$. Isn't this a surjection? Its image is clearly equal to its codomain, right?

 

[pasmith]

Supose A = {1,2,3}, B = {1,2,3,4,5}. Then f(n) = n for n = 1,2,3 is an injection form A to B. But there is no surjection from B to A.

Take $f: B \to A$ with $f(x) = x$ for $x \in \{1, 2, 3\}$ and $f(4)$ and $f(5)$ arbitrary. Then f is a surjection (for every $a \in A$ there exists at least one $b \in B$ such that $f(b) = a$.

What does not exist is an injection from B to A.

 

[LCKurtz]

Really?

Maybe I'm misunderstanding. Let $g:B\to A, x\mapsto\left\{\begin{matrix} 1 & \text{if } x\in\{1,4,5\} \\ 2 & \text{if } x=2 \\ 3 & \text{if } x=3\end{matrix}\right.$. Isn't this a surjection? Its image is clearly equal to its codomain, right?

Yes. Sorry, I was thinking bijection when I was reading surjection.

 

[mtayab1994]

So the first implication of the proof is fine right?

 

[LCKurtz]

So the first implication of the proof is fine right?

Yes, I think your reasoning is OK.

 

[pasmith]

Homework Statement

Let A and B be two sets.

Homework Equations

Prove that there exists a injection from A to B if and only if there exists a surjection from B to A

The Attempt at a Solution

I did one implication which is we suppose that f: B→A is a surjection.
Then by definition of a surjection: $$\forall a\in A,\exists b\in B/f(b)=a$$
Then for each a in A we consider the nonempty set $$f^{-1}(a)$$
and I let an arbitrary b in $$f^{-1}(a)$$ and then I defined the function:

g: A→B so we get g(a)=b for our choice of b in $$f^{-1}(a)$$

At this point you could note that if $g(a) \in f^{-1}(\{a\})$ then by definition $f(g(a)) = a$, and the proof that g is injective is then straightforward.

and this is injective,
because f was a function that we established earlier so if we take b1 in $$f^{-1}(a_{1})$$
and b2 in $$f^{-1}(a_{2})$$ then it's simple to see that b1≠b2, but if they were equal then by definition:

a1=f(b1)=f(b2)=a2. So therefore g is injective. Is this correct so far?

This is correct.

A point of notation: $f^{-1}(\{a\}) \subset B$ is the pre-image of the singleton subset $\{a\} \subset A$, which is well-defined even if f is not a bijection. This must be distinguished from $f^{-1}(a) \in B$, which is the image of $a \in A$ under the inverse of f, which is not well-defined unless f is a bijection.

 

[mtayab1994]

At this point you could note that if $g(a) \in f^{-1}(\{a\})$ then by definition $f(g(a)) = a$, and the proof that g is injective is then straightforward.



This is correct.

A point of notation: $f^{-1}(\{a\}) \subset B$ is the pre-image of the singleton subset $\{a\} \subset A$, which is well-defined even if f is not a bijection. This must be distinguished from $f^{-1}(a) \in B$, which is the image of $a \in A$ under the inverse of f, which is not well-defined unless f is a bijection.

Thank you every much for the information I really appreciate it .