Surjective function

|||
| --- | --- |
|width="210"|**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.
|||
| --- | --- |
|width="210"|**Not a surjection**. No element in the domain A is mapped to the element {4} in the codomain B.|

## 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.

### 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_<sub>o</sub> we can find at least one real number _x_<sub>o</sub> such that _y_<sub>o</sub>=_f_(_x_<sub>o</sub>).
Finding a pre-image _x_<sub>o</sub> for a given _y_<sub>o</sub> is equivalent to either question:

- Does the equation _f_(_x_)-_y_<sub>o</sub>=0 have a solution? or
- Does the function _f_(_x_)-_y_<sub>o</sub> 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_<sub>o</sub> into the function and solve for _x_. Since _a_≠0 we get _x_= (_y_<sub>o</sub>-_b_)/<sub>_a_</sub>. This means _x_<sub>o</sub>=(_y_<sub>o</sub>-_b_)/<sub>_a_</sub> is a pre-image of _y_<sub>o</sub>. 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_= –2_x_+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_<sup>3</sup>-3_x_ is a surjection.
- Discussion: The cubic equation _x_<sup>3</sup>-3_x_-_y_<sub>o</sub>=0 has real coefficients (_a_<sub>3</sub>=1, _a_<sub>2</sub>=0, _a_<sub>1</sub>=–3, _a_<sub>0</sub>=–_y_<sub>o</sub>). 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_<sub>o</sub> in the domain. That is, (_x_<sub>0</sub>)<sup>3</sup>-3_x_<sub>0</sub>-_y_<sub>o</sub>=0. So the function is a surjection. (However, this function is not an injection. For example, _y_<sub>o</sub>=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_<sup>2</sup> is **not** a surjection. There is no _x_ such that _x_<sup>2</sup> = −1. The range of _x_² is , 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_<sub>N</sub>(_x_):ℝ → 0,+∞) where _f_<sub>N</sub>(_x_) = _x_<sup>2</sup> 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<sup>_x_</sup> is **not** a surjection. The range of _10_<sup>_x_</sup> is (0,+∞), that is, the set of positive numbers. (This function is an injection.)

<div style="margin-left:15px">
|width="230"|<hr /> Surjection. _f_(_x_):ℝ→ℝ (and injection)|width="230"|<hr /> Surjection. _f_(_x_):ℝ→ℝ (not an injection)|width="230"|<hr /> Not a surjection. _f_(_x_):ℝ→ℝ (nor an injection)|
| --- | --- | --- | --- | --- | --- |
|width="230"|<hr />Not a surjection. _f_(_x_):ℝ→ℝ (but is an injection)|width="230"|<hr />Surjection. _f_(_x_):(0,+∞)→ℝ (and injection)|width="230"|<hr />Surjection. _z_:ℝ²→ℝ, _z_=_y_. (The picture shows that the pre-image of z=2 is the line y=2.)|
</div>

### Other examples with real-valued functions

**Example:** The **logarithmic function base 10**  _f_(_x_):→ℝ defined by _f_(_x_)=log(_x_) or _y_=log<sub>10</sub>(_x_) is a surjection (and an injection). (This is the inverse function of 10<sup>_x_</sup>.)

- The projection of a Cartesian product  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_<sub>o</sub> is the line y=_z_<sub>o</sub> in the _x_0_y_ 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

- interactive quiz
- interactive