Determiniertheitsaxiom

Das Axiom der Determiniertheit (abgekürzt mit AD) besagt, dass für bestimmte Spiele unendlicher Länge immer eine Gewinnstrategie existiert, der Gewinner also determiniert ist. Vor dem Hintergrund der üblichen Zermelo-Fraenkel-Mengenlehre (ZF) ist es nicht mit dem Auswahlaxiom verträglich. Aus dem Axiom der Determiniertheit folgt die Existenz gewisser unerreichbarer Kardinalzahlen in bestimmten Modellen. Da auf Grund des zweiten gödelschen Unvollständigkeitssatzes nicht gezeigt werden kann, dass die Annahme der Existenz unerreichbarer Kardinalzahlen konsistent ist, kann auch nicht gezeigt werden, dass das Axiom der Determiniertheit konsistent ist. Das Axiom der Determiniertheit ist äquikonsistent zu der Existenz unendlich vieler Woodin-Kardinalzahlen.

Unendliche Spiele wurden zuerst 1930 von Stanisław Mazur und Stefan Banach untersucht. Das Axiom der Determiniertheit wurde 1962 von Jan Mycielski und Hugo Steinhaus eingeführt.

Unendliche Spiele

$\omega ^{\omega }$ ist die Menge aller unendlichen Folgen natürlicher Zahlen, der Baire-Raum. Ist $A$ eine Teilmenge von $\omega ^{\omega }$, so definiert $A$ ein Spiel $G_{A}$ zwischen zwei Spielern, die mit I und II bezeichnet seien: I beginnt und wählt eine natürliche Zahl $a_{0}$, dann wählt II eine Zahl $a_{1}$, anschließend wählt I wieder eine Zahl $a_{2}$ und so weiter. Nach unendlich vielen Wahlen entsteht eine Folge $\langle a_{0},a_{1},a_{2},\ldots \rangle$. Liegt diese Folge in $A$, so hat Spieler I gewonnen, im anderen Fall Spieler II.

Eine Strategie eines Spielers ist eine Regel, die einen Zug (abhängig von der endlichen Folge der bereits gewählten Zahlen) festlegt. Eine Strategie ist eine Gewinnstrategie, wenn der Spieler, der ihr folgt, immer gewinnt. Das Spiel $G_{A}$ ist determiniert, wenn es für einen der beiden Spieler eine Gewinnstrategie gibt. Das Axiom der Determiniertheit sagt, dass das Spiel $G_{A}$ für jede Teilmenge $A$ von $\omega ^{\omega }$ determiniert ist.

Formale Definitionen

Um obigen eher informellen Zugang zu formalisieren, geht man von einer Strategie der Spielpartner aus. Spieler I bestimmt die erste Zahl der Folge, die dritte, die fünfte und so weiter. Eine Strategie für den Spieler I ist daher eine Funktion von der Menge aller endlichen Folgen $\{\langle a_{0},\ldots ,a_{n}\rangle |a_{k}\in \mathbb {N} {\text{ und }}n{\text{ ist ungerade}}\}\cup \{\emptyset \}$ nach $\mathbb {N}$. Ist also $\sigma$ eine solche Funktion, so spielt Spieler I zuerst $a_{0}:=\sigma (\emptyset )$. Spielt dann Spieler II im nächsten Zug $b_{0}$, so spielt Spieler I anschließend $\sigma (\langle a_{0},b_{0}\rangle )$ und so weiter.

Diese Zugfolge, die durch die von Spieler I festgelegte Strategie $\sigma$ und die von Spieler II gewählten Züge $\langle b_{0},\ldots \rangle$ bestimmt ist, wird mit $\sigma *b$ bezeichnet.

$\sigma$ ist nun für Spieler I im Spiel $G_{A}$ eine Gewinnstrategie, wenn er immer gewinnt, wenn also $\{\sigma *b|b\in \omega ^{\omega }\}\subset A$.

Analog wird eine Gewinnstrategie für Spieler II definiert.

Das Axiom der Determiniertheit lautet nun:

• Ist $A$ eine Teilmenge von $\omega ^{\omega }$, so besitzt entweder Spieler I oder Spieler II für das Spiel $G_{A}$ eine Gewinnstrategie.

AD und das Auswahlaxiom

Da die Mächtigkeit aller Strategien $2^{\aleph _{0}}$ ist, kann man mit dem Auswahlaxiom durch ein Diagonalargument zeigen, dass es ein Spiel $G_{A}$ gibt, das nicht determiniert ist. Dazu konstruiert man eine Menge $A$, die sämtliche Strategien beider Spieler widerlegt:

