Interplay of Axioms of Determinacy (AD) and Choice (AC) given Zermelo-Fraenkel

Question

I have been thinking and searching and by now I'm really asking myself if I do get something wrong.

So, according to the AD entry on wikipedia, inthe proof of incompatibility with AC we construct a game. The game is such that two players alternatingly pick a natural number, while a set of sequences $A$ is given to begin with. If the (countable) sequence the players together construct ends up being a member of $A$, then P1 wins, otherwise P2 wins.

I define as a strategy a set of moves, or more acurrately a mapping from finite sequences to finite sequences, i.e. given a partial (possibly empty) sequence $a_1a_2...a_n$ it gives an extending sequence $a_1a_2...a_na_{n+1}$. A winning strategy then is a strategy for player PX (for $X\in\{1,2\}$) such that regardless of what the other player plays, PX wins the game. I guess one could say that any combination of P1,P2 strategies simply results in a single sequence.

AD says that for every such game (defined by the set $A$) one of the players has a winning strategy.

Now the curious part: AC says that there is a game such that neither of the players has a winning strategy. Let's use $A_0$ for that peculiar game.

For $A_0$ I kind of start wondering...

• Is it right, that for any P1 strategy there is a P2 strategy such that the resulting sequence is not a member of $A$?
• Is it also right, that for any P2 strategy there is a P1 strategy such that the resulting sequence is not not a member of $A$?
• Is it still right, that for every resulting sequence we either get a member of $A$ or not?
• Or could this also mean that there is a sequence that is neither a member of $A$ nor of its complement? (I guess that's not possible though)
• Then again, strategies should not depend on the opponents strategy, which kind of makes me assume that there should be strategies that result in neither of the players winning, but how would that be possible?
• So it still holds that every combination of strategies P1 and P2 results in a sequence that makes one of them a winner, but none of the players has a strategy that can defy all the opponents strategies?
• This very much reminds me of the destructive LPs and universal LP players from Douglas Hofstadter's book, anyone else?
• Are there similar applications of AD/AC for single player games?

Update

The reference to the LPs and LP players is that for such "bad" sets $A_0$ given a strategy of one player (an indestructable LP player or a destroying LP) the other player can come up with a strategy that beats it (a LP that destroys the player or a player that is not destroyed). The reason I'm interested in this is that I intend implementing this game for abstract argumentation. In a way this means implementation as a directed graph. The essential remark is that graphs provide maximal conflict-free sets iff AC, my aim is to construct a graph that has an independent dominating set iff AD; Then obviously having AC or AD does make a difference. I do have an implementation now, but of course it's not beautiful or visually appealing.

Now, after a few more days of pondering, I have two more questions:

1. For the exemplary game does it suffice to have sequence of digits, i.e. $a_i\in\{0...n\}$ for some fixed $n$? Intuitively I'd say yes and hopefully I don't miss anything. Having sequences of digits say only $0,1$ makes it easier to illustrate and give examples.
2. Assuming the previous, in what sense is AD supposed to be intuitive? There is no finite case, as a restriction to finite cases means that one player has the advantage of moving last (the first move on the other hand is of no advantage).

The finite case I would compare the game with then assumes an even and fixed length of sequences, and players always moving simultaneously. But then already this reduced AD does not hold.

By moving simultaneously I mean a move consists starts with an even sequence, and both players at the same time state their next move, however P1's move is appended to the sequence first.

For instance consider sequences of length $2k$ and the set $A$ to consist of sequences from $\{0,1\}^{2k}$ such that there are an even amount of $1$s in each sequence. Then given knowledge of the other players strategy we can give a strategy to win the game. In fact, for the given set $A$ it suffices being able to know the opponents last move to win the game.

Mini example: $A=\{00,11\}$, the "strategy" (formally it is the strategy that can beat a given strategy of the other player here) for P1 is to do the same as P2 ($1\rightarrow 1$, $0\rightarrow 0$), the "strategy" for P2 is to do the opposite as P1 ($1\rightarrow 0$, $0\rightarrow 1$). No player has a winning strategy.

Is there a more reasonable finite motivation for AD?

Answer 1

• Is it right, that for any P1 strategy there is a P2 strategy such that the resulting sequence is not a member of $A$?
• Is it also right, that for any P2 strategy there is a P1 strategy such that the resulting sequence is not not a member of $A$?

The above two statements are true (for $A=A_0),$ but I think they're a confusing way of phrasing things. Instead, I would say:

• For any P1 strategy, there is a specific play of P2 (that is, a sequence of moves $a_2, a_4, a_6, \dots)$ such that the resulting sequence is not a member of $A_0;$

• For any P2 strategy, there is a specific play of P1 (that is, a sequence of moves $a_1, a_3, a_5, \dots)$ such that the resulting sequence is a member of $A_0.$

• Is it still right, that for every resulting sequence we either get a member of $A$ or not?

Sure — For every $x,$ either $x\in A$ or $x\not\in A.$ (All of this still uses classical logic, including the law of the excluded middle.)

• Or could this also mean that there is a sequence that is neither a member of $A$ nor of its complement? (I guess that's not possible though)

In the same way, the answer to this question is "No" (as you guessed) — for any $x,$ either $x$ is a member of $A$ or $x$ is a member of the complement of $A.$

• Then again, strategies should not depend on the opponents strategy, which kind of makes me assume that there should be strategies that result in neither of the players winning, but how would that be possible?

A strategy for Player $i$ tells Player $i$ what to play for each move of the game; it depends on the earlier moves in the game. (These are games of perfect information, where you know, at each move, everything about the game and what both players have done in it prior to the current move. A strategy for Player $i$ simply tells Player $i$ what to play at each move, based on what has already happened in the game before that.)

You can't have a particular play of the game in which nobody wins. At the end of the game, either the sequence of moves belongs to $A$ (in which case P1 wins) or it does not belong to $A$ (in which case P2 wins).

• So it still holds that every combination of strategies P1 and P2 results in a sequence that makes one of them a winner, but none of the players has a strategy that can defy all the opponents strategies?

Yes, if we have a strategy for P1 and a strategy for P2, and if each player follows their respective strategy, the two strategies combine to spell out a specific play of the entire game, and either P1 or P2 wins that play. But, for the particular set $A_0,$ there's no strategy for P1 that guarantees that P1 always wins, and there's no strategy for P2 that guarantees that P2 always wins.

• This very much reminds me of the destructive LPs and universal LP players from Douglas Hofstadter's book, anyone else?

What is the analogy that you see with Gödel, Escher, Bach? I don't have the book in front of me, but, as I recall, its focus was on phenomena that are self-referential. There are many proofs that AD contradicts AC, but I don't think that self-referentiality is the main underlying feature of any of the proofs. (Depending on the proof that you're looking at, there may be a diagonalization involved — I think that's as close as you'll come.)

• Are there similar applications of AD/AC for single player games?

A single-player game of this sort (with perfect information and no chance element) is trivial, in the sense that there's a simple strategy which guarantees that the player wins or there is a simple strategy which guarantees that the player loses. (In fact, the player can always make the same fixed moves: If there's any play that makes the player win, he can always play that specific way and be guaranteed a win. If not, then any play you want will guarantee a loss.)

Answer 2

It's probably worth pointing out that "the" undetermined game guaranteed by AC, isn't - there are lots of them. Specifically, AC proves that there are as many undetermined games as there are games at all. The converse is also true, btw - there are as many determined games as there are undetermined games.

"$A$ is an undetermined game" means

• Any strategy $\Sigma$ for player I can be beaten by some strategy $\Pi$ for player II, and

• Any strategy $\Pi$ for player II can be beaten by some strategy $\Sigma$ for player I.

It is always true that - given strategies $\Sigma$ and $\Pi$ for players I and II, respectively - the run $\Sigma\otimes \Pi$ is in either $A$ or $A^c$ (this is what complements mean).

I'm not really sure what you're getting at re: one-person games, meanwhile (since I'm not really sure what you mean by those); without opponents, there isn't really a determinacy question to ask. Meanwhile there isn't really a good analogy with Hofstadter's story: the destructive LP is designed after the LP-player is built, so this is really a two-step game, where one player (the destructive LP) has a winning strategy (look at what the LP-player is, and then break it). The analogy would be better if we imagined that the two players built their respective objects simultaneously, and without seeing what the other did - but that's a very different sort of thing than the games we're discussing (which are games of perfect information)! You might look up Blackwell determinacy if that sort of thing interests you.

---

It might be helpful, at this point, to remember how AC proves that there is an undetermined game:

• By AC, we may well-order the set of all strategies for player I as $$Strat(I)=\{\Sigma_\alpha: \alpha<\mathfrak{c}\}$$ (where $\mathfrak{c}$ is the cardinality of the continuum); similarly, we may well-order the set of all strategies for player II as $$Strat(II)=\{\Pi_\alpha: \alpha<\mathfrak{c}\}.$$ This is not the only time AC is used.

• Now we'll define a pair of sequences $In_\alpha, Out_\alpha$ (for $\alpha<\mathfrak{c})$ of sets of infinite sequences of naturals (hereafter "reals") by transfinite recursion as follows:

  • $In_0, Out_0=\emptyset$,

  • $In_\lambda=\bigcup_{\beta<\lambda}In_\beta$, $Out_\lambda=\bigcup_{\beta<\lambda}Out_\beta$ for $\lambda$ limit, and

  • for $\alpha=\beta+1$, we pick reals $r_\alpha$ and $s_\alpha$ not in $In_\beta\cup Out_\beta$ such that

    • There is a strategy $\hat{\Pi}$ for player II such that $\Sigma_\beta\otimes\hat{\Pi}=r_\alpha$, and

    • There is a strategy $\hat{\Sigma}$ for player I such that $\hat{\Sigma}\otimes\Pi_\beta=s_\alpha$;

  • we then let $In_\alpha=In_\beta\cup\{s_\alpha\}, Out_\alpha=Out_\beta\cup\{r_\beta\}$.

The existence of such $r_\alpha, s_\alpha$ is proved by induction: for any strategy, there are continuum-many reals which can arise from plays of that strategy (exercise), but by induction on $\beta$ there are fewer than continuum many reals in $In_\beta\cup Out_\beta$ (exercise). The choice of the specific $r_\alpha, s_\alpha$ is by AC.

Now let $$A=\bigcup_{\alpha<\mathfrak{c}} In_\alpha=\mathbb{N}^\mathbb{N}\setminus \bigcup_{\alpha<\mathfrak{c}}Out_\alpha.$$ For any strategy $\Sigma$ for player I, we have $\Sigma=\Sigma_\alpha$ for some $\alpha$; but then the appropriate $\hat{\Pi}$ defeats $\Sigma$ in the game $A$, since $\Sigma\otimes\hat{\Pi}=r_\alpha\not\in A$. Similarly, any strategy for player II is beaten by some strategy for player I.