MathOverflow is a question and answer site for professional mathematicians. 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 assuming someone must have scooped me on this simple argument. Where does it (first) appear in the literature?

Fix an ultrafilter $\mu$ on $\omega$, the natural numbers.

Alice and Bob play a nim-like game. At the start each player "holds" the empty set and the the starting "position" consists of $\omega$. Beginning with Alice, each player in turn will remove a non-empty finite initial segment from the current position (leaving some final segment of $\omega$) and deposit the removed segment into his or her holdings. Play proceeds for $\omega$ rounds.

Now the object of the game: to finish with holdings that belong to the ultrafilter $\mu$.

Strategy stealing obviates the possibility of either player possessing a winning strategy; the existence of $\mu$ thus contradicts AD. In more detail, if either player has a winning strategy, the game must admit infinitely many winning positions, but that would allow the other player to possibility of moving to a winning position on his or her very first move.

Many sources work much harder than this to prove the weaker results that AC contradicts AD. (Afterthought: I'd love to see a big-list question collecting theorems where unnecessarily complicated proofs permeate the literature despite the availability of simpler treatments...MO appropriate?)

share|cite|improve this question
The big-list question sounds interesting. – Andrés E. Caicedo Dec 17 '10 at 7:19
The big-list question seems okay, although maybe you should ask on meta to be sure. – Qiaochu Yuan Dec 17 '10 at 9:23

Hi David. Although your presentation is nice (I don't recall having seen the argument explicitly stated as a "nim-like game"), this proof is essentially the standard one; see Kanamori "The higher infinite", Proposition 28.1.

Kanamori calls it "an early observation about ultrafilters", so perhaps it is folklore. It seems the natural approach if one is familiar with the argument that a non-principal ultrafilter allows us to build a non-Lebesgue measurable set, using Sierpinski's original argument from 1938. It wouldn't surprise me if the argument already appears in the 1962 paper by Mycielski and Steinhaus where determinacy is introduced (but I do not have access to the paper currently, so I cannot confirm this).

share|cite|improve this answer
This result is typically used as follows: Any non-principal ultrafilter on a set $X$ is countably complete. Else, we can easily produce from it a non-principal ultrafilter on $\omega$. – Andrés E. Caicedo Dec 17 '10 at 7:23

I "discovered" this argument while I was a grad student (probably in 1969), but, alas, it was already known to Gene Kleinberg (if I remember correctly). My first guess for the original discoverer would be Fred Galvin; my second guess would be folklore.

share|cite|improve this answer
This is interesting! I think the result only becomes significant once we know there are non-principal ultrafilters (because then it automatically gives us measurable cardinals), but is is nice to confirm that people already knew of it by then. – Andrés E. Caicedo Dec 17 '10 at 20:49

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.