Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Without knowing much about the location in the notes, the fact that the AoD implies all sets of real numbers are Lebesgue measurable would be indication that it is incompatible with Choice. – Thomas Andrews Jul 11 '12 at 15:23
(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: – Thomas Andrews Jul 11 '12 at 15:44

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.

share|cite|improve this answer
One can go a bit further. If determinacy holds, then there are no Bernstein sets. It follows that there are no injections of $\omega_1$ into the reals. This is because otherwise either the reals have size $\omega_1$, but then the induction sketched by Asaf gives a Bernstein set, or else the reals have size larger than $\omega_1$, but then any subset of size $\omega_1$ is a set for which the perfect set property fails (as perfect sets have size continuum). – Andrés E. Caicedo Jul 11 '12 at 15:55
@Andres: Yes, however both argument this and Thomas' argument are using further facts about AD, and do not consist of a direct argument referring to games. – Asaf Karagila Jul 11 '12 at 16:50
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. – Andrés E. Caicedo Jul 11 '12 at 23:11

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.