対関数

対関数（ついかんすう、英: Pairing function）とは、2つの自然数を一意に符号化して1つの自然数を返す関数である。
集合論では、任意の対関数を用いて、有理数全体の集合 Q が可算濃度であることを証明できる。理論計算機科学では、自然数の多変数関数 "f" : N"k" → N を一変数関数 "g" : N → N に変換するために使われる。
対関数は非可算無限個存在する。したがってその中には計算可能関数でないものが非可算無限個存在する。計算可能性理論や計算複雑性理論の文脈では、ある複雑性クラスの中で対をコード化して扱いたいことがあることから、対関数とその逆関数がともに目的の関数クラスに属するような符号化を見つけることが重要となる。
定義.
対関数は次のような全単射関数である。
カントールの対関数.
カントールの対関数は次のように定義される対関数である。
formula_3 と formula_4 への対関数の適用をするとき、それによって得られる数を formula_5 と表記することが多い。
この定義を帰納的に一般化すると、カントールのタプル関数となる。すなわち、
であり、ここで
カントールの対関数の逆関数.
ここで "z" を次のように定義する。
このときの "x" と "y" を求めたい。そのために中間的な値を定義する。
ここで "t" は "w" の三角数である。そこで次の二次方程式を解く。
"w" を "t" の関数で表すと、次のようになる。
"t" が非負実数であれば、これは単調増加する連続関数である。ここで
が成り立つので、次が得られる。
従って
以上から "z" から "x" と "y" を計算すると次のようになる。
以上のようにカントールの対関数には逆関数が存在し、一対一対応している。
順序の言葉で述べるならば、formula_21を和formula_22が小さい順に並べ、和が等しいものについてはformula_23が小さい順に並べたとき、formula_24からformula_25への一意的な順序同型がカントールの対関数である。
ゲーデルの対関数.
対 formula_21 を最大値 formula_27 が小さい順に並べ、最大値が等しいものについては辞書式順序で並べれば、 formula_24 から formula_25 への一意的な順序同型 formula_30 が存在する。この関数は次のように表せる。
逆関数 formula_32 は次のように表せる。
ただし formula_35 である。