Here, by a Vitali set, I mean the following. Call $f_1,f_2:\omega\rightarrow 2$ tail-equivalent if {$n| f_1(n)\not=f_2(n)$}$<\infty$. Vitali sets (existence via AC) contain one such $f$ from each tail-equivalence class.

Since any Vitali set $V$, as a subset of $2^\omega$, has inner measure 0 and positive outer measure, $V$ gives rise to an indeterminate game roughly of the following sort: Alice must name successive binary digits of a number $v$ in $V$ while Bob names some increasingly very thin open sets $U_i$ hoping that in the end, for some $i$, $v\in U_i$ ("$U_i$ captures $v$").

My question: does any $V$, in itself, define the payoff set of an indeterminate game? (So now, a turn for either Alice or Bob consists of naming the next digit of one common number that Alice, but not Bob, would like to steer into $V$.)

(Easy observation: each tail-equivalence class contains many functions $f$ with $f(1)=0$, and a $V$ containing only these would give Bob a win as early has his first turn, thus making the game trivially determinate. So one can't expect all such $V$ to define indeterminate games. But how about all dense Vitali sets?)


It is a very nice question.

I claim that there is a non-determined dense Vitali set $A$, by a modification of the usual construction of a non-determined set.

First, enumerate all the possible strategies for Alice or Bob in a well-ordered sequence $\langle\sigma_\alpha\mid\alpha\lt\frak{c}\rangle$ of length continuum. A strategy is simply a function mapping the finite play so far to the next digit to be played, and there are at most continuum many such functions. Let us adopt the usual notation, by which $x\star\sigma$ means the play resulting from having Alice play the sequence $x$ and Bob play according to the strategy $\sigma$, and similarly for $\sigma\star y$, where Alice plays $\sigma$ and Bob plays $y$.

Next, in a transfinite recursive procedure, we will make promises about certain sequences being definitely in the payoff set $A$ and other promises about certain sequences being definitely not in $A$.

At stage $\alpha$, let $A_\alpha$ be the set of sequences that we have promised definitely to be in the payoff set $A$, and $B_\alpha$ is the set of sequences that we have promised to be out of $A$. These will be disjoint sets of size $|\alpha|$, which is less than the continuum. Consider now the strategy $\sigma_\alpha$, treating it first as a strategy for Bob. Let $x$ be a play for Alice that does not agree on a tail with Alice's play in any sequence of $A_\alpha\cup B_\alpha$. Such an $x$ exists because the sets are small and there are continuum many possible plays. Let us place $x*\sigma_\alpha$ into $A$, that is, $A_{\alpha+1}=A_\alpha\cup\{x*\sigma_\alpha\}$. This defeats $\sigma_\alpha$ as a winning strategy for Bob. Next, consider $\sigma_\alpha$ as a strategy for Alice. Let $y$ be a sequence that does not agree on a tail with any play by Bob for any sequence used up to this stage, that is, in $A_{\alpha+1}\cup B_\alpha$. We place $\sigma_\alpha\star y$ into $B$, meaning $B_{\alpha+1}=B_\alpha\cup\{\sigma_\alpha\star y\}$. This defeats $\sigma_\alpha$ as a winning strategy for Alice.

Having completed the recursion, let $A=\bigcup_\alpha A_\alpha$, and $B=\bigcup_\alpha B_\alpha$ be the resulting sets of size continuum. By construction, $A$ and $B$ are disjoint, and no two elements of $A\bigcup B$ contain sequences that have only finite difference, since every time we added a new sequence either to $A$ or to $B$, it was infinitely different from all the earlier sequences we added. Thus, $A\cup B$ contains at most one element from each tail equivalence class. The usual argument is completed here, since $A$ is not determined, as every strategy was defeated with respect to it.

But in order to get the full Vitali property, we do a bit more. By Zorn's lemma, we may extend $A\subset V$ to a maximal such set disjoint from $B$. That is, $V$ contains $A$, is disjoint from $B$ and no two elements agree on a tail. It follows by maximality that $V$ is a Vitali set. Furthermore, like $A$, the set $V$ is not determined, since by design, any given strategy $\sigma_\alpha$ has a specific play, chosen at stage $\alpha$, which defeats it as winning for either Alice or Bob.

Finally, we can easily arrange that $V$ is dense, by modifying the construction to start with a fixed countable dense set $A_0$ containing tail-inequivalent sequences.

So this is a dense non-determined Vitali set, as desired.

| cite | improve this answer | |

To answer the last (parenthetical) piece of the question, which Joel seems to have ignored: Density doesn't help; a dense Vitali set $V$ can still have an easy winning strategy for Bob. The point is that, if $C$ is a tail-equivalence class and $B$ is any basic open set (the set of all $f\in 2^\omega$ that extend a particular finite sequence $b$), then there is an element $f\in C\cap B$ for which the odd-numbered terms $f(2n+1)$ ("Bob's moves") are not all zero --- just define $f$ to agree with $b$ where $b$ is defined, to have a 1 in some later odd-numbered position, and thereafter to behave in a way that puts it into $C$. Now associate, arbitrarily, to each basic open set $B$, one tail-equivalence class $C_B$. For each of these, pick one $f\in C_B\cap B$ as above; for all the other tail-equivalence classes (those not associated to any $B$) pick any $f\in C$ whose odd-numbered terms are not all zero. Then the chosen $f$'s constitute a dense Vitali set, for which Bob has the winning strategy "always play 0".

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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