Surjective Functions

Does the Function Reach Every Target?

The previous tutorial, Injective Functions, asked whether different inputs can share an output. We now ask a different question: does every element of the codomain occur as an output? For this question, the codomain matters directly. A function may attain many values and still fail to be surjective if even one codomain element is never attained.

Let $f:A\to B$. The domain $A$ contains the inputs, and the codomain $B$ is the stated set in which outputs lie. The range $\operatorname{ran}(f)$ consists of the values actually attained. Earlier in this course, the Codomain–Range Equality Criterion established that the range equals the codomain exactly when every element of the codomain has a preimage.

Definition (Surjective Function). A function $f:A\to B$ is surjective if, for every $b\in B$, there exists $a\in A$ such that $$ f(a)=b. $$ A surjective function is also called onto.

The quantifiers determine the proof task. We must take an arbitrary target $b$ from $B$, and then produce at least one input $a$ from $A$ whose output is that target. The input is allowed to depend on the target. Surjectivity does not require different targets to have different preimages; several inputs may map to the same element of $B$.

Keep the codomain in view. A function can have the same domain and the same rule but be surjective for one codomain and not for another. Surjectivity asks whether every element of the specified codomain is attained, not whether the formula reaches every value one might naturally expect.

A Method for Proving Surjectivity

For a formula-defined function, begin with an arbitrary target $b$ in the codomain. Then solve the equation $f(a)=b$ for a possible input $a$. A successful solution is not enough by itself: it must belong to the stated domain, and substituting it into the function must give the chosen target.

Choose an arbitrary target: let $b\in B$. Do not restrict attention to selected or convenient targets.

Find a candidate input: solve $f(a)=b$, or use the definition of the function to identify an input.

Check the domain condition: verify that the candidate really belongs to $A$.

Verify the output: show that applying $f$ to the candidate gives exactly $b$, and conclude that the arbitrary target is attained.

Worked Example: A Linear Function from the Reals to the Reals

Define $f:\mathbb R\to\mathbb R$ by $f(x)=2x-7$. We prove that $f$ is surjective. Let $y\in\mathbb R$ be arbitrary. To obtain $f(x)=y$, solve $2x-7=y$, which gives the candidate $$ x=\frac{y+7}{2}. $$ Since $y$ is real, $(y+7)/2$ is real, so this candidate belongs to the domain $\mathbb R$. Substitution verifies the required value: $$ f\left(\frac{y+7}{2}\right) =2\left(\frac{y+7}{2}\right)-7 =y+7-7 =y. $$ Thus every real target $y$ has a preimage in $\mathbb R$, and $f$ is surjective.

The proof uses an arbitrary target, not a sample of outputs. The expression $(y+7)/2$ explicitly describes a preimage for each target $y$. This is often the central step in a surjectivity proof: reverse the function rule to construct an input.

Examples Where the Codomain Changes the Answer

A function's range can be smaller than its codomain. When that happens, elements of the codomain that are outside the range are exactly the targets that have no preimage. A single such target is sufficient to show that a function is not surjective.

Worked Example: Squaring onto the Nonnegative Reals

Define $s:\mathbb R\to[0,\infty)$ by $s(x)=x^2$. We show that $s$ is surjective. Let $y\in[0,\infty)$ be arbitrary. Because $y\geq0$, its nonnegative square root $\sqrt y$ is a real number and therefore belongs to the domain $\mathbb R$. Taking $x=\sqrt y$, we have $$ s(x)=s(\sqrt y)=(\sqrt y)^2=y. $$ Every target in the stated codomain is attained, so $s$ is surjective.

Now keep the same domain and formula but change the codomain: define $t:\mathbb R\to\mathbb R$ by $t(x)=x^2$. The target $-1$ belongs to the codomain $\mathbb R$, but it cannot be attained. Every real square is nonnegative, so there is no $x\in\mathbb R$ with $x^2=-1$. Thus $t$ is not surjective. These conclusions agree: the range of both functions is $[0,\infty)$, but only the first function has that set as its codomain.

Worked Example: A Function Between Finite Sets

Let $A=\{p,q,r,s\}$ and $B=\{1,2,3\}$, and define $h:A\to B$ by $$ h(p)=2,\qquad h(q)=1,\qquad h(r)=3,\qquad h(s)=2. $$ To verify surjectivity, check each element of the codomain: $1=h(q)$, $2=h(p)$, and $3=h(r)$. Thus every element of $B$ is attained, so $h$ is surjective. The repeated output $2$ causes no problem. Surjectivity requires at least one preimage for each target, not exactly one.

For comparison, if the assignment $h(r)=3$ were replaced by $h(r)=1$, then no input would map to $3$. The modified function would not be surjective onto $B$. For a finite codomain, listing a preimage for each target is a direct way to check the definition.

Worked Example: A Shift on the Integers

Define $u:\mathbb Z\to\mathbb Z$ by $u(n)=n+4$. Let $m\in\mathbb Z$ be any target. Choose $n=m-4$. Since the difference of two integers is an integer, $n\in\mathbb Z$. Then $$ u(n)=u(m-4)=(m-4)+4=m. $$ Every integer target has an integer preimage, so $u$ is surjective. This construction also shows why checking the domain is important: solving the equation must produce an input in the set on which the function is defined.

