対関数

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

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

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

定義

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

[math]\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}.[/math]

カントールの対関数

ファイル:Pairing natural.svg

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

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

[math]\pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2[/math]

[math]k_1[/math] と [math]k_2[/math] への対関数の適用をするとき、それによって得られる数を [math]\langle k_1, k_2 \rangle[/math] と表記することが多い。

この定義を帰納的に一般化すると、カントールのタプル関数となる。すなわち、

[math]\pi^{(n)}:\mathbb{N}^n \to \mathbb{N}[/math]

であり、ここで

[math]\pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n)[/math]

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

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

[math] z = \langle x, y \rangle = \frac{(x + y)(x + y + 1)}{2} + y [/math]

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

[math] w = x + y \![/math]

[math] t = \frac{w(w + 1)}{2} = \frac{w^2 + w}{2} [/math]

[math] z = t + y \![/math]

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

[math] w^2 + w - 2t = 0 \![/math]

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

[math] w = \frac{\sqrt{8t + 1} - 1}{2} [/math]

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

[math] t \leq z = t + y \lt t + (w + 1) = \frac{(w + 1)^2 + (w + 1)}{2} [/math]

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

[math] w \leq \frac{\sqrt{8z + 1} - 1}{2} \lt w + 1 [/math]

従って

[math] w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor [/math].

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

[math] w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor [/math]

[math] t = \frac{w^2 + w}{2} [/math]

[math] y = z - t \![/math]

[math] x = w - y \![/math]

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

参考文献

• Steven Pigeon. “Pairing function”. MathWorld（英語）.