 Pairing function

A pairing function is a computable function that gives a bijection from the Cartesian product ${\mathbb{N}}_0^2$ to ${\mathbb{N}}_0$, with two computable functions recovering its coordinates. Here ${\mathbb{N}}_0=\{0,1,2,\dots \}$ consists of the natural numbers, including zero. If $p$ is the pairing function and $L,R$ its decoding functions, the requirements areEvery ordered pair has exactly one code, every code represents an ordered pair, and decoding always terminates. For a bijection given by a total computable function, computability of the inverse function also follows by enumerating all ordered pairs until the one with code $z$ appears. A primitive recursive pairing function makes the stronger requirement that both encoding and coordinate decoding are primitive recursive.

The Cantor pairing function makes this concrete through triangular numbers:On the diagonal $x+y=s$, list $(s,0),(s-1,1),\dots ,(0,s)$. There are $s+1$ ordered pairs there, and $T(s)$ ordered pairs on earlier diagonals. Their codes therefore occupy precisely the consecutive natural numbers from $T(s)$ through $T(s+1)-1$. These intervals touch without overlapping and cover all natural numbers; within each interval the offset $y$ determines the ordered pair. This proves both injectivity and surjectivity, hence the bijection. It also explains why the infinite grid is a countably infinite set: every ordered pair is reached after finitely many steps. A row-by-row listing would never finish its first infinite row. Authored treatments give the same diagonal construction with the coordinates exchanged.^[ref]

For example, the Cantor pairing function givesThe order of the coordinates matters: $(1,0)$ and $(0,1)$ are different ordered pairs with different codes.

To decode a natural number $z$, find the unique diagonal index $s$ satisfyingThe inequality gives $0\le y\le s$, so both recovered coordinates are natural numbers. At $z=18$, $T(5)=15\le 18<T(6)=21$, hence $s=5$, $y=18-15=3$, and $x=5-3=2$. At $z=0$, $s=0$ and both coordinates are zero. Solving the quadratic inequality gives the equivalent floor function expressionThis is exact as a statement about the real numbers and their square roots. An implementation using floating-point arithmetic can round across a diagonal boundary, especially for large $z$. Use an exact integer square root instead: with $q=\lfloor \sqrt{8z+1}\rfloor$ computed using integer arithmetic, $s=\lfloor (q-1)/2\rfloor$. Alternatively, search for the diagonal using exact integer comparisons. The primitive recursive pairing function proof below uses bounded minimization and needs no approximate square root.

A pairing function is a reversible encoding: unlike a hash function mapping arbitrarily many inputs into a fixed finite range, it loses no coordinates. This works because the mathematical natural numbers have no upper bound. A machine word with $b$ binary digits has $2^b$ possible values, while two such words have $2^{2b}$ possible ordered pairs; a bijection into one word of the same width is impossible. Evaluating the Cantor pairing function in a fixed-width integer type can overflow, including in the intermediate product $(x+y)(x+y+1)$. Exact implementation requires sufficiently large integer storage or an explicit restricted input range. One mathematical code need not occupy fewer binary digits than its two inputs.

Iterating a pairing function gives a reversible encoding of tuples of any fixed positive length. With the left-nesting convention, the Cantor pairing function encodes $(2,3,4)$ asDecode the outer ordered pair first: $T(22)\le 257<T(23)=276$ gives $(18,4)$. Decode its first coordinate $18$ to recover $(2,3)$, giving the nested ordered pair $((2,3),4)$ and thus the original tuple $(2,3,4)$.

The tuple length and nesting convention must be known. The same code $257$ represents $(18,4)$ as a two-entry tuple and $(2,3,4)$ as a three-entry tuple; nesting alone does not make variable-length tuples self-describing. To encode variable-length tuples, supply their length or another explicit termination convention as part of the encoding. This simple change of representation is useful in computability theory and Gödel numbering: a function of several natural numbers can be studied through a single numerical input, while all coordinates remain recoverable. The striking fact is that a whole infinite grid can be serialized without omitting a point.

A historical reference for comparing sets through bijections is Georg Cantor's paper Ein Beitrag zur Mannigfaltigkeitslehre, published in 1878 in volume 84 of Journal für die reine und angewandte Mathematik, pages 242–258.^[ref]

A pairing function is a mathematical function that uniquely maps pairs of natural numbers (or non-negative integers) to a single natural number. This concept is particularly useful in various areas of mathematics and computer science, especially in combinatorics and theoretical computer science. Pairing functions can be used to encode two-dimensional data into one-dimensional data, making it easier to work with.