配对函数

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

在集合论中可以用任何配对函数来证明整数和有理数有同自然数相同的基数。在理论计算机科学中用它们把定义在自然数的向量上的函数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\,]

引用
*