# 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.

## Definition of a Function

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\}. \]

## Injective

Let \(f \colon X \to Y\) be a function. Then \(f\) isinjectiveif no element of \(Y\) is the image of more than one element of \(X.\)That is,

\[\forall x_1,x_2 \in X, f(x_1) = f(x_2) \Rightarrow x_1 = x_2, \quad \text{ or }\quad \forall x_1,x_2 \in X, x_1 \ne x_2 \Rightarrow f(x_1) \neq f(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) = \lfloor n/2 \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|.\)

*f*be a One-one (Injective) function, with domain \(D_{f} = \{x,y,z\} \)and Range \(\{1,2,3\}\). It is given that only one of the following \(3\) statement is true and remaining statements are false.

\[ \begin{eqnarray} f(x) &=& 1 \\ f(y) & \neq & 1 \\ f(z)& \neq & 2 \\ \end{eqnarray} \]

Find \( f^{-1} (1) \) .

## Surjective

Let \(f \colon X\to Y\) be a function. Then \(f\) issurjectiveif 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) = \lfloor n/2 \rfloor\) is surjective. For any integer \( m,\) note that \( f(2m) = \lfloor 2m/2 \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|.\)

## Bijective

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

bijectiveif it is injective and surjective; that is, every element \( y \in Y\) is the image ofexactly oneelement \( 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 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(f(x))=x\) and \( f(g(y))=y \) for all \(x\in X, y \in Y.\) When this happens, the function \( g \) is called the

inverse functionof \( 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 \( (x^3)^{1/3} = (x^{1/3})^3 = x.\) (Followup question: the same proof does not work for \( f(x) = x^2.\) Why not?)

**Cite as:**Bijection, Injection, And Surjection.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/bijection-injection-and-surjection/