In mathematics a pairing function is a process to uniquely encode two natural numbers into a single natural number.

Any pairing function can be used in set theory to prove that integers and rational numbers have the same cardinality as natural numbers. In theoretical computer science they are used to encode a function defined on a vector of natural numbers f:N^k → N into a new function g:N → N.

Definition

$\backslash pi:\backslash mathbb\{N\}\; \backslash times\; \backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}.$

Cantor pairing function

The Cantor pairing function is a pairing function

$\backslash pi:\backslash mathbb\{N\}\; \backslash times\; \backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}$

$\backslash pi(k\_1,k\_2)\; :=\; \backslash frac\{1\}\{2\}(k\_1\; +\; k\_2)(k\_1\; +\; k\_2\; +\; 1)+k\_2.$

When we apply the pairing function to $k\_1$ and $k\_2$ we often denote the resulting number as $\backslash langle\; k\_1,\; k\_2\; \backslash rangle$

This definition can be inductively generalized to the Cantor tuple function

$\backslash pi^\{(n)\}:\backslash mathbb\{N\}^n\; \backslash to\; \backslash mathbb\{N\}$

$\backslash pi^\{(n)\}(k\_1,\; \backslash ldots,\; k\_\{n-1\},\; k\_n)\; :=\; \backslash pi\; (\; \backslash pi^\{(n-1)\}(k\_1,\; \backslash ldots,\; k\_\{n-1\})\; ,\; k\_n)$

External link

• "Pairing function" at Mathworld

Set theory

Cantorsche Paarungsfunktion | Funzione coppia | 配对函数