Surjective function

Surjection. There is an arrow to every element in the codomain B from (at least) one element of the domain A.

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.

Not a surjection. No element in the domain A is mapped to the element {4} in the codomain B.

Basic properties

Formally:

$f:A\rightarrow B$  is a surjective function if  $\forall b\in B\,\,\exists a\in A$ such that $f(a)=b\,.$

where the element $b$ is called the image of the element $a$, and the element $a$ a pre-image of the element $b$.

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):ℝ→ℝ 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 y_o we can find at least one real number x_o such that y_o=f(x_o).

Finding a pre-image x_o for a given y_o is equivalent to either question:

• Does the equation f(x)-y_o=0 have a solution? or
• Does the function f(x)-y_o 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 a≠0 is a surjection. (It is also an injection and thus a bijection.)

Proof: Substitute y_o into the function and solve for x. Since a≠0 we get x= (y_o-b)/_a. This means x_o=(y_o-b)/_a is a pre-image of y_o. This proves that the function y=ax+b where a≠0 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. a≠0 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)=x³-3x is a surjection.

Discussion: The cubic equation x³-3x-y_o=0 has real coefficients (a₃=1, a₂=0, a₁=–3, a₀=–y_o). Every such cubic equation has at least one real root. Since the domain of the polynomial is ℝ, the means that ther is at least one pre-image x_o in the domain. That is, (x₀)³-3x₀-y_o=0. So the function is a surjection. (However, this function is not an injection. For example, y_o=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) = x² is not a surjection. There is no x such that x² = −1. The range of x² 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, f_N(x):ℝ → [0,+∞) where f_N(x) = x² 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) = 10^x is not a surjection. The range of 10^x is (0,+∞), that is, the set of positive numbers. (This function is an injection.)

Surjection. f(x):ℝ→ℝ (and injection)	Surjection. f(x):ℝ→ℝ (not an injection)	Not a surjection. f(x):ℝ→ℝ (nor an injection)
Not a surjection. f(x):ℝ→ℝ (but is an injection)	Surjection. f(x):(0,+∞)→ℝ (and injection)	Surjection. z:ℝ²→ℝ, z=y. (The picture shows that the pre-image of z=2 is the line y=2.)

Other examples with real-valued functions

Example: The logarithmic function base 10 f(x):(0,+∞)→ℝ defined by f(x)=log(x) or y=log₁₀(x) is a surjection (and an injection). (This is the inverse function of 10^x.)

• The projection of a Cartesian product A × B onto one of its factors is a surjection.

Example: The function f((x,y)):ℝ²→ℝ defined by z=y is a surjection. Its graph is a plane in 3-dimensional space. The pre-image of z_o is the line y=z_o in the x0y plane.

• In 3D games, 3-dimensional space is projected onto a 2-dimensional screen with a surjection.

Related pages

• Injective function
• Bijective function

Other websites

• "Injective, Surjective, Bijective". 2013. Retrieved 2013-12-01. interactive quiz
• "Injectivity, Surjectivity". Wolfram alpha. Archived from the original on 2013-11-25. Retrieved 2013-12-01. interactive