Injections, Surjections, and Bijections

Functions can be classified according to how they map elements of their domain to their codomain. These classifications—injections, surjections, and bijections—are fundamental to understanding cardinality and the structure of mathematical objects.

DefinitionInjection (One-to-One)

A function $f: A \to B$ is injective (or one-to-one) if distinct elements of $A$ map to distinct elements of $B$ :

\forall x, y \in A(f(x) = f(y) \rightarrow x = y)

Equivalently, $\forall x, y \in A(x \neq y \rightarrow f(x) \neq f(y))$ .

We write $f: A \hookrightarrow B$ or $f: A \rightarrowtail B$ to denote that $f$ is injective.

Injections preserve distinctness: no two different inputs produce the same output. This means the function can be "inverted" on its range, though it may not cover all of the codomain.

ExampleInjective Functions

The inclusion map $i: A \to B$ for $A \subseteq B$ , defined by $i(a) = a$ , is injective
The function $f: \mathbb{N} \to \mathbb{Z}$ defined by $f(n) = n$ is injective
The doubling function $f: \mathbb{N} \to \mathbb{N}$ defined by $f(n) = 2n$ is injective
The successor function $S: \omega \to \omega$ defined by $S(n) = n + 1$ is injective but not surjective (0 is not in the range)

DefinitionSurjection (Onto)

A function $f: A \to B$ is surjective (or onto) if every element of $B$ is the image of at least one element of $A$ :

\forall b \in B \, \exists a \in A(f(a) = b)

Equivalently, $f[A] = B$ , meaning the range equals the codomain.

We write $f: A \twoheadrightarrow B$ to denote that $f$ is surjective.

Surjections cover the entire codomain. Every element of $B$ has at least one preimage in $A$ , though there may be many.

ExampleSurjective Functions

The projection $\pi_1: A \times B \to A$ defined by $\pi_1(a, b) = a$ is surjective (assuming $B \neq \emptyset$ )
The absolute value function $|\cdot|: \mathbb{Z} \to \mathbb{N}$ is surjective
Any constant function $f: A \to \{c\}$ is surjective
The function $f: \mathbb{Z} \to \{0, 1\}$ defined by $f(n) = n \bmod 2$ is surjective

DefinitionBijection (One-to-One Correspondence)

A function $f: A \to B$ is bijective (or a one-to-one correspondence) if it is both injective and surjective. Equivalently, for every $b \in B$ , there exists a unique $a \in A$ such that $f(a) = b$ :

\forall b \in B \, \exists! a \in A(f(a) = b)

We write $f: A \xrightarrow{\sim} B$ or $f: A \cong B$ to denote that $f$ is bijective.

Bijections establish a perfect pairing between sets: every element of $A$ corresponds to exactly one element of $B$ , and vice versa. Bijections are invertible—if $f: A \to B$ is bijective, there exists a unique inverse function $f^{-1}: B \to A$ such that $f^{-1}(f(a)) = a$ for all $a \in A$ and $f(f^{-1}(b)) = b$ for all $b \in B$ .

ExampleBijective Functions

The identity function $\text{id}_A: A \to A$ is always bijective
The function $f: \mathbb{N} \to \mathbb{Z}$ defined by:

f(n) = \begin{cases} n/2 & \text{if } n \text{ is even} \\ -(n+1)/2 & \text{if } n \text{ is odd} \end{cases}

is bijective, showing $|\mathbb{N}| = |\mathbb{Z}|$

The function $f: (0, 1) \to \mathbb{R}$ defined by $f(x) = \tan(\pi(x - 1/2))$ is bijective, showing that open intervals have the same cardinality as $\mathbb{R}$
The exponential function $\exp: \mathbb{R} \to (0, \infty)$ is bijective

TheoremProperties of Function Types

Let $f: A \to B$ and $g: B \to C$ be functions.

If $f$ and $g$ are injective, then $g \circ f$ is injective
If $f$ and $g$ are surjective, then $g \circ f$ is surjective
If $f$ and $g$ are bijective, then $g \circ f$ is bijective, and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$
If $g \circ f$ is injective, then $f$ is injective
If $g \circ f$ is surjective, then $g$ is surjective

Remark

The converse of (4) and (5) do not hold. For example, if $f: \{1\} \to \{1, 2\}$ is the inclusion and $g: \{1, 2\} \to \{3\}$ is the constant function, then $g \circ f$ is bijective, but $f$ is not surjective and $g$ is not injective.

These function types are central to defining cardinality. We say two sets $A$ and $B$ have the same cardinality, written $|A| = |B|$ or $A \sim B$ , if there exists a bijection $f: A \to B$ . This equipollence relation partitions all sets into equivalence classes called cardinal numbers.

DefinitionCardinality Comparisons

For sets $A$ and $B$ :

$|A| \leq |B|$ if there exists an injection $f: A \hookrightarrow B$
$|A| < |B|$ if $|A| \leq |B|$ and $|A| \neq |B|$

The Schröder-Bernstein theorem states that if $|A| \leq |B|$ and $|B| \leq |A|$ , then $|A| = |B|$ .

ExampleCardinality of Natural Numbers

The following sets all have the same cardinality as $\mathbb{N}$ :

The even natural numbers (bijection: $n \mapsto 2n$ )
The integers $\mathbb{Z}$ (interleaving bijection)
The rational numbers $\mathbb{Q}$ (Cantor's pairing function)
Finite sequences of natural numbers

All these sets are countably infinite, denoted $\aleph_0 = |\mathbb{N}|$ . However, $\mathbb{R}$ is uncountable: $|\mathbb{R}| = 2^{\aleph_0} > \aleph_0$ by Cantor's diagonal argument.

Understanding injections, surjections, and bijections is essential for working with infinite sets, where our finite intuitions often fail. These concepts provide the rigorous foundation for cardinality theory and the rich hierarchy of infinities discovered by Cantor.