Explore BrainMass

One-to-one and Onto Functions

Suppose that X and Y are finite sets, with m and n elements respectively. Suppose
further that the function f : X → Y is one-to-one and the function g : X →Y is
(i) Use the function f to show that m ≤ n.
(ii) Use the function g to show that m ≥ n.
(iii) Is f : X → Y onto? Justify your assertion.
(iv) Is the function g : X → Y one-to-one? Justify your assertion.

(i) f : X → Y is one-to-one, so every element in X must have a distinct image in Y. For this to be true there can't be more elements in Y than there are in X else you'd have one or more elements in X mapping to the same element in Y. So m ≤ n.

(ii) g: X → Y is onto, so each element of Y is the image of some element in X. There must be at least as many elements in X as there are in Y for this to be true otherwise g: X → Y does not conform to a definition of a function i.e. every x in X must belong to a unique ordered pair in (x,y) in f. So m ≥ n.

(iii) You have no way of knowing whether f : X → Y is onto. For example, if Y had one more element than X then one element of Y under f would not map to an element in X.

(iv) Again, I don't think there's any way of knowing, is there?

Solution Summary

One-to-one and onto functions are investigated and discussed. The solution is detailed and well presented.