対関数

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

集合論では、任意の対関数を用いて、有理数全体の集合 Q が可算濃度であることを証明できる。理論計算機科学では、自然数の多変数関数 f : N^k → N を一変数関数 g : N → N に変換するために使われる。

対関数は非可算無限個存在する。したがってその中には計算可能関数でないものが非可算無限個存在する。計算可能性理論や計算複雑性理論の文脈では、ある複雑性クラスの中で対をコード化して扱いたいことがあることから、対関数とその逆関数がともに目的の関数クラスに属するような符号化を見つけることが重要となる。

定義

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

${\displaystyle \pi$ :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .}

カントールの対関数

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

${\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}}$

${\displaystyle k_{1}}$ と ${\displaystyle k_{2}}$ への対関数の適用をするとき、それによって得られる数を ${\displaystyle \langle k_{1},k_{2}\rangle }$ と表記することが多い。

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

${\displaystyle \pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N} }$

であり、ここで

${\displaystyle \pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})}$

ゲーデルの対関数

対 ${\displaystyle (x,y)}$ を最大値 ${\displaystyle \max(x,y)}$ が小さい順に並べ、最大値が等しいものについては辞書式順序で並べれば、 ${\displaystyle \mathbb {N} ^{2}}$ から ${\displaystyle \mathbb {N} }$ への一意的な順序同型 ${\displaystyle P\colon \mathbb {N} ^{2}\to \mathbb {N} }$ が存在する。この関数は次のように表せる。

${\displaystyle P(x,y)={\begin{cases}x+y^{2}&x<y\\x^{2}+x+y&x\geq y\end{cases}}}$

逆関数 ${\displaystyle Q,R\colon \mathbb {N} \to \mathbb {N} }$ は次のように表せる。

${\displaystyle Q(z)=\min(\lfloor {\sqrt {z}}\rfloor ,E(z))}$

${\displaystyle R(z)={\begin{cases}\lfloor {\sqrt {z}}\rfloor &E(z)<\lfloor {\sqrt {z}}\rfloor \\E(z)-\lfloor {\sqrt {z}}\rfloor &E(z)\geq \lfloor {\sqrt {z}}\rfloor \end{cases}}}$

ただし ${\displaystyle E(z)=z-\lfloor {\sqrt {z}}\rfloor ^{2}}$ である。

参考文献

• Pigeon, Steven. "Pairing function". mathworld.wolfram.com (英語).
• Nagashima, Takashi (1965), “On a certain class of recursive functions”, Hitotsubashi Journal of Arts and Sciences 16: 72–81 

関連項目

• Fueter–Pólya theorem

外部リンク

• Cantor の対関数の全単射性の証明 (PDF)