5
$\begingroup$

I am reading Kechris' descriptive set theory text book, and there is this Theorem regarding infinite games:

Gale-Stewart: Let $T$ be a non-empty pruned tree on $A$. Let $X\subset[T]$ be closed or open. Then $G(T,X)$ is determined.

There is this exercise: show that AC is equivalent to Gale-Stewart Theorem.

Assuming the exercise is true, if we consider the statement:

$\blacksquare$ Every infinite game is determined.

Then the statement $\blacksquare$ implies Gale-Stewart Theorem, which implies AC, which implies the negation of $\blacksquare$.

Does this mean ZF$+\blacksquare$ is inconsistent? Can we conclude that we can find a non-determined infinite game without using AC? If so, do you have any example in your mind?

Thanks!

$\endgroup$
2
  • $\begingroup$ What is $A$ in this context? $\endgroup$
    – Asaf Karagila
    Commented Oct 17, 2022 at 21:06
  • $\begingroup$ $A$ is a non-empty set. I meant to have $T\subset A^{<\mathbb{N}}$, a non-empty pruned tree. $\endgroup$ Commented Oct 17, 2022 at 21:37

1 Answer 1

6
$\begingroup$

Your reasoning is correct: $\mathsf{ZF}$ proves $\lnot \blacksquare$.

Note that $\blacksquare$ is not $\mathsf{AD}$, the Axiom of Determinacy. $\mathsf{AD}$ states that every Gale-Stewart game on $\omega^\omega$ is determined, which is much weaker than $\blacksquare$.

It is possible to prove in $\mathsf{ZF}$ alone that there is a game on $\omega_1^\omega$ which is undetermined ($\omega_1$ is the first uncountable ordinal). A reference is Theorem 10.2 in Games with perfect information by Mycielski, Chapter 3 in Handbook of Game Theory with Economic Applications, 1992, vol. 1, pp 41-70 (link).

For a more explicit example of an undetermined game in $\mathsf{ZF}$, see the answer here by Joel David Hamkins.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .