Pairing Function

set-theory

Definition

Pairing Function

A pairing function is a bijection $\pi :{\mathbb{N}}^2\to \mathbb{N}$. That is, it encodes an ordered pair of natural numbers as a single natural number such that $\pi (a,b)=\pi (c,d)$ implies $a=c$ and $b=d$.

A common example is the Cantor pairing function:

$$\pi (a,b)=\frac{(a+b)(a+b+1)}{2}+a$$

Pairing functions are used in Gödel numbering and in proofs of countability (e.g. showing ${\mathbb{N}}^2$ is countable).