# When the size of two finite sets is equal

• Dec 21st 2011, 05:53 PM
issacnewton
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
(Emo)
• Dec 21st 2011, 07:28 PM
Deveno
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?
• Dec 21st 2011, 09:29 PM
nikhilbhr
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.
• Dec 21st 2011, 09:30 PM
nikhilbhr
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.
• Dec 22nd 2011, 02:57 AM
Plato
Re: When the size of two finite sets is equal
Quote:

Originally Posted by issacnewton
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?