Boolean Prime Ideal Theorem versus the Axiom of Determinacy

Question

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?)

Answer 1

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).

Answer 2

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.