Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Injection from finite set to equally sized set is surjection

  1. May 28, 2015 #1
    This is a rather simple question, so it has been rattling my brain recently.
    Consider a surjective map ## f : S \rightarrow T ## where both ## S ## and ## T ## are finite sets of equal cardinality. Then is ## f ## necessarily injective? I proved the converse, which turned out to be quite trivial, but this is giving me some trouble indeed. Any initial thoughts on whether it's true (pretty sure it is true!) and how I might go about proving it?

    Thanks!

    BiP
     
    Last edited: May 28, 2015
  2. jcsd
  3. May 28, 2015 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The truth of this is actually the basis for counting!
     
  4. May 28, 2015 #3

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    For an overkill, try inclusion/exclusion . Still, an issue with this question is the set of starting definitions.
    My working definition is that, for finite sets S,T , they have the same cardinality iff there is a bijection between them.
    What is yours, OP?
     
  5. May 28, 2015 #4
    P.S. Slight mistake, I meant to prove that surjection implies injection, not the other way around.

    I agree with the definition that two sets have equal cardinality if a bijection exists between them. But how does that prove that every surjection from ## S ## to ## T ## is also a bijection?

    So far, it is clear that ## |S| = |f(S)| ## since ## f ## is a surjection. But what next?
     
  6. May 28, 2015 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Imagine there are 30 students in a class and 30 desks. Where the students sit is a mapping from the set of students to the set of desks.

    If every desk is occupied (surjection) then every desk must have only one student (injection). How could there be two students sharing a desk unless one desk is unoccupied?

    This is simply counting, surely?
     
  7. May 28, 2015 #6

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    You don't like the inclusion/exclusion argument? It is high-powered, but I think it does the job: what is the size of f(S): it is ## |S|-| t \in T : t= f(s_k)=f(s_j), s_j, s_k \in S, s_j \neq s_j |+ |t \in T: t=f(s_j)=f(s_k)=f(s_t): s_j \neq s_k , s_j \neq s_t |+...... ##

    i.e., |f(S)\= size of S minus the number of elements of T that are "hit" twice +.. number. of elemets hit 3 times - ....
     
  8. May 28, 2015 #7

    wabbit

    User Avatar
    Gold Member

    One issue with this is that is I can't imagine the same person asking the question and understanding your answer. Can you ?
     
  9. May 28, 2015 #8

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Yes, it is too high tech for the situation, but I cant think of anything else at this point.
     
  10. May 28, 2015 #9

    wabbit

    User Avatar
    Gold Member

    The easiest way as suggested by PeroK is just counting. But if we want an abstract version with no counting, that can be applied as soon as we define "finite set" etc, maybe the following :

    Since S and T have the same cardinality, there is a bijection ##\phi: T \rightarrow S##. Let's use that and set ##g=\phi\circ f##.

    (1) g is a surjective function from S onto itself.

    Now assume f is not injective so that there exist ##x\neq y, g(x)=g(y)##, and consider the restriction h of g to ##S-\{x\}##

    (2) h has the same image as g.

    So h is a surjective function from a strict subset of S onto S.

    (3) This means that S is infinite.

    OP should check (1), (2), and (3)

    Actually (3) is kinda cheating, I am assuming that is the definition given for a finite set. If a different definition is used, proving (3) may or may not be easy. @Bipolarity, what is your definition of a finite set?
     
    Last edited: May 28, 2015
  11. May 28, 2015 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Let ##|S| = |T| = n \ (n \ge 1) ## and ##f:S \ \rightarrow \ T##

    Proposition: ##f## is a surjection iff it is an injection.

    Let ##S = \lbrace s_1 \dots s_n \rbrace## and ##T = \lbrace t_1 \dots t_n \rbrace##

    You can do this from the definition of a finite set of order ##n##

    Assume ##f## is a surjection but not a injection. ##\exists i \ne j## such that ##f(s_i) = f(s_j)##

    Now the restriction of ##f: S-s_j \ \rightarrow T ## is a surjection, hence ##|T| \le n-1##, which is a contradiction.

    Assume ##f## is an injection but not a surjection. ##\exists i## such that ##t_i## is not mapped to by ##f##

    Hence ##f## is an injection from ##S## to ##T-t_i## and ##|S| \le n-1## which is also a contradiction.
     
  12. May 29, 2015 #11
    I think you can find a surjective map that is not an injection (in fact i cheat on the word map):

    Let S={a,b} T={1,2}

    Pose f(a)=1 f(b)={1,2} a multivalued map it is clearly surjective but not injective since one image of b is the same as of a.
     
  13. May 29, 2015 #12

    wabbit

    User Avatar
    Gold Member

    No. This is not a map from S to T but from S to something else - you did not define it but whatever you choose must be a set X such that ##\{1,\{1,2\}\}\subset X##.

    It is clearly injective in any case since ##f(a)\neq f(b)##, in fact ##f(a)\in f(b) ##. It may or may not be surjective depending on what target space you decide upon.
     
  14. May 29, 2015 #13
    Yes the notation is not good but we can clearly see in a Venn diagram. Maybe if we write f(b)=1,2 ?
     
  15. May 29, 2015 #14

    wabbit

    User Avatar
    Gold Member

    Not quite, f(b)=1,2 doesn't mean much. You can define multivalued functions but they are not functions from S to T here but functions from S to 2^T. Of course you can define a notion of "multivalued surjectivity" too and derive its properties, but since this doesn't have a lot to do with the topic of this thread, perhaps a new thread would be more appropriate.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Injection from finite set to equally sized set is surjection
  1. Size of a set. (Replies: 2)

Loading...