ℕ × ℕ ist abzählbar: Die Cantorsche Paarungsfunktion
Satz
ℕ × ℕ ist abzählbar.
Beweis
Definiere π : ℕ × ℕ → ℕ bijektiv durch
π(a, b) = (a + b)(a + b + 1)/2 + a.
Zum Beispiel ist π(3,2) = 30/2 + 3 = 18.
Die Funktion π heißt die Cantorsche Paarungsfunktion. π ist bijektiv und zählt die Menge ℕ × ℕ diagonal auf, wie in dem folgenden Diagramm dargestellt:
Obige Formel für die Werte von π erhält man durch die Beobachtung, dass in der ersten Senkrechten des Diagramms (a = 0) die Partialsummen der Reihe 0 + 1 + 2 + 3 + 4 … stehen, und diese berechnen sich zu n(n + 1))/2. Weiter ist die Summe a + b der Koordinaten konstant auf den Diagonalen.
Gegeben (a, b) bestimmt man zuerst die Diagonale, in der sich (a, b) befindet. Der erste Wert dieser Diagonale ist nach obiger Überlegung
π(0, a + b) = (a + b)(a + b + 1)/2.
Und offenbar ist dann π(a, b) = π(0, a + b) + a.
Übung
Für alle n ∈ ℕ gilt: 1 + 2 + … + n = (n (n + 1))/2.
[Durch Induktion oder durch den Gaußtrick n + 1 = (n − 1) + 2 = (n − 2) + 3 = …]
Übung
(i) | Sei A abzählbar. Dann ist auch A × A abzählbar. |
(ii) | Ist A abzählbar und n ≥ 1, so ist auch An abzählbar. |
(iii) | Gilt |A × A| = |A| für eine Menge A, so auch |An| = |A| für alle n ≥ 1. |
Die Cantorsche Paarungsfunktion ist ein Polynom in a und b zweiten Grades. Es ist erstaunlich, dass die diagonale Aufzählung von ℕ × ℕ durch so eine einfache Funktion beschrieben werden kann.
Cantor (1878):
„Es hat nämlich die Funktion μ + ((μ + ν − 1) (μ + ν − 2))/2, wie leicht zu zeigen, die bemerkenswerte Eigenschaft, dass sie alle positiven ganzen Zahlen und jede nur einmal darstellt, wenn in ihr μ und ν unabhängig voneinander ebenfalls jeden positiven, ganzzahligen Wert erhalten.“
In der Tat gibt es keine weiteren Polynome höchstens zweiten Grades in a und b, die ℕ × ℕ bijektiv auf ℕ abbilden, mit Ausnahme der Funktion π͂ : ℕ × ℕ → ℕ, definiert durch π͂(a, b) = π(b, a). Diese Tatsache, die die herausragende Stellung der Cantorschen Paarungsfunktion belegt, ist nichttrivial und als Satz von Fueter-Polya (1923) bekannt − zum Beweis wird das Transzendenz-Resultat von Ferdinand Lindemann (1852 − 1939) benutzt. Viele Fragen in diesem Umfeld sind noch offen. Z. B. ist unbekannt, ob es ein Polynom höheren Grades in a, b geben kann, das ℕ × ℕ bijektiv auf ℕ abbildet [hierzu und zum Satz von Fueter-Polya siehe Smoryński 1991 und Lew/Rosenberg 1978].
Im Hinblick auf den Satz von Fueter-Polya ist interessant, dass es „Fast-Polynome“ zweiten Grades in a, b gibt, die ℕ × ℕ bijektiv auf ℕ abbilden:
Übung
Wir definieren ρ : ℕ × ℕ → ℕ durch
ρ(a, b) = max(a2, b2) + a + (a ∸ b) für a, b ∈ ℕ, wobei
(Man wird ρ liebgewinnen, wenn man einige Werte in ein ℕ × ℕ-Gitter wie im Diagramm zur Cantorschen Paarungsfunktion einzeichnet.)
Es gilt: ρ : ℕ × ℕ → ℕ ist bijektiv.
Die Konstruktion der Cantorschen Paarungsfunktion lässt sich auf höhere Dimensionen verallgemeinern, und man erhält ein bijektives πn : ℕn → ℕ für alle n ≥ 3. πn ist ein Polynom n-ten Grades in a1, … , an.
Eine zweite Möglichkeit, Bijektionen zwischen ℕn und ℕ zu erhalten, ist die Komposition, z. B.
| π3(a1, a2, a3) | = π(π(a1, a2), a3), |
| π4(a1, a2, a3, a4) | = π(π3(a1, a2, a3), a4), |
| π4(a1, a2, a3, a4) | = π(π(a1, a2), π(a3, a4)), usw. |
Beide Möglichkeiten liefern Polynome in a1, a2, … , an, die zweite erzeugt Polynome höheren Grades als die Anzahl der Variablen, z. B. ist π3 vom Grad 4. Es ist nicht bekannt, ob es Polynome gibt, die ℕn bijektiv auf ℕ abbilden und die nicht durch diese beiden Möglichkeiten (und Umordnung der Variablen wie in π͂(a, b) = π(b, a)) gebildet werden.
Abzählungen von ℕ × ℕ und allgemeiner ℕn für n ≥ 2 gibt es natürlich zuhauf. Jede Wanderung auf dem ℕ × ℕ-Feld, in beliebigem Zickzackkurs, die jeden Punkt (a, b) ∈ ℕ × ℕ genau einmal besucht, liefert eine Bijektion zwischen ℕ und ℕ × ℕ.
Übung
Geben Sie ein Polynom dritten Grades in a, b, c an, welches ℕ3 bijektiv auf ℕ abbildet.
[Analog zur Cantorschen Aufzählung, wobei nun die ℕ3-Punkte der Ebenen a + b + c = 0, a + b + c = 1, … nacheinander geeignet aufgezählt werden.]
Übung
Die Funktion f : ℕ2 → ℕ mit f(n, m) = 2n + 1 (m + 1) − 2n − 1 für alle n, m ∈ ℕ ist bijektiv.