Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Assume AC. Suppose $X$ is a subset of the irrationals (Baire Space) for which neither player has a winning strategy (i.e. the game $G(\omega, X)$ is not determined). Is $X$ non-measurable in the Lebesgue sense as a subset of $\mathbb{R}$?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

(My argument is somewhat easier if you consider games where the players play $0$s and $1$s, so that the payoff set is in Cantor space $2^\omega$, and we use the usual coin-flipping probability measure; but an essentially similar idea works in Baire space.)

For any game with payoff set $A$, where player I wins if the play is in $A$, consider the following slightly modified game $A^\ast$, which is just like $A$, except we insert a pair of dummy moves between each pair of actual moves, and insist that player I play a $0$ in this dummy round, while player II can play anything. Thus, a sequence or play is in the payoff set $A^\ast$ if indeed that sequence shows that player I did play a $0$ in all the dummy rounds (so every fourth digit is $0$), and furthermore, if we omit the dummy rounds entirely from the sequence, we get a sequence in $A$.

Thus, playing the game $A^*$ is just like playing $A$, except that the play is interrupted for these silly dummy rounds. Note that player I has no incentive not to play a $0$ on those rounds, and player II's plays in the dummy rounds are ignored entirely.

Thus, it is clear that a player has a winning strategy for $A$ if and only if he or she has a winning strategy for $A^\ast$, since we can translate the strategies from $A$ to $A^\ast$ and back again. The dummy rounds really don't change the difficulty of winning the game.

But the point now is that because every fourth digit of $A^\ast$ is $0$, it follows that $A^\ast$ has measure $0$. (Every time you insist that a particular digit is $0$, it cuts the measure in half again.)

The conclusion, therefore, which does not use the axiom of choice, is that if there is a non-determined set, then there is a non-determined set with measure $0$. In particular, there is a non-determined set that is measurable.

share|improve this answer
I'm not convinced... Cantor Space is homeomorphic to the Cantor Set which has measure zero... Thus any payoff set in it will have measure zero when considered as a subset of $\mathbb{R}$ by virtue of being a subset of the Cantor Set... I'm not convinced that your argument about halving the measure carries through to non-measurable sets... further my guess (I should probably ask this as a question) is that the existence of a non-determined game in Cantor Space is stronger than AC... –  George Lazou Jun 9 '11 at 23:51
I am not using the Cantor set as a subset of $\mathbb{R}$ and the Lebesgue measure on that, but rather, using the natural probability measure on $2^\omega$, for which $2^\omega$ is the whole space and has measure $1$; the measure of the basic open set determined by a finite binary sequence of length $n$ has measure $\frac{1}{2^n}$, like flipping a coin. A subset of $2^\omega$ which is $0$ in every fourth digit has measure $0$ (an easy calculation). The same idea works in Baire space, but you seem to be mapping spaces by homeomorphisms that may not be measure-preserving... –  Joel David Hamkins Jun 10 '11 at 0:24
As for your final question, I think you mean to ask whether the existence of a non-determined game is weaker than AC, rather than stronger, since ZFC proves the existence of such non-determined games for Cantor space in exactly the same way that it does for Baire space. I don't expect the existence of such a non-determined set to imply full AC, but I'd have to think a bit more to give a precise model showing this. If this is right, then the existence of non-determined sets would be a weak choice principle. –  Joel David Hamkins Jun 10 '11 at 0:29
But I would encourage you to ask that as a question, since perhaps someone knows a good model, and I would be interested to see it. –  Joel David Hamkins Jun 10 '11 at 2:16
There is an old beautiful argument of Sierpinski that shows that the axiom of choice for PAIRS $AC_2$ implies the existence of a nonmeasurable set; which in turn shows that $AD$ fails as soon as $AC_2$ is true. So a model in which $AC$ fails but $AC_2$ holds is yet another way of seeing that the negation of $AD$ does not imply $AC$. Cohen's so-called "first (symmetric) model" in which $AC$ fails is such a model (since every set has can be linearly ordered in that model, but the reals cannot be well-ordered there). –  Ali Enayat Jun 10 '11 at 19:14
show 3 more comments

I have two possible answers. The first is short and possibly not the one you want. The second is probably the right one.

First: take any (co)analytic subset $X$ of the Baire space $\omega^{\omega}$, which is not Borel. Than it is consistent with ZFC that the game $G(\omega,X)$ is not determined (ZFC just proves the determinacy of Borel games), but $X$ is Lebesgue-measurable (in fact universally measurable).

I guess this is a consistent proof of "no", to your question.

Second Assume AC. Then there exists a universally-null set (hence Lebesgue null, since the Lebesgue measure is atomless) $X$ of cardinality $\geq\aleph_{1}$. Then one can show that such a set $X$ can not be a Perfect set. Now let us consider the so-called Perfect-set game $PSG(\omega, X)$, which is technically a Gale -Stewart game $G(\omega, Y)$, with $Y$ of about the same complexity of $X$ (in particular $Y$ is universally-null non-perfect set of cardinality $\geq\aleph_{1}$). This game is not determined since $Y$ is not Perfect nor countable by construction, and it is knonw that such a game is determined only if $Y$ is Perfect or countable. Yet $Y$ is universally null, hence Lebesgue measurable.

This second example is mentioned in Martin's "Blackwell's determinacy", where it is credited to Greg Hjorth.

This is a proof in ZFC of "no", to your quesiton.

share|improve this answer
add comment

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.