Nicht determinierte Mengen

Beispiele

Eine Menge, die nicht determiniert ist, lässt sich leicht mit dem Auswahlaxiom definieren. Dazu verwendet man eine Wohlordnung von ℝ, anhand der man (mit transfiniter Induktion) alle möglichen Strategien durchgeht und eine Gewinnmenge definiert, die zu keiner Strategie passt.
Bernstein-Mengen^[1] (= Weder sie noch ihr Komplement enthalten eine perfekte Teilmenge, also eine abgeschlossene Teilmenge ohne isolierte Punkte.)
ebenso unmessbare Mengen, Mengen ohne Baire-Eigenschaft, ...

Eigenschaften

Jede Gewinnstrategie (für Spieler 1 oder 2) bestimmt eine perfekte Teilmenge, nämlich die Menge aller Spiele, die mit dieser Strategie möglich sind. Eine nicht determinierte Menge hat mit jeder dieser perfekten Teilmengen Elemente gemeinsam, enthält aber keine einzige.^[2]
Die kleinste nicht determinierte Menge hat die Mächtigkeit von ℝ – auch wenn die in Bezug auf die Alephs (eine Art von Kardinalzahlen) sehr groß ist (was z. B. dann, wenn das Determiniertheitsaxiom angenommen wird, möglich ist).^[3]
Wenn es eine nicht determinierte Menge gibt, dann gibt es auch eine nicht determinierte, messbare Menge (mit Maß 0)^[4] und eine Bernstein-Menge^[5].
Der Durchschnitt von 2 determinierten Mengen muss nicht determiniert sein.^[6]

Wie sehen nicht determinierte Mengen konkret aus?

In der ZF-Mengenlehre ohne Auswahlaxiom lässt sich keine nicht determinierte Menge angeben.^[7] Somit gibt es auch in der ZFC-Mengenlehre keine nicht determinierte Menge, die man explizit angeben kann (denn mit Hilfe des Auswahlaxioms erhält man nur reine Existenzbeweise).

Mit anderen Axiomen, die man zusätzlich zu ZF annimmt, ist das aber möglich.^[8] Folgende Beispiele für nicht determinierte Spiele habe ich gefunden:

Annahme	Abk.	Spiel
Das Axiom der abhängigen Auswahl gilt nicht. D. h. es gibt eine Menge `X`, bei der jedes Element mit einem anderen Element der Menge in Beziehung steht, und dennoch gibt es keine Folge von Elementen, die jeweils mit ihren benachbarten Folgengliedern in Beziehung stehen.	¬DC	Spieler 1 wählt ein `x` ∈ `X`. Spieler 2 wählt ein `y` ∈ `X`. Wenn `x` und `y` in Beziehung stehen, gewinnt Spieler 2 (ansonsten Spieler 1). Spieler 1 kann keine Gewinnstrategie haben, denn egal, welches Element er nennt, es gibt immer ein Element, das zu dem in Beziehung steht, sodass Spieler 2 gewinnen kann. Wenn Spieler 2 eine Gewinnstrategie hätte, dann könnte er (bei unendlich oft wiederholtem Spiel) eine Folge von Elementen, die jeweils mit ihren benachbarten Folgengliedern in Beziehung stehen, nennen. Das widerspräche aber der Annahme.
Es gibt einen freien Ultrafilter auf ℕ. (Ein Ultrafilter ist eine Familie von Teilmengen mit bestimmten Eigenschaften. Insbesondere ist nie gleichzeitig eine Teilmenge und ihr Komplement in der Familie.)	UF(ℕ)	Die Spieler wählen abwechselnd eine natürliche Zahl, sodass sich eine ansteigende Folge (`a`₁, `a`₂, `a`₃, ...) ergibt. Spieler 1 gewinnt, wenn {0, ..., `a`₁ – 1} ∪ {`a`₂, ..., `a`₃ – 1} ∪ ... in einem vorgegebenen Ultrafilter auf ℕ enthalten ist. Spieler 2 gewinnt, wenn das Komplement {`a`₁, ..., `a`₂ – 1} ∪ {`a`₃, ..., `a`₄ – 1} ∪ ... in dem Ultrafilter enthalten ist. Die Situation ist für beide Spieler gleich. Wenn einer der Spieler eine Gewinnstrategie hätte, könnte sie genauso der andere Spieler nutzen. Daher kann kein Spieler eine Gewinnstrategie haben.

Annahme

Abk.

Spiel

