配對函式 -- 來自 - 數學天地

配對函式是一個可逆地將對映到的函式，其中 $Z^*={0,1,2,...}$ 表示非負整數。配對函式自然地出現在證明有理數和非負整數的基數相同，即，其中被稱為 aleph-0，最初由 Georg Cantor 提出。配對函式也出現在編碼問題中，在這些問題中，整數值的向量需要可逆地摺疊成單個整數值。

設

(1)

然後 Hopcroft 和 Ullman（1979，第 169 頁）定義了配對函式

			(2)
			(3)

如上表所示，其中。逆函式可以從以下公式計算得出

Hopcroft-Ullman 函式可以重新引數化，使得和在中，而不是中。這個函式被稱為康託函式，由下式給出

(8)

如上表所示。它的逆函式由下式給出

Fueter 和 Pólya 的一個定理指出，康托爾配對函式和 Hopcroft 與 Ullman 的變體是唯一具有實值係數的二次函式，可以將可逆地對映到 (Stein 1999, pp. 448-452)。

Stein (1999) 提出了兩種迴文式（“牛耕式”）變體，如上所示，但沒有給出明確的公式。

還有其他定義配對函式的方法。例如，Pigeon（2001，第 115 頁）提出了一個基於位交織的配對函式。這個“按位”配對函式，如上所示，定義為

$<i,j>_P={_|_ if i=j=0; <|_i/2_|,|_j/2_|>_(SP):i_0:j_0 otherwise,$

(12)

其中（和）是（或）的最低有效位，是連線運算子，符號是空位字串

要配對兩個以上的數字，可以使用配對的配對。例如，可以定義為或，但應定義為，以最小化由此產生的數字的大小。一般的方案是

等等。

配對函式