4
$\begingroup$

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.

  • 1
    (Addendum: Since choice is used to prove the existence of sets of reals which are not Lebesgue measurable.) The Wikipedia page for the AofD also has an outline of a proof of the incompatibility: http://en.wikipedia.org/wiki/Axiom_of_determinacy2012-07-11

2 Answers 2

3

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.

  • 0
    There is a direct game argument that proves the perfect set property. But yes, the expected answer is that you can use the well-ordering of $\mathbb R$ to diagonalize against all strategies.2012-07-11
0

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.