• Zu jeder Strategie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma} von Spieler II wählt man eine Antwort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} von Spieler I und definiert diesen Ausgang als Gewinn für Spieler I, d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma * b \in A} .
• Weiterhin wählt man für jede Strategie von Spieler I eine Antwort des zweiten Spielers und legt fest, dass die entstehende Zugfolge nicht in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} liegt.

Damit die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} widerspruchsfrei definiert werden kann, dürfen sich die gewählten Folgen sich nicht wiederholen. Dies ist möglich, da mit dem Auswahlaxiom eine Wohlordnung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R} (und somit auch der Menge der Strategien) existiert. Die Konstruktion lässt sich als transfinite Induktion über die Menge aller Strategien der beiden Spieler durchführen.

Umgekehrt folgt aus dem Axiom der Determiniertheit aber, dass jede abzählbare Familie nichtleerer Mengen reeller Zahlen eine Auswahlfunktion besitzt.

Da sich die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R} eineindeutig auf den Raum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^\omega} abbilden lässt, ist dafür zu zeigen, dass jede abzählbare Familie nicht leerer Mengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (A_i)_{i \in \omega}, \ A_i \subset \omega^\omega} eine Auswahlfunktion besitzt. Das Spiel zu dieser Familie wird nun wie folgt definiert: Wenn der Spieler I als erstes die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} wählt, so gewinnt Spieler II genau dann, wenn die Folge der von ihm gewählten Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle b_0, \ldots \rangle} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_n} liegt. Liegt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle b_0, \ldots, \rangle} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_n} , so ist die Strategie, diese Zahlen der Reihe nach zu wählen, eine Gewinnstrategie für den Spieler II zwar nur für den Fall, dass Spieler I am Anfang Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} wählt. Aber das zeigt, dass Spieler I keine Gewinnstrategie haben kann. Nimmt man das Axiom der Determiniertheit an, so muss also Spieler II eine Gewinnstrategie haben. Aus dieser Strategie lässt sich eine Auswahlfunktion gewinnen: Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_n} wählt man die Folge, die Spieler II spielt, wenn Spieler I Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle n, 0, 0, \ldots \rangle} spielt.

Folgerungen

• Aus dem Axiom der Determiniertheit folgt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \aleph_1} unerreichbar in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L[a]} für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \subset \omega} ist.

Lebesgue-Messbarkeit

Mit dem Auswahlaxiom können nicht-Lebesgue-messbare Mengen konstruiert werden, zum Beispiel Vitali-Mengen. Aus dem Axiom der Determiniertheit folgt hingegen:

• Jede Menge reeller Zahlen ist Lebesgue-messbar.
• Jede Menge reeller Zahlen hat die Baire-Eigenschaft
• Jede überabzählbare Menge reeller Zahlen enthält eine perfekte Teilmenge

Messbare Kardinalzahlen

Aus dem Axiom der Determiniertheit folgt, dass messbare Kardinalzahlen existieren.

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \aleph_1} ist eine messbare Kardinalzahl und der Filter der Club-Mengen ist ein Ultrafilter
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \aleph_2} ist eine messbare Kardinalzahl.

Konsistenz von AD

Seit den frühen 1970er Jahren wurde angenommen, dass AD ein Axiom über große Kardinalzahlen ist. Es konnte später dann unter der Voraussetzung der Existenz unendlich vieler Woodin Kardinalzahlen mit einer messbaren Kardinalzahl über ihnen bewiesen werden, dass es ein Inneres Modell gibt, in dem das Axiom der Determiniertheit gilt.

W. Hugh Woodin zeigte, dass folgende Theorien äquikonsistent sind:

• ZFC + Es gibt unendlich viele Woodin Kardinalzahlen
• ZF + AD

Ähnliche Axiome

• Das Axiom der reellen Determiniertheit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\mathrm {AD}_{\mathbb R})} sagt aus, dass auch jedes Spiel determiniert ist, wenn die Spieler statt natürlichen Zahlen reelle Zahlen wählen dürfen. Dieses Axiom ist echt stärker als AD.
• Das Axiom der projektiven Determiniertheit wiederum fordert die Determiniertheit nur für Gewinnmengen, die eine projektive Teilmenge des Baire-Raumes ist.

Literatur

• Thomas Jech: Set Theory. 3. millenium edition, revised and expanded. Springer, Berlin u. a. 2003, ISBN 3-540-44085-2, S. 627 ff.
• Akihiro Kanamori: The Higher Infinite. Large Cardinals in Set Theory from the Beginnings. Springer, Berlin u. a. 1994, ISBN 3-540-57071-3 (2nd edition. ebenda 2003, ISBN 3-540-00384-3).