Unendlichkeit und natürliche Zahlen

Zeugen für die Unendlichkeit einer Menge A sind Injektionen von A nach A, die Werte auslassen. Andererseits ist eine solche Injektion auf ganz A definiert, insbesondere also auch auf den Werten, die sie selbst auslässt. Dies führt zur folgenden allgemeinen Definition.

Definition (Orbit eines Punktes)

Sei g : A → A eine Funktion, und sei x  ∈  A.

Dann ist S_x : ℕ → A, der Orbit von x unter g in A, rekursiv wie folgt definiert:

S_x(0)	= x,
S_x(n + 1)	= g(S_x(n)) für n  ∈  ℕ.

Ein Orbit S heißt azyklisch, falls S injektiv ist. Andernfalls heißt S zyklisch.

Ein x  ∈  A heißt azyklisch, falls S_x azyklisch ist. Andernfalls heißt x zyklisch.

Der Buchstabe S erinnert hierbei an „Spur“. Der Orbit S_x von x unter g beschreibt die Bahn des Punktes x, wenn wiederholt die Funktion g auf x und seine Bilder angewendet wird.

Ist g(x) = x, so ist S_x(n) = x für alle n  ∈  ℕ. Ist g(x) = y, g(y) = x und x ≠ y, so ist S_x(n) = x für gerade n und S_x(n) = y für ungerade n. Das Wort „zyklisch“ wird zudem motiviert durch die folgende Übung.

Übung (Orbitalbahn eines zyklischen Punktes)

Sei g : A → A eine Funktion, und sei x  ∈  A zyklisch. Dann gilt:

Es existieren n₀  ∈  ℕ und m  ∈  ℕ − { 0 } mit der Eigenschaft:

Für alle n, n′ ≥ n₀ gilt:

S_x(n) = S_x(n′) gdw n ≡ _m n′.

Ist g injektiv, so ist n₀ = 0 geeignet.

[Zur Erinnerung: n ≡ _m n′ gdw n und n′ haben den gleichen Rest bei Division durch m.]

Das (eindeutig bestimmte) derartige m heißt dann der Zyklus von x, das kleinste derartige n₀ die Vorlaufzeit von x.

Eine weitere, etwas informal formulierte Übungsaufgabe für den Leser ist, sich die möglichen Orbit-Typen unter nicht injektiven und unter surjektiven Funktionen g : A → A zu überlegen. Der „Weg rückwärts“ von x zu einem y mit g(y) = x ist für surjektive g immer möglich, aber im Allgemeinen nicht eindeutig. Für Injektionen dagegen kann man weiter den Rückwärtsorbit eines Punktes x definieren (solange entsprechende Urbilder existieren). Für Bijektionen gibt es dann stets einen unendlichen Vorwärts- und Rückwärtsorbit, und die Orbitalbahn wird am besten durch ein h : ℤ → A beschrieben mit h(0) = x. Diese ℤ-Orbits für Bijektionen sind dann entweder Kreise oder ℤ-ähnlich ohne Überlappung. Der Leser ist aufgefordert, auf dem Papier ein bisschen herumzuspielen. Er kann hier ein Stück Mathematik selber formulieren und entdecken.

Der Begriff des Orbits ist für sich interessant, spielt aber im Umfeld der Unendlichkeit nach Dedekind eine besondere Rolle:

Satz (Existenz azyklischer Orbits)

Sei g : A → A injektiv.

Dann ist jedes x  ∈  A − rng(g) azyklisch.

Beweis

Sei x  ∈  A − rng(g), und sei S = S_x der Orbit von x unter g.

Wir zeigen durch Induktion nach n:

Für alle n  ∈  ℕ gilt: S(n) ≠ S(m) für alle 0 ≤ m < n.

Induktionsschritt n: Annahme S(n) = S(m) für ein 0 ≤ m < n.

Dann ist m ≠ 0 wegen S(0) = x  ∉  rng(g) und S(n)  ∈  rng(g).

Dann aber S(n − 1) = S(m − 1) wegen g injektiv, im Widerspruch zur Induktionsvoraussetzung.

Den Leser hat der Begriff des Orbits und der Beweis des obigen Satzes vielleicht an den Beweis des Satzes von Cantor-Bernstein erinnert. In der Tat haben wir dort bereits implizit die Orbits aller Punkte der Menge C unter der Funktion f betrachtet (vgl. das Diagramm im Beweis des Satzes).

Ist also A eine unendliche Menge, so gibt es nach dem Existenzsatz eine Injektion g : A → A und ein x  ∈  A, dessen Orbit unter g azyklisch ist. Die Umkehrung ist Teil des folgenden Satzes, der den fundamentalen Zusammenhang zwischen unendlichen Mengen und natürlichen Zahlen wiedergibt.

Satz (Einbettbarkeit der natürlichen Zahlen in unendliche Mengen)

Sei A eine Menge. Dann sind äquivalent:

(i)	A ist unendlich.

(ii)	Es gibt ein g : A → A und ein x  ∈  A mit einem azyklischen Orbit.

(iii)

|ℕ| ≤ |A|.

Beweis

(i) ↷ (ii): Sei g : A → A′ ⊂ A injektiv. Dann ist jedes x  ∈  A − A′ azyklisch unter g nach dem Satz oben.

