The Strong Measure Zero Game


Originally, my first post was going to be an introduction to selection principles, especially those in topology, and a few other related concepts. I decided I could not do justice to the subject in one post (especially with my minimal knowledge), and have opted to present some very cool results that will, hopefully, give a taste of the ideas that come up when studying the subject.

Definition of the game . Let and be collections of sets, we define the game to be a game with two players, that we will denote and , and the game will have innings, where each inning consists of a turn by and then a turn by . By innings we mean there is an inning for each (if you prefer ). The innings follow this pattern: player starts off, in inning , by presenting a nonempty set from which marks the end of player ’s turn, and then player picks an . At the end of the innings we are left with a play

of what happened in that game. Player wins if and wins otherwise.

A couple of examples to consider:

  • Let consist of all dense subsets of . Consider .
  • Let be a countable subset of some topological space and is the set of all open covers of , and the set of covers for . Consider .
  • is a finite dimensional rational vector space, and is the set of infinite vector subspaces of , and is the set of sets that contain infinite rational vector subspaces of . Consider
  • Let be an ultrafilter on some set. Consider .
  • Let be a group and the set of subsets of that normally generate the group. Consider . There are also variation of considering sets that generate the group , and looking at , , (there is a very good chance I am going to write about this bullet point, and related ideas, in future posts, since it is basically the reason I started the blog).
  • etc. Think of some others!

A strategy for a player is a function that takes what has been played and outputs the next move. So will be strategies for players respectively, and , and . We get a similar description for . Basically they are instructions on a game tree that tell the player what to do next given where they are in the game tree. We call a winning strategy provided the cooresponding player will always win following that strategy. It is interesting that in some games there is no winning strategy for either player, and in fact the two main theorems that will be presented will give such an example(assuming Borel’s conjecture is false)

Do any of the above (bulleted)examples have winning strategies for one of the players? How about the games you came up with?

Definition of strong measure zero. A set is strong measure zero if, for all sequences of positive real numbers, then there exists a sequence of intervals , where the length of is less than for all , and .

Every strong measure zero set is Lebesgue measure zero, although not every measure zero set is strong measure zero, the Cantor set provides such an example. It is also easy to see that every countable set is strong measure zero. In fact Borel’s conjecture actually conjectures that every strong measure zero set is countable. That conjecture ended up being independent of the usual axioms, ZFC, so it is consistent for there to be uncountable strong measure zero sets, and consistent for there to be only countable strong measure zero sets. Luzin sets provide examples of strong measure zero sets that are not countable.

Let , , be the set of all intervals of length less than , and say , and the set of open covers of some set (where the open sets come from and not with the subspace topology).

Definition of the strong measure zero game. Let . Then the strong measure zero game is the game .

There are a couple of other definitions I could have chosen, but I want to stress that the game has a very strong connection to strong measure zero, since player can choose a sequence of and play , in inning , and then tries to cover by collecting one interval from each .

A very natural question to ask is when does player have a winning strategy, and when does player have a winning strategy in ? This brings us to “the main event”:

Theorem 1. Player has a winning strategy in the strong measure zero game, if, and only if, is countable.

Theorem 2. Player has a winning strategy in the strong measure zero game, if, and only if, is not strong measure zero.

One of the things that makes these results interesting is that this means it is consistent for winning strategies to always exist, that is when all strong measure zero sets are countable, and it is consistent for there to be sets where there is no winning strategy, which is when there are uncountable strong measure zero sets(as an example the Luzin sets mentioned before).

The Proofs of Theorem 1 and 2

The proofs of Theorem 1 and 2, that will be presented, is Galvin’s with some modification and can be found in his paper Indeterminacy of point-open games. I found out about this proof in a class, taught by Marion Scheepers, a few years ago.

First, some notation, will be the set of infinite sequences of order type , will be the set of finite sequences indexed by finite ordinals. And if are sequences, then will be the concatenation of the sequences. As examples


Lemma 3. Let be a set and suppose that for each we have that a set , which is a set of positive integer, finite length, sequences such that:

  1. For every infinite sequence there is a such that .
  2. For each finite sequence ,

then we have that ( is countable).

proof of Lemma 3. We will prove by contradiction, so suppose that is an uncountable set with the above properties. This means that

since the part that is being removed from is countable. Let be an element from this nonempty set. By the definition of the above set, we know that has the property, that for any sequence , that there is an such that . Starting with the empty sequence, , we know there is a least such that , and we can continue doing this inductively, constructing sequences of length . This contradicts property 1.

Theorem 1. Player has a winning strategy in the strong measure zero game, if, and only if, is countable.

proof of Theorem 1. It is easy to see that has a winning strategy, when is countable, since we can enumerate the set , and in turn , covers the -th element. For the other direction, we will need to define a different game. Let be a separable metric space, so it also has a countable basis. (Separable means contains a countable dense set subset.) The game has these rules:

  1. There is an inning for each .
  2. In inning player chooses a set , where is open and the distance between and is positive, where distance between the two sets is defined to be . We will call such pairs playable
  3. Player chooses one of the sets, which we will call .
  4. Player wins if .

