配对函数

在数学中，配对函数是一种将两个自然数唯一地编码成一个自然数的过程。

在集合论中可以用任何配对函数来证明整数和有理数有同自然数相同的基数。在理论计算机科学中用它们把定义在自然数的向量上的函数$f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$编码成一个新函数$g:\mathbb {N} \rightarrow \mathbb {N}$。

定义

配对函数是一种可计算的双射函数

$\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ 。

康托尔配对函数

康拖尔配对函数。

康托尔配对函数是一种原始递归配对函数

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

定义为

$\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}.$

在应用配对函数到 $k_{1}$ 和 $k_{2}$ 的时候，我们经常指示结果的数为 $\langle k_{1},k_{2}\rangle$

可以把上面的函数以递回定义推广成以下的康托尔元组函数

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

定义为

$\pi ^{(2)}(k_{1},\,k_{2})=\pi (k_{1},\,k_{2})$

$\pi ^{(n)}(k_{1},\,\ldots ,k_{n-1},\,k_{n}):=\pi [\,\pi ^{(n-1)}(k_{1},\,\ldots ,\,k_{n-1}),\,k_{n}\,]$

引用

• Steven Pigeon. Pairing function. MathWorld.