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)

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?

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.

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.

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?