## Encyclopedia > Surjective

Article Content

# Surjection

Redirected from Surjective

A function fX → 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 fR → R can be visualized as one whose graph will be intersected by any horizontal line.

### Examples and counterexamples

Consider the function fR → 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 gR → R defined by g(x) = x2 is not surjective, because (for example) there is no real number x such that x2 = -1.

However, if we define the function hR → 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 = x2 to get solutions x = √y and x = −√y.

### Properties

• A function fX → Y is surjective if and only if there exists a function gY → 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.
• fX → 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 fX → 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 hX → 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 fX → 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.)

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Charles V, Holy Roman Emperor ... Revolt in Germany and the formation of the Lutheran Schmalkaldic League, and Charles delegated increasing responsibility for Germany to his brother Ferdinand while he ...