# Infinite combinatorial games

1. Hercules vs. Hydra: Recall the story where every time Hercules cuts of a head, two more heads grow instead. Now suppose the following: The hydra starts off with one head, but every time Hercules cuts off a head, $\aleph_0$ grow anew. Show that Hercules will be able to defeat the Hydra before $\omega_1$ steps. That is, we will reach a step $\lambda<\omega_1$ where the Hydra doesn't have any heads.

2. Two players play in the following game: In each turn $n \in \mathbb{N}$, the player whose turn it is chooses a set $A_n$ that is contained in the previous set,i.e $A_n \subseteq A_{n-1}$ such that $A_n$ are stationary sets $A_n \subseteq \omega_1$. Player 1 starts. After $\aleph_0$ such turns, Player 2 wins if the intersection $\cap_nA_n$ contains at most 1 ordinal (we can say Player 1 wins otherwise). Show that Player 2 has a winning strategy, that is a way to choose the $2n+1$ set to ensure he wins.

• You seem to know the answers already. Where'd you get these problems from? – Samuel Jun 7 '13 at 11:15
• It would be quite helpful if instead of just spitting out homework problems, you'd also add what you'd tried to do in order to solve them. – Asaf Karagila Jun 7 '13 at 11:15
• @ctlaltdefeat: A hint for the first question: What happens at limit stages? For example how many heads has the hydra produced in the first $\omega$ cuts of Hercules? – Apostolos Jun 7 '13 at 12:53
• Well, $\omega\times\omega$ is still countable and Hercules killed countable many heads as well. If Hercules is allowed to cut the heads in any order that he prefers, can you think of a way to make him cut all these heads in the first $\omega$ kills? If on the other hand we assume that the heads get well ordered and Hercules has to cut them in order (as you describe in your comment) what can you say about the function that sends each kill to the order of the heads that has been produced? – Apostolos Jun 7 '13 at 13:27
• @ctlaltdefeat: I would advice you not to erase the question. This is not a site where answers are given just to the person that asks the question, but rather to anyone interested. Maybe someone in the future has a similar question. I think a better idea would be to write down a complete answer for the first question as a community wiki answer and submit it, while leaving the first question as part of your original question. Also, all these comments will not make sense to someone who will visit this question in the future. – Apostolos Jun 7 '13 at 15:48

OK, let's see.

For the first question, enumerate the heads as they are added: The original head is head $0$. We can enumerate the heads added in stage $\alpha$ by ordinals in the ordinal interval $(\omega\alpha,\omega(\alpha+1)]$. If we suppose for no $\alpha<\omega_1$ the Hydra has no heads at the beginning of stage $\alpha$ then, for a club $C$ of countable ordinals $\alpha$, the heads enumerated so far at the beginning of stage $\alpha$ are indexed precisely by the ordinals less than $\alpha$.

This allows us to define a regressive function on $C$, that to each $\alpha\in C$ assigns $\beta<\alpha$ iff $\beta$ is the index of the head removed at stage $\alpha$. By Fodor's lemma, the same index is used more than once (in fact, stationarily often). But this is impossible, and we have a contradiction. (This is a nice problem. I forget where it originated.)

The second question reminds me of arguments of Mycielski and Solovay from the early 70s. I give here an argument that applies not just to subsets of $\omega_1$, but also to subsets of any regular $\kappa\le\mathfrak c$, the cardinality of the continuum. I suspect this restriction is a distraction, but I'll use it below.

Accordingly, suppose $\kappa$ is regular, $\kappa\le\mathfrak c$, and we play the game you describe, except that the $A_n$ are stationary in $\kappa$. Since $\kappa\le\mathfrak c$, we may fix an injection of $\kappa$ into the interval $[0,1]$. In what follows, we identify subsets of $\kappa$ with subsets of $[0,1]$ via this injection. Also, to each bounded set $A\subseteq[0,1]$ with infimum $m=m(A)$ and supremum $M=m(A)$, we associate a strictly increasing sequence $m=a_0=a_0(A)<a_1<\dots$ converging to $M$, with $a_1=(m+M)/2$, $a_2=(a_1+M)/2$, etc. (So $a_1$ is the midpoint of the interval $[m,M]$, $a_2$ is the midpoint of $[a_1,M]$, etc.)

Now we describe how player II must respond to the moves of player I. Say that at stage $n$, player I has played $A=A_{2n}$. There must be an interval $[a_k(A),a_{k+1}(A))$ whose intersection with $A$ is (via the injection fixed above) a stationary subset of $\kappa$. The reason is that the stationary set $A\setminus\{M(A)\}$ is the countable union of these sets, and the countable intersection of clubs is club, so one of these sets must be stationary as well.

More precisely, if $i$ is the injection, then $A\setminus\{i^{-1}(M)\}=\bigcup_k i^{-1}([a_k,a_{k+1})\cap i[A])$.

Let $A_{2n+1}$ be this stationary set $i^{-1}([a_k,a_{k+1})\cap i[A_{2n}])$ (where, if you wish, we let $k$ be least so that this is stationary).

The point is this: Call the size of $A_n$ the number $M(A_n)-m(A_n)$. Then the size of $A_{2n+2}$ is at most half the size of $A_{2n}$. Since the sets $i[A_n]$ shrink to size $0$, their intersection is empty or a singleton.

• In the first question, what is the club set $C$? After the sentence "The original head is head 0. we can enumerate the heads added in stage α by ordinals in the ordinal interval (ωα,ω(α+1)]", I don't see how you reached your conclusion about existence of such a C. Also you wrote C is a club of $\alpha$, so you have such a club for each $\alpha$? – ctlaltdefeat Jun 9 '13 at 15:10
• $C$ is a club subset of $\omega_1$, consisting of ordinals $\alpha$ such that ... This is usually abbreviated by saying that $C$ is a club of ordinals $\alpha$ such that ... – Andrés E. Caicedo Jun 9 '13 at 17:22
• As for the existence of $C$: Let $f$ be the function that assigns to $\alpha$ the supremum of the ordinals $\beta$ that have been used enumerating heads prior to stage $\alpha$, so $f(0)=0$, $f(1)=\omega$, etc. The point is that $f(\tau)$ is countable for each countable ordinal $\tau$. For any function $g:\omega_1\to\omega_1$, the set of ordinals $\alpha<\omega_1$ such that $g(\beta)<\alpha$ for all $\beta<\alpha$ is a club set. When $g$ is the function $f$ just described, then the club set is $C$. – Andrés E. Caicedo Jun 9 '13 at 17:24
• I get it, thanks mate. – ctlaltdefeat Jun 9 '13 at 17:30