Prove the following statement are equivalent

Question

Let $|A| = |B| = n$ and let $f : A \to B$ be everywhere defined function. Prove that the following three statements are equivalent.

1. $f$ is one to one.
2. $f$ is onto.
3. $f$ is one-to-one correspondence (that is, $f$ is one-to-one and onto).

I don't know how to solve this question. Is this the question where I need to show reflexive , symmetric and transitive?

Answer 1

Intuitively, the two sets of elements have the same finite number of elements. A function can be one-to-one or not. If it is one-to-one, then every one of the $n$ elements of $A$ are mapped to $n$ different elements of $B$. But $B$ only has $n$ elements so all elements are mapped to. If all the element of $B$ are mapped to then $f$ is onto as well.

So $f$ being one-to-one $\implies f$ is onto. So 1) implies 2). And if $f$ one-to-one then it is onto, is it is both one to one and onto so 1) implies 3)

And a function can be onto or not. If $f$ is onto every $n$ element of $B$ is mapped to. As the $n$ different values that are mapped to, most come from different values the must be mapped to from at least $n$ different elements of $A$. But $A$ only has $n$ elements so no two of them can map to the same element. So all the $n$ elements of $A$ are mapped to different elements of $B$. So $f$ is one-to-one.

So $f$ being onto implies $f$ is one to one. So 2) \implies 1). And if $f$ is onto then $f$ is one-to-one so it is both one to one and onto so 2) implies 3).

And if $f$ is both one to one and onto. Then it is one-to-one so 3) implies 1). And if $f$ is both then it is onto so 3) implies 2).

And that's it. Each one by itself implies all the others so they are equivalent.

===

It's not nescessary but it informative to note that not being one-to-one implies $f$ is not onto.

If $f$ is not one to one then there are two elements in $A$ that map to the same elements of $B$. There are only $n-2$ other elements in $A$ to be mapped from, but there are $n-1$ more elements $B$ to be mapped to. So there are not enough elements left in $A$ to map to all the elements left in $B$. So some elements in $B$ will not be mapped to. So $f$ is not onto.

And if $f$ is not onto then there is an element of $B$ not mapped to. Now all the $n$ elements of $A$ must be mapped from, but there is at most $n-1$ elements for them to be mapped to. SO some of the elements of $A$ must be mapped to the same element of $B$. So $f$ is not one-to-one.

Answer 2

You only have to prove that 1. and 2. are equivalent. To this end let $A=\{a_1,...,a_n\}$ and $B=\{b_1,...,b_n\}$ with $a_i \ne a_j, b_i \ne b_j$ for $i \ne j.$

We have $f(A)=\{f(a_1),...,f(a_n)\} \subseteq B.$

1. implies 2.: Since $f$ is one to one, $f(a_i) \ne f(a_j)$ for $i \ne j.$ Hence $f(A)$ has $n$ elements. This gives $f(A)=B.$

2. implies 1.: let $f$ be onto and assume that there are $i,j$ such that $i \ne j$ and $f(a_i)=f(a_j).$ We get $|f(A)|<n,$ a contradiction, sinc $f(A)=B.$