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

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

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

定義編集

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

 

カントールの対関数編集

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

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

 

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

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

 

であり、ここで

 

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

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

 

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

 
 
 

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

 

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

 

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

 

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

 

従って

 .

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

 
 
 
 

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

参考文献編集

  • Steven Pigeon. "Pairing function". MathWorld (英語).