康托尔的配对功能

对角线参数外,Georg Cantor还开发了Cantor配对函数\(\mathbb{N}^2 \to \mathbb{W}, \quad c(x,y) = \binom{x+y+1}{2}+x = z\)将新数字\(x,y \in \mathbb{N}\)中的\(\mathbb{N}^2 \to \mathbb{W}, \quad c(x,y) = \binom{x+y+1}{2}+x = z\)编码为任意两个数字\(x,y \in \mathbb{N}\) \(z \in \mathbb{N}\) 。 例如, \(c(3,4)=\binom{3+4+1}{2}+3 = \binom{8}{2}+3=\frac{8!}{6!\cdot 2!} +3 = 31 = z\)数字\(31\)数字\(3\)\(4\)的唯一编码。 显示:一组值\(\mathbb{W} = \mathbb{N}\) ,即\(z\)假定所有自然数。


我们证明下表的特殊结构:

  0 1 2 3 ...
0 0 2 5 9 ...
1 1 4 8 13 ...
2 3 7 12 18 ...
3 6 11 17 24 ...
... ... ... ... ... ...

因此对于\(x > 0, y \geq 0\)
$$
c(x + 1,y)-c(x,y + 1)=
$$
$$
\ binom {x + 1 + y + 1} {2} + x + 1-\左(\ binom {x + y + 1 + 1} {2} + x \右))= \ binom {x + y + 2} {2}-\ binom {x + y + 2} {2} + x-x + 1 = 1
$$
以及\(x \geq 0\)
$$
c(0,x + 1)-c(x,0)=
$$
$$
\ binom {0 + x + 1 + 1} {2} + 0-\ binom {x + 0 + 1} {2}-x = \ binom {x + 2} {2}-\ binom {x + 1} {2}-x =
$$
$$
\ frac {(x + 2)!} {2! x!}-\ frac {(x + 1)!} {2!(x-1)!}-x =
$$
$$
\ frac {(x + 2)(x + 1)} {2}-\ frac {(x + 1)x} {2}-x = \ frac {{x + 1)\左((x + 2) -x \ right)} {2}-x = x + 1-x = 1
$$
这意味着所有自然数都可以实现。

背部