対関数
対関数（ついかんすう、英: Pairing function）とは、2つの自然数を一意に符号化して1つの自然数を返す関数である。
集合論では、任意の対関数を用いて、有理数全体の集合 Q が可算濃度であることを証明できる。理論計算機科学では、自然数のベクトルの関数 "f" : N → N を新たな関数 "g" : N → N に変換するために使われる。
全ての対関数は原始再帰関数である。
対関数は次のような全単射関数である。
カントールの対関数は次のように定義される対関数である。
formula_3 と formula_4 への対関数の適用をするとき、それによって得られる数を formula_5 と表記することが多い。
この定義を帰納的に一般化すると、カントールのタプル関数となる。すなわち、
であり、ここで
ここで "z" を次のように定義する。
このときの "x" と "y" を求めたい。そのために中間的な値を定義する。
ここで "t" は "w" の三角数である。そこで次の二次方程式を解く。
"w" を "t" の関数で表すと、次のようになる。
"t" が非負実数であれば、これは単調増加する連続関数である。ここで
が成り立つので、次が得られる。
以上から "z" から "x" と "y" を計算すると次のようになる。
以上のようにカントールの対関数には逆関数が存在し、一対一対応している。