対関数
カントールの対関数は次のように定義される対関数である。
π ( k 1 , k 2 ) := 1 2 ( k 1 + k 2 ) ( k 1 + k 2 + 1 ) + k 2 {\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}}
k 1 {\displaystyle k_{1}} と k 2 {\displaystyle k_{2}} への対関数の適用をするとき、それによって得られる数を ⟨ k 1 , k 2 ⟩ {\displaystyle \langle k_{1},k_{2}\rangle } と表記することが多い。
この定義を帰納的に一般化すると、カントールのタプル関数となる。すなわち、
π ( n ) : N n → N {\displaystyle \pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N} }
であり、ここで
π ( n ) ( k 1 , ... , k n − 1 , k n ) := π ( π ( n − 1 ) ( k 1 , ... , k n − 1 ) , k n ) {\displaystyle \pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})}
対 ( x , y ) {\displaystyle (x,y)} を最大値 max ( x , y ) {\displaystyle \max(x,y)} が小さい順に並べ、最大値が等しいものについては辞書式順序で並べれば、 N 2 {\displaystyle \mathbb {N} ^{2}} から N {\displaystyle \mathbb {N} } への一意的な順序同型 P : N 2 → N {\displaystyle P\colon \mathbb {N} ^{2}\to \mathbb {N} } が存在する。この関数は次のように表せる。
P ( x , y ) = { x + y 2 x < y x 2 + x + y x ≥ y {\displaystyle P(x,y)={\begin{cases}x+y^{2}&x<y\\x^{2}+x+y&x\geq y\end{cases}}}
逆関数 Q , R : N → N {\displaystyle Q,R\colon \mathbb {N} \to \mathbb {N} } は次のように表せる。