Surjectivity and Composition

Functions can be applied in succession when the codomain of the first function is the domain of the second. If $f:A\to B$ and $g:B\to C$, their composition $g\circ f:A\to C$ is defined by $$ (g\circ f)(a)=g(f(a)). $$ The value $f(a)$ is in $B$, so it is a valid input for $g$. Surjectivity of $f$ ensures that the first function can produce every possible input needed by $g$.

The next proposition makes that observation precise. It also accounts for the case when $g$ does not attain every element of its codomain: composing with a surjective function $f$ still allows the composite to attain every value that $g$ itself attains.

Proposition (Surjective Precomposition Preserves the Range). Let $f:A\to B$ be surjective and let $g:B\to C$ be a function. Then $$ \operatorname{ran}(g\circ f)=\operatorname{ran}(g). $$

Proof. We prove the two inclusions. First, let $z\in\operatorname{ran}(g\circ f)$. By the definition of range, there exists $a\in A$ such that $z=(g\circ f)(a)=g(f(a))$. Since $f(a)\in B$, this expresses $z$ as a value of $g$, so $z\in\operatorname{ran}(g)$. Therefore $\operatorname{ran}(g\circ f)\subseteq\operatorname{ran}(g)$.

For the reverse inclusion, let $z\in\operatorname{ran}(g)$. Then there exists $b\in B$ such that $g(b)=z$. Since $f$ is surjective, there exists $a\in A$ with $f(a)=b$. Consequently, $$ (g\circ f)(a)=g(f(a))=g(b)=z. $$ Thus $z\in\operatorname{ran}(g\circ f)$, which proves $\operatorname{ran}(g)\subseteq\operatorname{ran}(g\circ f)$. By equality by double inclusion, the two ranges are equal. $\square$

In particular, if $g$ is also surjective, its range is all of $C$. The proposition then gives $\operatorname{ran}(g\circ f)=C$, so the composite is surjective.

Theorem (Composition of Surjective Functions). If $f:A\to B$ and $g:B\to C$ are both surjective, then $g\circ f:A\to C$ is surjective.

Proof. Let $c\in C$ be arbitrary. Since $g$ is surjective, there exists $b\in B$ such that $g(b)=c$. Since $f$ is surjective, there exists $a\in A$ such that $f(a)=b$. Therefore $$ (g\circ f)(a)=g(f(a))=g(b)=c. $$ We have found an input $a\in A$ for the arbitrary target $c\in C$. Hence $g\circ f$ is surjective. $\square$

Why the order of the construction matters. To find a preimage of a target $c$ under $g\circ f$, first use surjectivity of $g$ to find a $b$ that maps to $c$, then use surjectivity of $f$ to find an $a$ that maps to $b$. The resulting input $a$ satisfies $g(f(a))=c$.

Common Misreadings and Edge Cases

Surjectivity is a statement about every element of the codomain. Checking a few outputs cannot prove it when the codomain has more elements than those checked, and it cannot establish it for an infinite codomain. A proof must either handle an arbitrary target or, for a finite codomain, verify every target.

To disprove surjectivity, the quantifiers point to a simpler task: find one target $b\in B$ for which no input in $A$ has value $b$. In the real squaring example, $-1$ served as such a target. Merely observing that some values were not produced in a few calculations would not be sufficient; the argument that every real square is nonnegative rules out all possible inputs for that target.

The empty-set cases follow directly from the definition. If $A=\varnothing$ and $B\ne\varnothing$, then $f:A\to B$ cannot be surjective: for any $b\in B$, there is no input in the empty domain. If $B=\varnothing$, a function $f:A\to B$ can exist only when $A=\varnothing$, because an element of a nonempty $A$ would need an output in the empty set. The unique function $\varnothing\to\varnothing$ is surjective: there are no targets in its codomain for which the required preimage condition could fail.

Write the mapping completely: identify the domain, codomain, and rule or assignments.

For a proof: let an arbitrary element of the codomain be the target.

Construct a preimage: solve for an input and verify that it belongs to the domain.

For a disproof: identify a codomain element and prove that no input maps to it.

Check Your Understanding

State the definition of a surjective function $f:A\to B$ using an arbitrary $b\in B$.
Let $v:\mathbb R\to\mathbb R$ be defined by $v(x)=3x+5$. Find an input that maps to an arbitrary target $y\in\mathbb R$, and use it to prove that $v$ is surjective.
Let $w:\mathbb R\to\mathbb R$ be defined by $w(x)=x^2+1$. Give a codomain element that is not attained and justify why $w$ is not surjective.
Define $k:\mathbb Z\to\mathbb Z$ by $k(n)=n-6$. What candidate input should be used for an arbitrary integer target $m$, and why is it in the domain?
Suppose $f:A\to B$ and $g:B\to C$ are surjective. Which function should be used first to find a preimage of an arbitrary $c\in C$ under $g\circ f$?

What You'll Learn