Ferramentas do usuário
Tabela de conteúdos
Jogo e Teorema de Gale-Stewart
Apesar de não ser estritamente necessário, é interessante ler a lista sobre árvores.
Introdução
Seja $A \neq \emptyset$ um conjunto, sem perda relativa de generalidade, vamos considerar nessa sessão apenas árvores de sequência $ A^{<\omega} $ munidas de função óbvia de comprimento / altura $ |t| = n $ quando $t \in A^n$ com ordem $\subset$ usual.Nesta lista, árvore será um caso particular de árvores. Ou seja, vamos considerar árvores aparadas (todos os seus ramos têm mesma altura) de altura $\omega$. O leitor orientado à categorias pode visualizar isso como functor $ F:\omega^{\textbf{op}} \to \textbf{Set} $ tal que, para cada $n < m$, $F(m \to n) = F(m) \rightarrow F(n) $ é sobrejetora, ou seja, todo elemento no nível $n$ têm descendente no nível $m$.
1 Considere $[A^{<\omega}] \doteq \{ \text{ ramos de $A^{<\omega}$ } \} \overset{\text{id.}}{=} A^\omega $. Dado $t \in A^{<\omega}$, $ \Sigma(t)\doteq \{ \alpha \in A^\omega \, : \, \alpha \upharpoonright |t| = t \}$ ramos de $A^{<\omega}$ que têm $t$ como segmento inicial.
1.1 Mostre que $\Sigma(t)$ é base para a topologia produto de $A^\omega$, considerando $A$ munido da topologia discreta.
1.2 Mostre que se $A^\omega$ é metrizável.
1.3 Mostre que se $A^\omega$ é zero-dimensional. Dica
Considere o seguinte jogo : fixemos $X \subset A^\omega$, que se pode chamar target, alvo de I ou conjunto de ganho. O jogador I escolhe $a_0 \in A$, em seguida II escolhe $a_1 \in A$. O jogador I vence se $\langle a_0,a_1,\ldots\rangle \in X$, II vence caso contrário. Classicamente, $A = \omega$ e este jogo é chamado de jogo de Gale-Stewart.
Vamos considerar nesta lista que subárvores são $T \subset A^{<\omega} $ subconjuntos de $A^{<\omega}$ quem contém $\langle \rangle$, a mesma ordem, são fechados com relação à $ \upharpoonright n $, $ n \in \omega $ e, são elas próprias aparadas de altura $\omega$, ou equivalentemente : $ \forall t \in T \, \exists a \in A \, t^{\frown}a \in T $.
2 Considere o jogo definido acima:
2.1 Como você definiria uma estratégia $\sigma$ do jogador I do jogo de Gale-Stewart como uma sub-árvore de $A^{<\omega}$? O que seria “uma partida onde I jogou de acordo com $\sigma$”? Que condição pedir para que $\sigma$ caracterize estratégia vencedora? Dica.
2.2 Qual a associação entre a definição de estratégias como árvores e a definição usada até aqui, como função?.
2.3 Dada uma estratégia $\sigma$ de I e uma estratégia $\rho$ de II, o que é $\sigma \cap \rho$? Pode ser que I e II tenham estratégias vencedoras?
3 Note que os ramos de $T$ são ramos de $A^{<\omega}$, e que $ [T] \subset A^{<\omega} $ tem topologia de subespaço. Considere o jogo de Gale-Stewart com regra codificado por $ T $: fixado $ X \subset [T] $, os jogadores devem jogar em $ T $, ou seja, se estamos na posição $ t $, o próximo jogador só pode jogar $ a $ se $ t^{\frown}a \in T $. Mostre que o jogo $ (T,X) $ é equivalente ao jogo:
\[ \left( A^{<\omega}, \{ \alpha \in A^\omega \, : \, \alpha \in X \lor \left( \underbrace{ \exists t \in T \, |t| \text{ é ímpar } \land \, t^\frown a \notin T } _{\text{II foi levado e fez jogada ilegal}} \right) \, \land \, \alpha \in \Sigma(t^\frown a) \} \right) \]
Mostrando, como usual que I $\uparrow$ $(T,X) $ $\iff$ I$\uparrow$ $(A^{<\omega},X)$, porém, usando a definição de estratégia como árvore (pense em termos de diagrama e sucessores). Note que isso quer dizer que um jogo “com regras” (só pode jogar em $T$) é equivalente à um jogo sem regras, adaptando-se o alvo de I. Ou seja, não perdemos generalidade supondo que jogamos em $A^{<\omega}$.
4 Mostre que todo jogo topológico é um jogo de Gale-Stewart. Por exemplo, para o jogo do ponto aberto, $ A \doteq X \cup \tau_X $. Note que o próprio jogo de Gale-Stewart é um jogo de Banach-Mazur com regras. Dica
Quasi-estratégias
Vamos definir uma quasi-estratégia $\sigma$ de I como uma subárvore de $ A^{<\omega} $ tal que, se $ |t| $ é ímpar e $ t \in \sigma $, então todos os seus sucessores $ t^\frown a \in \sigma $ estão ainda na estratégia. Mutandis mutatis temos a definição de quasi-estratégia de II. Uma quasi-estratégia é vencedora se $[\sigma] \subset X$ todos os seus ramos são vencedores para I. Diz-se que um jogo é quasi-determinado se um dos jogadores tem quasi-estratégia vencedora.
5 Seja $ \sigma $ uma quasi-estratégia de I.
5.1 Mostre que existe uma estratégia $\tilde{\sigma} \subset \sigma$. Note que você usou o axioma da escolha no conjunto dos conjuntos de sucessores dos elementos de $\sigma$ de comprimento par.
5.2 Seja $(A,\prec)$ uma boa ordem. Note que $[AC]$ não é mais necessário para extrair uma estratégia de quasi-estratégias.
6 Sobre $[AC]$, se um jogo é quasi-determinado então ele é determinado. Note também que estratégias são quasi-estratégias, logo jogos determinados são quasi-determinados.
Posições, (Quasi)-estratégias Defensivas
Imagine que você está jogando um jogo e que você chegou à uma posição fixada $t = \langle a_0,\ldots,a_n\rangle$. Pode-se interpretar isso como jogar um novo jogo, desde o começo, forçando os jogadores a jogar estes primeiros termos, ou seja, impor que devemos jogar em $T_t = \{ \text{elementos comparáveis com $t$} \}$, com alvo atualizado $[T_t]\cap X$.
Uma posição $t \in A^{<\omega}$ é dita posição denfensiva para I se II não tem estratégia vencedora em $(T_t,[T_t] \cap X)$. Uma subárvore $\sigma$ é dita (quasi)-estratégia defensiva de I se todas as suas posições são defensivas para I.
7 Considere o jogo $(T_t,[T_t]\cap X)$ visto à partir de uma posição e suponha que $|t|$ é par (é turno de I). Suponha para todo $a \in A$, $\exists b \in A$ tal que $II$ vence $(T_{t^\frown a^\frown b},[T_{t^\frown a^\frown b}]\cap X) $, mostre que II $\uparrow$ $(T_t,[T_t]\cap X)$. Dica
8 Seja $t$ posição defensiva de um jogador, mostre que existe $a \in A$ tal que para todo $b \in A$, $t ^\frown a ^\frown b$ é defensiva para I.
9 Note que dizer que II não vence é o mesmo que dizer que a raiz $\langle \rangle \in A^{<\omega}$ é defensiva para I. Mostre que se II não vence $(A^{<\omega},X)$ então I tem quasi-estratégia defensiva.
Teorema de Gale-Stewart
10 Mostre que existe um jogo $(T,X)$ indeterminado tal que $(T,[T]\backslash X)$ é determinado, ou seja, mostre que não necessariamente $\{X \subset [T] \, : \, (T,X) \text{ é determinado}\}$ é fechado com relação à complementação. Solução
11 Vamos agora mostrar o teorema de quasi-Gale-Stewart: Jogos $(A^{<\omega},X)$ onde $ X $ é aberto ou fechado são quasi-determinados. É importante notar que dado $ \alpha \in A^\omega \backslash X $ aberto deve ter aberto básico $\alpha \in \Sigma(t) \subset A^\omega \backslash X $.
11.1 Mostre que se $X \subset A^\omega$ é fechado e II não vence, então I têm quasi-estratégia vencedora em $(A^{<\omega},X) $.
11.2 Mostre que se $X \subset A^\omega$ é aberto e I não vence, então II têm quasi-estratégia vencedora em $(A^{<\omega},X) $.
No que segue, considere $[AC]$ o axioma da escolha como a afirmação de que todo $X \neq \emptyset$ que tem todos seus elementos $x \in X \implies x \neq \emptyset $ não vazios, então existe uma função (escolha) $f:X \to \bigcup X$ tal que $\forall x \in X \,\, f(x) \in x $.
12 Considere $[GS] \doteq $ “jogos abertos e fechados são determinados!”. Vamos mostrar que esta afirmação é equivalente ao axioma da escolha.
12.1 Mostre que $ [AC] \implies [GS] $ (Teorema de Gale-Stewart).
12.2 Mostre que $ [GS] \implies [AC] $. Solução
Ferramentas da página