Das Axiom der abhängigen Auswahl gilt nicht. D. h. es gibt eine Menge X, bei der jedes Element mit einem anderen Element der Menge in Beziehung steht, und dennoch gibt es keine Folge von Elementen, die jeweils mit ihren benachbarten Folgengliedern in Beziehung stehen.

¬DC

Spieler 1 wählt ein x ∈ X. Spieler 2 wählt ein y ∈ X. Wenn x und y in Beziehung stehen, gewinnt Spieler 2 (ansonsten Spieler 1).

Spieler 1 kann keine Gewinnstrategie haben, denn egal, welches Element er nennt, es gibt immer ein Element, das zu dem in Beziehung steht, sodass Spieler 2 gewinnen kann.

Wenn Spieler 2 eine Gewinnstrategie hätte, dann könnte er (bei unendlich oft wiederholtem Spiel) eine Folge von Elementen, die jeweils mit ihren benachbarten Folgengliedern in Beziehung stehen, nennen. Das widerspräche aber der Annahme.

Es gibt einen freien Ultrafilter auf ℕ. (Ein Ultrafilter ist eine Familie von Teilmengen mit bestimmten Eigenschaften. Insbesondere ist nie gleichzeitig eine Teilmenge und ihr Komplement in der Familie.)

UF(ℕ)

Die Spieler wählen abwechselnd eine natürliche Zahl, sodass sich eine ansteigende Folge (a₁, a₂, a₃, ...) ergibt. Spieler 1 gewinnt, wenn {0, ..., a₁ – 1} ∪ {a₂, ..., a₃ – 1} ∪ ... in einem vorgegebenen Ultrafilter auf ℕ enthalten ist. Spieler 2 gewinnt, wenn das Komplement {a₁, ..., a₂ – 1} ∪ {a₃, ..., a₄ – 1} ∪ ... in dem Ultrafilter enthalten ist.

Die Situation ist für beide Spieler gleich. Wenn einer der Spieler eine Gewinnstrategie hätte, könnte sie genauso der andere Spieler nutzen. Daher kann kein Spieler eine Gewinnstrategie haben.

Weiter

Schreibweise von mathematischen Ausdrücken

Quellen

[1]	Oliver Deiser: Reelle Zahlen, Abschnitt „Nichtdeterminierte Mengen“ – „Bernstein-Mengen sind nicht determiniert.“
[2]	Noah Schweber im Diskussionsforum StackExchange – „each strategy Σ (for either player) determines a perfect set `P`_Σ ⊆ `ω`^ω, namely the set of reals which can arise as plays consistent with Σ. A set being undetermined just means that it meets but does not contain every `P`_Σ.“
[3]	Joel David Hamkins: The axiom of determinacy for small sets – „the size of the smallest non-determined set, in the sense of the axiom of determinacy, is the continuum; every set of size less than the continuum is determined, even when the continuum is enormous.“ (Beweis auf der Seite)
[4]	Joel David Hamkins im Diskussionsforum MathOverflow – „if there is a non-determined set, then there is a non-determined set with measure 0. In particular, there is a non-determined set that is measurable.“
[5]	Noah Schweber im Diskussionsforum StackExchange – „if you can produce an undetermined set then you can produce a Bernstein set.“
[6]	John Gowers: Determinacy of Borel games II – „an intersection of two determined sets does not have to be determined“
[7]	englische Wikipedia, Artikel „Non-measurable set“, Abschnitt „Consistent definitions of measure and probability“ – „Solovay demonstrated that the existence of a non-measurable set for the Lebesgue measure is not provable within the framework of Zermelo-Fraenkel set theory in the absence of an additional axiom (such as the axiom of choice)“. Stanford Encyclopedia of Philosophy, Artikel „Set Theory“, Abschnitt „Determinacy“ – „One can prove in ZFC—and the use of the AC is necessary—that there are non-determined sets.“ Yurii Khomskii: Infinite Games (PDF), S. 15 (im PDF S. 17) – „the Axiom of Choice is necessary to show that a not determined set exists: one can show (using meta mathematical arguments) that without using it, it is impossible to prove this result.“
[8]	Oliver Deiser: Reelle Zahlen, Abschnitt „Nichtdeterminierte Mengen“ – „Wir halten ohne Beweis fest, dass sich die Existenz einer nichtdeterminierten Menge P ⊆ ^ℕA für überabzählbare A sogar ohne Auswahlaxiom zeigen lässt.“

Seite erstellt am 29.8.2025 – letzte Änderung am 29.8.2025

Mathematik

Wissenschaft

Hauptthemen

Neue und erweiterte Seiten