surjection

Surjection, also called onto function, is a function f from a set A (the domain) to a set B (the codomain) with the property that every element of B is the image of at least one element of A. Equivalently, the image of f equals the codomain, i.e., f(A) = B. In other words, the function covers the entire target set.

Surjectivity is often described as completeness of the target: no element of B is left unmapped. It is a dual notion to injectivity, which requires distinct inputs to have distinct outputs. A function can be surjective, injective, both (bijective), or neither.

Examples: The function f: Z -> Z defined by f(n) = floor(n/2) is surjective, since every integer m is achieved by f(2m). The function f: R -> R, f(x) = x^3, is both injective and surjective (hence bijective).

For finite sets, a surjection f: A -> B implies |A| ≥ |B|; if |A| = |B|, surjectivity implies bijectivity. In general, a surjection has a right inverse g: B -> A with f(g(b)) = b for all b in B if the axiom of choice holds. Without AC, a surjection need not admit a global right inverse.