Endlichkeit und natürliche Zahlen
Das offene Problem aus dem letzten Zwischenabschnitt lautete: Ist jede endliche Menge von der Form { a1, ..., an } für ein n ∈ ℕ ? Dies wollen wir nun beweisen.
Zunächst definieren wir für jedes n ∈ ℕ eine Referenzmenge mit genau n Elementen.
Definition (die Mengen n für n ∈ ℕ)
Für n ∈ ℕ sei
n = { 0, 1, … , n − 1 } = { m ∈ ℕ | m < n }.
Die in der Realität auftauchenden Nusshaufen sind endlich im Sinne der Definition von Dedekind. Andernfalls wäre der Algorithmus des paarweisen Abtragens der Nusshaufen H1 und H2 keine korrekte Methode zur Feststellung eines Größenunterschiedes zwischen den Haufen!
Die Mengen n sind nun gewissermaßen die Nusshaufen der mathematischen Welt, und für sie können wir die Korrektheit des Abtragealgorithmus beweisen (vgl. das Korollar unten).
Satz (Endlichkeit von n)
Für jedes n ∈ ℕ ist n endlich.
Beweis
Wir zeigen die Aussage durch Induktion nach n ∈ ℕ.
Induktionsanfang n = 0:
0 = { } ist offenbar endlich.
Induktionsschritt von n nach n + 1:
Sei m = n + 1. Dann ist m = { 0, …, n } = n ∪ { n }.
Nach Induktionsvoraussetzung ist n endlich. Nach dem Satz über das Hinzufügen eines Elementes ist dann auch m endlich.
Wir geben noch einen direkten, von den vorangehenden Überlegungen unabhängigen Beweis des Satzes.
Zweiter Beweis des Satzes
Annahme nicht. Sei dann n das kleinste Element von ℕ mit „n ist unendlich“.
Sei dann f : n → A ⊂ n bijektiv. Offenbar ist n ≠ 0 und A ≠ ∅. Sei also n = n′ + 1. Ohne Einschränkung ist n′ ∈ A.
Andernfalls sei A′ = (A − { min(A) }) ∪ { n′ }. Dann gilt A′ ⊂ n und |A| = |A′|. Also existiert g : n → A′ bijektiv, A′ ⊂ n, und es ist n′ ∈ A′.
Ohne Einschränkung ist zudem f (n′) = n′.
Andernfalls existiert wegen n′ ∈ A ein n* < n′ mit f (n*) = n′. Wir setzen dann
g = (f − { (n′, f (n′)), (n*, n′) }) ∪ { (n′, n′), (n*, f (n′)) }.
Die Funktion g ist genau wie f, lediglich die beiden Werte für n′ und n* sind vertauscht!
Dann ist g : n → A bijektiv und g(n′) = n′.
Wegen f : n → A bijektiv und f (n′) = n′ ist dann aber
f|n′ : n′ → A − { n′ } bijektiv
und A − { n′ } ⊂ n′. Also ist n′ unendlich, im Widerspruch zur minimalen Wahl von n.
Korollar (|n| < |m| für n < m)
Seien n, m ∈ ℕ, und sei f : n → m bijektiv. Dann gilt n = m.
Beweis
Sei f : n → m bijektiv, n ≠ m. Ohne Einschränkung ist m < n (sonst betrachten wir f −1). Dann ist aber m ⊂ n, also n unendlich, Widerspruch!
Übung (Taubenschlagprinzip)
Sei n ∈ ℕ, und sei f : n → n. Dann sind äquivalent:
(i) | f ist injektiv. |
(ii) | f ist bijektiv. |
(iii) | f ist surjektiv. |
[Ist f surjektiv, so betrachten wir g : n → n mit
g(m) = „das kleinste k mit f (k) = m“.]
Schließlich erhalten wir eine nützliche Äquivalenz für die Endlichkeit einer Menge:
Satz (Charakterisierung der endlichen Mengen mit Hilfe der natürlichen Zahlen)
Sei A eine Menge. Dann sind äquivalent:
(i) | A ist endlich. |
(ii) | Es existiert ein n ∈ ℕ mit |A| = |n|. |
Beweis
(i) ↷ (ii): Sei A endlich. Ist A = ∅ sind wir fertig. Andernfalls sei x0 ∈ A.
Wir definieren rekursiv für n ∈ ℕ:
xn + 1 = „ein x ∈ A − { x0, … , xn }“,
solange A − { x0, … , xn } ≠ ∅. (Hier begegnet uns wieder eine Auswahl-Situation.)
Die erhaltenen xn sind paarweise verschieden. Also muss ein kleinstes n* ∈ ℕ existieren, für das xn* nicht definiert ist.
[Denn andernfalls ist g : ℕ → A mit g(n) = xn injektiv, also |ℕ| ≤ |A|, im Widerspruch zu A endlich.]
Dann ist aber f : n* → A mit f (n) = xn bijektiv. Also gilt (ii).
(ii) ↷ (i): Sei n ∈ ℕ und f : A → n bijektiv. Wäre A unendlich, so wäre auch n unendlich, im Widerspruch zum Satz oben. Also ist A endlich.
Es folgt, dass jede endliche Menge A die Form A = { a1, …, an } für ein n ∈ ℕ hat, denn es gilt |A| = |n| für ein n ∈ ℕ, und dann ist A = { f (0), …, f (n − 1) } für eine beliebige Bijektion f : n → A.
Der Beweis des Satzes verwendet die Sätze über Zerlegungen und Überdeckungen unendlicher Mengen nicht, und wir erhalten neue Beweise für die Endlichkeit der Vereinigung endlicher vieler endlicher Mengen. Diese Beweise sind sehr einfach, ruhen aber auf dem obigen Auswahlakt im Beweis von (i) ↷ (ii).
Übung
Zeigen Sie mit Hilfe des obigen Charakterisierungssatzes:
(i) | Die Vereinigung zweier endlicher Mengen ist endlich. |
(ii) | Die Vereinigung endlich vieler endlicher Mengen ist endlich. |
Definition (ℕ-unendlich)
Eine Menge A heißt ℕ-endlich, falls es ein n ∈ ℕ gibt mit |A| = |n|.
A heißt ℕ-unendlich, falls A nicht ℕ-endlich ist.
Man kann die Theorie umgekehrt aufziehen, und die ℕ-Versionen als primäre Definitionen der Unendlichkeit und Endlichkeit benutzen, was ebenso natürlich erscheint wie ein Start mit den Dedekind-Definitionen. Wir haben gezeigt, dass eine Menge genau dann Dedekind-endlich ist, wenn sie ℕ-endlich ist. Interessant ist, dass ein Beweis der Implikation „Dedekind-endlich folgt ℕ-endlich“ oder gleichwertig „ℕ-unendlich folgt Dedekind-unendlich“ abstrakte Auswahlakte benötigt. Die Unterschiede der beiden Definitionen werden sehr klar, wenn man folgende Umformulierung von ℕ-unendlich betrachtet:
Übung
Sei A eine Menge. Dann sind äquivalent:
(i) | A ist ℕ-unendlich. |
(ii) | |n| ≤ |A| für alle n ∈ ℕ. |
Dedekind-unendlich ist dagegen gleichwertig mit |ℕ| ≤ |A|. Die kritische Implikation lautet dann also umformuliert:
Ist |n| ≤ |A| für alle n ∈ ℕ, so gilt |ℕ| ≤ |A|.
Das sieht sehr überzeugend aus, braucht aber bereits starke Hilfsmittel für einen Beweis. Mit ähnlichen Feinheiten wollen wir uns nun beschäftigen.