Die Cantorsche Paarungsfunktion (manchmal auch Nummerierungsfunktion) ist eine in der theoretischen Informatik verwendete Abbildung. Ihre Verallgemeinerung von Paaren auf Tupel wird als Cantorsche Tupelfunktion bezeichnet.

Mit ihr kann man ein beliebiges Paar (i, j) natürlicher Zahlen durch eine einzige natürliche Zahl k darstellen. Man nummeriert damit alle Zahlenpaare. Diese Nummerierung ist sogar eindeutig umkehrbar. Das heißt, man kann aus der Zahl k das ursprüngliche Zahlenpaar (i, j) wieder ermitteln. Die Idee der diagonalen Abzählung der Menge aller Paare natürlicher Zahlen $\backslash mathbb\{N\}^2$ geht auf Georg Cantor zurück.

Mathematisch gesprochen heißt das: Die Cantorsche Paarungsfunktion ist eine bijektive totale Funktion, die jedem 2-Tupel (i, j) natürlicher Zahlen eine natürliche Zahl k zuordnet.

Motivation

---

In der theoretischen Informatik wird die Cantorsche Paarungsfunktion benutzt, um Funktionen, die mehr als einen Parameter haben, auf Funktionen zurückführen, die nur genau einen Parameter haben, was viele Beweise deutlich erleichtert.

Die Zurückführung eines Problems auf ein (evtl. einfacheres) bereits bekanntes Problem, ist eine bewährte Beweistechnik, die man als Reduktion bezeichnet.

Mit der Cantorschen Paarungsfunktion lässt sich die Berechenbarkeit von k-stelligen Zahlenfunktionen auf die Berechenbarkeit von 1-stelligen Zahlenfunktionen reduzieren. D.h. man kann sich bei der Untersuchung der Berechenbarkeit von Zahlenfunktionen auf die Untersuchung von einstelligen beschränken und weiß, dass die gewonnenen Ergebnisse für alle, also auch für die mehrstelligen Zahlenfunktionen gelten.

Grundsätzliches

---

Es ist vielleicht nicht unmittelbar einsichtig, dass es möglich ist, alle beliebigen Kombinationen von zwei Zahlen durch eine Zahl zu verschlüsseln: Die Menge aller Zahlenpaare $\backslash mathbb\{N\}^2\; =\; \backslash mathbb\{N\}\backslash times\backslash mathbb\{N\}$ scheint viel größer zu sein als die Menge aller Zahlen $\backslash mathbb\{N\}$.

^ | . . . . . . . . . . . . x x x x x x x x x x x x . x x x x x x x x x x x x . x x x x x x x x x x x x . ~ -x-x-x-x-x-x-x-x-x-x-x-x-> = -x-x-x-x-x-x-x-x-x-x-x-x-> | 0 |N x |N als zweidimensionales |N als Menge von Punkten Gitter auf dem Zahlenstrahl 1

Die Cantorsche Paarungsfunktion zeigt jedoch, dass beide Mengen gleich groß sind, denn sie stellt eine 1:1 Beziehung her, sie ist eine Bijektion.

Eine Menge, die man bijektiv auf die natürlichen Zahlen abbilden kann, nennt man abzählbar unendlich (insbesondere haben die natürlichen Zahlen selbst diese Eigenschaft). Die Cantorsche Paarungsfunktion zeigt dann, dass auch die Menge der Paare natürlicher Zahlen abzählbar unendlich ist.

Definition

---

Die Cantorsche Paarungsfunktion definiert man als

$\backslash pi\; :\; \backslash mathbb\{N\}\; \backslash times\; \backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}\; :$

\pi(x, y) = \sum_{i=0}^{x+y} i + y = \frac{1}{2} (x + y) (x + y + 1) + y

wobei man die natürlichen Zahlen bei 0 beginnen lässt.

Kurzschreibweise:

$\backslash langle\; i,\; j\; \backslash rangle\; =\; \backslash pi(i,j)\; =\; k$

