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.
Definition A pairing function is a bijection
π : N × N → N . {\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .}
Generalization More generally, a pairing function on a set A {\displaystyle A} is a function that maps each pair of elements from A {\displaystyle A} into an element of A {\displaystyle A} , such that distinct pairs of elements of A {\displaystyle A} are associated with distinct elements of A {\displaystyle A} , or a bijection from A 2 {\displaystyle A^{2}} to A {\displaystyle A} . Instead of abstracting from the domain, the arity of the pairing function can also be generalized: there exists an n-ary generalized Cantor pairing function on N {\displaystyle \mathbb {N} } .
Cantor pairing function
The Cantor pairing function is a primitive recursive pairing function
π : N × N → N {\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} }
defined by
π ( k 1 , k 2 ) := 1 2 ( k 1 + k 2 ) ( k 1 + k 2 + 1 ) + k 2 = ( k 1 + k 2 + 1 2 ) + k 2 {\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}={\binom {k_{1}+k_{2}+1}{2}}+k_{2}}
… excerpt ends here. Continue reading the full article.
