game of 2 players on an ultrafilter $\cal U$ on $\omega$ in which neither player has a winning strategy

54 Views Asked by At

There is a game of 2 players (I and II) with an ultrafilter $\cal U$ on $\omega$ such that neither player has a winning strategy. I would like to understand in this game where in which part of the solution of example $9.$ it is used that $\cal U$ is non-principal.

enter image description here

enter image description here

1

There are 1 best solutions below

2
On BEST ANSWER

When they say "$[0,n_1)\cup [n_2,n_3)\cup\ldots$ does not belong to $\mathcal U$," hence the set "$[0,n_0)\cup[n_1,n_2)\cup\ldots$" must belong to $\mathcal U$." Those sets aren't complements of each other! Particularly, if $\mathcal U$ is a principal ultrafilter generated by a number in $[n_0,n_1),$ then it doesn't work. Nonprincipal-ness allows us to ignore the segment $[n_0,n_1)$ since it's finite.

More concretely, if the ultrafilter is the principal ultrafilter generated by $100,$ and player 1 sets $n_0=1,$ player 2 could set $n_1=101$ and win. Of course player 1 could prevent this by picking $n_0=101$ instead and winning.

So the proof could be modified to show that player 2 has no winning strategy regardless of whether the ultrafilter is principal. Of course, when you do the similar proof that player 1 has no winning strategy, you will see that it is unavoidable to assume the ultrafilter is nonprincipal.


The game and proof are easier to think about this way:

There is a queue of all the natural numbers, and we each take turns popping an arbitrary finite number off and taking them. After $\omega$ rounds, we've exhausted the naturals and whoever's subset lands in the ultrafilter wins.

Nonprinicipal-ness implies any finite amount of stuff that has happened so far is irrelevant to who wins... only the tail of the game matters.

So, how could either player have a winning strategy? The game is symmetric, in the sense that aside from playing order, both players follow the exact same rules and have the exact same goal. Since what happened previously doesn't matter, either player could begin using any purported winning strategy at any time and win... but they can't both win, so such such a strategy can't exist.