Results 1 to 2 of 2

Math Help - one to one and onto

  1. #1
    Newbie
    Joined
    May 2012
    From
    here
    Posts
    8

    one to one and onto

    f: A --> A where A is finite. Prove f is onto if and only if f is one to one.

    if f is 1-1 then it is onto
    I was thinking that if f is a function, if a E A, then (a,b) E f and it is mapped to a unique b. therefore there must be at least as many b's as a's in order for f to be a function since A is finite. since all elements of A are present as a's and b's also come from A, all elements of A must be present as a b, therefore f is onto

    if f is onto then it is 1-1
    I was thinking that since f is onto then all elements of A are present as both first and second terms therefore there is the same number of first and second terms . if f is not 1-1 then there is at least one second term that is paired with two distinct first terms. but if there are the same number of first and second terms there will be at least one second term that cannot be paired with a unique first term since A is finite. it must then either be excluded or be paired with a first term that already appears with a different second term, both of these are contradictions since f is a function and f is onto.
    therefore, f is 1-1.

    Is this proof too informal? If it is incorrect can someone suggest a different approach
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    Re: One-to-one and onto

    Yes, your proof is too informal. The first part also does not seem to be correct since you did not use the fact that f is one-to-one.

    Suppose A=\{a_1,a_2,\ldots,a_n\} is finite with n elements and f:A\to A is one-to-one. Let f(A)=\{f(a_i):1\leqslant i \leqslant n\}. Since f is one-to-one, we have i\ne j \Rightarrow a_i\ne a_j \Rightarrow f(a_i)\ne f(a_j). Therefore f(A) has n elements since dsitnct i give rise to distinct f(a_i). But A also has n elements and f(A)\subseteq A. Hence f(A) = A; therefore given any a_j\in A, we have a_j\in f(A), i.e. there exists a_i\in A such that f(a_i)=a_j, i.e. f is onto.

    For the second part, it looks like you have the correct idea, but you need to write your proof like what I've done above. Can you do that?
    Last edited by Sylvia104; May 20th 2012 at 06:09 AM.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum