In mathematics, a pairing function is a process to uniquely encode two natural numbers into a single natural number.[1]
Any pairing function can be used in set theory to prove that integers and rational numbers have the same cardinality as natural numbers.[1]
Hopcroft and Ullman (1979) define the following pairing function: ⟨ i , j ⟩ := 1 2 ( i + j − 2 ) ( i + j − 1 ) + i {\displaystyle \langle i,j\rangle :={\frac {1}{2}}(i+j-2)(i+j-1)+i} , where i , j ∈ { 1 , 2 , 3 , … } {\displaystyle i,j\in \{1,2,3,\dots \}} .[1] This is the same as the Cantor pairing function below, shifted to exclude 0 (i.e., i = k 2 + 1 {\displaystyle i=k_{2}+1} , j = k 1 + 1 {\displaystyle j=k_{1}+1} , and ⟨ i , j ⟩ − 1 = π ( k 2 , k 1 ) {\displaystyle \langle i,j\rangle -1=\pi (k_{2},k_{1})} ).
, where 
.[1] This is the same as the Cantor pairing function below, shifted to exclude 0 (i.e., 
, 
, and 
).
