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.
Here's the Solution to this Question
Let , where and are finite sets with
Let us show that is one-to-one if and only if it is onto.
If is one-to-one, then for any and hence the set has the same number of different elements as . It follows that Since and is finite, we conclude that and hence is onto.
If is onto, then the preimage for any Let us prove using the method by contradiction. Suppose that is not one-to-one. Then for some Then Since and we conclude that for some We get that and so we have the contradiction with This contraction proves that is one-to-one.