surjekcj

Surjection, also called an onto function, is a relation f: A → B between sets such that every element of B has a preimage in A. In other words, for every b in B there exists an a in A with f(a) = b. Equivalently, the image of f is the entire codomain B, written as im(f) = B.

A surjective function is contrasted with an injective (one-to-one) function, where distinct elements of A map to distinct elements of B, and with a bijective function, which is both injective and surjective. In finite sets, a necessary condition for surjectivity is that the size of the domain is at least as large as the size of the codomain, |A| ≥ |B|. If |A| = |B|, surjectivity implies bijectivity.

Key properties include: the composition of surjections is surjective; if f: A → B and g: B → C are surjective, then g ∘ f: A → C is surjective. Every surjection has a right inverse: there exists s: B → A with f(s(b)) = b for all b ∈ B, a fact guaranteed (in general) by the axiom of choice to select a preimage for each b.

Examples help illustrate the concept: f: R → R with f(x) = x^3 is surjective (and bijective). The exponential map exp: R → (0, ∞) is surjective onto its codomain but not onto all of R. The map f: {1,2} → {a} defined by f(1) = f(2) = a is surjective.

In category theory, surjections correspond to epimorphisms in the category of sets.