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.
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) = x2 is not surjective, because (for example) there is no real number x such that x2 = -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 = x2 to get solutions x = √y and x = −√y.
- 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 −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 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.)
See also: Injective function, Bijection
All Wikipedia text
is available under the
terms of the GNU Free Documentation License