Determination axiom

The axiom of determinacy (abbreviated as AD) says that for certain games of infinite length there is always a winning strategy, i.e. the winner is determined . Against the background of the usual Zermelo-Fraenkel set theory (ZF), it is not compatible with the axiom of choice . From the axiom of determinacy it follows that certain unreachable cardinal numbers exist in certain models. Since, on the basis of Gödel's second incompleteness theorem, it cannot be shown that the assumption of the existence of unreachable cardinal numbers is consistent , it cannot be shown either that the axiom of determinacy is consistent. The axiom of determinacy is equiconsistent with the existence of an infinite number of Woodin cardinal numbers .

Infinite games were first examined in 1930 by Stanisław Mazur and Stefan Banach . The axiom of determinacy was introduced in 1962 by Jan Mycielski and Hugo Steinhaus .

Infinite games

${\displaystyle \omega ^{\omega }}$is the set of all infinite sequences of natural numbers, the Baire space . If a subset of , then defines a game between two players, who are denoted by I and II: I begins and chooses a natural number , then II chooses a number , then I chooses another number and so on. After an infinite number of elections, a sequence emerges . If this sequence is in , then player I wins, otherwise player II. ${\displaystyle A}$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle A}$ ${\displaystyle G_{A}}$ ${\displaystyle a_{0}}$ ${\displaystyle a_{1}}$ ${\displaystyle a_{2}}$ ${\displaystyle \langle a_{0},a_{1},a_{2},\ldots \rangle }$ ${\displaystyle A}$

A player's strategy is a rule that determines a move (depending on the finite sequence of numbers already chosen). A strategy is a winning strategy if the player who follows it always wins. The game is determined when there is a winning strategy for one of the two players. The axiom of determinateness says that the game is determined for any subset of . ${\displaystyle G_{A}}$ ${\displaystyle G_{A}}$ ${\displaystyle A}$ ${\displaystyle \omega ^{\omega }}$

Formal definitions

In order to formalize the above rather informal access, one assumes a strategy of the game partners. Player I determines the first number in the sequence, the third, the fifth, and so on. A strategy for player I is therefore a function of the set of all finite sequences after . So if there is such a function, player I plays first . If player II then plays on the next turn , player I then plays and so on. ${\displaystyle \{\langle a_{0},\ldots ,a_{n}\rangle |a_{k}\in \mathbb {N} {\text{ und }}n{\text{ ist ungerade}}\}\cup \{\emptyset \}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \sigma }$ ${\displaystyle a_{0}:=\sigma (\emptyset )}$ ${\displaystyle b_{0}}$ ${\displaystyle \sigma (\langle a_{0},b_{0}\rangle )}$

This sequence of moves, which is determined by the strategy determined by player I and the moves chosen by player II , is denoted by. ${\displaystyle \sigma }$ ${\displaystyle \langle b_{0},\ldots \rangle }$ ${\displaystyle \sigma *b}$

${\displaystyle \sigma }$is now a winning strategy for player I in the game , if he always wins, so if . ${\displaystyle G_{A}}$ ${\displaystyle \{\sigma *b|b\in \omega ^{\omega }\}\subset A}$

A winning strategy for player II is defined analogously.

The axiom of determinacy now reads:

• If a subset of , either player I or player II has a winning strategy for the game . ${\displaystyle A}$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle G_{A}}$

AD and the Axiom of Choice

Since the power of all strategies is, one can show with the axiom of choice through a diagonal argument that there is a game that is not determined. To do this, you construct a set that refutes all strategies of both players: ${\displaystyle 2^{\aleph _{0}}}$ ${\displaystyle G_{A}}$ ${\displaystyle A}$

• For each strategy of player II one chooses an answer from player I and defines this outcome as a win for player I, i. H. . ${\displaystyle \sigma }$ ${\displaystyle b}$ ${\displaystyle \sigma *b\in A}$
• Furthermore, for each strategy of player I, one chooses an answer from the second player and determines that the resulting sequence of moves is not in . ${\displaystyle A}$

So that the set can be defined consistently, the selected sequences must not be repeated. This is possible because with the axiom of choice there is a well-ordering of (and thus also of the set of strategies). The construction can be carried out as a transfinite induction over the set of all strategies of the two players. ${\displaystyle A}$ ${\displaystyle \mathbb {R} }$

Conversely, it follows from the axiom of determinacy that every countable family of non-empty sets of real numbers has a selection function.

Since the set can be mapped uniquely to space , it must be shown that every countable family of non-empty sets has a selection function. The game of this family will be defined as follows: If the player I first the number selected, wins Players II if and only if the result of his chosen numbers in is. If in , the strategy of choosing these numbers in sequence is a winning strategy for player II only in the event that player I chooses at the beginning . But that shows that Player I cannot have a winning strategy. If one accepts the axiom of determinacy, then player II must have a winning strategy. A selection function can be obtained from this strategy: For one selects the sequence that player II plays when player I plays. ${\displaystyle \mathbb {R} }$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle (A_{i})_{i\in \omega },\ A_{i}\subset \omega ^{\omega }}$ ${\displaystyle n}$ ${\displaystyle \langle b_{0},\ldots \rangle }$ ${\displaystyle A_{n}}$ ${\displaystyle \langle b_{0},\ldots ,\rangle }$ ${\displaystyle A_{n}}$ ${\displaystyle n}$ ${\displaystyle A_{n}}$ ${\displaystyle \langle n,0,0,\ldots \rangle }$

Inferences

• From the axiom of determinacy it follows that in is unattainable for everyone . ${\displaystyle \aleph _{1}}$ ${\displaystyle L[a]}$ ${\displaystyle a\subset \omega }$

Lebesgue measurability

With the axiom of choice, non- Lebesgue measurable sets can be constructed, for example Vitali sets . From the axiom of determinacy, however, it follows:

• Any amount of real numbers is Lebesgue measurable.
• Any set of real numbers has the Baire property
• Every uncountable set of real numbers contains a perfect subset

Measurable cardinal numbers

From the axiom of determinacy it follows that measurable cardinal numbers exist.

• ${\displaystyle \aleph _{1}}$is a measurable cardinal number and the filter of club sets is an ultrafilter
• ${\displaystyle \aleph _{2}}$ is a measurable cardinal number.

Consistency of AD

Since the early 1970s, AD was believed to be an axiom about large cardinal numbers. Later, assuming the existence of an infinite number of Woodin cardinal numbers with a measurable cardinal number above them, it was possible to prove that there is an inner model in which the axiom of determinacy applies.

W. Hugh Woodin showed that the following theories are equiconsistent:

• ZFC + There are an infinite number of Woodin cardinal numbers
• ZF + AD

Similar axioms

• The axiom of real determinacy states that every game is also determined if the players are allowed to choose real numbers instead of natural numbers. This axiom is really stronger than AD. ${\displaystyle (\mathrm {AD} _{\mathbb {R} })}$
• The axiom of projective determinacy in turn requires determinacy only for sets of profits that are a projective subset of Baire space.

literature

• Thomas Jech : Set Theory. 3rd millennium edition, revised and expanded. Springer, Berlin et al. 2003, ISBN 3-540-44085-2 , pp. 627ff
• Akihiro Kanamori : The Higher Infinite. Large Cardinals in Set Theory from the Beginnings. Springer Verlag 1994, 2nd edition 2003, ISBN 3540003843