# Is determinacy on an infinite Dedekind finite set consistent?

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)$$.)

• 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. May 7, 2017 at 0:11
• The strategy you give for player II in the game on $2\times X$ seems to require a choice. ("there must be some..." - but what if there is more than one?) But the following simpler description uses no choice and gives the same strategy (which could be called a "tactic", as no memory is needed): Whenever player I plays $(a,x)$, respond with $(1-a,x)$. Nov 14, 2022 at 16:20

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.

• +1, a very nice argument May 7, 2017 at 3:53
• +1, and note for the OP that this also shows that without some amount of choice, countably closed forcing can add reals! May 7, 2017 at 16:31