In the previous section it was said that the range of a function from a first set into a second set is contained in that second set because it is a subset. The word into makes no restriction on the size of the range. (But it cannot be empty because there would be no function.) Therefore, it may happen that the range is all of the second set. Abstractly, the situation is shown in the adjacent figure. All the elements in the second set are images. Intuitively speaking, this means that every element in the second set is on the "receiving end" of the function's arrows, and the second set can be written in blue, instead of black.
[3.1a] The range of a function from a first set onto a second set is all of the second set.
[3.1b] A function is onto a second set if and only if every element in that second set is an image under the function.
[3.1c]
In the truth set of ordered pairs of a function from a first set onto a second set, every element of the second set appears as a second coordinate of all the ordered pairs. (That all the elements of the first set appear once and only once as first coordinates still is true, because the relation is actually a function in this section.)
The adjoining figure Fig D is a modification of Fig C. The black elements which are not images of anything have been removed and the new second set is made smaller. Now the entire second set is the range of the function. Each element now has an arrow pointing at it and is therefore an image. The function is "onto" this new second set.
Another example,
[3.2] suppose a function from a first set = {1,2,3,4,5,6,7} into a second set = {35,40,45,50} is defined by:
As another check that the function is "onto" a list (which turns out to be a partition) is made of what elements in the first set "are carried onto" each element in the second set:
If the assignment 2 -> 50 is changed to 2 -> 35 then the function is no longer onto, because 50 is not the image of anything in the first set.
Let J be the set of all integers J = {...-3, -2, -1, 0, 1, 2, 3, ...} and let P be the set of all positive integers P = {1, 2, 3, ...}. The function f defined by f(x) = x2 + 1 carries all integers into the set of positive integers. A partial listing of the images is:
For more examples and discussions of functions that are onto and functions that are not onto but merely into, click here.
It should be noticed that a function is always into the second set (because all the images are there), but not always onto the second set (there may be some elements that are not images). Being into does not exclude being onto. Perhaps the word "to" should replace the word "into" to remove any confusion about being "into."
There is a natural carryover to the working definition of a function. It is suggested by [1.2b]. Suppose there is a function from a first set onto a second set. Then each element y in the second set is the image of one or more elements x. All these different x's form a collection of subset of the first set. Let y run through all the elements in the second set, producing subsets of first set.
It would not be difficult to show directly that these subsets form a partition of the first set. But this can also be done by using some equivalence relation. Two elements are related iff they have the same image under the function. It is easily verified that this relation is an equivalence relation. The subsets form a partition of the first set. Click here for more discussion of this topic.
Make a slight adjustment in Fig. C to get the adjacent figure Fig E. In Fig C two arrows point to the same blue element. The second arrow is changed to point to a different element, changing its color from black to blue. In Fig E all arrows point to different (blue) elements.
(Notice that the functions in Fig C and in Fig E are not "onto.")
[3.3a]
A function from a first set into a second set is one-to-one if all the images are distinct.
[3.3b] A function f from a first set into a second set is one-to-one if for any distinct elements (in the first set) their images (in the second set) are distinct.
This definition can be stated in terms of elements: f is one-to-one iff the following implication is always true:
[3.3c] A function from a first set into a second set is one-to-one if the following implication is always true:
Actually, the implication in [3.3b] is the contrapositive of the implication in [3.3c].
The following function from P4 into the second set {A,B,C,D,E,F,G} is one-to-one:
None of the arrows point to the same letter. Arrows from different numbers point to different letters. Definitions [3.3a] and [3.3b] are convenient to use to see if functions with small domains are one-to-one or not.
For functions defined by algebraic formulas or equations definition [3.4c] is often more useful. The function f from the set P of all positive integers into itself (P --> P) defined by f(x) = 2x is also one-to-one. To prove this, a chain of implications supports the implication in definition [3.3c]:
Before leaving this section on one-to-one functions and functions that are "onto", the products of such functions should be examined. Recall that a function g is conformable with a function f if the product gf can be formed (i.e. domain of g is contained in the range of f).
[3.4] Theorem If two functions f and g are both "onto" (and g is conformable with f), then their product gf is "onto".
Let set V be the domain of g.
Let f: U ---> V and g: V ---> W be "onto" functions. Let w be any element in W. Since g is onto (all of) W, w is an image, and this means that for some v in V, g(v) = w. Since f is onto (all of) V, v is an image, and this means that for some u in U, f(u) = v. Apply g to both sides of this last equation: gf(u) = g(v) = w. So w is an image under gf. This means that all elements of W are (indirectly) images of elements in U. Therefore, the product gf: U ---> W is "onto."
Click here to see examples of products of functions that are "onto."
[3.5] Theorem If two functions f and g are both one-to-one (and g is conformable with f), then their product gf is one-to-one.
Let set V be the domain of g.
Let f: U ---> V and g: V ---> W be one-to-one functions. Let u1 and u2 be any distinct elements of U. Since f is one-to-one, f(u1) and f(u2) are distinct elements in V. Since g is one-to-one, gf(u1) and gf(u2) are distinct elements in W. Therefore, gf carries distinct elements in U onto distinct elements in W. So gf is one-to-one.
Click here to see examples of products of functions that are one-to-one.
[3.6] A function is a one-to-one correspondence if and only if the function is both one-to-one and "onto."
If f is a one-to-one correspondence from a set U to a set V then every element in V is involved once and only once. Since every element in V is involved, every element in V is an image. Therefore, the range of f is all of V. Hence f is "onto." Also f is one-to-one because no element in V is involved more than once.
Reversing the steps and modifying some of them show that a one-to-one function that is "onto" is a one-to-one correspondence.
The statement [3.6] provides a method to show that some function is actually a one-to-one correspondence.