Results 1 to 5 of 5

Math Help - When the size of two finite sets is equal

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    When the size of two finite sets is equal

    Hi

    I am trying to prove the following. Suppose A and B are finite sets
    and f:A\to B

    Prove that if |A|=|B| then f is one to one iff f
    is onto.

    I have proved one direction and I am trying to prove the other direction. i.e.
    If f is onto then its one to one. Here are few things which I have come up with. Since f is onto

    Ran(f)=f(A)=B

    since A and B are finite with same size, A\sim B \Rightarrow A\sim f(A)

    So to prove that f is one to one, should I just assume that there are two
    values, x_1,x_2 such that f(x_1)=f(x_2) and try to prove that
    x_1=x_2. This is the standard approach to prove that the function is one to one but I am having difficulty with this route. Can people offer any hints ?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: When the size of two finite sets is equal

    suppose that f(x_1) = f(x_2) but that x_1 \neq x_2, that is, that one target in B has two different sources.

    well, there's only so many points of A to go around. and if we've "doubled up" two of those to send to a single point in B, how can f be onto?

    alternatively, begin with what you're given. f is ONTO.

    this means that every point b \in B has a pre-image a \in A, f(a) = b. note that every element of B must have a distinct pre-image

    in A, since f is a FUNCTION. after we've sent every element b of B "back to (a) pre-image", are there any elements of A left over?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Re: When the size of two finite sets is equal

    f:A->B
    range of f is a subset of B.
    since f is onto so the ,range of f=B=f(A).
    Now We can prove that f is one-to-one by contradiction.
    Assume x1 ,x2 belongs to A and we have
    f(x1)=f(x2) but x1!=x2.
    Since |A|=|B|,there will exist one element in B which wont have any preimage in A.
    Which means that f is not Onto ..
    hence it is proved by contradiction that when f(x1)=f(x2) then x1=x2 ie f is one-to-one.

    Correct me if i am wrong.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Re: When the size of two finite sets is equal

    f:A->B
    range of f is a subset of B.
    since f is onto so the ,range of f=B=f(A).
    Now We can prove that f is one-to-one by contradiction.
    Assume x1 ,x2 belongs to A and we have
    f(x1)=f(x2) but x1!=x2.
    Since |A|=|B|,there will exist one element in B which wont have any pre image in A.
    Which means that f is not Onto ..
    hence it is proved by contradiction that when f(x1)=f(x2) then x1=x2 ie f is one-to-one.

    Correct me if i am wrong.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1606
    Awards
    1

    Re: When the size of two finite sets is equal

    Quote Originally Posted by issacnewton View Post
    Suppose A and B are finite sets
    and f:A\to B
    Prove that if |A|=|B| then f is one to one iff f is onto.[/tex]
    For each b\in B then f^{-1}(\{b\}) is a nonempty subset of A.
    That is |B|=|A| nonempty, disjoint subsets of A.
    Can any one of them contain more than one term?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equal power sets -> Equal sets?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 5th 2012, 09:23 AM
  2. Finding equal size payments
    Posted in the Business Math Forum
    Replies: 1
    Last Post: January 25th 2010, 07:37 PM
  3. Proving two sets equal
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 25th 2008, 07:26 AM
  4. inductive proof of size of power sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 14th 2007, 11:01 AM
  5. Finite size if finite number of subgroups
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: March 9th 2006, 12:32 PM

Search Tags


/mathhelpforum @mathhelpforum