対関数

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

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

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

定義

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

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

カントールの対関数

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

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

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

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

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

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

であり、ここで

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

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

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

$z=\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+y$

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

$w=x+y\!$

$t={\frac {w(w+1)}{2}}={\frac {w^{2}+w}{2}}$

$z=t+y\!$

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

$w^{2}+w-2t=0\!$

w を t の関数で表すと、次のようになる。

$w={\frac {{\sqrt {8t+1}}-1}{2}}$

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

$t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}}$

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

$w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1$

従って

$w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor$.

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

$w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor$

$t={\frac {w^{2}+w}{2}}$

$y=z-t\!$

$x=w-y\!$

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

順序の言葉で述べるならば、$(x,y)$を和$x+y$が小さい順に並べ、和が等しいものについては$y$が小さい順に並べたとき、$\mathbb {N} ^{2}$から$\mathbb {N}$への一意的な順序同型がカントールの対関数である。

ゲーデルの対関数

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

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

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

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

$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}}$

ただし $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)

動画

• N×NからNへの全単射の存在｜カントールの対関数｜単射・全射トレーニング - YouTube
• N×NからNへの全単射の存在｜素因数分解を使って示す｜単射・全射トレーニング - YouTube