k kodiert das Paar (i, j)

Hier ist eine Skizze der Diagonal-Abzählung:

| 0 1 2 3 4 y --+

---

---

---

---

---

---> 0 | 0 2 5 9 14 . 1 | 1 4 8 13 . 2 | 3 7 12 . 3 | 6 11 . 4 |10 . | . x v

Auf den Achsen sind die beiden Werte aufgetragen, wie in einer Entfernungstabelle schlägt man den Wert der Cantorschen Paarungsfunktion im Schnittpunkt nach, zum Beispiel $\backslash langle\; 1,\; 2\backslash rangle\; =\; 8$.

Die Nummerierung ist denkbar einfach: Man zählt diagonal mit Null beginnend die Paare ab: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2) usw.

Man kann das obige Bildungsgesetz direkt ablesen, wenn man sich die Summation jeweils über eine Spalte verdeutlicht.

Erweiterung auf n-Tupel

---

Durch mehrfache Anwendung lassen sich auch n-Tupel eindeutig nummerieren. Man definiert induktiv für $k\; =\; 1,2,3,\backslash ldots$ die Funktionen

$\backslash pi^\{(k)\}\; :\; \backslash mathbb\{N\}^k\; \backslash to\; \backslash mathbb\{N\}$

mit Hilfe der Paarungsfunktion $\backslash pi$ durch:

$\backslash pi^\{(1)\}(x)\; =\; x$

und

$\backslash pi^\{(n+1)\}(x\_1,\; \backslash ldots,\; x\_\{n+1\})\; =\; \backslash pi(\backslash pi^\{(n)\}(x\_1,\; \backslash ldots,\; x\_\{n\}),\; x\_\{n+1\})$

Die Funktionen $\backslash pi^\{(k)\}$ bezeichnet man als Cantorsche Tupelfunktionen.

Kurzschreibweise:

$\backslash langle\; x\_1,\; x\_2,\; \backslash ldots,\; x\_n\backslash rangle\; :=\; \backslash pi^\{(n)\}(x\_1,\; x\_2,\; \backslash ldots,\; x\_n)$

Umkehrfunktion

---

Die Cantorsche Paarungsfunktion ist umkehrbar. Die Umkehrung ist eindeutig und berechenbar. Letzteres ist für die Anwendung in der theoretischen Informatik wichtig, da die Berechenbarkeit der Funktion und der Umkehrfunktion Bedingung sind, um ohne Probleme alle berechenbaren Funktionen durch einstellige Funktionen darzustellen.

Umkehrbar heißt, man kann aus einer Zahl n auf die beiden Zahlen x und y schließen, für die gilt: $n\; =\; \backslash pi\; (x,y)$. Die Umkehrfunktion setzt sich aus zwei Hilfsfunktionen f und q zusammen. Diese Funktionen werden weiter unten formal definiert.

Beispiel

Welches Zahlenpaar repräsentiert die Zahl 17?

Dazu bestimmt man zunächst eine Zahl j, die die größte Zahl ist, für die gilt $f(j)\; \backslash le\; 17$. Das lässt sich am einfachsten durch Ausprobieren ermitteln. Dabei hilft die Wertetabelle von f(j):

j 1 2 3 4 5 6 f(j) 1 3 6 10 15 21

Damit ergibt sich j zu 5. Dann ist y = 17 - f(j) = 17 - f(5) = 17 - 15 = 2. Und x = j - y = 5 - 2 = 3.

Also ist <3,2> = 17. Das lässt sich einfach anhand der Skizze oben verifizieren.

Formale Definition

Man schreibt ihre Inverse $\backslash left(\backslash pi^\{(k)\}\backslash right)^\{-1\}:\backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}^k$ komponentenweise als $\backslash pi^\{(k)\}\_i:\backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}$, wobei gilt:

