Bijection, Injection, And Surjection

Functions can be injections (one-to-one functions), surjections (onto functions) or bijections (both one-to-one and onto). Informally, an injection has each output mapped to by at most one input, a surjection includes the entire possible range in the output, and a bijection has both conditions be true.

This concept allows for comparisons between cardinalities of sets, in proofs comparing the sizes of both finite and infinite sets.

A function \(f \colon X\to Y\) is a rule that, for every element \( x\in X,\) associates an element \( f(x) \in Y.\) The element \( f(x)\) is sometimes called the image of \( x,\) and the subset of \( Y \) consisting of images of elements in \( X\) is called the image of \( f.\) That is,

\[\text{image}(f) = \{ y \in Y : y = f(x) \text{ for some } x \in X\}.\]

Let \(f \colon X \to Y\) be a function. Then \(f\) is injective if distinct elements of \(X\) are mapped to distinct elements of \(Y.\)

That is, if \(x_1\) and \(x_2\) are in \(X\) such that \(x_1 \ne x_2\), then \(f(x_1) \ne f(x_2)\).

This is equivalent to saying if \(f(x_1) = f(x_2)\), then \(x_1 = x_2\).

A synonym for "injective" is "one-to-one."

The function \( f\colon {\mathbb Z} \to {\mathbb Z}\) defined by \( f(n) = 2n\) is injective: if \( 2x_1=2x_2,\) dividing both sides by \( 2 \) yields \( x_1=x_2.\)

The function \( f\colon {\mathbb Z} \to {\mathbb Z}\) defined by \( f(n) = \big\lfloor \frac n2 \big\rfloor\) is not injective; for example, \(f(2) = f(3) = 1\) but \( 2 \ne 3.\)

The function \( f\colon \{ \text{German football players dressed for the 2014 World Cup final}\} \to {\mathbb N} \) defined by \(f(A) = \text{the jersey number of } A\) is injective; no two players were allowed to wear the same number.

The existence of an injective function gives information about the relative sizes of its domain and range:

If \( X \) and \( Y \) are finite sets and \( f\colon X\to Y \) is injective, then \( |X| \le |Y|.\)

Let \(f \colon X\to Y\) be a function. Then \(f\) is surjective if every element of \(Y\) is the image of at least one element of \(X.\) That is, \( \text{image}(f) = Y.\)

Symbolically,

\[\forall y \in Y, \exists x \in X \text{ such that } f(x) = y.\]

A synonym for "surjective" is "onto."

The function \( f\colon {\mathbb Z} \to {\mathbb Z}\) defined by \( f(n) = 2n\) is not surjective: there is no integer \( n\) such that \( f(n)=3,\) because \( 2n=3\) has no solutions in \( \mathbb Z.\) So \( 3\) is not in the image of \( f.\)

The function \( f\colon {\mathbb Z} \to {\mathbb Z}\) defined by \( f(n) = \big\lfloor \frac n2 \big\rfloor\) is surjective. For any integer \( m,\) note that \( f(2m) = \big\lfloor \frac{2m}2 \big\rfloor = m,\) so \( m \) is in the image of \( f.\) So the image of \(f\) equals \(\mathbb Z.\)

The function \(f \colon \{\text{US senators}\} \to \{\text{US states}\}\) defined by \(f(A) = \text{the state that } A \text{ represents}\) is surjective; every state has at least one senator.

The existence of a surjective function gives information about the relative sizes of its domain and range:

If \( X \) and \( Y \) are finite sets and \( f\colon X\to Y \) is surjective, then \( |X| \ge |Y|.\)

A function is bijective for two sets if every element of one set is paired with only one element of a second set, and each element of the second set is paired with only one element of the first set. This means that all elements are paired and paired once.

Let \(f \colon X \to Y \) be a function. Then \(f\) is bijective if it is injective and surjective; that is, every element \( y \in Y\) is the image of exactly one element \( x \in X.\)

The function \( f \colon {\mathbb R} \to {\mathbb R} \) defined by \( f(x) = 2x\) is a bijection.

The function \( f \colon {\mathbb Z} \to {\mathbb Z} \) defined by \( f(n) = \begin{cases} n+1 &\text{if } n \text{ is odd} \\ n-1&\text{if } n \text{ is even}\end{cases}\) is a bijection.

The function \( f\colon \{ \text{months of the year}\} \to \{1,2,3,4,5,6,7,8,9,10,11,12\} \) defined by \(f(M) = \text{ the number } n \text{ such that } M \text{ is the } n^\text{th} \text{ month}\) is a bijection.

Note that the above discussions imply the following fact (see the Bijective Functions wiki for examples):

If \( X \) and \( Y \) are finite sets and \( f\colon X\to Y \) is bijective, then \( |X| = |Y|.\)

The following alternate characterization of bijections is often useful in proofs:

Suppose \( X \) is nonempty. Then \( f \colon X \to Y \) is a bijection if and only if there is a function \( g\colon Y \to X \) such that \( g \circ f \) is the identity on \( X \) and \( f\circ g\) is the identity on \( Y;\) that is, \(g\big(f(x)\big)=x\) and \( f\big(g(y)\big)=y \) for all \(x\in X, y \in Y.\) When this happens, the function \( g \) is called the inverse function of \( f \) and is also a bijection.

Show that the function \( f\colon {\mathbb R} \to {\mathbb R} \) defined by \( f(x)=x^3\) is a bijection.

---

Rather than showing \(f\) is injective and surjective, it is easier to define \( g\colon {\mathbb R} \to {\mathbb R}\) by \(g(x) = x^{1/3} \) and to show that \( g\) is the inverse of \( f.\) This follows from the identities \( \big(x^3\big)^{1/3} = \big(x^{1/3}\big)^3 = x.\) \(\big(\)Followup question: the same proof does not work for \( f(x) = x^2.\) Why not?\(\big)\)