Determinierte Mengen
Eine Menge von reellen Zahlen heißt determiniert, wenn von 2 „Spielern“, die jeweils abwechselnd eine Stelle einer unendlichen Dezimalzahl nennen dürfen, entweder Spieler 1 erzwingen kann, dass die Zahl zu der Menge gehört oder Spieler 2, dass sie nicht dazugehört.
Beispiele
| Gewinnstrategie | |||
|---|---|---|---|
| Spieler 1 beginnt mit einer 1. | ||
| Spieler 2 wählt in seinem n-|
|
| |
Es handelt sich nicht um tatsächlich ausführbare Spiele, da diese i. A. unendlich lang dauern, d. h. nie fertig werden. Für den Begriff der determinierten Menge wird lediglich die Existenz von Gewinnstrategien benutzt.
Eigenschaften
Determinierte Mengen sind „gutartig“ – nach allen Kriterien, die üblicherweise für die Definition von „gutartigen“ Mengen verwendet werden[1] (messbar, haben die Baire-
Wie ist man darauf gekommen?
Wenn nur 3 Ziffern zu spielen sind, lässt sich die Existenz einer Gewinnstrategie für Spieler 1 so formalisieren:
∃ x1 ∀ x2 ∃ x3 : x1x2x3 ∈ A
(Es gibt ein x1, sodass für alle x2 ein x3 existiert, sodass x1x2x3 zur Gewinnmenge A gehört.)
Das logische Gegenteil lautet:
∀ x1 ∃ x2 ∀ x3 : x1x2x3 ∉ A
(Für alle x1 gibt es ein x2, sodass für alle x3 die Zahl x1x2x3 nicht zur Gewinnmenge A gehört.)
Das ist genau eine Gewinnstrategie für Spieler 2. Da immer eine Aussage oder ihr Gegenteil wahr sein muss, sind endliche Spiele der beschriebenen Art also immer determiniert (was oben für 3 Ziffern dargelegt ist, geht analog für n Ziffern).
Für unendliche Spiele dieser Art kann man nicht so argumentieren, da hier der formale Ausdruck unendlich lang wäre, was nicht zulässig ist.[2] Der Begriff der Determiniertheit ergibt sich somit als naheliegende Übertragung einer Eigenschaft im Endlichen auf das Unendliche.
Die Interpretation des formalen Sachverhalts als Gewinnstrategien in einem unendlichen Spiel erleichtert das Verständnis und das Sprechen darüber. Aber da sich die meisten Quellen auf diese Interpretation beschränken, habe ich zunächst nicht verstanden, wie man auf die Idee gekommen ist, in der Mengenlehre unendliche Spiele zu betrachten.
Gleichwertige Varianten
- Die Gewinnmenge darf nur positive reelle Zahlen mit einer 0 vor dem Komma enthalten, ansonsten müssen die „Spieler“ auch genau einmal ein Vorzeichen und ein Komma nennen dürfen. Die Zahlen im Intervall [0, 1) sind jedoch umkehrbar eindeutig allen reellen Zahlen zuordenbar, daher reicht es, nur Zahlen der Form 0,... zuzulassen.
- Ebenso ist es möglich, dass die „Spieler“ in jedem Zug beliebige natürliche Zahlen statt nur 0–
9 nennen dürfen. Über die Kettenbruchentwicklung lassen sich alle positiven irrationalen Zahlen solchen Folgen von natürlichen Zahlen zuordnen (und die rationalen Zahlen sind eine kleine Menge, die man hier weglassen darf). Vorteil: mathematisch einfacher, da die Dezimalzahl- Darstellung mehrdeutig ist (0,1 = 0,0999...). - Manchmal ist es einfacher, die „Spieler“ nur 0 oder 1 „nennen zu lassen“. Auch das führt auf exakt denselben Begriff der determinierten Menge.[3]
Weiter
Siehe auch
- Determiniertheitsaxiom – Aufgrund der schönen Eigenschaften von determinierten Mengen wurde vorgeschlagen, dass per Definition alle Teilmengen von ℝ determiniert sind (indem die entsprechende Grundannahme den Axiomen der ZF-
Mengenlehre hinzugefügt wird).
Quellen
| [1] | Stanford Encyclopedia of Philosophy, Artikel „Set Theory“, Abschnitt „Determinacy“ – Determinacy = „A regularity property of sets that subsumes all other classical regularity properties“ |
| [2] | Yurii Khomskii: Infinite Games (PDF), S. 15 (im PDF S. 17) – „we can no longer apply the quantifier switch ... since we would now have to write an infinite sequence of alternating quantifiers ∃x0∀y0∃x1∀y1 ... which is not a valid logical formula.“ |
| [3] | Horst Herrlich: Axiom of Choice (PDF). Berlin: Springer, 2006, S. 151 (im PDF S. 162), Proposition 7.11 |