Answer to Question #261541 in Discrete Mathematics for Amraj

Question

A function f is said to be one-to-one, or an injection, if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f. Note that a function f is one-to-one if and only if f(a) ≠ f(b) whenever a ≠ b. This way of expressing that f is one-to-one is obtained by taking the contrapositive of the implication in the definition. A function f from A to B is called onto, or a surjection, if and only if for every element b ∈ B there is an element a ∈ A with f(a) = b. A function f is onto if ∀y∃x( f(x) = y), where the domain for x is the domain of the function and the domain for y is the codomain of the function

Now consider that f is a function from A to B, where A and B are finite sets with |A| = |B|. Show that f is one-to-one if and only if it is onto.

Answer 1

Consider that $f: A \to B$, where $A$ and $B$ are finite sets with $|A| = |B|.$ Let us show that $f$ is one-to-one if and only if it is onto.

If $f$ is one-to-one, then $f(x)\ne f(y)$ for any $x\ne y,$ and hence the set $Im(f)=\{f(a):a\in A\}$ has the same number of different elements as $A$. It follows that $|Im(f)|=|A|=|B|.$ Since $Im(f)\subset B$ and $B$ is finite, we conclude that $Im(f)=B,$ and hence $f$ is onto.

If $f$ is onto, then the preimage $f^{-1}(b)\ne\emptyset$ for any $b\in B.$ Let us prove using the method by contradiction. Suppose that $f$ is not one-to-one. Then $f(x)=f(y)=b$ for some $x,y\in A, b\in B, x\ne y.$ Then $A\supset f^{-1}(b)\supset\{x,y\}.$ Since $|f^{-1}(b)|\ge2$ and $|B|=|A|,$ we conclude that $|f^{-1}(b')|=0$ for some $b'\in B.$ We get that $f^{-1}(b')=\emptyset,$ and so we have the contradiction with $f^{-1}(b')\ne\emptyset.$ This contraction proves that $f$ is one-to-one.