1.4: Injections, Surjections, Bijections
- Page ID
- 99054
Most basic among the characteristics a function may have are the properties of injectivity, surjectivity and bijectivity.
Let \(f: X \rightarrow Y\). The function \(f\) is called an injection if, whenever \(x\) and \(y\) are distinct elements of \(X\), we have \(f(x) \neq f(y)\). Injections are also called one-to-one functions.
Another way of stating the definition (the contrapositive) is that if \(f(x)=f(y)\) then \(x=y\).
The real function \(f(x)=x^{3}\) is an injection. To see this, let \(x\) and \(y\) be real numbers, and suppose that \[f(x)=x^{3}=y^{3}=f(y) .\] Then \[x=\left(x^{3}\right)^{1 / 3}=\left(y^{3}\right)^{1 / 3}=y .\] So, for \(x, y \in X\), \[f(x)=f(y) \text { only if } x=y .\]
The real function \(f(x)=x^{2}\) is not an injection, since \[f(2)=4=f(-2) .\] Observe that a single example suffices to show that \(f\) not an injection.
Suppose \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\). Prove that if \(f\) and \(g\) are injective, so is \(g \circ f\).
PROOF. Suppose that \(g \circ f(x)=g \circ f(y)\). Since \(g\) is injective, this means that \(f(x)=f(y)\). Since \(f\) is injective, this in turn means that \(x=y\). Therefore \(g \circ f\) is injective, as desired. (See Exercise \(1.20\) below).
Let \(f: X \rightarrow Y\). We say \(f\) is a surjection from \(X\) to \(Y\) if \(\operatorname{Ran}(f)=Y\). We also describe this by saying that \(f\) is onto \(Y\).
The function \(f: \mathbb{R} \rightarrow \mathbb{R}\) defined by \(f(x)=x^{2}\) is not a surjection. For instance, \(-1\) is in the codomain of \(f\), but \(-1 \notin \operatorname{Ran}(f)\). Therefore, \(\operatorname{Ran}(f) \subsetneq \mathbb{R}\).
Let \(Y=\{x \in \mathbb{R} \mid x \geq 0\}\), and \(f: \mathbb{R} \rightarrow Y\) be given by \(f(x)=x^{2}\). Then \(f\) is a surjection. To prove this, we need to show that \(Y=\operatorname{Ran}(f)\). We know that \(\operatorname{Ran}(f) \subseteq Y\), so we must show \(Y \subseteq \operatorname{Ran}(f)\). Let \(y \in Y\), so \(y\) is a non-negative real number. Then \(\sqrt{y} \in \mathbb{R}\), and \(f(\sqrt{y})=y\). So \(y \in \operatorname{Ran}(f)\). Since \(y\) was an arbitrary element of \(Y, Y \subseteq \operatorname{Ran}(f)\). Hence \(Y=\operatorname{Ran}(f)\) and \(f\) is a surjection.
Whether a function is a surjection depends on the choice of the codomain. A function is always onto its range. You might wonder why one would not simply define the codomain as the range of the function (guaranteeing that the function is a surjection). One reason is that we may be more interested in relating two sets using functions than we are in any particular function between the sets. We study an important application of functions to relating sets in Chapter 6, where we use functions to compare the size of sets. This is of particular interest when comparing infinite sets, and has led to deep insights in the foundations of mathematics.
If we put the ideas of an injection and a surjection together, we arrive at the key idea of a bijection.
Let \(f: X \rightarrow Y\). If \(f\) is an injection and a surjection, then \(f\) is a bijection. This is written as \(f: X \mapsto Y\).
Why are bijections so important? From a theoretical point of view, functions may be used to relate the domain and the codomain of the function. If you are familiar with one set you may be able to develop insights into a different set by finding a function between the sets which preserves some of the key characteristics of the sets. For instance, an injection can "interpret" one set into a different set. If the injection preserves the critical information from the domain, we can behave as if the domain of the function is virtually a subset of the codomain by using the function to "rename" the elements of the domain. If the function is a bijection, and it preserves key structural features of the domain, we can treat the domain and the codomain as virtually the same set. What the key structural features are depends on the area of mathematics you are studying. For example, if you are studying algebraic structures, you are probably most interested in preserving the operations of the structure. If you are studying geometry, you are interested in functions that preserve shape. The preservation of key structural features of the domain or codomain often allows us to translate knowledge of one set into equivalent knowledge of another set.
Let \(X\) be a set. A permutation of \(X\) is a bijection \(f: X \mapsto X\).
Let \(f: \mathbb{Z} \rightarrow \mathbb{Z}\) be defined by \[f(x)=x+1 .\] Then \(f\) is a permutation of \(\mathbb{Z}\).
Let \(X=\{0,1,-1\}\). Then \(f: X \rightarrow X\) given by \(f(x)=-x\) is a permutation of \(X\).