Skip to main content

Section 2.3 Injective and surjective

Definition 2.3.1.

Let \(f \colon X\rightarrow Y\) be a function. We say that

  • the map \(f\) is surjective (or a surjection or onto) if and only if

    \begin{equation*} (\forall y\in Y)(\exists x\in X)(f(x)=y); \end{equation*}

  • the map \(f\) is injective (or an injection or one-to-one) if and only if

    \begin{equation*} (\forall x,y\in X)((f(x)=f(y)) \implies (x=y)); \end{equation*}

    and

  • the map \(f\) is bijective (or a bijection or a one-to-one correspondence) if and only if it is injective and surjective.

Let \(f \colon X \to Y\) be a map. The map \(f\) is an injection if and only if, for every element \(y \in Y\text{,}\) there exists at most one element \(x \in X\) such that \(y =f(x)\text{.}\) The map \(f\) is a surjection if and only if, for every element \(y \in Y\text{,}\) there exists at least one element \(x \in X\) such that \(y = f(x)\text{.}\) Finally, the map \(f\) is a bijection if and only if, for every element \(y\in Y\text{,}\) there exists exactly one element \(x \in X\) such that \(y = f(x)\text{.}\)

Note 2.3.2.

When proving that a function \(f:X\rightarrow Y\) is injective, start by assuming \(x,y\in X\) are elements such that \(f(x)=f(y)\) and show that this implies \(x=y\text{.}\) To show a function is not injective, you just need to find one pair \(x,y\in X\) such that \(x\neq y\) even though \(f(x)=f(y)\text{.}\)

The function \(f\colon\NN\rightarrow \NN\) defined by \(f(n)=n^2\) is injective. To see this, let \(x,y\in\NN\) be such that \(f(x)=f(y)\text{.}\) Then \(x^2=y^2\text{,}\) and so

\begin{equation*} 0=x^2-y^2=(x-y)(x+y) \end{equation*}

and since \(x+y>0\text{,}\) this means that \(x-y=0\text{,}\) i.e. \(x=y\text{.}\) Thus \(f\) is injective. (It is not surjective since there is no \(n\) so that \(f(n)=2\text{.}\))

If we change the domain from \(\NN_0\) to \(\ZZ\text{,}\) then the map \(f\colon\ZZ\rightarrow \NN_0\) defined by \(f(m)=m^2\) is no longer injective, because \(f(-1)=f(1)\text{.}\)

Note 2.3.4.

When proving that a function \(f\colon X\rightarrow Y\) is surjective, start by assuming \(y\) is some element of \(Y\) and show that there must be an \(x\in X\) with \(f(x)=y\text{.}\) To show it is not surjective, you just need to exhibit one \(y\in Y\) for which \(f(x)\neq y\) for all \(x\in X\text{.}\)

Let \(g \colon \NN_0 \to \NN_0\) be the map defined by the rule \(g(m)=3m\text{.}\) This is not surjective, since there are natural numbers that are not divisible by \(3\text{.}\)

We can fix this by altering the target of our map. Let \(S = \{n \in \NN_0 : n \text{ is divisible by }3\}\text{.}\) Then if we define \(g\colon \NN_0 \to S\) by the rule \(g(m)=3m\text{,}\) it is surjective.

We can mess this up again by altering the source of our map. If we define \(g\colon \NN \to S\) by the rule \(g(m)=3m\text{,}\) it is no longer surjective, because \(0 \in S\) is not hit by \(g\text{.}\)

The lesson here is that the surjectivity of a map depends critically on the declared domain and codomain of the map!

The proof of the following result is a good one to study, since it showcases how to prove injectivity and surjectivity for functions.

Let \(f:X\rightarrow Y\) and \(g:Y\rightarrow Z\) be functions.

  1. Suppose \(f\) and \(g\) are injective. To show that \(g\circ f\) is injective, we need to show that if \(g\circ f(x)=g\circ f(y)\text{,}\) then \(x=y\text{.}\) So suppose \(x,y\in X\) are so that \(g\circ f(x)=g\circ f(y)\text{.}\) Then \(g(f(x))=g(f(y))\text{.}\) Since \(g\) is injective, this means \(f(x)=f(y)\text{;}\) since \(f\) is injective, this implies \(x=y\text{,}\) as desired. This completes the proof that \(g\circ f\) is injective.

  2. Now suppose \(f\) and \(g\) are surjective. To show that \(g\circ f\) is surjective, we need to show that for all \(z\in Z\text{,}\) there is \(x\in X\) so that \(z=g\circ f(x)=g(f(x))\text{.}\) Since \(g\) is surjective, there is \(y\in Y\) so that \(z=g(y)\text{;}\) since \(f\) is surjective, there is \(x\in X\) so that \(f(x)=y\text{,}\) and so \(g(f(x))=g(y)=z\text{,}\) as desired. This finishes the proof that \(g\circ f\) is surjective.

  3. If \(g\) and \(f\) are bijective, then they are both injective and surjective, so by the previous two cases, \(g\circ f\) is also both injective and surjective, hence \(g\circ f\) is bijective.

