8
$\begingroup$

Hello, all,

Several months ago I sat in on a seminar on AD+, which was incredibly wonderful even though I could barely follow it at all. AD+ is a technical variant of AD, the axiom of determinacy, which asserts that $$ \text{For all countable } X, A\subseteq X^\omega, \text{ the game with payoff set A is determined.}$$ It is easy to show that $ZFC+AD$ is contradictory; however, assuming some large cardinals, $ZF+AD$ is consistent, and in fact has the natural model $L(\mathbb{R})$.

One of the results mentioned was the fact that a natural strengthening of AD, in which $\omega$ is replaced by an arbitrary ordinal, is inconsistent with ZF (even though assuming large cardinals, many classes of long games are determined; this I gleaned from the amazon.com preview of Itay Neeman's "Determinacy of Long Games," which I suspect has the answers to my questions, but I don't have access to it). Having lost my notes from the seminar, I have two questions:

1) What is the proof of this fact?

2) When/by whom was it proved?

Thanks to all in advance!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
14
$\begingroup$

Your statement of AD is incorrect. $X$ should be at most $\omega$ (and at least 2), not an arbitrary set. Specifically, for $X=\aleph_1$, determinacy of games in $X^\omega$ is inconsistent with ZF.

Concerning your actual question, determinacy of games of length $\omega_1$, even with $X=2$, is inconsistent. I believe that this result and the one in the first paragraph of my answer are in Mycielski's first big paper on AD, "On the axiom of determinateness" in Fundamenta Mathematicae 1963 or 1964. For the proof, fix a coding of the well-orderings of $\omega$ as $\omega$-sequences of 0's and 1's, and consider the following game of length $\omega_1$. Player I must, at one of his moves, play 1 (if he always plays 0, he loses). As soon as he plays a 1, say at move $\alpha$, player II must, in his next $\omega$ moves, play a code for a well-ordering of $\omega$ of length $\alpha$. Clearly, player I cannot have a winning strategy, since every $\alpha$ has a code. Determinacy of this game would mean that player II has a winning strategy, but that would give a function assigning to each countable ordinal $\alpha$ one of its codes. The existence of such a function (or of any set of reals of size $\aleph_1$) contradicts AD (which is, of course, a consequence of length-$\omega_1$ determinacy).

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ The result about $\omega$-length games on $\aleph_1$ in the first paragraph of my answer has a very similar proof. Consider the game where player I must, on his first move, name a countable ordinal $\alpha$ and player II must then, on his remaining $\omega$ moves, play a code for $\alpha$. Again, player I can't have a winning strategy, and a winning strategy for II gives a function assigning to each countable ordinal one of its codes, contrary to AD. $\endgroup$
    – Andreas Blass
    Commented Jun 21, 2012 at 1:38
  • 1
    $\begingroup$ Good point about the statement of AD - I fixed it. I even knew that wasn't the right statement, and still managed to write it down . . . $\endgroup$
    – Noah Schweber
    Commented Jun 21, 2012 at 1:48
  • 1
    $\begingroup$ Re: your answer, this looks great. Thanks a ton! And thanks as well for the helpful comment. $\endgroup$
    – Noah Schweber
    Commented Jun 21, 2012 at 1:50

You must log in to answer this question.

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