Question

6. Let A and B be some finite sets with N elements. • Prove that any onto function : A B is an one-to-one function. • Prove that any one-to-one function /: A B is an onto function. • How many different one-to-one functions f: A+B are there?

Answer 1

6.  

Given A and B are finite sets with N elements

i) let $\inline f:A\rightarrow B$ be an onto function

since f is onto every element of B is an image of elements of A

that is range of f = B

to prove that f is one - to one

suppose f is not one -to-one

then distinct elements of A does not have distinct images in B

that is

for $x_{1},x_{2}\epsilon A;f(x_{1})=f({x_{2}})\Rightarrow x_{1}\neq x_{2}$

this means the two distinct elements $\inline x_{1},x_{2}\epsilon A$ have same images in B

Also the number of elements in A and B are same

so there exist an element in B which is not an image of element of A

then range of is not equal to B, which is a contradiction to f is onto

hence our assumption is wrong

hence f is one - to- one

ii) let $\inline f:A\rightarrow B$ be a one -to- one function with the number of elements in A and B is N

since f isone -to-one every element of B has distinct pre images in A

that is

$for\; x_{1},x_{2}\epsilon A;f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}$

to prove that f is onto

suppose f is not onto

then $range\: f\: \neq B$

this means there exist one element in B which is not an image of any element inA

Also A and B have same number of elements

and two distinct elements of A have same images in B

that is

$f(x_{1})=f(x_{2})\Rightarrow x_{1}\neq x_{2}\; \; ;x_{1},x_{2}\epsilon A$ , which contradicts that f is one-to-one

hence our assumption was wronfg

hence f is onto

iii) the number of distinct one to one functions from A to B is N! since the number of elements of A = number of elements of B=N