Surjective Function

A surjective function, or surjection, is a function whose outputs cover its entire specified target set. If $f:A\to B$, surjectivity means that every element of $B$ equals $f(x)$ for at least one element $x$ of $A$. Several inputs may produce the same output; surjectivity requires coverage, not uniqueness. It is one of the fundamental properties used to classify functions in set theory. (jirka.org)

Definition and codomain dependence

For a function $f:A\to B$, $A$ is its domain and $B$ its codomain. The image of $A$ is

The function is surjective precisely when $f(A)=B$. Equivalently,

The order of the quantifiers matters: an appropriate input may depend on the chosen output. (jirka.org)

Surjectivity therefore depends on the codomain, not merely on a formula. For example, $x\mapsto x^2$ is not surjective from the real numbers to $\mathbb R$, because negative numbers are never outputs. The same rule defines a surjection $\mathbb R\to[0,\infty)$. More generally, every function becomes surjective when its codomain is restricted to its image without changing its domain or values. (richardhammack.github.io)

For $y\in B$, the set

is the fiber over $y$. Surjectivity says exactly that every fiber is nonempty. This preimage notation does not require an inverse function to exist. (ocw.mit.edu)

Examples and proof methods

Examples illustrate how the choice of sets affects the property:

• $f:\mathbb R\to\mathbb R$, $f(x)=x^3$, is surjective: for any $y$, the input $x=\sqrt[3]{y}$ satisfies $f(x)=y$.
• $f:\mathbb R\to\mathbb R$, $f(x)=2x+1$, is surjective because $x=(y-1)/2$ produces any prescribed $y$.
• $f:\mathbb Z\to\mathbb Z$, $f(n)=2n$, is not surjective, since no odd integer occurs as an output. It is surjective if its codomain is instead $2\mathbb Z$, the even integers.

These conclusions follow directly by applying the definition and solving the output equation in the specified domain. (richardhammack.github.io)

A standard proof of surjectivity begins with an arbitrary $y\in B$, constructs an $x\in A$, and verifies $f(x)=y$. It must establish both that the proposed input belongs to the domain and that it produces the desired output. To disprove surjectivity, one counterexample in the codomain with no preimage suffices. (richardhammack.github.io)

For finite sets, an arrow diagram gives a direct test: every codomain element must receive at least one arrow. Checking only selected outputs cannot establish surjectivity when the codomain is infinite. (richardhammack.github.io)

Relation to injectivity and cardinality

An injective function gives different outputs to different inputs. A bijective function is both injective and surjective, so every codomain element has exactly one preimage. Thus surjectivity expresses existence of inputs, while injectivity expresses uniqueness whenever an input exists. A two-sided inverse exists precisely for a bijection. (homepages.ucl.ac.uk)

For finite sets, a surjection $A\to B$ requires

If the sets have equal finite cardinality, a function between them is surjective if and only if it is injective. This equivalence fails for infinite sets. On the natural numbers $\mathbb N=\{0,1,2,\ldots\}$, the successor function $n\mapsto n+1$ is injective but misses $0$. Conversely, the function taking $0$ to $0$ and $n\geq1$ to $n-1$ is surjective but maps both $0$ and $1$ to $0$. (richardhammack.github.io)

Composition and right inverses

Surjectivity is preserved by composition. If $f:A\to B$ and $g:B\to C$ are surjective, then $g\circ f$ is surjective: first choose $b$ producing a desired $c$, then choose $a$ producing $b$. If $g\circ f$ is surjective, $g$ must be surjective, but $f$ need not be. (richardhammack.github.io)

A right inverse, or section, of $f$ is a function $s:B\to A$ satisfying

Its existence implies surjectivity, because $s(y)$ supplies a preimage of every $y$. Conversely, constructing a section requires selecting one element from each fiber. In set theory, the assertion that every surjection has a right inverse is equivalent to the axiom of choice. A finite codomain requires only finitely many choices, so that case needs no choice axiom. (webhomes.maths.ed.ac.uk)

Linear algebra and quotient constructions

In linear algebra, a linear map $T:V\to W$ is surjective when its image is the whole target vector space. For an $m\times n$ matrix $M$, the map $x\mapsto Mx$ onto $\mathbb R^m$ is surjective exactly when its columns span $\mathbb R^m$, equivalently when its rank is $m$. Thus the system $Mx=b$ has a solution for every $b$. For finite-dimensional spaces of equal dimension, the rank–nullity theorem makes surjectivity equivalent to injectivity. (math.mit.edu)

Surjections also describe identification of elements. Define an equivalence relation on $A$ by $x\sim x'$ when $f(x)=f(x')$. Its equivalence classes are the nonempty fibers. The projection $A\to A/{\sim}$ is surjective, and the induced map

is bijective. When $f$ is surjective, $f(A)=B$: the codomain corresponds exactly to the classes obtained by identifying inputs with equal outputs. (whitman.edu)