対関数（ついかんすう、英: 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" を計算すると次のようになる。以上のようにカントールの対関数には逆関数が存在し、一対一対応している。

出典:wikipedia