13. Paradoxien der naiven Mengenlehre
Zum Schluss dieses Abschnitts und passend zur Kapitelzahl nutzen wir unsere Diagonalisierungserfahrung, um zu zeigen, dass die naive Komprehension
M = { x | ℰ(x) }
von Objekten x mit einer gewissen Eigenschaft ℰ(x) zu einer Menge M widersprüchlich ist. Die Mengenbildung und Existenzaussagen über Mengen müssen also sorgfältiger behandelt werden.
Wir betrachten zunächst das folgende Paradoxon, das auf Cantor zurückgeht.
Cantorsches Paradoxon
Sei V = { x | x = x } die Menge aller Objekte.
Wir betrachten ℘(V). Offenbar gilt ℘(V) ⊆ V, denn x ∈ ℘(V) folgt x = x.
Wir definieren also f : ℘(V) → V durch
f (x) = x für x ∈ ℘(V).
Dann ist f injektiv, also haben wir:
|℘(V)| ≤ |V|.
Aber nach dem Satz von Cantor gilt |M| < |℘(M)| für alle Mengen M.
Also |V| < |℘(V)| ≤ |V|, Widerspruch!
Der gleiche Widerspruch ergibt sich, wenn wir statt der Menge V aller Objekte die Menge V′ = { x | x ist Menge } aller Mengen betrachten, denn auch hier gilt ℘(V′) ⊆ V′. Jede Inklusion ℘(M) ⊆ M für eine Menge M ist ein Widerspruch zum Satz von Cantor.
Bertrand Russell ist durch das Studium dieses Argumentes auf sein berühmtes eigenes Paradoxon gestoßen. Es wurde unabhängig auch von Ernst Zermelo entdeckt.
Russell-Zermelosches Paradoxon
Sei R = { x | x ist Menge und x ∉ x } die Menge aller Mengen, die nicht Element von sich selbst sind. Dann gilt für alle Mengen y:
(+) y ∈ R gdw y ∉ y.
Insbesondere gilt (+) auch für y = R. Dies ergibt:
R ∈ R gdw R ∉ R.
Widerspruch!
Russell (1903, Kapitel 10, S. 102):
„In terms of classes the contradiction appears even more extraordinary. A class as one may be a term of itself as many. Thus the class of all classes is a class; the class of all the terms that are not men is not a man, and so on. Do all the classes that have this property form a class? If so, is it as one a member of itself as many or not? If it is, then it is one of the classes which, as ones, are not members of themselves as many, and vice versâ. Thus we must conclude again that the classes which as ones are not members of themselves as many do not form a class − or rather, that they do not form a class as one, for the argument cannot show that they do not form a class as many.“
Russell entdeckte seine Paradoxie Mitte 1901, wie er später erzählt. Er teilte sie Gottlob Frege (1848 − 1925) brieflich am 16. Juni 1902 mit. (Englische Übersetzungen des auf Deutsch geschriebenen Briefes von Russell und der Antwort von Frege vom 22. Juni 1902 finden sich in der Sammlung [Heijenoort 1967]. Vgl. auch [Frege 1903]). Unabhängig wurde die Paradoxie von Ernst Zermelo gefunden:
Zermelo (1908a):
„Und doch hätte schon die elementare Form, welche Herr B. Russell** den mengentheoretischen Antinomieen gegeben hat, sie [die Skeptizisten der Mengenlehre] überzeugen können, dass die Lösung dieser Schwierigkeiten … in einer geeigneten Einschränkung des Mengenbegriffes zu suchen ist …
**) ‚The Principles of Mathematics‘, vol. I (Cambridge 1903), p. 366 − 368. Indessen hatte ich selbst diese Antinomie unabhängig von Russell gefunden, und sie schon vor 1903 u. a. Herrn Prof. Hilbert mitgeteilt.“
Die Paradoxie von Russell-Zermelo hängt eng mit Cantors Diagonalargument zusammen:
R = { x | x ist Menge und x ∉ x }
ist nichts anderes als die Cantorsche Diagonalisierung
D = { x ∈ M | x ∉ f (x) }
aus dem Beweis der Ungleichung |M| < |℘(M)| für den Spezialfall
M = V′ = { x | x ist Menge }
und der Funktion f = idV′, d. h. f (x) = x für alle Mengen x. Aus dem Beweis des Satzes von Cantor wissen wir, dass
R = { x ∈ V′ | x ∉ f (x) }
nicht im Wertebereich von f liegen kann (vgl. das Korollar zum Satz von Cantor in Kapitel 10). Aber rng(f) = V′, es gilt also R ∉ V′. R ist aber nach dem Komprehensionsaxiom eine Menge, also haben wir R ∈ V′, Widerspruch!
Die Russell-Zermelo-Paradoxie ist also eine Reduzierung der Cantorschen Paradoxie auf einen Spezialfall. Dennoch ist sie von einer bestechenden Brillanz, und zudem ein rein logisches Paradoxon: Es wird ohne Zuhilfenahme von weitergehenden Sätzen gezeigt, dass ein R mit der Eigenschaft (+) nicht existieren kann, oder genauer, dass wir R nicht zu dem Bereich von Objekten rechnen dürfen, die wir in (+) für y einsetzen können. Das Cantorsche Paradoxon benutzt dagegen den nichttrivialen Satz von Cantor, und sein mengentheoretischer Inhalt ist, dass die Objekt- oder Mengenwelt selber keine Menge mehr ist − in dieser Formulierung sicher keine große Überraschung.
Eine einprägsame Version der Russell-Antinomie ist der „fleißige Barbier“: In einem Dorf lebt ein Barbier, der folgende Aussage macht: „Ich schneide genau denjenigen Dorfbewohnern die Haare, die sich ihre Haare nicht selbst schneiden.“ Nun ist der Barbier aber selber ein Dorfbewohner. Er muss sich also nach seiner Aussage die Haare genau dann schneiden, wenn er sie sich nicht selbst schneidet. Widerspruch! Der Barbier kann also sein Versprechen nicht in die Tat umsetzen, seine Aussage ist eine Lüge. Außermathematische Beispiele für Objekte, die sich selbst als Element enthalten sind zudem etwa: Die „Menge aller Ideen“ ist wieder eine Idee; ein Katalog, der alle Titel von Büchern listet, listet seinen eigenen Titel; usw. In der heute üblichen axiomatischen Mengenlehre sind Mengen x mit der Eigenschaft „x ∈ x“ durch das sog. Fundierungsaxiom ausgeschlossen.
Übung
Sei R+ = { x | x ∉ x } = R ∪ { x | x ist Grundobjekt }. Zeigen Sie die Paradoxie:
R+ ∈ R+ gdw R+ ∉ R+.
Eine Variation der Russell-Zermelo-Paradoxie führt zur Paradoxie von Dimitry Mirimanov (1861 − 1945) aus dem Jahre 1917. Hierzu betrachten wir zunächst eine Verallgemeinerung der reflexiven Bedingung „x ∈ x“.
Definition (n-reflexiv)
Sei n ∈ ℕ. Eine Menge x heißt n-reflexiv, falls es Mengen y1, …, yn gibt mit
x ∈ y1 ∈ y2 ∈ … ∈ yn ∈ x.
Insbesondere gilt für alle x:
x ist 0-reflexiv gdw x ∈ x.
Übung
Für n ∈ ℕ sei Rn = { x | x ist nicht n-reflexiv }. Zeigen Sie für alle n ∈ ℕ die Paradoxie:
Rn ist n-reflexiv gdw Rn ist nicht n-reflexiv.
Statt ∈ -Ketten, die bei x starten und wieder bei x enden, können wir auch unendlich absteigende ∈ -Ketten betrachten. Mengen, für die solche Ketten nicht existieren, nennen wir fundiert:
Definition (fundiert)
Eine Menge x heißt fundiert, falls es keine Mengen xn, n ∈ ℕ, gibt mit
x ∋ x0 ∋ x1 ∋ x2 ∋ x3 …
Ist x ∈ x, so ist x nicht fundiert, denn dann gilt x ∋ x ∋ x ∋ … Allgemeiner ist für n ∈ ℕ jedes n-reflexive x nicht fundiert. Ist x ∋ x0 ∋ x1 ∋ … ∋ xn ∋ …, so ist offenbar nicht nur x, sondern auch jedes xn selbst nicht fundiert.
Mirimanovsches Paradoxon, 1. Fassung
Sei M = { x | x ist fundiert }. Annahme, M ist fundiert. Dann gilt M ∈ M, also ist M nicht fundiert. Widerspruch. Also ist M nicht fundiert. Dann existieren Mengen xn, n ∈ ℕ, mit
M ∋ x0 ∋ x1 ∋ x2 ∋ x3 ∋ …
Dann ist aber x0 nicht fundiert. Aber x0 ∈ M, also ist x0 fundiert nach Definition von M, Widerspruch!
Die Paradoxie lässt sich in einer Weise notieren, die an das Cantorsche Paradoxon erinnert. Dort ist ℘(V) ⊆ V die Schlüsseleigenschaft. Allgemein definieren wir:
Definition (induktiv)
Sei x eine Menge. x heißt induktiv, falls für alle y gilt:
Ist y ⊆ x, so ist y ∈ x.
Nach Definitionen ist x genau dann induktiv, wenn ℘(x) ⊆ x.
Wegen x ⊆ x gilt x ∈ x für alle induktiven x. Ist x induktiv und y ⊆ x, so ist auch ℘(y) ⊆ ℘(x) ⊆ x. Iteration ergibt, dass
∅ ⊆ ℘(∅) ⊆ ℘(℘(∅)) ⊆ … ⊆ x,
also sind ∅, ℘(∅), ℘(℘(∅)), … Teilmengen und damit Elemente von allen induktiven Mengen x. Der Leser wird schnell sehen, dass induktive Mengen uferlos groß sind. Sie sind zudem stabil unter Durchschnitten, und dies führt zur zweiten Fassung der Mirimanov-Paradoxie.
Mirimanovsches Paradoxon, 2. Fassung
Sei U = ⋂ { X | X ist induktiv }.
Dann ist U induktiv.
Denn ist x ⊆ U, so ist x ⊆ X für jedes induktive X. Dann ist aber x ∈ X für jedes induktive X, also x ∈ U.
Wegen U induktiv gilt U ∈ U. Wir setzen
U′ = U − { U }.
Dann ist U′ ⊂ U. Weiter ist U′ induktiv.
Denn sei x ⊆ U′. Wegen U′ ⊆ U gilt dann x ⊆ U. Also x ∈ U wegen U induktiv. Aber es gilt x ≠ U denn wir haben U ∉ x, U ∈ U. Also ist x ∈ U − { U } = U′.
Also U′ ⊂ U = ⋂ { X | X ist induktiv } ⊆ U′, Widerspruch!
Die Sprechweise „erste und zweite Fassung“ ist gerechtfertigt, denn die in den Mirimanov-Paradoxien auftretenden „Mengen“ M und U sind identisch (und mit einem natürlichen Argument als identisch zu erkennen, das nicht direkt die paradoxalen Eigenschaften von M und U verwendet ):
Übung
Sei M = { x | x ist fundiert }, U = ⋂ { x | x ist induktiv }. Dann gilt M = U.
[zu U ⊆ M: Ist jedes z ∈ y fundiert, so ist y fundiert. Also ist M induktiv.
zu M ⊆ U: Wir haben U ⊆ M. Annahme, es gibt ein x0 ∈ M − U. Dann gilt non(x0 ⊆ U) wegen U induktiv. Also existiert ein x1 ∈ x0 mit x1 ∉ U. Induktiv zeigt man: Für alle n existiert ein xn + 1 ∈ xn mit xn + 1 ∉ U. Also ist x0 ∈ M nicht fundiert, Widerspruch.]