Cantorの対関数
次の関数$ \N^2 \mapsto \Nは全単射である $ f(x,y) = \frac{(x + y)(x + y + 1)}{2} + y
ただしここでの自然数は0を含む
例えば
$ f(0,0) = 0
$ f(0,1) = 1
$ f(1,0) = 2
$ f(0,2) = 3
$ f(1,1) = 4
つまり$ \N^2は加算集合
これを用いれば任意の$ nに対して$ \N^nが加算集合であることがわかる つまり$ f(f(x,y),z)のようにすれば$ \N^3は$ \Nと全単射で 逆関数
$ z \coloneqq \frac{(x+y)(x+y+1)}{2} + y
$ t \coloneqq \frac{w(w+1)}{2}
$ w \coloneqq \left\lfloor \frac{\sqrt{8z+1} - 1}{2} \right\rfloor
$ y = z - t
$ x = w - y