対関数のソースを表示

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

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

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

== 定義 ==
対関数は次のような[[全単射]]関数である。
:<math>\pi:\mathbb{N} \times \mathbb{N} \to \mathbb{N}.</math>

== カントールの対関数 ==
[[ファイル:Pairing natural.svg|thumb|300px|カントールの対関数は、2つの自然数の対に1つの自然数を割り当てる。]]

[[ゲオルク・カントール|カントール]]の対関数は次のように定義される対関数である。
:<math>\pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2</math>

<math>k_1</math> と <math>k_2</math> への対関数の適用をするとき、それによって得られる数を <math>\langle k_1, k_2 \rangle</math> と表記することが多い。

この定義を帰納的に一般化すると、カントールのタプル関数となる。すなわち、
:<math>\pi^{(n)}:\mathbb{N}^n \to \mathbb{N}</math>
であり、ここで
:<math>\pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n)</math>

=== カントールの対関数の逆関数 ===
ここで ''z'' を次のように定義する。
:<math> z = \langle x, y \rangle = \frac{(x + y)(x + y + 1)}{2} + y </math>

このときの ''x'' と ''y'' を求めたい。そのために中間的な値を定義する。
:<math> w = x + y \!</math>
:<math> t = \frac{w(w + 1)}{2} = \frac{w^2 + w}{2} </math>
:<math> z = t + y \!</math>

ここで ''t'' は ''w'' の[[三角数]]である。そこで次の二次方程式を解く。
:<math> w^2 + w - 2t = 0 \!</math>

''w'' を ''t'' の関数で表すと、次のようになる。
:<math> w = \frac{\sqrt{8t + 1} - 1}{2} </math>

''t'' が非負実数であれば、これは単調増加する連続関数である。ここで
:<math> t \leq z = t + y < t + (w + 1) =  \frac{(w + 1)^2 + (w + 1)}{2} </math>

が成り立つので、次が得られる。
:<math> w \leq \frac{\sqrt{8z + 1} - 1}{2} < w + 1 </math>

従って
:<math> w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor </math>.

以上から ''z'' から ''x'' と ''y'' を計算すると次のようになる。
:<math> w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor </math>
:<math> t = \frac{w^2 + w}{2} </math>
:<math> y = z - t \!</math>
:<math> x = w - y \!</math>

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

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

== ゲーデルの対関数 ==
対 <math>(x, y)</math> を最大値 <math>\max(x, y)</math> が小さい順に並べ、最大値が等しいものについては辞書式順序で並べれば、 <math>\mathbb{N}^{2}</math> から <math>\mathbb{N}</math> への一意的な順序同型 <math>P\colon \mathbb{N}^{2} \to \mathbb{N}</math> が存在する。この関数は次のように表せる。
: <math>P(x, y) = \begin{cases} x+y^{2} & x < y \\ x^{2}+x+y & x\geq y \end{cases}</math>

逆関数 <math>Q,R\colon \mathbb {N}\to \mathbb {N}</math> は次のように表せる。
: <math>Q(z) = \min(\lfloor \sqrt{z} \rfloor, E(z))</math>
: <math>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}</math>

ただし <math>E(z) = z - \lfloor \sqrt{z} \rfloor^2</math> である。

== 参考文献 ==
*{{MathWorld|urlname=PairingFunction|title=Pairing function|author=Pigeon, Steven}}
*{{cite | first = Takashi | last = Nagashima | title = On a certain class of recursive functions | journal = Hitotsubashi Journal of Arts and Sciences | volume = 16 | pages = 72–81 | year = 1965}}

== 関連項目 ==
* [[:en:Fueter–Pólya theorem|Fueter–Pólya theorem]]

== 外部リンク ==
*{{PDFlink|[http://iso.2022.jp/math/pairing_function.pdf Cantor の対関数の全単射性の証明]}}

=== 動画 ===
*{{YouTube|rRpkLoUpvuM|N×NからNへの全単射の存在｜カントールの対関数｜単射・全射トレーニング}}
*{{YouTube|S67g6YfFz5Y|N×NからNへの全単射の存在｜素因数分解を使って示す｜単射・全射トレーニング}}

{{DEFAULTSORT:ついかんすう}}
[[Category:集合論]]
[[Category:ゲオルク・カントール]]
[[Category:数学に関する記事]]