Lets call this game , or the disjoint open ball game on . We will now show that when has a winning strategy for then the set is countably infinite. Let be a winning strategy for . Note that we may assume that only plays from sets from a basis, and since we have a countably basis, we may assume that plays from some countable basis. Let where is an enumeration of all playable , where are from our chosen countable basis. For we define

Given that is a winning strategy for , we can see that for any and sequence that some segment , since otherwise for all , so contradicting that set being empty. Hence we have condition 1, from Lemma 3. We will now show condition 2 of Lemma 3. Suppose that we have distinct

for . We can choose playable pairs

where the index on the open sets says that it contains but not the where , since we are in a metric space. And note that only one of the can be in , hence other two, , are not contained in that set. This is true for each combination, so we have

So we get that , and by shuffling things around, we get that each of the three points, , have cooresponding sets that they are not in, hence they are not in the intersection of all those sets. This worked for an arbitrary choice of three points, so it must be

Using Lemma 3, we get that the space is countable.

Let be a winning strategy for in the strong measure zero game on . We are going to show that the strategy will help us construct a winning strategy in the game , hence will be countable.

Say that player plays in , and plays in the strong measure zero game. We will have player play , and then will be an element disjoint from , which we can pick since the length of is less than . So we can define a strategy where if and otherwise. We will now show that this is in fact a winning strategy. Note that

but the union part covers the whole space so the intersection on the left must be empty. So player has a winning strategy for when has a winning strategy for the strong measure zero game. Thus is countable.

Lemma 4 (Lebesgue covering lemma). If is a compact metric space, then for any open cover of , there exists a postive real number , the Lebesgue number, such that: for any of diameter less than there is a in the open cover such that .

proof of Lemma 4. This is a well known theorem, so no proof will be given.

Theorem 2. Player has a winning strategy in the strong measure zero game, if, and only if, is not strong measure zero.

proof of Theorem 2. First we will prove (), so suppose that is not strong measure zero. Hence there is a sequence for such that, such that for all sequences of intervals , for , length of is less than or equal too . So have player plays in inning , so player can not cover the space, since it will only pick intervals less than at inning .

We will now prove (), we will do the contrapositive, so we will show that if is strong measure zero then does not have a winning strategy. Let be an arbitrary strategy for player , and is strong measure zero. We will show that there is a play, by player that will beat this strategy. Here are some things that we are going to assume, to make the problem a bit easier:

  1. That we are playing on strong measure zero sets, that are subsets of compact sets, and in fact we will assume to be working with . This is enough since we can write as a countable union of compact sets, for example , and partition the innings, into countably infinite many infinite sets (think of sets of the form , prime ), so we play the strong measure zero game on the th compact set when the inning we are in is in the th partition.
  2. We will assume that the ’s that are played by player have ’s of the form , since for some we can just move to a smaller number of the form without losing any generality.
  3. Let be some sequence of turns, that is in the domain of player ’s strategy , then we define .

We will now construct a play in which which beats player strategy . Say that . Lets say is a finte open cover of (which exists since is compact). Consider , and we will choose large enough so that:

  1. ,
  2. ,
  3. and is a Lebesgue number of the cover .

Basically we are going to go down, and play every possible outcome of the strategy possible. Let , be a finite open cover, so in particular this works as a subcover for for since . Then we are going to choose an large enough so that:

  1. (this also means that for , which are the corresponding “n_i” terms ),
  2. ,
  3. And is a Lebesgue number of the cover .

Basically we continue in this fashion, and construct , for arbitrary (which if that statement was good enough for you, I recommend skipping this paragraph). Suppose that we have constructed. Then we are going to construct by letting be a finite open cover. Then we choose large enough such that:

  1. ,
  2. ,
  3. And is a Lebesgue number of the cover .

So know we have a sequence , where each is a Lebesgue number of the coverings . Since is strong measure zero we have that there is a covering where each has length less than . Since is a Lebesgue number of the cooresponding coverings, we can find an such that . We can choose the as our sets, and so we found a play where wins, hence is not a winning strategy, and since was arbitrary we are done.


You can find out more about these sorts of things from this, non-exhaustive, list:

  • F. Galvin, Indeterminacy of point-open games, Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys. 26 :5 (1978), 445–449 (this is sort of difficult to find, so included all the information, for libraries)
  • “The combinatorics of open covers (I): Ramsey theory” by Marion Scheepers,
  • “The combinatorics of open covers (II)” by Winfried Just, Arnold W. Miller, Marion Scheepers, and Paul J. Szeptycki,
  • “The combinatorics of open covers ()” by … (well there are at least 11 of these…),
  • “Ramsey theory of open covers lecture 1” by Nadav Samet and Boaz Tsaban,
  • “Ramsey theory of open covers lecture 5” by Nadav Samet and Boaz Tsaban.
  • You can browse around here

The “Ramsey theory of open covers” are more accessible and shorter than “The combinatorics of open covers…” and discuss some of the Ramsey theoretic aspects that are related to these games and to “selection principles” (which I did not discuss here, although are very related to games ).