Results 1 to 5 of 5

Thread: When the size of two finite sets is equal

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

    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 $\displaystyle f:A\to B$

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

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

    $\displaystyle Ran(f)=f(A)=B$

    since A and B are finite with same size, $\displaystyle 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, $\displaystyle x_1,x_2$ such that $\displaystyle f(x_1)=f(x_2)$ and try to prove that
    $\displaystyle 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,546
    Thanks
    842

    Re: When the size of two finite sets is equal

    suppose that $\displaystyle f(x_1) = f(x_2)$ but that $\displaystyle 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 $\displaystyle b \in B$ has a pre-image $\displaystyle 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
    21,796
    Thanks
    2827
    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 $\displaystyle f:A\to B$
    Prove that if $\displaystyle |A|=|B|$ then $\displaystyle f$ is one to one iff $\displaystyle f$ is onto.[/tex]
    For each $\displaystyle b\in B$ then $\displaystyle f^{-1}(\{b\})$ is a nonempty subset of $\displaystyle A$.
    That is $\displaystyle |B|=|A|$ nonempty, disjoint subsets of $\displaystyle 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: Jul 5th 2012, 09:23 AM
  2. Finding equal size payments
    Posted in the Business Math Forum
    Replies: 1
    Last Post: Jan 25th 2010, 07:37 PM
  3. Proving two sets equal
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Jan 25th 2008, 07:26 AM
  4. inductive proof of size of power sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 14th 2007, 11:01 AM
  5. Finite size if finite number of subgroups
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Mar 9th 2006, 12:32 PM

Search Tags


/mathhelpforum @mathhelpforum