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

Prove that if then is one to one iff

is onto.

I have proved one direction and I am trying to prove the other direction. i.e.

If is onto then its one to one. Here are few things which I have come up with. Since is onto

since A and B are finite with same size,

So to prove that f is one to one, should I just assume that there are two

values, such that and try to prove that

. 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 but that , 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 has a pre-image . 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

Prove that if

then

is one to one iff

is onto.[/tex]

For each then is a nonempty subset of .

That is nonempty, disjoint subsets of .

Can any one of them contain more than one term?