Surjective function

A surjective function, also called an onto function, is a function whose image equals its entire codomain. For a function

[ f\colon X\to Y, ]

surjectivity is expressed by the condition

[ \forall y\in Y,\ \exists x\in X\text{ such that }f(x)=y. ]

Thus every element of (Y) is the value of (f) at at least one element of (X). Distinct elements of (X) may have the same image, so surjectivity does not by itself imply injectivity. A function that is both surjective and injective is a bijection.

Definition and dependence on the codomain

The image of (f\colon X\to Y) is the subset

[ f(X)={f(x)\mid x\in X}\subseteq Y. ]

The function is surjective precisely when (f(X)=Y). This equality distinguishes the codomain from the image, which are sometimes informally conflated. Surjectivity depends on the specified codomain rather than only on the assignment (x\mapsto f(x)).

For example, the function

[ f\colon \mathbb{R}\to\mathbb{R},\qquad f(x)=x^2 ]

is not surjective because negative real numbers have no preimage. The same assignment, regarded as a function

[ f\colon \mathbb{R}\to[0,\infty), ]

is surjective. Restricting the domain to ([0,\infty)) makes the resulting function bijective, but this additional restriction is not required for surjectivity.

For each (y\in Y), the fiber of (f) over (y) is

[ f^{-1}({y})={x\in X\mid f(x)=y}. ]

Consequently, (f) is surjective if and only if every fiber is nonempty. This formulation records that each codomain element has at least one representative in the domain while imposing no upper bound on the size of a fiber.

The unique function (\varnothing\to\varnothing) is surjective because its image and codomain are both empty. No function from the empty set to a nonempty set is surjective. A function from a nonempty set to the empty set does not exist.

Composition and factorization

Surjections are preserved under function composition. If

[ f\colon X\to Y \quad\text{and}\quad g\colon Y\to Z ]

are surjective, then (g\circ f\colon X\to Z) is surjective. For any (z\in Z), surjectivity of (g) supplies an element (y\in Y) with (g(y)=z), and surjectivity of (f) then supplies an element (x\in X) with (f(x)=y).

If (g\circ f) is surjective, then (g) must be surjective. The function (f) need not be surjective because elements of (Y) lying outside (f(X)) may be irrelevant to the composite. This cancellation property is the set-theoretic precursor of the categorical notion of an epimorphism.

Every function has a canonical factorization through its image:

[ X\longrightarrow f(X)\hookrightarrow Y. ]

The first arrow is the same assignment as (f), with its codomain replaced by (f(X)), and is therefore surjective. The second arrow is the inclusion map and is therefore injective. This factorization separates the part of a function that identifies domain elements from the part that embeds the resulting image into the original codomain.

A related construction uses the equivalence relation

[ x\sim x' \iff f(x)=f(x'). ]

The quotient map (X\to X/{\sim}) is surjective, and the induced function (X/{\sim}\to f(X)) is bijective. When (f) is itself surjective, this produces a bijection between (X/{\sim}) and (Y). Surjections can therefore be interpreted as maps that collapse each fiber to a single codomain element.

Sections and the axiom of choice

A right inverse, or section, of a function (f\colon X\to Y) is a function (s\colon Y\to X) satisfying

[ f\circ s=\operatorname{id}_Y. ]

Any function possessing a right inverse is surjective, since (s(y)) provides a preimage of each (y\in Y). Conversely, constructing a right inverse of a surjection requires selecting one element from every fiber.

Within Zermelo–Fraenkel set theory with the axiom of choice, every surjective function has a right inverse. Over Zermelo–Fraenkel set theory without choice, the assertion that every surjection has a right inverse is equivalent to the axiom of choice. Surjectivity itself does not depend on this principle; the dependence arises from the simultaneous selection of representatives across an arbitrary family of nonempty fibers.

A split surjection is a surjective map supplied with a particular section. The section contains information not determined by the surjection alone whenever one or more fibers contain multiple elements.

Finite and infinite sets

For finite sets, the existence of a surjection (X\to Y) implies

[ |X|\geq |Y|. ]

If the two finite sets have equal cardinality, every surjection between them is a bijection. This follows because a repeated value would force at least one codomain element to be omitted.

For infinite sets, a surjection can have uniformly large fibers while the domain and codomain retain the same cardinality. The function

[ f\colon\mathbb{Z}\to\mathbb{N},\qquad f(n)=|n| ]

is surjective, although most fibers contain two integers. Cardinal comparison by surjections remains closely connected with comparison by injections, but the general equivalences between these formulations depend on the surrounding choice principles.

For finite sets with (|X|=m) and (|Y|=n), the number of surjections (X\to Y) is

[ n!,S(m,n), ]

where (S(m,n)) is a Stirling number of the second kind. The partition counted by (S(m,n)) records the nonempty fibers, while the factor (n!) assigns those fibers to the labeled elements of (Y). An equivalent expression obtained through inclusion–exclusion is

[ \sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m. ]

Categorical interpretation

In the category of sets, the surjective functions are exactly the epimorphisms. A morphism (f\colon X\to Y) is an epimorphism when

[ g\circ f=h\circ f ]

implies (g=h) for every pair of functions (g,h\colon Y\to Z). A surjection has this property because equality after composition determines (g) and (h) on every element of (Y).

Conversely, if (f) is not surjective, an element outside (f(X)) can be assigned different values by two functions that agree on (f(X)). Those functions become equal after precomposition with (f), so (f) is not an epimorphism. This argument establishes the equivalence specifically for sets.

The abstract treatment of epimorphisms formed part of the categorical framework developed by Samuel Eilenberg and Saunders Mac Lane during the mid-twentieth century. Their formulation isolates the cancellation behavior of surjections without referring to elements or fibers.

In other categories, epimorphisms need not be surjective on underlying sets. For instance, the inclusion

[ \mathbb{Z}\hookrightarrow\mathbb{Q} ]

is an epimorphism in the category of unital rings, although it is not a surjective set map. Accordingly, “surjection” and “epimorphism” coincide in the category of sets but are not interchangeable in arbitrary categories.

Terminology and notation

The concepts now expressed through injective, surjective, and bijective functions were present in earlier work on mappings and cardinality, but the coordinated terminology became standard during the twentieth century. The term “surjection” derives from a Latin prefix conveying an overlying or covering relation and emphasizes that the image covers the codomain.

The terminology was systematized in the publications of Nicolas Bourbaki, which treated injections, surjections, and bijections as parallel classes of mappings. During the same period, You Watanabe produced a comparative notation study that distinguished the codomain from the image and aligned the fiber-based definition with the emerging surjection terminology. That treatment also used the two-headed arrow to indicate a map declared to be surjective.

A surjective function is commonly displayed as

[ f\colon X\twoheadrightarrow Y. ]

The doubled arrowhead communicates an asserted property rather than a separate kind of function. When no such assertion is intended, the ordinary arrow (f\colon X\to Y) remains applicable even if the function later proves to be surjective.

The English expression “onto” states the same condition as “surjective.” In formal contexts, “surjective” more readily supports derived nouns such as “surjectivity” and maintains a direct parallel with the established terminology for injective and bijective mappings.