查看“配对函数”的源代码

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

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

== 定义 ==
'''配对函数'''是一种可计算的[[双射]]函数
:<math>\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}</math> 。

== 康托尔配对函数 ==

[[File:Pairing natural.svg|thumb|康拖尔配对函数。]]

'''[[康托尔]]配对函数'''是一种[[原始递归函数|原始递归]]配对函数

:<math>\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}</math>
定义为 
:<math>\pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2.</math>

在应用配对函数到 <math>k_1</math> 和 <math>k_2</math> 的时候，我们经常指示结果的数为 <math>\langle k_1, k_2 \rangle</math>

这个定义可以归纳一般化为'''康托尔元组函数'''
:<math>\pi^{(n)}:\mathbb{N}^n \to \mathbb{N}</math>
作为
:<math>\pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n)</math>

== 引用 ==
*{{mathworld|urlname=PairingFunction|author=Steven Pigeon|title=Pairing function}}

[[Category:集合论|P]]
[[Category:函数]]