Surjections

A surjection, or surjective function, is a function f from a set X to a set Y with the property that every element of Y has at least one preimage in X. In other words, for every y in Y there exists an x in X such that f(x) = y. Such a function is also described as onto. Equivalently, the image of f equals the codomain Y.

Surjectivity depends on the chosen codomain. If Y is enlarged, a map that was surjective onto the previous codomain may no longer be onto the larger set. For example, the inclusion map i: {1} → {1,2} is not surjective, while a map f: {1,2,3} → {a,b} with f(1)=a, f(2)=a, f(3)=b is surjective.

In general, a map is surjective if every element of the codomain is achieved by some element of the domain. In finite sets, a function f: X → Y is surjective exactly when the image has size |Y|, which requires that |X| is at least |Y| and that no element of Y is missed.

Several basic properties are associated with surjections. The composition of two surjections is a surjection: if f: X→Y and g: Y→Z are surjective, then g∘f: X→Z is surjective. A surjection has a right inverse: there exists a function g: Y→X with f∘g = id_Y, provided one can choose a preimage for each y in Y (this often relies on the axiom of choice).

Surjections are contrasted with injections (one-to-one functions) and bijections (both injective and surjective). A bijection is necessarily a surjection.