Surjective function

In mathematics, a **surjective** or **onto** function is a  function *f*&nbsp;:&nbsp;*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:
:f:A \rightarrow B&nbsp; is a surjective function if &nbsp;\forall b \in B \,\, \exists a \in A&nbsp;such that&nbsp;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*):&#8477;→&#8477; 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*&ne;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*&ne;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*&ne;0 is a surjection. (Since there is exactly one pre-image, this function is also an injection.)
:Practical example: *y*= &ndash;2*x*+4. What is the pre-image of *y*=2? Solution: Here *a*= &ndash;2, i.e. *a*&ne;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*3-3*x* is a surjection. 
:Discussion: The cubic equation *x*3-3*x*-*y*o=0 has real coefficients (*a*3=1, *a*2=0, *a*1=&ndash;3, *a*0=&ndash;*y*o). Every such cubic equation has at least one real root. Since the domain of the polynomial is &#8477;, the means that ther is at least one pre-image *x*o in the domain. That is, (*x*0)3-3*x*0-*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*=&ndash;1 and *x*=2. In fact, every *y*, &ndash;2≤*y*≤2 has at least 2 pre-images.)

**Example:** The quadratic function *f*(*x*) = *x*2 is **not** a surjection. There is no *x* such that *x*2 = −1. The range of *x*&sup2; 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*N(*x*):&#8477; → [0,+∞) where *f*N(*x*) = *x*2 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.)

### Other examples with real-valued functions
**Example:** The **logarithmic function base 10**  *f*(*x*):→&#8477; defined by *f*(*x*)=log(*x*) or *y*=log10(*x*) is a surjection (and an injection). (This is the inverse function of 10*x*.)

*The projection of a Cartesian product  onto one of its factors is a surjection.

**Example:** The function *f*((*x*,*y*)):&#8477;&sup2;→&#8477; 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 *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

## References
## Other websites
*  interactive quiz
*  interactive