When the size of two finite sets is equal

Printable View

December 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 $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
(Emo)
December 21st 2011, 07:28 PM
Deveno

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?
December 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.
December 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.
December 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 $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?