Surjective function

In mathematics, a surjective or onto function is a function f : A - B with the following property. For every element b in the codomain B, there is at least one element a in the domain A such that f(a)=b. This means that no element in the codomain is unmapped, and that the range and codomain of f are the same set.
The term surjection and the related terms injection and bijection were introduced by the group of mathematicians that called itself Nicholas Bourbaki. In the 1930s, this group of mathematicians published a series of books on modern advanced mathematics. The French prefix sur means above or onto and was chosen since a surjective function maps its domain on to its codomain.
Basic properties
Formally:
is a surjective function if such that
where the element is called the image of the element , and the element a pre-image of the element .
The formal definition can also be interpreted in two ways:
Every element of the codomain B is the image of at least one element in the domain A.
Every element of the codomain B has at least one pre-image in the domain A.
A pre-image does not have to be unique. In the top image, both {X} and {Y} are pre-images of the element {1}. It is only important that there be at least one pre-image.
Examples
Elementary functions
Let f(x):R-R be a real-valued function y=f(x) of a real-valued argument x. (This means both the input and output are numbers.)
Graphic meaning: The function f is a surjection if every horizontal line intersects the graph of f in at least one point.
Analytic meaning: The function f is a surjection if for every real number yo we can find at least one real number xo such that yo=f(xo).
Finding a pre-image xo for a given yo is equivalent to either question:
Does the equation f(x)-yo=0 have a solution? or
Does the function f(x)-yo have a root?
In mathematics, we can find exact (analytic) roots only of polynomials of first, second (and third) degree. We find roots of all other functions approximately (numerically). This means a formal proof of surjectivity is rarely direct. So the discussions below are informal.
Example: The linear function of a slanted line is onto. That is, y=ax+b where a0 is a surjection. (It is also an injection and thus a bijection.)
Proof: Substitute yo into the function and solve for x. Since a0 we get x= (yo-b)/a. This means xo=(yo-b)/a is a pre-image of yo. This proves that the function y=ax+b where a0 is a surjection. (Since there is exactly one pre-image, this function is also an injection.)
Practical example: y= -2x+4. What is the pre-image of y=2? Solution: Here a= -2, i.e. a0 and the question is: For what x is y=2? We substitute y=2 into the function. We get x=1, i.e. y(1)=2. So the answer is: x=1 is the pre-image of y=2.
Example: The cubic polynomial (of third degree) f(x)=x3-3x is a surjection.
Discussion: The cubic equation x3-3x-yo=0 has real coefficients (a3=1, a2=0, a1=-3, a0=-yo). Every such cubic equation has at least one real root. Since the domain of the polynomial is R, the means that ther is at least one pre-image xo in the domain. That is, (x0)3-3x0-yo=0. So the function is a surjection. (However, this function is not an injection. For example, yo=2 has 2 pre-images: x=-1 and x=2. In fact, every y, -2<=y<=2 has at least 2 pre-images.)
Example: The quadratic function f(x) = x2 is not a surjection. There is no x such that x2 = -1. The range of x2 is [0,+) , that is, the set of non-negative numbers. (Also, this function is not an injection.)
Note: One can make a non-surjective function into a surjection by restricting its codomain to elements of its range. For example, the new function, fN(x):R - [0,+) where fN(x) = x2 is a surjective function. (This is not the same as the restriction of a function which restricts the domain!)
Example: The exponential function f(x) = 10x is not a surjection. The range of 10x is (0,+), that is, the set of positive numbers. (This function is an injection.)
Other examples with real-valued functions
Example: The logarithmic function base 10 f(x):(0,+)-R defined by f(x)=log(x) or y=log10(x) is a surjection (and an injection). (This is the inverse function of 10x.)
The projection of a Cartesian product onto one of its factors is a surjection.
Example: The function f((x,y)):R2-R defined by z=y is a surjection. Its graph is a plane in 3-dimensional space. The pre-image of zo is the line y=zo in the x0y plane.
In 3D games, 3-dimensional space is projected onto a 2-dimensional screen with a surjection.