Paradoxa der naiven Mengenlehre

Paradoxa der naiven Mengenlehre
1
Paradoxa der naiven Mengenlehre
von Ivo Hedtke, Jena
Georg Cantor baute um das Jahr 1880 herum seine Mengenlehre (heute als naive Mengenlehre bezeichnet) zur Grundlage der Mathematik aus.
Im Jahr 1903 veröffentlichte Bertrand Russell seine berühmte Antinomie1 , die wir später besprechen. Diese Publikation markierte den Beginn
der Grundlagenkrise der Mathematik (die bis ca. 1930 andauerte). Wir
wollen uns in diesem Artikel mit den Widersprüchen in Cantors naiver
Mengenlehre auseinandersetzen und damit auf die Notwendigkeit der Axiomatisierung der Mengenlehre (wie sie z. B. durch Ernst Zermelo und
Adolf Fraenkel geschah) hinweisen.
1
Grundlagen
Wir greifen – wie auch in den Einstiegsvorlesungen in Mathematik üblich –
auf die Mengendefinition von Cantor zurück:
Definition. Unter einer „Menge“ verstehen wir jede Zusammenfassung
M von bestimmten wohlunterschiedenen Objekten m unserer Anschauung
oder unseres Denkens (welche die „Elemente“ von M genannt werden) zu
einem Ganzen.
Um einige Paradoxa aufzudecken, benötigen wir noch den Satz von Cantor
über die Potenzmenge, der hier ohne Beweis aufgeführt wird.
Satz (von Cantor). Sei M eine Menge und P(M ) = {X : X ⊆ M } die
Potenzmenge von M . Dann gilt card(M ) < card(P(M )).
2
Prominente Paradoxa
Allein aus den obigen Grundlagen können wir einige Beispiele für Paradoxa
innerhalb der naiven Mengenlehre aufzeigen.
2.1
CANTORsches Paradoxon
Das Cantorsche Paradoxon basiert auf Mengen, deren Potenzmenge eine
bestimmte (paradoxe) Eigenschaft besitzen. Wir werden es in zwei Fassungen betrachten.
1 ein
beweisbarer logischer Widerspruch
√
WURZEL
1. 10. 2008
23:52
paradoxa.tex
Paradoxa der naiven Mengenlehre
2
CANTORsches Paradoxon, 1. Fassung: Sei V := {x : x = x} die Menge
aller Objekte. Wir betrachten P(V ). Nach dem Satz von Cantor gilt:
card(V ) < card(P(V )).
Nun gilt aber für diese spezielle Menge V , dass P(V ) ⊆ V . Hieraus folgt,
dass card(P(V )) ≤ card(V ). Dies ergibt zusammen mit dem Satz von
Cantor folgenden Widerspruch:
card(V ) < card(P(V )) ≤ card(V ),
sodass card(V ) < card(V ).
Die zweite Fassung ist analog der ersten, wir betrachten nur eine andere
Menge:
CANTORsches Paradoxon, 2. Fassung: Sei V = {X : X ist eine Menge}
die Menge aller Mengen. Rest: Analog zur ersten Fassung, denn auch hier
gilt P(V ) ⊆ V .
Allgemein gilt: Jede Inklusion P(M ) ⊆ M für eine Menge M ist ein Widerspruch zum Satz von Cantor.
2.2
RUSSELL–ZERMELOsches Paradoxon
Russell ist durch das Studium dieser paradoxen Eigenschaft der Menge V
aus dem Cantorschen Paradoxon auf sein berühmtes eigenes Paradoxon
gestoßen. Es wurde unabhängig auch von Zermelo entdeckt. Wir werden auch hier mehrere Fassungen studieren und die paradoxe Eigenschaft
mehrfach nutzen.
RUSSELL–ZERMELOsches Paradoxon, 1. Fassung: Wir definieren R :=
{X : X ist Menge und X ∈
/ X} als die Menge aller Mengen, die sich nicht
selbst enthalten. Dann gilt für eine beliebige Menge Y : Y ∈ R ⇔ Y ∈
/
Y . Insbesondere gilt dann für Y = R: R ∈ R ⇔ R ∈
/ R. Dies ist ein
Widerspruch.
Der fleißige Barbier (RUSSELL–ZERMELOsches Paradoxon, 2. Fassung): In einem Dorf lebt ein Barbier, der folgendes Schild in sein Fenster
gehängt hat:
ICH RASIERE ALLE, DIE SICH NICHT SELBST RASIEREN.
Die Frage ist nun, darf sich der Barbier selbst rasieren? Laut seiner Aussage muss er sich genau dann rasieren, wenn er sich nicht rasiert. Ein
Widerspruch. Außermathematische Beispiele für Objekte, sie sich selbst als
1. 10. 2008
23:52
paradoxa.tex
√
WURZEL
Paradoxa der naiven Mengenlehre
3
Element enthalten sind:
− Die „Menge aller Ideen“, denn sie ist selbst wieder eine Idee.
− Ein Katalog, der alle Titel von Büchern listet, denn er listet stets selbst
seinen eigenen Titel auf.
In der axiomatischen Mengenlehre sind Mengen M mit der Eigenschaft M ∈
M durch das Fundierungsaxiom ausgeschlossen.
Bemerkung: Frege versuchte eine Axiomatisierung der Mengenlehre. Bemerkenswert ist, dass die Russellsche Antinomie in Freges System stattfand. Als Reaktion auf den Brief von Russell an Frege, fügte dieser dem
sich gerade im Druck befindenden zweiten Band der „Grundlagen der Arithmetik“ eine Bemerkung im Nachwort hinzu, die auf die Antinomie hinwies.
Frege sah dadurch sein Lebenswerk als gescheitert an.
2.3
MIRIMANOFFsches Paradoxon
Für das Paradoxon von D. Mirimanoff ist einiges an Vorarbeit zu leisten.
Wir werden einige Definitionen kennenlernen, bevor wir auf das Mirimanoffsche Paradoxon stoßen, welches wir in zwei Fassungen ansehen wollen.
Definition. Sei n ∈ N0 . Eine Menge X heißt n-reflexiv, falls es Mengen
Y1 , . . . , Yn gibt, mit X ∈ Y1 ∈ . . . ∈ Yn ∈ X.
Insbesondere gilt, eine Menge X ist 0-reflexiv ⇔ X ∈ X.
Definition. Eine Menge X heißt fundiert, falls es keine Mengen Xn , n ∈
N0 gibt, mit X 3 X0 3 X1 3 X2 3 . . .
Ist eine Menge X 0-reflexiv (es gilt X ∈ X), so ist X nicht fundiert, denn
es gilt X 3 X 3 X 3 . . . Allgemeiner ist für n ∈ N0 jede n-reflexive
Menge X nicht fundiert. Gilt X 3 X0 3 X1 3 X2 . . ., so ist nicht nur X
nicht fundiert, sondern auch jedes Xn . Wir analysieren nun zwei Fassungen
des Mirimanoffschen Paradoxons. Man kann auch feststellen, dass der
Ausdruck „1. Version“ und „2. Version“ gerechtfertig ist, denn die beiden
untersuchten Mengen sind gleich (siehe Quelle [3]).
{hedtke}
MIRIMANOFFsches Paradoxon, 1. Version: Wir definieren M := {X :
X ist fundiert}. Ist M selbst fundiert oder nicht?
1. Annahme: M ist fundiert. Dann gilt M ∈ M . Aber dann ist M
nicht fundiert. 2. Also ist M nicht fundiert. Dann existieren Mengen
Xn , n ∈ N0 , mit M 3 X0 3 X1 3 X2 3 . . . Man sieht, dass dann auch X0
nicht fundiert ist. Aber wegen M 3 X0 ist X0 fundiert nach der Definition
von M . Widerspruch!
Für die zweite Version benötigen wir noch eine kleine Vorbemerkung:
Definition. Eine Menge X heißt induktiv, falls für alle Y gilt: Ist Y ⊆ X,
so ist Y ∈ X.
√
WURZEL
1. 10. 2008
23:52
paradoxa.tex
Paradoxa der naiven Mengenlehre
4
MIRIMANOFFsches T
Paradoxon, 2. Version:
Wir definieren U := {X : X ist induktiv}. Dann ist U selbst 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 .
Da U induktiv ist, ist U ∈ U . U ist durch seine Definition auch die kleinste
induktive Menge, sie ist Teilmenge jeder anderen induktiven Menge. Wir
definieren U 0 := U \ {U }. Dann ist U 0 ( U .
U 0 ist auch induktiv. Denn: Sei x ⊆ U 0 . Dann ist auch x ⊆ U . Da U
induktiv, gilt auch x ∈ U . Es gilt auch x 6= U , da U ∈
/ x und U ∈ U . Also
ist x ∈ U 0 .
Da U 0 induktiv ist, gilt U ⊆ U 0 . Somit gilt: U 0 ( U ⊆ U 0 , also U 0 ( U 0 .
Widerspruch!
3
Semantische Paradoxa
Semantischen Paradoxa können der Mathematik nicht wirklich gefährlich
werden, denn setzt man diese semantischen Paradoxa mathematisch um, so
führen sie nicht zu Widersprüchen, sondern zu fundamentalen Erkenntnissen. Der erste Gödelsche Unvollständigkeitssatz gipfelt in der Konstruktion einer formalen Aussage, die inhaltlich besagt: „Ich bin nicht beweisbar.“
3.1
Paradoxon von EPIMENIDES
Beim Paradoxon von Epimenides geht es um folgenden Satz:
Paradoxon von EPIMENIDES: „Diese Aussage ist falsch.“
Ist er wahr, so ist er falsch und ist er falsch, so ist er wahr. Ein Widerspruch.
Durch dieses Prinzip lassen sich noch weitere Paradoxa entwickeln, so z. B.
das folgende Tonband.
paradoxical meditation 120: Sprechen Sie auf ein leeres Tonband mit zwei
Stunden Laufzeit genau einen Satz bei Minute 60, und zwar diesen: „Alle
Sätze auf diesem Tonband sind falsch.“ Spulen Sie das Band zurück,
und hören Sie es sich vollständig an. Haben Sie einen wahren Satz auf dem
Tonband gehört oder nicht?
Nimmt man an, dieser eine Satz, den man gehört hat ist wahr, so sagt er
aus, dass alle Sätze falsch sind, also ist er selbst falsch. Setzen wir voraus,
dass der Satz falsch ist, so ist er inhaltlich richtig und darum nicht falsch
sondern richtig. Ein Widerspruch.
3.2
Paradoxon von J. RICHARD
Das Paradoxon von Richard verwendet für die Bildung des Widerspruchs
das Cantorsche Diagonalisierungsverfahren.
1. 10. 2008
23:52
paradoxa.tex
√
WURZEL
Paradoxa der naiven Mengenlehre
5
Paradoxon von J. RICHARD: Sei S = (Sn )n∈N0 die abzählbar unendliche Liste aller Sätze Sn , n ∈ N0 der deutschen Sprache, die eine reelle Zahl
definieren. Diese Definitionen können lexikalisch geordnet und die definierten Dezimalzahlen nummeriert und in Form einer Liste S0 zusammengefasst
werden. In dieser Liste S0 wird die n-te Ziffer p der n-ten Dezimalzahl durch
die Ziffer p + 1 ersetzt, wenn p nicht gleich 8 oder 9 ist; andernfalls wird p
durch die Ziffer 1 ersetzt. Hintereinander geschrieben bilden die ersetzten
Ziffern eine Dezimalzahl. Diese Dezimalzahl ist in der ursprünglichen Liste
S0 nicht enthalten, weil sie sich von jedem Listeneintrag an mindestens einer
Stelle unterscheidet, nämlich von der n-ten Dezimalzahl an der n-ten Stelle.
Sie kann aber durch einen Satz S der deutschen Sprache definiert werden
(der kursive Satz). Es gilt dann aber, dass S ∈ S und somit die durch S
definierte Zahl in S0 enthalten ist. Ein Widerspruch!
3.3
Paradoxon von G. BERRY
Hinweis: In Quelle[1] ist das Paradoxon von Berry falsch wiedergegeben, {deiser}
es darf unter den im folgenden beschriebenen Umständen nämlich kein Satz
der deutschen Sprache sein.2
Paradoxon von G. G. BERRY: Sei A ⊆ N die Mengen der natürlichen
Zahlen, die durch einen Satz der englischen Sprache definiert werden können,
der höchstens 10 Worte lang ist. A ist endlich, da es nur endlich viele
derartige Sätze gibt. Wir definieren: n := min(N \ A). Dann gilt aber: n =
„The smallest positive integer not definable in under eleven words.“ Dann ist
n aber durch einen Satz der englischen Sprache mit 10 Wörtern definierbar,
also gilt n ∈ A. Ein Widerspruch!
Schlusssatz
Das Studium der Paradoxa der naiven Mengenlehre zeigt uns nicht nur
die Notwendigkeit einer Axiomatisierung, es schärft auch unseren Sinn für
logisches Denken und ist ein spannender Zeitvertreib.
Literatur
{deiser}
[1] O. Deiser: Einführung in die Mengenlehre. 2. Aufl., Springer-Verlag, 2004.
{frege}
[2] G. Frege: Grundlagen der Arithmetik. Reclam-Verlag, 2001.
{hedtke}
[3] I. Hedtke: Warum axiomatische Mengenlehre?, 2007.
http://users.minet.uni-jena.de/~hedtke
2 Denn in der deutschen Sprache ist ein Zahlwort wirklich ein Wort, in der englischen
Sprache besteht es aber bis auf wenige Ausnahmen aus mehreren Wörtern.
√
WURZEL
1. 10. 2008
23:52
paradoxa.tex