# Surjective function

In mathematics, a **surjective function** (also known as **surjection**, or **onto function**) is a function *f* that maps an element *x* to every element *y*; that is, for every *y*, there is an *x* such that *f*(*x*) = *y*. In other words, every element of the function's codomain is the image of *at least* one element of its domain.^{[1]}^{[2]} It is not required that *x* be unique; the function *f* may map one or more elements of *X* to the same element of *Y*.

The term *surjective* and the related terms *injective* and *bijective* were introduced by Nicolas Bourbaki,^{[3]}^{[4]} a group of mainly French 20th-century mathematicians who, under this pseudonym, wrote a series of books presenting an exposition of modern advanced mathematics, beginning in 1935. The French word *sur* means *over* or *above*, and relates to the fact that the image of the domain of a surjective function completely covers the function's codomain.

Any function induces a surjection by restricting its codomain to the image of its domain. Every surjective function has a right inverse, and every function with a right inverse is necessarily a surjection. The composition of surjective functions is always surjective. Any function can be decomposed into a surjection and an injection.

A function is bijective if and only if it is both surjective and injective.

If (as is often done) a function is identified with its graph, then surjectivity is not a property of the function itself, but rather a property of the mapping.^{[7]} This is, the function together with its codomain. Unlike injectivity, surjectivity cannot be read off of the graph of the function alone.

The function *g* : *Y* → *X* is said to be a right inverse of the function *f* : *X* → *Y* if *f*(*g*(*y*)) = *y* for every *y* in *Y* (*g* can be undone by *f*). In other words, *g* is a right inverse of *f* if the composition *f* o *g* of *g* and *f* in that order is the identity function on the domain *Y* of *g*. The function *g* need not be a complete inverse of *f* because the composition in the other order, *g* o *f*, may not be the identity function on the domain *X* of *f*. In other words, *f* can undo or "*reverse*" *g*, but cannot necessarily be reversed by it.

Every function with a right inverse is necessarily a surjection. The proposition that every surjective function has a right inverse is equivalent to the axiom of choice.

If *f* : *X* → *Y* is surjective and *B* is a subset of *Y*, then *f*(*f*^{ −1}(*B*)) = *B*. Thus, *B* can be recovered from its preimage *f*^{ −1}(*B*).

For example, in the first illustration above, there is some function *g* such that *g*(*C*) = 4. There is also some function *f* such that *f*(4) = *C*. It doesn't matter that *g*(*C*) can also equal 3; it only matters that *f* "reverses" *g*.

A function *f* : *X* → *Y* is surjective if and only if it is right-cancellative:^{[8]} given any functions *g*,*h* : *Y* → *Z*, whenever *g* o *f* = *h* o *f*, then *g* = *h*. This property is formulated in terms of functions and their composition and can be generalized to the more general notion of the morphisms of a category and their composition. Right-cancellative morphisms are called epimorphisms. Specifically, surjective functions are precisely the epimorphisms in the category of sets. The prefix *epi* is derived from the Greek preposition *ἐπί* meaning *over*, *above*, *on*.

Any morphism with a right inverse is an epimorphism, but the converse is not true in general. A right inverse *g* of a morphism *f* is called a section of *f*. A morphism with a right inverse is called a split epimorphism.

Any function with domain *X* and codomain *Y* can be seen as a left-total and right-unique binary relation between *X* and *Y* by identifying it with its function graph. A surjective function with domain *X* and codomain *Y* is then a binary relation between *X* and *Y* that is right-unique and both left-total and right-total.

The cardinality of the domain of a surjective function is greater than or equal to the cardinality of its codomain: If *f* : *X* → *Y* is a surjective function, then *X* has at least as many elements as *Y*, in the sense of cardinal numbers. (The proof appeals to the axiom of choice to show that a function
*g* : *Y* → *X* satisfying *f*(*g*(*y*)) = *y* for all *y* in *Y* exists. *g* is easily seen to be injective, thus the formal definition of |*Y*| ≤ |*X*| is satisfied.)

Specifically, if both *X* and *Y* are finite with the same number of elements, then *f* : *X* → *Y* is surjective if and only if *f* is injective.

Given two sets *X* and *Y*, the notation *X* ≤^{*} *Y* is used to say that either *X* is empty or that there is a surjection from *Y* onto *X*. Using the axiom of choice one can show that *X* ≤^{*} *Y* and *Y* ≤^{*} *X* together imply that |*Y*| = |*X*|, a variant of the Schröder–Bernstein theorem.

The composition of surjective functions is always surjective: If *f* and *g* are both surjective, and the codomain of *g* is equal to the domain of *f*, then *f* o *g* is surjective. Conversely, if *f* o *g* is surjective, then *f* is surjective (but *g*, the function applied first, need not be). These properties generalize from surjections in the category of sets to any epimorphisms in any category.

Any function can be decomposed into a surjection and an injection: For any function *h* : *X* → *Z* there exist a surjection *f* : *X* → *Y* and an injection *g* : *Y* → *Z* such that *h* = *g* o *f*. To see this, define *Y* to be the set of preimages *h*^{−1}(*z*) where *z* is in *h*(*X*). These preimages are disjoint and partition *X*. Then *f* carries each *x* to the element of *Y* which contains it, and *g* carries each element of *Y* to the point in *Z* to which *h* sends its points. Then *f* is surjective since it is a projection map, and *g* is injective by definition.

Any function induces a surjection by restricting its codomain to its range. Any surjective function induces a bijection defined on a quotient of its domain by collapsing all arguments mapping to a given fixed image. More precisely, every surjection *f* : *A* → *B* can be factored as a projection followed by a bijection as follows. Let *A*/~ be the equivalence classes of *A* under the following equivalence relation: *x* ~ *y* if and only if *f*(*x*) = *f*(*y*). Equivalently, *A*/~ is the set of all preimages under *f*. Let *P*(~) : *A* → *A*/~ be the projection map which sends each *x* in *A* to its equivalence class [*x*]_{~}, and let *f*_{P} : *A*/~ → *B* be the well-defined function given by *f*_{P}([*x*]_{~}) = *f*(*x*). Then *f* = *f*_{P} o *P*(~).