配對函數

在數學中，配對函數是一種將兩個自然數唯一地編碼成一個自然數的過程。

在集合論中可以用任何配對函數來證明整數和有理數有同自然數相同的基數。在理論計算機科學中用它們把定義在自然數的向量上的函數$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}\,]$

引用

• Steven Pigeon. Pairing function. MathWorld.