Dedekind-Unendlichkeit
Wir hatten eine Menge A als endlich definiert, falls es eine natürliche Zahl n und eine Bijektion f : A → { 1, …, n } gibt. Anschaulich ist eine solche Bijektion eine Zählung f (1), …, f (n) der Elemente von A. Die Definition ist für sich genommen sehr klar, und sie ist auch die in der heutigen axiomatischen Mengenlehre bevorzugte Definition der Endlichkeit. Es gibt aber auch einen alternativen Weg, der die Verwendung der natürlichen Zahlen vollkommen vermeidet und alles aus dem Funktionsbegriff heraus entwickelt. Hierzu wird das Schubfachprinzip an die Spitze gestellt. Wir wissen, dass für eine endliche Menge A eine Injektion f : A → A automatisch bijektiv ist. Für unendliche Mengen ist dies anders. Das einfachste Beispiel ist vielleicht die Nachfolgerfunktion S : ℕ → ℕ mit S(n) = n + 1 für alle n. Diese Funktion ist injektiv, aber nicht bijektiv. Die automatische Bijektivität einer injektiven Transformation unterscheidet die endlichen Mengen von den unendlichen Mengen. Diese Überlegungen motivieren:
Definition (Dedekind-Unendlichkeit)
Eine Menge A heißt Dedekind-unendlich, falls es eine Injektion f : A → A gibt, die nicht surjektiv ist. Andernfalls heißt A Dedekind-endlich.
Eine äquivalente Formulierung der Dedekind-Unendlichkeit ist: Es gibt eine Bijektion zwischen A und einer echten Teilmenge B von A. Die Dedekind-Endlichkeit bedeutet, dass jede Injektion f : A → A eine Bijektion ist. Dies ist eine Version des Schubfachprinzips.
Die beiden Endlichkeits- bzw. Unendlichkeitsdefinitionen erweisen sich als äquivalent. Hierzu beweisen wir zunächst:
Satz (Einbettbarkeit der natürlichen Zahlen)
Sei A eine Menge. Dann sind äquivalent:
(a) | A ist Dedekind-unendlich. |
(b) | Es gibt eine Injektion g : ℕ → A. |
Beweis
(a) impliziert (b):
Sei f : A → A injektiv, aber nicht surjektiv. Dann gibt es ein a0 ∈ A, das nicht im Wertebereich f [ A ] = { f (a) | a ∈ A } von f liegt. Wir betrachten nun den Orbit (an)n ∈ ℕ von a0 unter f, d. h. die Folge (an)n ∈ ℕ mit
an + 1 = f (an) für alle n ≥ 0.
Da f injektiv ist, ist an ≠ am für alle n ≠ m mit n, m ≥ 1. Da a0 nicht im Wertebereich von f liegt, ist zudem an ≠ a0 für alle n > 0. Damit ist g = (an)n ∈ ℕ eine Injektion von ℕ nach A.
(b) impliziert (a):
Sei g : ℕ → A injektiv. Wir definieren zwei Funktionen f1 : g[ ℕ ] → A und f2 : A − g[ ℕ ] → A durch
f1(g(n)) = g(n + 1) für alle n ≥ 0,
f2(a) = a für alle a ∈ A − g[ ℕ ].
Weiter sei
f = f1 ∪ f2,
sodass f : A → A mit f (a) = f1(a) für a ∈ g[ ℕ ] und f (a) = f2(a) sonst. Die Funktion f ist als Vereinigung zweier injektiver Funktionen mit disjunkten Wertebereichen injektiv. Weiter gilt f [ A ] = A − { a0 }, sodass f nicht surjektiv ist.
Ist f : A → A injektiv, nicht surjektiv, A0 = A − f [ A ], A1 = f [ A ], so ist der Orbit jedes Elements a0 von A0 unter f eine Kopie von ℕ in A
Die Dedekind-unendlichen Mengen sind also genau die Mengen, die eine „Kopie“ der natürlichen Zahlen enthalten: Ist g : ℕ → A injektiv, so können wir die Folge g(0), g(1), g(2), …, g(n), … als eine Version von ℕ innerhalb von A betrachten. Auf diesem Abbild von ℕ können wir die Nachfolgerfunktion bilden, und dies liefert zusammen mit der Identität auf allen anderen Elementen eine Injektion, die nicht bijektiv ist. Umgekehrt ist der Orbit jedes ausgelassenen Elements einer nicht surjektiven Injektion f : A → A eine Kopie von ℕ.
Mit Hilfe der Einbettung der natürlichen Zahlen in eine Dedekind-unendliche Menge zeigen wir nun:
Satz (Äquivalenz der Endlichkeits-Definitionen)
Sei A eine Menge. Dann sind äquivalent:
(a) | A ist endlich. |
(b) | A ist Dedekind-endlich. |
Beweis
(a) impliziert (b):
Sei A endlich, und sei f : A → A eine Injektion. Dann ist f bijektiv nach dem Schubfachprinzip. Dies zeigt, dass A Dedekind-endlich ist.
(b) impliziert (a):
Wir zeigen die Implikation indirekt. Sei also A eine unendliche Menge. Wir konstruieren eine Injektion g : ℕ → A und zeigen damit, dass A Dedekind-unendlich ist. Sei hierzu a0 ∈ A beliebig. Wir definieren rekursiv
an + 1 = „ein a ∈ A mit a ≠ ai für alle i = 0, …, n“ für alle n ≥ 0.
Ein derartiges Element a in A existiert für jedes n ≥ 0, denn aufgrund der Unendlichkeit von A ist A ≠ { a0, …, an }. Nach Konstruktion ist g = (an)n ∈ ℕ eine Injektion von ℕ nach A.
Aus einer unendlichen Menge A können wir rekursiv eine injektive Folge a0, a1, a2, … ausheben, durch eine „unendliche Auswahl“ unverbrauchter Elemente
Der zweite Teil des Beweises weist eine Besonderheit auf: Wir müssen unendlich oft aus einer nichtleeren Menge ein im Allgemeinen nicht weiter spezifiziertes Element auswählen. Im Bild gesprochen ziehen wir aus einer Urne mit unendlich vielen Kugeln unendlich oft eine Kugel ohne Zurücklegen. Dass dieses Vorgehen hier und an zahlreichen anderen Stellen erlaubt ist, regeln die Axiome der Mengenlehre. Wir werden darauf noch zurückkommen, weisen aber bereits an dieser Stelle darauf hin. Der Beweis des Satzes besitzt, so einfach und klar er erscheinen mag, eine gewisse grundlagentheoretische Komplexität.