# Surjection

(Redirected from Surjective)

Jump to navigation
Jump to search
Error creating thumbnail: Unable to save thumbnail to destination

Error creating thumbnail: Unable to save thumbnail to destination

Error creating thumbnail: Unable to save thumbnail to destination

In mathematics, a function *f* is said to be **surjective** if and only if its values span its whole codomain; that is, for every *y* in the codomain, there is at least one *x* in the domain such that *f*(*x*) = *y*.

Said another way, a function *f*: *X* → *Y* is surjective if and only if its range *f*(*X*) is equal to its codomain *Y*. A surjective function is called a **surjection**, and said to be **onto**.

## Examples and counterexamples

- For any set
*X*, the identity function id_{X}on*X*is surjective. - The function
*f*:**R**→**R**defined by

*f*(*x*) = 2*x* + 1 is surjective, because for every real number *y* we have *f*(*x*) = *y* where *x* is (*y* - 1)/2.

- The natural logarithm function ln: (0..+∞) →
**R**is surjective. - The function
*g*:**R**→**R**defined by*g*(*x*) =*x*² is*not*surjective, because (for example) there is no real number*x*such that*x*² = −1. However, if the codomain is defined as [0,+∞), then*g*is surjective. - The function
*f*:**Z**→**{0,1,2,3}**defined by

*f*(*x*) = *x* **mod** 4 is surjective.

## Properties

- A function
*f*:*X*→*Y*is surjective if and only if there exists a function*g*:*Y*→*X*such that*f*o*g*equals the identity function on*Y*. (This statement is equivalent to the axiom of choice.) - If
*f*and*g*are both surjective, then*f*o*g*is surjective.

Error creating thumbnail: Unable to save thumbnail to destination

- If
*f*o*g*is surjective, then*f*is surjective (but*g*maynot be). *f*:*X*→*Y*is surjective if and only if, given any functions*g*,*h*:*Y*→*Z*, whenever*g*o*f*=*h*o*f*, then*g*=*h*. In other words, surjective functions are precisely the epimorphisms in the category**Set**of sets.- 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*). - Every function
*h*:*X*→*Z*can be decomposed as*h*=*g*o*f*for a suitable surjection*f*and injective function*g*. This decomposition is unique up to isomorphism, and*f*may be thought of as a function with the same values as*h*but with its codomain restricted to the range*h*(*W*) of*h*, which is only a subset of the codomain*Z*of*h*. - By collapsing all arguments mapping to a given fixed image, every surjection induces a bijection defined on a quotient of its domain. 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*(~). - If
*f*:*X*→*Y*is a surjective function, then*X*has at least as many elements as*Y*, in the sense of cardinal numbers. - 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.

## See also

## Category theory view

In the language of category theory, surjective functions are precisely the epimorphisms in the category of sets.