Let A and B be two finite sets Let f A B be any map Assume t

Let A and B be two finite sets. Let f: A -->B be any map. Assume that |A|=|B|.

(i) Show that if f is surjective, then f is injective.
(ii) Show that if f is injective, then f is surjective.

Solution

i)

Let f be surjective.

Let f not be injective

Let, a and b be two distinct elemetns in A so that

f(a)=f(b)

IN a map one element can map to only one element

Hence, remaining |A|-2 elements other than a and b map to at most |A|-2=|B|-2 elements in B

a and b map to f(a)

Hence , f maps to at most |B|-2+1 =|B|-1 elements in B

But f is sujrective to |f(A)|=|B|

HEnce contradiction

So, f is injective

ii)

Let, f be injective

Let, |A|=|B|=n

Let, elemetns of A as

a1,..,an such ai is not equal to aj with i is not equal to j

and elements of B as

b1,b2,...bn so tha

f(ai)=bi

f is injective so

f(ai) is not equal to f(aj) for i not equal to j

Hence, b1,...bn are are mutually distinct

Hence, f(A) has n=|B| elements

Hence, f is surjective