Thread: 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

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?

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.

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.

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?