Solution to A function f is said to be one-to-one, or an injection, if and only if … - Sikademy
Author Image

Archangel Macsika

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.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-997-qpid-852