$\backslash pi^\{(k)\}\_i\; =\; \backslash mbox\{pr\}^\{(k)\}\_i\; \backslash circ\; \backslash left(\backslash pi^\{(k)\}\backslash right)^\{-1\}$

vermöge der Projektion

$\backslash mbox\{pr\}^\{(k)\}\_i(x\_1,\; \backslash ldots,\; x\_k)\; =\; x\_i$,

welche die i-te Komponente aus einem Tupel der Länge k auswählt.

Bei Paaren (der Fall $k\; =\; 2$) schreibt man kurz $\backslash pi^\{(2)\}\_1\; =\; \backslash pi\_1$ und $\backslash pi^\{(2)\}\_2\; =\; \backslash pi\_2$, so dass man die Inverse der Paarungsfunktion als $\backslash pi^\{-1\}\; =\; (\backslash pi\_1,\; \backslash pi\_2)$ schreiben kann.

Mit den Hilfsfunktionen

$f(w)\; =\; \backslash sum\_\{i=0\}^w\; i\; =\; \backslash frac\{1\}\{2\}w(w+1)$

und

$q(z)\; =\; \backslash max\backslash \{v\; |\; f(v)\; \backslash le\; z\backslash \}$

kann man $\backslash pi\_1$ und $\backslash pi\_2$ wie folgt berechnen:

$\backslash pi\_2(z)\; =\; z\; -\; f(q(z))$

und

$\backslash pi\_1(z)\; =\; q(z)\; -\; \backslash pi\_2(z)$.

Computerimplementierungen

---

Implementierung der Berechnungen in Java

Vielleicht etwas zeitgemäßer als Pascal ist folgende Klasse in Java. Bei großen Werten von z steigt der Zeitbedarf durch die WHILE-Schleife enorm, daher wurde darauf verzichtet, Schleifen zu verwenden.

import java.math.*; public class Cantor { public long compute( int x , int y ) { return this.compute( (long) x , (long) y ); } public long computeX( int z ) { return this.computeX( (long) z ); } public long computeY( int z ) { return this.computeY( (long) z ); } public long compute( long x , long y ) { return (long) (0.5 * (x + y) * (x + y + 1) + y); } public long computeX( long z ) { long j = (long) Math.floor( -0.5 + Math.sqrt( 0.25 + 2.0 * z ) ); return j - this.computeY( z ); } public long computeY( long z ) { long j = (long) Math.floor( -0.5 + Math.sqrt( 0.25 + 2.0 * z ) ); return z - (long) ( 0.5 * j * (j + 1)); } }

Die Methode compute berechnet die dem übergebenen Zahlenpaar x und y zugeordnete Zahl, mit computeX und computeY lässt sich das jeweilige Element des Paares aus der dem Paar zugeordneten Zahl errechnen.

Pascal-Programm zur Berechnung der Umkehrung

Das folgende Pascal-Programm berechnet die Umkehrfunktion $\backslash pi^\{-1\}$:

procedure CantorPair( I : Integer; Var X,Y : Integer); { Gibt das i-te Paar (X,Y) in Diagonalabzaehlung zurueck } var J : Integer; function F(Z : Integer) : Integer; begin F := Z * (Z + 1) div 2 end; function Q(Z : Integer) : Integer; var V : Integer; begin V := 0; while F(V) <= Z do V := V + 1; Q := V - 1 end; begin J := Q(I); Y := I - F(J); X := J - Y; end;

Hinweis: Wird das Pascal-Programm auf realen Rechnern übersetzt, muss es mit den Einschränkungen realer Rechner leben. Das heißt insbesondere, dass Speicherplatzbegrenzungen und Rundungsungenauigkeiten das Ergebnis verfälschen können. Das ist allerdings erst bei sehr großen Werten von z bzw. x und y relevant. Für die Anschauung ist ein Pascal-Programm jedoch verständlicher als eine Registermaschine.

Berechenbarkeit

---

