How many surjective functions are there from a set with three elements to a set with two elements?

Two simple properties that functions may have turn out to be exceptionally useful. If the codomain of a function is also its range, then the function is onto or surjective. If a function does not map two different elements in the domain to the same element in the range, it is one-to-one or injective. In this section, we define these concepts "officially'' in terms of preimages, and explore some easy examples and consequences.

Definition 4.3.1 A function $f\colon A\to B$ is injective if each $b\in B$ has at most one preimage in $A$, that is, there is at most one $a\in A$ such that $f(a)=b$. $\square$

Example 4.3.2 Suppose $A=\{1,2,3\}$ and $B=\{r,s,t,u,v\}$ and

$$ \begin{array}{} f(1)=s&g(1)=r\\ f(2)=t&g(2)=t\\ f(3)=r&g(3)=r\\ \end{array} $$

Here $f$ is injective since $r,s,t$ have one preimage and $u,v$ have no preimages. On the other hand, $g$ fails to be injective, since $r$ has more than one preimage. $\square$

Example 4.3.3 Define $f,g\,\colon \R\to \R$ by $f(x)=x^2$, $g(x)=2^x$. Function $f$ fails to be injective because any positive number has two preimages (its positive and negative square roots). On the other hand, $g$ is injective, since if $b\in \R$, then $g(x)=b$ has at most one solution (if $b>0$ it has one solution, $\log_2 b$, and if $b\le 0$ it has no solutions). $\square$

Example 4.3.4 If $A\subseteq B$, then the inclusion map from $A$ to $B$ is injective. $\square$

An injective function is called an injection. An injection may also be called a one-to-one (or 1–1) function; some people consider this less formal than "injection''.

There is another way to characterize injectivity which is useful for doing proofs. To say that the elements of the codomain have at most one preimage is to say that no two elements of the domain are taken to the same element, as we indicated in the opening paragraph. In other words, $f\colon A\to B$ is injective if and only if for all $a,a'\in A$, $a\ne a'$ implies $f(a)\ne f(a')$. Taking the contrapositive, $f$ is injective if and only if for all $a,a' \in A$, $f(a)=f(a')$ implies $a=a'$.

Theorem 4.3.5 If $f\colon A\to B$ and $g\,\colon B\to C$ are injective functions, then $g\circ f\colon A \to C$ is injective also.

Proof. Suppose $g(f(a))=g(f(a'))$. Since $g$ is injective, $f(a)=f(a')$. Since $f$ is injective, $a=a'$. Thus, $(g\circ f)(a)=(g\circ f)(a')$ implies $a=a'$, so $(g\circ f)$ is injective. $\qed$

Definition 4.3.6 A function $f\colon A\to B$ is surjective if each $b\in B$ has at least one preimage, that is, there is at least one $a\in A$ such that $f(a)=b$. $\square$

Example 4.3.7 Suppose $A=\{1,2,3,4,5\}$, $B=\{r,s,t\}$, and

$$ \begin{array}{} f(1)=s&g(1)=t\\ f(2)=r&g(2)=r\\ f(3)=s&g(3)=r\\ f(4)=t&g(4)=t\\ f(5)=r&g(5)=t\\ \end{array} $$

Under $f$, the elements $r,s,t$ have 2, 2, and 1 preimages, respectively, so $f$ is surjective. Under $g$, the element $s$ has no preimages, so $g$ is not surjective. $\square$

Example 4.3.8 Define $f,g\,\colon \R\to \R$ by $f(x)=3^x$, $g(x)=x^3$. Since $3^x$ is always positive, $f$ is not surjective (any $b\le 0$ has no preimages). On the other hand, for any $b\in \R$ the equation $b=g(x)$ has a solution (namely $x=\root 3 \of b$) so $b$ has a preimage under $g$. Therefore $g$ is surjective. $\square$

Example 4.3.9 Suppose $A$ and $B$ are sets with $A\ne \emptyset$. Then $p\,\colon A\times B\to B$ given by $p((a,b))=b$ is surjective, and is called the projection onto $B$. $\square$

Example 4.3.10 For any set $A$ the identity map $i_A$ is both injective and surjective. $\square$

A surjective function is called a surjection. A surjection may also be called an onto function; some people consider this less formal than "surjection''. To say that a function $f\colon A\to B$ is a surjection means that every $b\in B$ is in the range of $f$, that is, the range is the same as the codomain, as we indicated above.

Theorem 4.3.11 Suppose $f\colon A\to B$ and $g\,\colon B\to C$ are surjective functions. Then $g\circ f\colon A \to C$ is surjective also.

Proof. Suppose $c\in C$. Since $g$ is surjective, there is a $b\in B$ such that $g(b)=c$. Since $f$ is surjective, there is an $a\in A$, such that $f(a)=b$. Hence $c=g(b)=g(f(a))=(g\circ f)(a)$, so $g\circ f$ is surjective. $\qed$

Exercises 4.3

Ex 4.3.1 Decide if the following functions from $\R$ to $\R$ are injections, surjections, or both.

Ex 4.3.2

a) Find an example of an injection $f\colon A\to B$ and a surjection $g\,\colon B\to C$ such that $g\circ f$ is neither injective nor surjective.

b) Find an example of a surjection $f\colon A\to B$ and an injection $g\,\colon B\to C$ such that $g\circ f$ is neither injective nor surjective.

Ex 4.3.3

a) Suppose $A$ and $B$ are finite sets and $f\colon A\to B$ is injective. What conclusion is possible regarding the number of elements in $A$ and $B$? Justify your answer.

b) If instead of injective, we assume $f$ is surjective, what conclusion is possible? Justify your answer.

Ex 4.3.4 Suppose $A$ is a finite set. Can we construct a function $f\colon A\to A$ that is injective, but not surjective? Surjective, but not injective?

Ex 4.3.5

a) Find a function $f\colon \N\to \N$ that is injective, but not surjective.

b) Find a function $g\,\colon \N\to \N$ that is surjective, but not injective.

Ex 4.3.6 Suppose $A$ and $B$ are non-empty sets with $m$ and $n$ elements respectively, where $m\le n$. How many injective functions are there from $A$ to $B$?

Ex 4.3.7 Find an injection $f\colon \N\times \N\to \N$. (Hint: use prime factorizations.)

Ex 4.3.8 If $f\colon A\to B$ is a function, $A=X\cup Y$ and $f\vert_X$ and $f\vert_Y$ are both injective, can we conclude that $f$ is injective?