Generlized Büchi Games and Closed under superset Muller Games For a unique infinite play $p$ in a 2-Player game $G=(V_0,V_1,E)$. Let
$$ \inf(p) \subseteq V_0 \cup V_1 $$
be the set of vertices which occur infinitly often in $p$.
Generlized Büchi (GB) Games are infinite games with a certain winning condition. Let $\mathcal{B} = \{B_1, \dots , B_k\}$ with $B_i \subset V$. Player $0$ wins the GB-game play $p$ iff for each $i$
$$ B_i \cap \inf(p) \neq \emptyset.$$
Which means that in each of the $B_i$ sets at least one vertex occurs infinitly often in the game.
Muller games are more general. The winning condition consists of a set $\mathcal{F_0} \subseteq \mathcal{P}(V)$ and Player $0$ wins a play $p$ iff
$$\inf(p) \in \mathcal{F}_0.$$
Muller games closed under superset are Muller games such that $\mathcal{F}_0$ is closed under supersets:
$$ X \in \mathcal{F}_0, X \subseteq Y \Rightarrow Y \in \mathcal{F}_0.$$
The taks now is to prove that GB-games and Muller games closed under superset are the same winning conditions.
One direction is easy. Just show that $\mathcal{F}_0 := \{X \subset V \mid \forall 1 \leq i \leq k, X \cap B_i \neq \emptyset\}$ is closed under supersets.
The other direction is a little bit more tricky:
Show that for each muller condition closed under supersets there is a GB condition with the same $\inf$-set for each game. E.g. :
$$ V=\{1,2,3,4\} ~~ \mathcal{F}_0=\{\{1,2\},\{3,4\},\{1,2,3,4\}\}$$
The muller condition is closed under supersets. Now the GB-Condition
$$\{\{1,3\},\{2,4\}, \dots$$
Here is where I'm stuck. How do I prevent $\inf(p)=\{1,4\}$ or $\inf(p)=\{2,3\}$? There is no construction for "forbidden combinations". Any ideas?
 A: For the other direction, let $S$ be the set of all $\it{minimal}$ (without proper subset) set of sets in $\mathcal{F}_0$ in Muller condition, i.e, let $$ S = \{X \subset \mathcal{F}_0 \mid \forall Y \in \mathcal{F}_0, Y \not \subset X \} $$
In your example, $S = \{ \{1, 2\}, \{3, 4\}\}$.
Now consider the cross product of all elements of $S$. Claim is that this cross product forms the corresponding GB-condition. In your example,
$$ S_\times = \{1, 2\} \times \{3, 4\} = \{ \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}\}$$
forms the accepting condition of the GB-game. There are two things to be proved:


*

*Every winning play $p$ of GB-game is also winning in Muller game. This is true because every state in $inf(p)$ comes from at least one state in $S$ in Muller game. Thus, $inf(p) \subseteq \cup_{X \in S} X$. The proof follows from the fact that Muller game is closed under subset.

*Every winning play $p$ of Muller game is also winning in GB-game. In this case, let $inf(p) = R \in \mathcal{F}_0$ be the winning set. Since Muller game is closed under superset, there exists a $\it{minimal}$ set $X$ such that $X \subseteq R$. Now at least one element of $X$ appears in any winning condition of the GB-game. Hence, $R \cap \beta \neq \emptyset$, proving the other direction as well.

