1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equivalence between an injection and a surjection

  1. Nov 11, 2013 #1
    1. The problem statement, all variables and given/known data

    Let A and B be two sets.

    2. Relevant equations

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

    3. 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: [tex]\forall a\in A,\exists b\in B/f(b)=a[/tex]
    Then for each a in A we consider the nonempty set [tex]f^{-1}(a)[/tex]
    and I let an arbitrary b in [tex]f^{-1}(a)[/tex] and then I defined the function:

    g: A→B so we get g(a)=b for our choice of b in [tex]f^{-1}(a)[/tex] and this is injective, because f was a function that we established earlier so if we take b1 in [tex]f^{-1}(a_{1})[/tex]
    and b2 in [tex]f^{-1}(a_{2})[/tex] 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?
     
  2. jcsd
  3. Nov 11, 2013 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
    Last edited: Nov 11, 2013
  4. Nov 11, 2013 #3
    Really? :confused:

    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?
     
  5. Nov 11, 2013 #4

    pasmith

    User Avatar
    Homework Helper

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

    What does not exist is an injection from B to A.
     
  6. Nov 11, 2013 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes. Sorry, I was thinking bijection when I was reading surjection. :redface:
     
  7. Nov 11, 2013 #6
    So the first implication of the proof is fine right?
     
  8. Nov 11, 2013 #7

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, I think your reasoning is OK.
     
  9. Nov 11, 2013 #8

    pasmith

    User Avatar
    Homework Helper

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

    This is correct.

    A point of notation: [itex]f^{-1}(\{a\}) \subset B[/itex] is the pre-image of the singleton subset [itex]\{a\} \subset A[/itex], which is well-defined even if f is not a bijection. This must be distinguished from [itex]f^{-1}(a) \in B[/itex], which is the image of [itex]a \in A[/itex] under the inverse of f, which is not well-defined unless f is a bijection.
     
  10. Nov 11, 2013 #9
    Thank you every much for the information I really appreciate it .
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Equivalence between an injection and a surjection
Loading...