Proof of Incompatibility of Axioms of Determinacy and Choice

Question

I'm working through some lecture notes on the axiom of determinacy, and have run into some trouble with the proof of the incompatibility of the axiom of determinacy with the axiom of choice. Specifically, the theorem takes the following form,

Assume that $\omega^\omega$ can be well ordered. There is a set $A\subseteq\omega^\omega$ which is not determined.

The proof in the notes is a bit confusing, and I can't quite follow it, although I do get the basic idea that we use a diagonal argument by recursively defining a set for which there can be no winning strategy. Could anybody either post a proof or direct me to one?

Thanks in advance. Ben.

Answer 1

If you are familiar with Bernstein's proof of a set without the perfect set property, then principle is essentially the same.

First we prove that there are only continuum many strategies. This is simply because a strategy is essentially a function from a countable tree into $\omega^\omega$.

Next we enumerate these strategies, and by induction ensure that all the strategies fail. At the $\alpha$ step we choose a sequence guaranteeing that neither the player can win with its $\alpha$-th strategy.

The result is therefore a game which cannot be won.

Answer 2

I don't know what notes you are using, but a good supplemental source, which happens to include a proof of this theorem, is these notes from a UCLA Logic Summer School course that talked about Determinacy and Set Theory.