11
$\begingroup$

Consider $\mathrm{AD}_X$, determinacy for games where players pick moves from $X$. We know that it is consistent for $X = \omega$ or $\mathbb{R}$ (under large cardinal assumptions), but inconsistent for $X = \omega_1$.

Since this implies determinacy is inconsistent for any set with $\omega_1 \leq X$, this answers the question of consistency for most cardinalities that we might consider (e.g. $\omega_1 \cup \mathbb{R}$, $\mathcal{P}(\mathbb{R})$, all uncountable ordinals). Of course, in the absence of choice other cardinalities might exist. This leads me to the following two questions:

Q1: Is the existence of infinite Dedekind finite sets consistent with $\mathrm{AD}$?

Q2: If so, is 'there exists an infinite Dedekind finite set $X$ such that $\mathrm{AD}_X$ holds' consistent? (Let's call this statement $\mathrm{AD}_\mathrm{DF}$.)

(Note that assuming the consistency of $\mathrm{AD_\mathbb{R}}+\mathrm{DC}$, we have that $\mathrm{AD}_\mathrm{DF}$ can't be a consequence of either $\mathrm{AD}$ or $\mathrm{AD_\mathbb{R}}$.)

Games on infinite Dedekind finite sets seem very strange. For example, consider the game where the first player to play a move that's already been played loses. By Dedekind finiteness somebody has to win this game (and in finite time!), but both players always have not-losing moves at every point. I initially thought this game would be nondetermined, but someone pointed out the following to me:

Let $X$ be infinite Dedekind finite. Then $2 \times X$ is as well. Player 2 has a winning strategy for this game on $2 \times X$: given that an odd number of moves have been played, if nobody has lost yet then there must be some $x \in X$ such that one but not both of $(0, x)$ and $(1, x)$ have been played. Thus we play the other one.

(This means that Player 1 has a winning strategy for this game on $2 \times X \setminus (0, x)$, by pretending they are Player 2 in the game on $2 \times X$ and that the first move was $(0, x)$.)

$\endgroup$
  • 5
    $\begingroup$ Yes, you can add by forcing over $L(\mathbb R) $ a Dedekind finite subset of a set living high above $\Theta $ (thus beyond the "influence" of $\mathsf {AD} $), without adding reals or sets of reals. $\endgroup$ – Andrés E. Caicedo May 7 '17 at 0:11
17
$\begingroup$

The answer is no, you cannot have determinacy for all games on an infinite Dedekind-finite set. Indeed, one cannot even have clopen determinacy for games on such a set. So the answer to question 2 is negative.

Theorem. If $X$ is an infinite Dedekind-finite set, then there is a non-determined clopen game on $X$.

In particular, $\text{AD}_X$ fails, and hence also $\text{AD}_{\text{DF}}$ is false.

Proof. Suppose that $X$ is an infinite Dedekind-finite set. Fix some particular element $a\in X$, and consider the following game. Player I plays distinct elements of $X$, while player II responds with the element $a$, until Player I plays $a$, at which time player II must play an element not yet played. If he can do so, he wins, and otherwise player I wins.

This game must terminate in finitely many moves, because player I cannot play distinct elements forever, as $X$ has no countably infinite subset. So this is a clopen game.

It is clear that player I cannot have a winning strategy, since that strategy would call for her to play some elements of $X$ and eventually the element $a$, during which time all the while player II does something very easy, just playing the element $a$, until player I plays $a$, at which time player II can defeat the strategy by simply playing some new element.

But I claim that also player II cannot have a winning strategy. If there were a winning strategy for player II, then we could use that strategy to generate a countable subset of $X$, since it provides a systematic way to extend any particular finite sequence of distinct elements of $X$. Just have player I play that finite sequence, and then $a$, and player II will respond with a fresh element of $X$. Since $X$ has no countably infinite subsets, there can be no such strategy.

So the game is not determined. QED

This game is related to the classical fact that clopen determinacy implies the axiom of choice, since in the comparatively trivial game, where player I plays a nonempty set from a fixed collection, and player II playing an element of that set (and winning upon doing so), it is clear that the first player cannot have a winning strategy, but a winning strategy for player II provides a choice function.

$\endgroup$
  • 2
    $\begingroup$ +1, a very nice argument $\endgroup$ – Mohammad Golshani May 7 '17 at 3:53
  • $\begingroup$ +1, and note for the OP that this also shows that without some amount of choice, countably closed forcing can add reals! $\endgroup$ – Noah Schweber May 7 '17 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.