配对函数

也称康托尔配对函数，从ω×ω到ω的原始递归的一一对应函数。这样的函数有无穷多个，例如

及

J(x，y)=2(2y+1)－1

都是常用的配对函数。

配对函数有三个特点：(1)．是ω×ω到ω的一一对应；(2)．是原始递归函数；(3)．x≤J(x，y)，y≤J(x，y)。由于J(x，y)是一一对应，故有反函数J：ω→ω×ω，以L(z)表示J(z)的第一个分量，以R(z)表示J(z)的第二个分量，L(z)，R(z)都是原始递归函数，显然J(L(z)，R(z))=z。一般文献常将J(x，y)，L(z)，R(z)通称为配对函数。配对函数也常记作π(x，y)或〈x，y〉、(x，y)等。

利用归纳法，可以定义n元配对函数：

　　J(x)=x，

　　J(x，y)=J(x，y)，

　　J(x，y，z)=J(J(x，y)，z)

　　　……

　　J(x，x，…，x)=J(1J(x，…，x)，x)

其相应的反函数依次记作

(z)，(z)，…，(z)

这些函数也都是原始递归函数；J：ωn→ω是一一对应，J((z)，(z)，…，(z))=z，(z)≤z。n元配对函数J(x，…，x)也常记作π(x，…，x)，〈x，…，x〉或(x，…，x)。

利用n元配对函数，可以将n维的问题化成一维的。因为n元组集合Sω的递归性(递归可枚举性、算术性，等等)与自然数集

S=｛J(x，…，x)｜(x，…，x)∈S｝

相同。所以在递归论中往往可以以S代替S，只考虑一维的情形而不致失去一般性。这可使论述大为化简。