An ultrafilter game

The following post is inspired by a cute game-theoretic result about ultrafilters in the slides (PDF) from a talk by Andreas Blass.

Let's start with a bit of finite game theory. Suppose G is a two-player, deterministic, zero-sum, sequential, finite game with perfect information (e.g., Go played by two omniscient beings). Then either player I has an winning strategy or player II has a winning strategy. The (informal) proof of this is simple. Player I can either force player II into an unwinnable position, or he can't. If he can, player I has a winning strategy, by definition. If he can't, then player II has a winning strategy: avoid unwinnable positions. When the game ends after finitely many moves, player II wins, by definition.

Venturing further into the lofty mountains of abstraction, let us allow the number of turns to be infinite. Here's a simple infinite game. Suppose A is a collection of sets of whole numbers. For concreteness, let A be the collection of all sets containing infinitely many odd numbers. The game G(A) is played as follows. Players I and II take turns choosing finitely many whole numbers. (Choosing no numbers on a turn is allowed.) Once a number is chosen, it can never be chosen again by either player. After infinitely many moves, player I has chosen a possibly infinite set X of numbers, and player II has chosen a possibly infinite set Y of numbers not in X. If X is in the collection A, then player I wins. Otherwise, player II wins.

Player I has a simple winning strategy for G(A): just pick the least odd number that hasn't already been picked. Let's try G(B) where B is the collection of all sets containing at least twenty primes. Again, player I can always win: he can pick twenty primes on his first move. Well, what about G(C), where C is the collection of all sets that contain all but finitely many of the even numbers? Player II can always win by always picking the least even number available.

So, is every infinite game of this form is determined, meaning either player I of player II has a winning strategy? The answer depends on your axioms of set theory. The mainstream answer of mathematicians is "no, because of the axiom of choice." (This is my answer, too.) However, the axiom of choice has counterintuitive consequences. Moreover, a beautiful theory has been built up from the axiom of determinacy, which asserts that the answer to our game-theoretic question is "yes."

A particularly interesting consequence of the axiom of choice is that there exist wonderful objects called free ultrafilters. A free ultrafilter (on the whole numbers) is a collection U of sets of whole numbers with the following properties.

• Every set in U is infinite.
• If X and Y are in U, then their intersection is in U.
• For every set of numbers X, either X is in U, or the set of numbers not in X is in U.

(I omitted the traditionally included property that if X is in U and X is a subset of Y, then Y is in U. This property follows from the above listed properties, and it is not relevant to this blog post.)

It follows from these properties that the set of all whole numbers is in U. Also, if two sets are disjoint (e.g., the multiples of 4 and the primes), then they can't both be in U. Moreover, for any element X of U, and any partition of X into two pieces Y and Z, one of Y and Z must be in U, and the other must not be in U. Because such partitions can be arbitrarily complex, it takes an infinite (in fact, uncountably infinite) sequence of choices to "build" an ultrafilter. The axiom of choice says such sequences exist, even though we might not be able to specify any particular such sequence with a finite number of words/symbols.

Now, let's analyze the game G(U). It turns out neither player has a winning strategy. For the sake of argument, suppose player I has a winning strategy---call it S. The trouble is that the game G(U) has enough symmetry that if player I can use S, then player II can use it too. Suppose player I follows S, and that F is the set of numbers he picks on his first turn. Now suppose player II pretends that she's player I following S and that her opponent chose nothing after she chose F. Let X be the set of numbers chosen by player I and Y be the set of numbers chosen by player II. Then X is in U because S always wins. But the union of Y and F is also in U because S always wins. Therefore, the intersection of these two sets, which is F, is in U. This is impossible because all members of U are infinite. Therefore, player I does not have a winning strategy.

Does player II have a winning strategy? Suppose she did, and let T be such a strategy. Let's modify T a little bit, producing another winning strategy T'. The idea behind T' is that choosing more numbers on her turn can't hurt player II; it will just make things harder for player I. Let's be more precise. On every turn, T' says to choose the numbers T says to choose, along with the least number not already chosen by either player. Technically, this will only work on player II's first turn, because on player II's second turn, T could say, "sorry, you didn't follow my advice last turn." But there's an easy work-around. Ask T, "what would you advise in the situation where that extra number you didn't want me to choose were chosen on player I's last turn, in addition to what he actually chose?" In general, T' says to do what T would say to do if each extra number previously chosen by player II were chosen on player I's last turn, in addition to what player I actually chose. Then T' says to also choose the least number not already chosen. Now we can see that T' is a winning strategy. If player I could beat T', then he could also beat T by additionally choosing the appropriate extra number on each turn. But player I can't beat T, so player I can't beat T' either.

Now suppose player II follows T'. Further suppose player I pretends that he's player II following T' and that his opponent chose nothing on her first turn. Again let X be the set of numbers chosen by player I and Y be the set of numbers chosen by player II. Then neither X nor Y is in U because T' always wins. But, because of how we constructed T', every number is eventually chosen by player I or player II. Therefore, Y is the set of all numbers not in X. This is impossible, for it implies either X or Y is in U. Therefore, player II has no winning strategy.