Surjection

Definition

A map $f:X\to Y$ between sets $X$ and $Y$ is a surjection (or onto map) iff every element of $Y$ is in the image of $f$: $\forall y\in Y.\exists x\in X.f(x)=y.$

Properties

• Right inverse: $f:X\to Y$ is surjective iff there exists $g:Y\to X$ such that $f\circ g={\mathrm{id}}_Y$. Such a $g$ is called a right inverse or section of $f$. Constructing such a $g$ in general is equivalent to the axiom of choice.
• Composition: if $f:X\to Y$ and $g:Y\to Z$ are both surjective, then $g\circ f:X\to Z$ is surjective.
• Cancellation: $f$ is surjective iff it is right-cancellable, i.e. $g\circ f=h\circ f\Rightarrow g=h$ for all $g,h$.
• Categorical: surjections between sets are precisely the epimorphisms in Set.
• Factorisation: every function $f:X\to Y$ factors as a surjection followed by an injection, via the image $\mathrm{im}(f)\subseteq Y$: $X\twoheadrightarrow \mathrm{im}(f)\hookrightarrow Y.$

Relationship to Cardinality

A surjection $f:X\to Y$ witnesses that $Y$ is no larger than $X$ in the sense of cardinality: $|Y|\le |X|$. Assuming the Axiom of Choice, this is equivalent to the existence of an injection $Y\to X$.

Related Concepts

• Injection
• Bijection
• Epimorphism
• Cardinal
• Quotient
• Axiom of Choice