Surjection

In mathematics, a surjection is a type of function with the property that all possible output values of the function are generated as values of the function as the input to the function ranges over all possible input values.

More formally, a function f: X → Y is called surjective or onto or a surjection if for every y in the codomain Y there is at least one x in the domain X with f(x) = y. Put another way, the range f(X) is equal to the codomain Y.

Surjective, not injective	Injective, not surjective
Bijective	Not surjective, not injective

When X and Y are both the real line R, then a surjective function f: R → R can be visualized as one whose graph will be intersected by any horizontal line.

Examples and counterexamples

Consider the function f: R → R defined by f(x) = 2x + 1. This function is surjective, since given an arbitrary real number y, we can solve y = 2x + 1 for x to get a solution x = (y − 1)/2.

On the other hand, 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 we define the function h: R → R⁺ by the same formula as g, but with the codomain has been restricted to only the nonnegative real numbers, then the function h is surjective. This is because, given an arbitrary nonnegative real number y, we can solve y = x² to get solutions x = √y and x = −√y.

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.)
• A function is bijective if and only if it is both surjective and injective.
• If f o g is surjective, then f is surjective.
• If f and g are both surjective, then f o g is surjective.
• 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 of sets.
• If f: X → Y is surjective and B is a subset of Y, then f(f ⁻¹(B)) = B. Thus, B can be recovered from its preimage f ⁻¹(B).
• Every function h: X → Z can be decomposed as h = g o f for a suitable surjection f and injection 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.
• If f: X → Y is a surjective function, then X has at least as many elements as Y, in the sense of cardinal numbers. (This statement is also equivalent to the axiom of choice.)
• 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: Injective function, Bijection