対関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

定義[編集]

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

\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_1k_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

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

 w = x + y \!
 t = \frac{w(w + 1)}{2} = \frac{w^2 + w}{2}
 z = t + y \!

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

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

wt の関数で表すと、次のようになる。

 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 から xy を計算すると次のようになる。

 w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor
 t = \frac{w^2 + w}{2}
 y = z - t \!
 x = w - y \!

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

参考文献[編集]