Bijection

Definition

A map $f:X\to Y$ between sets $X$ and $Y$ is a bijection (or one-to-one correspondence) iff it is both an injection and a surjection: $\forall y\in Y.\exists !x\in X.f(x)=y.$

Equivalently, $f$ is a bijection iff it has a two-sided inverse: there exists $g:Y\to X$ such that $g\circ f={\mathrm{id}}_X$ and $f\circ g={\mathrm{id}}_Y$. Such a $g$ is unique and is called the inverse of $f$, written $f^{-1}$.

Properties

• Invertibility: $f:X\to Y$ is a bijection iff it is invertible, i.e. has a two-sided inverse $f^{-1}:Y\to X$.
• Composition: if $f:X\to Y$ and $g:Y\to Z$ are bijections, then $g\circ f:X\to Z$ is a bijection with inverse $f^{-1}\circ g^{-1}$.
• Symmetry group: the set of all bijections $X\to X$ forms a group under composition, called the symmetric group $\mathrm{Sym}(X)$.
• Categorical: bijections between sets are precisely the isomorphisms in Set.

Relationship to Cardinality

Two sets $X$ and $Y$ have the same cardinality, written $|X|=|Y|$, iff there exists a bijection $f:X\to Y$. This is the definition of equipotence.

The Schröder-Bernstein theorem states that if injections $f:X\to Y$ and $g:Y\to X$ both exist, then a bijection between $X$ and $Y$ exists, so $|X|=|Y|$.

Related Concepts

• Injection
• Surjection
• Isomorphism
• Cardinality
• Schröder-Bernstein theorem
• Equivalence Relation