A pairing function in mathematics is a bijection that uniquely encodes a pair of natural numbers $(x,y)$ as a single natural number. Formally, it is a function $\pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ that is both one-to-one and onto. This provides a way to enumerate all pairs of natural numbers using a single sequence of natural numbers and has important applications in set theory, particularly in demonstrating that the integers and rational numbers have the same cardinality as the natural numbers.
The most famous example is the Cantor pairing function, which is defined by $\pi(x,y)=\frac{1}{2}(x+y)(x+y+1)+y$. It enumerates pairs along successive diagonals of the two-dimensional grid and is strictly increasing in each argument.
The Cantor pairing function is also invertible, meaning that given a natural number $z$, one can uniquely recover the original pair $(x,y)$. The inverse is obtained by first calculating $w=\left\lfloor\frac{\sqrt{8z+1}-1}{2}\right\rfloor$, then $t=\frac{w(w+1)}{2}$, $y=z-t$, and $x=w-y$. The construction can be generalized to encode three or more natural numbers into a single natural number, while related pairing functions can be defined for other mathematical structures, including ordinal numbers.
Beyond its practical use for encoding data, pairing functions illustrate a fundamental idea in mathematics: an apparently much larger space such as $\mathbb{N}\times\mathbb{N}$ can have the same cardinality as $\mathbb{N}$ itself.
ARTICLE
The most famous example is the Cantor pairing function, which is defined by $\pi(x,y)=\frac{1}{2}(x+y)(x+y+1)+y$. It enumerates pairs along successive diagonals of the two-dimensional grid and is strictly increasing in each argument.
The Cantor pairing function is also invertible, meaning that given a natural number $z$, one can uniquely recover the original pair $(x,y)$. The inverse is obtained by first calculating $w=\left\lfloor\frac{\sqrt{8z+1}-1}{2}\right\rfloor$, then $t=\frac{w(w+1)}{2}$, $y=z-t$, and $x=w-y$. The construction can be generalized to encode three or more natural numbers into a single natural number, while related pairing functions can be defined for other mathematical structures, including ordinal numbers.
Beyond its practical use for encoding data, pairing functions illustrate a fundamental idea in mathematics: an apparently much larger space such as $\mathbb{N}\times\mathbb{N}$ can have the same cardinality as $\mathbb{N}$ itself.
ARTICLE
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