= Pairing function
{title2=$\langle x,y\rangle$}
{wiki}
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,\ldots\}$ consists of the <natural numbers>, including zero. If $p$ is the <pairing function> and $L,R$ its decoding <functions>, the requirements are
$$
L(p(x,y))=x,\qquad R(p(x,y))=y,\qquad p(L(z),R(z))=z.
$$
Every <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>:
$$
T(s)=\frac{s(s+1)}2,\qquad \pi(x,y)=T(x+y)+y.
$$
On the diagonal $x+y=s$, list $(s,0),(s-1,1),\ldots,(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.https://www.cs.cmu.edu/~cdm/resources/02-coding.pdf[Klaus Sutner, Primitive Recursion, Carnegie Mellon University, spring 2021, slides 9–13: pairing systems and the Cantor polynomial]{ref}
For example, the <Cantor pairing function> gives
$$
\pi(0,0)=0,\qquad \pi(1,0)=1,\qquad \pi(0,1)=2,\qquad \pi(2,3)=T(5)+3=18.
$$
The order of the coordinates matters: $(1,0)$ and $(0,1)$ are different <ordered pairs> with different codes.
\Image[/cantor-pairing-diagonal-enumeration.png]
{title=The Cantor pairing function on a finite window: labels are codes, and the first 21 ordered pairs fill diagonals zero through five}
To decode a <natural number> $z$, find the unique diagonal index $s$ satisfying
$$
T(s)\leq z<T(s+1),\qquad y=z-T(s),\qquad x=s-y.
$$
The <inequality> gives $0\leq y\leq s$, so both recovered coordinates are <natural numbers>. At $z=18$, $T(5)=15\leq18<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> expression
$$
s=\left\lfloor\frac{\sqrt{8z+1}-1}{2}\right\rfloor.
$$
This 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)$ as
$$
\pi(\pi(2,3),4)=\pi(18,4)=T(22)+4=253+4=257.
$$
Decode the outer <ordered pair> first: $T(22)\leq257<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)$.
\Image[/pairing-function-tuple-decoding.png]
{title=Decoding a known three-entry tuple: first unpair 257 into (18, 4), then unpair 18 into (2, 3)}
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 \i[Ein Beitrag zur Mannigfaltigkeitslehre], published in 1878 in volume 84 of \i[Journal für die reine und angewandte Mathematik], pages 242–258.https://doi.org/10.1515/crelle-1878-18788413[Georg Cantor, Ein Beitrag zur Mannigfaltigkeitslehre, 1878: publisher bibliographic record]{ref}
Back to article page