(ii) ↷ (iii): Sei S ein azyklischer Orbit unter g. Dann ist S : ℕ → A injektiv.

(iii) ↷ (i): ℕ ist unendlich. Wegen |ℕ| ≤ |A| also auch A.

Die letzte Implikation kann man auch so beweisen: Sei h : ℕ → A injektiv. Für n  ∈  ℕ sei x_n = h(n). Wir „verschieben die x_n um eins“: Wir definieren g : A → A durch

$g (x) = { \begin{matrix} x_{n + 1}, & falls x = x_{n} für ein n \in ℕ, \\ x, & sonst. \end{matrix}$

Dann ist g : A → A − { x₀ } bijektiv. Also A unendlich. Weiter gilt: h ist der Orbit von x₀ unter g.

Mit diesen Ergebnissen können wir nun zeigen, dass wir unendliche Mengen nicht durch endliche Vereinigungen von endlichen Mengen erhalten können.

Satz (Endliche Zerlegungen unendlicher Mengen)

Sei A eine unendliche Menge, und sei P ⊆ ℘(A) eine endliche Zerlegung von A, d. h. P ist endlich, ⋃ P = A, und die Elemente von P sind paarweise disjunkte Mengen. Dann existiert ein unendliches B  ∈  P.

Beweis (durch Besuchszeitenanalyse)

Sei S : ℕ → A der Orbit eines azyklischen x  ∈  A (unter einer beliebigen Injektion g : A → A′ ⊂ A). Für B  ∈  P sei

N_B = { n  ∈  ℕ | S(n)  ∈  B }.

[N_B ist die Menge der „Besuchszeiten“ von x in der Menge B.]

Ist N_B unbeschränkt in ℕ für ein B  ∈  P, so ist |ℕ| = |N_B| ≤ |B|, also B unendlich, und wir sind fertig.

Annahme, N_B ist beschränkt in ℕ für alle B  ∈  P.

Für B  ∈  P mit N_B ≠ ∅ sei

m_B = max(N_B) = „das größte m  ∈  ℕ mit m  ∈  N_B“.

[Die Menge B wird also zum Zeitpunkt m_B zum letzten Mal besucht.]

Schließlich sei

U = { m_B | B  ∈  P, N_B ≠ ∅ }.

Dann ist U unbeschränkt in ℕ.

[Annahme, es gibt ein k  ∈  ℕ mit m < k für alle m  ∈  U. Sei B  ∈  P mit S(k)  ∈  B. Dann ist k  ∈  N_B, also k ≤ m_B  ∈  U, Widerspruch!]

Aber f : U → P mit

f (m) = „das eindeutige B  ∈  P mit S(m)  ∈  B“ für m  ∈  U

ist injektiv nach Konstruktion von U.

Also |ℕ| = |U| ≤ |P|. Also ist P unendlich, Widerspruch!

Übung

Seien A, B endliche Mengen. Dann gilt:

(i)	A ∪ B ist endlich,

(ii)	A × B ist endlich.

Satz (endliche Überdeckungen unendlicher Mengen)

Sei A eine unendliche Menge, und sei P ⊆ ℘(A) eine endliche Überdeckung von A, d. h. P ist endlich und ⋃ P = A. Dann existiert ein unendliches B  ∈  P.

Beweis

Fast genau wie eben, wir müssen lediglich die Definition der Funktion f anpassen. Hierzu setzen wir:

f (m) = „ein B  ∈  P mit S(m)  ∈  B und m_B = m“ für m  ∈  U.

Als Folgerung erhalten wir:

Korollar (Vereinigung endlich vieler endlicher Mengen)

Sei P eine endliche Menge, und jedes B  ∈  P sei endlich.

Dann ist ⋃ P endlich.

In der Analyse des Unendlichkeitsbegriffs nach Dedekind haben wir eine Auswahl der Form „ein …“ zum ersten Mal für den Überdeckungssatz oben verwendet. In der Tat ist ein „ein …“ hier (und für einen Beweis des Korollars) unvermeidlich. Dass die Vereinigung endlich vieler paarweise disjunkter Mengen endlich ist, lässt sich ohne Auswahlakte beweisen, da dies ein Korollar zum Zerlegungssatz ist. Weiter gilt

B₁ ∪ B₂ = B₁ ∪ (B₂ − B₁),

und es folgt induktiv ganz ohne „ein …“, dass B₁ ∪ … ∪ B_n endlich ist für beliebige endliche Mengen B₁, …, B_n, n  ∈  ℕ.

Dagegen ist für die folgende Übung wieder eine Definition der Form „ein …“ nötig:

Übung

Sei A eine endliche Menge. Dann ist ℘(A) endlich.

[Sei S : ℕ → ℘(A) ein azyklischer Orbit. Jedes S(n) ⊆ A ist endlich. Für alle { a₁, …, a_k } ⊆ A, k  ∈  ℕ, existiert ein n  ∈  ℕ mit

S(n) − { a₁, …, a_k } ≠ ∅,

denn S ist injektiv und ℘({ a₁, …, a_k }) hat höchstens 2^k Elemente. Eine induktive Auswahl aus solchen nichtleeren Mengen liefert einen Widerspruch zur Endlichkeit von A.]