Skip to main content
1 of 4
Joel David Hamkins
  • 236.4k
  • 44
  • 777
  • 1.4k

Here is an amusing concrete non-determined game, under the assumption that the dependent choice principle fails.

Assume DC fails. This means that there is a set $X$ and a binary relation $R$ on $X$, such for every $x\in X$ there is $y$ with $x\mathrel{R} y$, but there is no sequence $\langle x_n\mid n\in\omega\rangle$ with $x_n\mathrel{R} x_{n+1}$ for all $n$. In other words, the tree of finite sequences that accord with $R$ has no leaves — every node can be extended one more step — but there is no way to iterate these steps and the tree has no infinite branch.

Consider the game on $X$ where player I plays a point $a$ from $X$ and player II responds with $b$, and player II wins just in case $a\mathrel{R} b$; otherwise player I wins. So the game is over very quickly, after just one move for each player. (If you insist that games should have infinitely many plays, then you can continue with infinitely many irrelevant moves.)

Player I obviously cannot have a winning strategy, since whatever point $a$ is played, there is a way for II to defeat it by playing some $b$ with $a\mathrel{R} b$.

But player II also cannot have a winning strategy, since any such strategy would provide a choice function on the $R$-successors of the points in $X$, and any such function could be iterated to thread $R$, whereas there is no such infinite thread.

Since the game is an open game (in fact clopen), this argument shows that one cannot prove open determinacy without DC. The usual proof of open determinacy uses DC, when showing that if a position does not have an ordinal rank, then the closed player can avoid losing by maintaining rank. But in order to do so, that player needs DC to find the infinite thread of rank-maintaining moves.

Joel David Hamkins
  • 236.4k
  • 44
  • 777
  • 1.4k