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 .