配對函數

在數學中，配對函數是唯一編碼兩個自然數到一個單一的自然數的過程。

在集合論中可以用任何配對函數來證明整數和有理數有同自然數相同的基數。在理論計算機科學中用它們把定義在自然數的向量上函數 f:N^k → N 編碼到一個新函數 g:N → 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 ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})