対関数

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

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

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

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

定義[編集]

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

カントールの対関数[編集]

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

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

への対関数の適用をするとき、それによって得られる数を と表記することが多い。

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

であり、ここで

カントールの対関数の逆関数[編集]

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

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

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

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

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

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

従って

.

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

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

参考文献[編集]