Die Cantorsche Paarungsfunktion ist eine totale, bijektive, berechenbare (sogar primitiv rekursive) Funktion, daher ist auch ihre Umkehrung berechenbar.

Beweis Berechenbarkeit der Cantorschen Paarungsfunktion

Eine Methode, zu beweisen, dass eine Funktion berechenbar ist, ist eine Registermaschine anzugeben, die die Funktion berechnet.

Dieser Maschine muss man im Register R1 den Funktionsparameter x und im Register R2 y übergeben. Man erhält dann im Ausgaberegister R0 den Wert von $\backslash pi$ an der Stelle (x,y).

Die folgende 2-stellige Maschine berechnet die Cantorsche Paarungsfunktion $\backslash pi(x,y)\; =\; \backslash frac\{1\}\{2\}\; (x\; +\; y)\; (x\; +\; y\; +\; 1)\; +\; y$:

R4 = R1 + R2; R5 = R1 + R2 + 1; R4 = R4 * R5; R0 = R4 + R2;

Auf einen formalen Beweis, dass die Registermaschine tatsächlich die Funktion berechnet, wird verzichtet: Das ist offensichtlich erkennbar, wenn man die Funktionsvorschrift zur Berechnung der Cantorschen Paarungsfunktion mit der Maschine vergleicht.

Diese Registermaschine nutzt jedoch Befehle, die die einfache Registermaschine nicht kennt. Die einfache Registermaschine kennt nur die Operationen R+1, R-1 und den einfachen Test.

Durch Verfeinerung lässt sich diese Registermaschine aber auf eine einfache Registermaschine zurückführen.

Damit gibt es eine Registermaschine, die die Cantorsche Paarungsfunktion berechnet. Somit ist die Cantorsche Paarungsfunktion berechenbar.

Beweis der Berechenbarkeit der Umkehrfunktion

Für den Beweis der Umkehrfunktion bietet es sich an, eine andere Definition der Berechenbarkeit zu nutzen:

Eine Funktion ist berechenbar, genau dann, wenn ein WHILE-Programm existiert, das diese Funktion berechnet.

Das oben angegebene Pascal-Programm lässt sich zu einem WHILE-Programm verfeinern. Also gibt es ein WHILE-Programm, das die Umkehrfunktion berechnet. Somit ist auch die Umkehrung berechenbar.

Anwendung der Berechenbarkeit

Dadurch, dass die Cantorsche Paarungsfunktion und ihre Umkehrung berechenbar sind, folgt, dass es für die Theorie der Berechenbarkeit ausreichend ist, sich mit einstelligen Funktionen von $\backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}$ zu befassen. Für Funktionen von $\backslash mathbb\{N\}^n\; \backslash to\; \backslash mathbb\{N\}^n$ folgt die Berechenbarkeit dann durch die Anwendung der Cantorschen Paarungsfunktion und ihrer Umkehrfunktion:

$f\; :\; \backslash mathbb\{N\}^n\; \backslash to\; \backslash mathbb\{N\}^m$ berechenbar, genau dann wenn es eine Funktion g gibt, mit $g\; :\; \backslash mathbb\{N\}\; \backslash to\; \backslash mathbb\{N\}$, $\backslash forall\; n\; \backslash in\; \backslash mathbb\{N\}^n$ gilt $f\; (n)\; :=\; \backslash pi\_m^\{-1\}\; (\; g\; (\; \backslash pi\_n\; (n)\; )\; )$ und g ist berechenbar.

Man kann zum Beispiel zeigen, dass sich alle rationalen Zahlen durch ein 3-Tupel i,j,k darstellen lassen. Damit kann man die Berechenbarkeit leicht von den natürlichen Zahlen auf die Menge der rationalen Zahlen erweitern.

Herkunft

---

