配对函数

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

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

康拖尔配对函数。

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

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

定义为

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

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

这个定义可以归纳一般化为康托尔元组函数

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

作为

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

• Steven Pigeon. . MathWorld.