When mathematicians are presented with a set, for many purposes, they won't be too very worried about what the elements are, but what structures they have. The idea is that a bijection of sets is meant to be a mere labelling of the elements of a set \(S\) by the elements of a set \(T\text{.}\) That labelling is meant to be a perfect match of information: you should never use the same label twice, and all the labels should be used. So a bijection of sets is a map \(f\colon S \to T\) such that for any \(t\in T\text{,}\) there exists a unique \(s\in S\) such that \(f(s)=t\text{.}\)

Let \(S\) and \(T\) be two sets. There is a bijection \(\sigma \colon S \times T \to T \times S\text{,}\) which is given by \(\sigma(s,t) = (t,s)\text{.}\)

Let \(S = \{7, \text{the Battle of Hastings}, \pi\}\text{.}\) We can see that it has three elements, but what do we mean by this? Recall that \(3=\{0,1,2\}\text{.}\) So we can define a bijection \(f \colon S \to 3\) by the rule

\begin{align*} 7 \amp\mapsto 0\\ \text{the Battle of Hastings} \amp\mapsto 1\\ \pi \amp\mapsto 2\text{.} \end{align*}

This is counting: we establish a bijection between a natural number \(n\) and the set whose elements we're trying to count. We'll see more about counting in the next section.

Here is an interesting bijection: let us define \(S \colon \NN_0 \to \NN\) by the rule \(S(m) = m+1\text{.}\)

The reason this is interesting is that \(\NN \subset \NN_0\text{.}\) If we had a finite set, we couldn't do this: you can't define a bijection between a finite set and a proper subset; there just isn't enough room. But the set \(\NN_0\) is different. This will actually serve as a good recipe for defining infinite sets.

If \(f \colon S \to T\) is a bijection, then there exists a map \(g \colon T \to S\) such that \(g \circ f = \mathrm{id}\text{,}\) and \(f \circ g = \mathrm{id}\text{.}\) To prove this, let us construct \(g\text{:}\) the function \(f\) gives us a subset \(\Gamma(f) \subseteq S \times T\) such that for any \(s \in S\text{,}\) there exists a unique \(t \in T\) such that \((s, t) \in \Gamma(f)\text{.}\) So now let's define \(g = (T, S, \Gamma(g))\text{,}\) where \(\Gamma(g) = \{ (t,s) \in T \times S : (s, t) \in \Gamma(f) \}\text{.}\) Of course \(\Gamma(g)\) makes perfect sense as a subset, but we aren't done: we have to show it is a map from \(S\) to \(T\text{.}\) For this we can use the fact that, since \(f\) is a bijection, for every \(t \in T\text{,}\) there exists a unique \(s \in S\) such that \((s,t) \in \Gamma(f)\text{.}\) In other words, for every \(t \in T\text{,}\) there exists a unique \(s \in S\) such that \((t,s) \in \Gamma(g)\text{.}\) Thus if \(t \in T\text{,}\) then \(g(t) \in S\) is the unique element such that \(f(g(t) = t\text{.}\) Thus \(f \circ g = \mathrm{id}\text{.}\) To see that \(g \circ f = \mathrm{id}\text{,}\) let \(s \in S\text{;}\) then \(g(f(s)) \in S\) is the unique element such that \(f(g(f(s))) = f(s)\text{.}\) But since this element of \(S\) is unique with this property, it follows that \(g(f(s)) = s\text{.}\)

The converse is also correct: if \(f \colon S \to T\) is a map such that there exists a function \(g \colon T \to S\) such that \(g \circ f =\mathrm{id}\) and \(f \circ g = \mathrm{id}\text{,}\) then \(f\) is a bijection. Indeed, let \(t \in T\) be an element; we aim to prove that there exists a unique element \(s \in S\) such that \(t = f(s)\text{.}\) The function \(g\) provides us with exactly such an element: \(g(t) \in T\) is an element, and \(t = f(g(t))\text{.}\) Now suppose that \(s'\in S\) is an element such that \(t = f(s')\text{;}\) we see that \(g(t) = g(f(s')) = s'\text{,}\) so we have the uniqueness we sought!

In this case, we say that \(g\) is the inverse of \(f\text{,}\) and we sometimes write \(f^{-1}\) for \(g\text{.}\)

Let's return to our set \(S = \{7, \text{the Battle of Hastings}, \pi\}\text{.}\) Recall that \(3=\{0,1,2\}\text{.}\) We defined a bijection \(f \colon S \to 3\) by the rule

\begin{align*} 7 \amp\mapsto 0\\ \text{the Battle of Hastings} \amp\mapsto 1\\ \pi \amp\mapsto 2\text{.} \end{align*}

The inverse of this bijection is the bijection \(f^{-1} \colon 3 \to S\) given by the rule

\begin{align*} 0 \amp\mapsto 7\\ 1 \amp\mapsto \text{the Battle of Hastings}\\ 2 \amp\mapsto \pi\text{.} \end{align*}

We defined the bijection \(S \colon \NN_0 \to \NN\) by the rule \(S(m) = m+1\text{.}\) The inverse \(S^{-1} \colon \NN \to \NN_0\) is given by the rule \(S^{-1}(m)=m-1\text{.}\)