対関数

対関数（ついかんすう、英: Pairing function）とは、2つの自然数を一意に符号化して1つの自然数を返す関数である。

集合論では、任意の対関数を用いて、有理数全体の集合 Q が可算濃度であることを証明できる。理論計算機科学では、自然数のベクトルの関数 f : N^k → N を新たな関数 g : N → N に変換するために使われる。

全ての対関数は原始再帰関数である。

定義

対関数は次のような全単射関数である。

$\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}.$

カントールの対関数

カントールの対関数は、2つの自然数の対に1つの自然数を割り当てる。

カントールの対関数は次のように定義される対関数である。

$\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)$

カントールの対関数の逆関数

ここで z を次のように定義する。

$z = \langle x, y \rangle = \frac{(x + y)(x + y + 1)}{2} + y$

このときの x と y を求めたい。そのために中間的な値を定義する。

$w = x + y \!$

$t = \frac{w(w + 1)}{2} = \frac{w^2 + w}{2}$

$z = t + y \!$

ここで t は w の三角数である。そこで次の二次方程式を解く。

$w^2 + w - 2t = 0 \!$

w を t の関数で表すと、次のようになる。

$w = \frac{\sqrt{8t + 1} - 1}{2}$

t が非負実数であれば、これは単調増加する連続関数である。ここで

$t \leq z = t + y < t + (w + 1) = \frac{(w + 1)^2 + (w + 1)}{2}$

が成り立つので、次が得られる。

$w \leq \frac{\sqrt{8z + 1} - 1}{2} < w + 1$

従って

$w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor$.

以上から z から x と y を計算すると次のようになる。

$w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor$

$t = \frac{w^2 + w}{2}$

$y = z - t \!$

$x = w - y \!$

以上のようにカントールの対関数には逆関数が存在し、一対一対応している。

参考文献

• Steven Pigeon, "Pairing function" - MathWorld.（英語）