Die Idee stammt aus der naiven Mengenlehre. Georg Cantor hatte die Idee, die Größe einer Menge (Mächtigkeit, Kardinalität) mit der Größe einer anderen Menge zu vergleichen, indem man versucht, eine 1:1 Abbildung (Bijektion) der Elemente dieser Menge mit den Elementen der anderen Menge zu finden. Jedem Element der ersten Menge soll genau ein Element der zweiten Menge zugeordnet werden und umgekehrt. Das erscheint kompliziert, findet aber seine Berechtigung, wenn es um Mengen mit unendlich vielen Elementen geht. Mit einer Diagonal-Abzählung, wie oben angedeutet, zeigt man leicht, dass bei einer abzählbaren Menge $M$ das kartesische Produkt $M\; \backslash times\; M\; =\; M^2\; =\; \backslash \{\; (a,\; b)\; |\; a,b\; \backslash in\; M\; \backslash \}$ genau so mächtig ist wie $M$, was vielleicht gegen die Intuition spricht, da hier die Mengen in unterschiedlicher Potenz bzw. die Tupel in verschiedener Länge auftreten.

Alternativen

---

Es gibt viele andere Möglichkeiten Paare natürlicher Zahlen bijektiv durch eine natürliche Zahl zu kodieren, z.B. kann man ein wenig anders abzählen:

| 0 1 2 3 4 y --+

---

---

---

---

---

---> 0 | 0 2 3 9 10 . 1 | 1 4 8 11 . 2 | 5 7 12 . 3 | 6 13 . 4 |14 . | . x v

Auch die einfache Formel $2^x\backslash cdot(2y+1)$ liefert eine Bijektion zwischen $\{\backslash mathbb\; N\}\backslash times\; \{\backslash mathbb\; N\}$ und $\{\backslash mathbb\; N\}\; \backslash setminus\; \backslash \{0\backslash \}$:

| 0 1 2 3 4 y --+

---

---

---

---

---

---> 0 | 1 3 5 7 9 . 1 | 2 6 10 14 18 . 2 | 4 12 20 28 36 . $z=2^x\backslash cdot(2y+1)$ 3 | 8 24 40 56 72 . 4 |16 48 80 112 144 . | . x v

Beweis der Umkehrbarkeit: Faktorisiere z. x ist die Anzahl der 2 als Primfaktor. Sei R das Produkt der anderen Primfaktoren. Dann ist y=(R-1)/2.

Die Primfaktorzerlegung gibt eine Möglichkeit an, beliebige Tupel natürlicher Zahlen durch natürliche Zahlen zu kodieren:

$\backslash langle\; i\_1,\; i\_2,\; i\_3,\; i\_4,\; i\_5,\; \backslash ldots\; \backslash rangle\; =\; 2^\{i\_1\}\; 3^\{i\_2\}\; 5^\{i\_3\}\; 7^\{i\_4\}\; 11^\{i\_5\}\; \backslash cdots$

Beispiel:

$\backslash langle\; 2,\; 1,\; 0,\; 1,\; 0,\; 0\backslash rangle\; =\; 2^2\; 3^1\; 5^0\; 7^1\; 11^0\; 13^0\; \backslash cdots\; =\; 4\; \backslash cdot\; 3\; \backslash cdot\; 7\; =\; 84$

Literatur

---

• Klaus Weihrauch: Computability, Springer (1987), ISBN 3-540-13721-1
• Klaus Weihrauch: Einführung in die Theoretische Informatik A, Kurs 01653 der FernUniversität in Hagen (die aktualisierte Fassung des 1. Teils des Computability Buches, einsehbar in Studienzentren oder im Rahmen eines Akademiestudiums einzeln beziehbar)
• Eric W. Weisstein et al.: Pairing Function, MathWorld--A Wolfram Web Resource
• Erk, Priese: Theoretische Informatik, 2. Auflage, Springer, S. 263 f, ISBN 3540426248
• Schöning: Theoretische Informatik kurzgefasst, 4. Auflage, Spektrum, S. 111 f, ISBN 3827410991

Theoretische Informatik | Mengenlehre

Pairing function | Funzione coppia | 配对函数