Relations and functions · Definition

Surjective function

set theoryrelations and functions

Before you start you need to know

A surjective function guarantees that no element of the codomain is left unreached from the domain.

Definition

Function \(f\colon A\to B\) whose image is the whole codomain \(B\).

\[\forall b\in B\,\exists a\in A\,(f(a)=b)\]

Let \(f\colon A\to B\). It is surjective if for every \(b\in B\) there is at least one \(a\in A\) with \(f(a)=b\). Equivalently, \(f(A)=B\), since the image \(f(A)\) is always contained in \(B\) and surjectivity requires the other inclusion.

Worked example: \(f\colon\mathbb{Z}\to\mathbb{Z}\), \(f(n)=n+1\), is surjective, because for every \(m\in\mathbb{Z}\) we have \(f(m-1)=m\). By contrast, \(g\colon\mathbb{Z}\to\mathbb{Z}\), \(g(n)=2n\), is not: \(1\) has no preimage, since \(2n=1\) has no integer solution.

Typical mistake: confusing the codomain with the image. If \(f\colon\{1,2\}\to\{a,b,c\}\), the function can be injective but never surjective, because it takes at most two values. A large domain is not enough either: what must be checked is that no element of \(B\) lies outside the image.

Think about it

Can a function from a two-element domain be surjective onto a three-element codomain?

No: its image has at most two values, so it cannot cover three.

Exercises 10

  1. What does it mean for \(f\colon A\to B\) to be surjective?
  2. Which of these functions from \(\mathbb{R}\) to \(\mathbb{R}\) is surjective?
  3. What is the logical form of the definition of a surjective function?
  4. If \(f\colon A\to B\) is not surjective, what holds?
  5. Let \(f\colon\{1,2,3\}\to\{a,b\}\). Can \(f\) be surjective?
  6. What is the name of the set \(f(A)\) of all values taken by \(f\)?
  7. Let \(f\colon\mathbb{Z}\to\mathbb{Z}\), \(f(n)=2n\). What is the image \(f(\mathbb{Z})\)?
  8. Let \(A=\{1,2,3,4\}\) and \(B=\{a,b\}\). How many surjective functions \(f\colon A\to B\) are there?
  9. If \(f\colon A\to B\) and \(g\colon B\to C\) are surjective, is \(g\circ f\)?
  10. Let \(f\colon\{1,2\}\to\{a,b,c\}\). Can \(f\) be surjective?

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.