Answer to Question #261717 in Discrete Mathematics for ojal

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

We have next statement: for finite sets A and B such that |A| = |B| (f:A->B is one to one)$\leftrightarrow$(f:A->B is onto)

((f:A->B is one to one)$\leftrightarrow$(f:A->B is onto)) = ((f:A->B is one to one)$\to$(f:A->B is onto))$\land$((f:A->B is onto)$\to$(f:A->B is one to one))

So, to prove the given statement we will prove two statements:

1) ((f:A->B is one to one)$\to$(f:A->B is onto))

2) ((f:A->B is onto)$\to$(f:A->B is one to one))

Letter b means b $\in$ B, other letters $\isin$ A

1) Let's suppose that (f:A->B is one to one)$\land$(f:A->B is not onto) $\implies$($f(a)\not=f(c)\leftrightarrow a\not=c)$$\land$$(\exists b\forall a(f(a) \not=b))\to |A| < |B|$. But |A| = |B|, so we came to the contradiction, which means our assumption is false, so (f:A->B is onto). The first statement is proven

2) Let's suppose that (f:A->B is onto)$\land$(f:A->B is not one to one) $\implies$($∀b∃a( f(a) = b)$$\land$$(\exists a,c:(f(a)=f(c))\land(a \not=b))\to |A| > |B|$. But |A| = |B|, so we came to the contradiction, which means our assumption is false, so (f:A->B is one to one). The second statement is proven

The statement has been proven