Bijection

In mathematics, a bijection, bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other set, and vice versa.

Definition

A function $f: X \to Y$ is bijective if it satisfies two conditions: it is both injective (one-to-one) and surjective (onto).

1. Injective (One-to-One): For every $x_1, x_2 \in X$, if $f(x_1) = f(x_2)$, then $x_1 = x_2$. Equivalently, distinct elements in the domain map to distinct elements in the codomain.
2. Surjective (Onto): For every $y \in Y$, there exists at least one $x \in X$ such that $f(x) = y$. This means the range of the function is equal to its codomain.

When both conditions are met, every element $y$ in the codomain $Y$ has exactly one pre-image $x$ in the domain $X$. This relationship is often denoted as a one-to-one correspondence between the sets $X$ and $Y$.

Properties

Inverse Function

A fundamental property of a bijective function is that it possesses an inverse function. If $f: X \to Y$ is a bijection, there exists a unique function $f^{-1}: Y \to X$ such that $f^{-1}(f(x)) = x$ for all $x \in X$ and $f(f^{-1}(y)) = y$ for all $y \in Y$. The inverse function $f^{-1}$ is also a bijection. A function is invertible if and only if it is bijective.

Composition

The composition of two bijective functions is also bijective. If $f: X \to Y$ and $g: Y \to Z$ are both bijections, then their composition $g \circ f: X \to Z$ is a bijection. Furthermore, the inverse of the composition is the composition of the inverses in reverse order: $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

Symmetry and Transitivity

The property of having a bijection between two sets is an equivalence relation. It is reflexive (the identity function is a bijection from a set to itself), symmetric (if there is a bijection from $X$ to $Y$, its inverse is a bijection from $Y$ to $X$), and transitive (the composition of bijections is a bijection).

Examples

Real-Valued Functions

• The linear function $f(x) = ax + b$, where $a \neq 0$, is a bijection from the set of real numbers $\mathbb{R}$ to itself. Its inverse is $f^{-1}(x) = \frac{x - b}{a}$.
• The exponential function $f(x) = e^x$ is a bijection from $\mathbb{R}$ to the set of positive real numbers $\mathbb{R}^+$. Its inverse is the natural logarithm function, $f^{-1}(x) = \ln(x)$.
• The function $f(x) = x^2$ is not a bijection from $\mathbb{R}$ to $\mathbb{R}$ because it is neither injective (e.g., $f(2) = f(-2) = 4$) nor surjective (no real number maps to a negative number). However, if the domain and codomain are restricted to non-negative real numbers $[0, \infty)$, it becomes a bijection.

Finite Sets

Consider the sets $X = \{1, 2, 3\}$ and $Y = \{a, b, c\}$. The function defined by $f(1) = a$, $f(2) = b$, and $f(3) = c$ is a bijection. Any permutation of a finite set is a bijection from the set to itself.

Bijections and Cardinality

Bijections play a central role in the concept of cardinality, which is a measure of the "number of elements" in a set.

Finite Sets

For finite sets $X$ and $Y$, a bijection between them exists if and only if they have the same number of elements. This is the foundational principle of counting: when we count a set of objects, we are essentially establishing a bijection between the set of objects and a subset of the natural numbers $\{1, 2, \dots, n\}$.

Infinite Sets

For infinite sets, the existence of a bijection defines whether two sets have the same cardinality. Two sets are said to be equipotent or equinumerous if there exists a bijection between them.

• The set of natural numbers $\mathbb{N}$ and the set of even natural numbers have the same cardinality, as demonstrated by the bijection $f(n) = 2n$. Sets that can be put into a bijection with $\mathbb{N}$ are called countably infinite.
• Georg Cantor proved that there is no bijection between the set of natural numbers $\mathbb{N}$ and the set of real numbers $\mathbb{R}$. This implies that the cardinality of $\mathbb{R}$ (the continuum) is strictly greater than the cardinality of $\mathbb{N}$, establishing the existence of different sizes of infinity.

Applications

Combinatorics

In combinatorics, bijections are frequently used to prove that two sets have the same size by constructing an explicit one-to-one correspondence between them. This technique, known as a bijective proof, is often more insightful than algebraic manipulation because it reveals the underlying structural equivalence of the combinatorial objects being counted.

Cryptography

Bijective functions are essential in cryptography, particularly in the design of block ciphers and substitution boxes (S-boxes). The encryption process must be a bijection to ensure that every ciphertext can be uniquely decrypted back to its original plaintext. If the function were not injective, multiple plaintexts could map to the same ciphertext, making unique decryption impossible.

Computer Science

In computer science, bijections are used in data structures, hashing, and encoding schemes. A perfect hash function is a bijection between a set of keys and a set of integer indices, allowing for constant-time lookups without collisions. Furthermore, isomorphisms in graph theory and database theory rely on bijective mappings to establish structural equivalence between different systems.

Category Theory

In the language of category theory, a bijection is an isomorphism in the category of sets (denoted as Set). An isomorphism is a morphism that has an inverse morphism. This abstraction allows the concept of a bijection to be generalized to other categories, such as groups (where isomorphisms are bijective homomorphisms) and topological spaces (where homeomorphisms are continuous bijections with continuous inverses).