Die Cantorsche Paarungsfunktion

Neben den Diagonalargumenten entwickelte Georg Cantor auch die Cantorsche Paarungsfunktion \(\mathbb{N}^2 \to \mathbb{W}, \quad c(x,y) = \binom{x+y+1}{2}+x = z\), die zwei beliebige Zahlen \(x,y \in \mathbb{N}\) in einer neuen Zahl \(z \in \mathbb{N}\) kodiert. So ist zum Beispiel \(c(3,4)=\binom{3+4+1}{2}+3 = \binom{8}{2}+3=\frac{8!}{6!\cdot 2!} +3 = 31 = z\) eine eindeutige Kodierung der Zahlen \(3\) und \(4\) in der Zahl \(31\). Man zeige: Die Wertemenge \(\mathbb{W} = \mathbb{N}\), d.h. \(z\) nimmt alle natürlichen Zahlen an.


Wir beweisen den speziellen Aufbau der folgenden Tabelle:

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

So ist für \(x > 0, y \geq 0\)
$$
c(x+1,y)-c(x,y+1)=
$$
$$
\binom{x+1+y+1}{2} + x + 1 - \left( \binom{x+y+1+1}{2} + x \right) ) = \binom{x+y+2}{2} - \binom{x+y+2}{2} +x - x + 1 = 1
$$
sowie für \(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)\left( (x+2) - x \right )}{2} - x = x+1 - x = 1
$$
Damit werden alle natürlichen Zahlen erreicht.

Zurück