Topologia e conjuntos em exercícios

===== Jogo e Teorema de Gale-Stewart =====

<WRAP tip>
Apesar de não ser estritamente necessário, é interessante ler a lista sobre [[lista:Arvores|árvores]].
</WRAP>

==== Introdução ==== 

<WRAP info>
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 [[lista:Arvores|á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$.
</WRAP>

**~~#~~** 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.



{{ wiki:basic_open.png?400 }}




**~~#.#~~** Mostre que $\Sigma(t)$ é base para a topologia produto de $A^\omega$, considerando $A$ munido da topologia discreta.

**~~#.#~~** Mostre que se $A^\omega$ é metrizável.

**~~#.#~~** Mostre que se $A^\omega$ é zero-dimensional. <wrap tip>[[dica:zero-dim-pow|Dica]]</wrap>

<WRAP info>
Considere o seguinte jogo : fixemos $X \subset A^\omega$, que se pode chamar {{entry>target}}, {{entry>alvo de I}} ou {{entry>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,...\rangle \in X$, II vence caso contrário. Classicamente,  $A = \omega$ e este jogo é chamado de {{entry>jogo de Gale-Stewart}}.
</WRAP>

<WRAP info>
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 $.
</WRAP>

**~~#~~** Considere o jogo definido acima:

**~~#.#~~** 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? <wrap tip>[[Solucao:StrategyTree|Dica]]</wrap>.

{{  wiki:strategyone.png?500  }}

**~~#.#~~** Qual a associação entre a definição de estratégias como árvores e a definição usada até aqui, como função?.

**~~#.#~~** 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? 

**~~#~~** 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}$.

**~~#~~** 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. <wrap tip>[[Solucao:StrategyTree|Dica]]</wrap>

==== Quasi-estratégias ====

<WRAP info>
Vamos definir uma {{entry>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 é {{entry>quasi-determinado}} se um dos jogadores tem quasi-estratégia vencedora.
</WRAP>

**~~#~~** Seja $ \sigma $ uma quasi-estratégia de I.

**~~#.#~~** 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.

**~~#.#~~** Seja $(A,\prec)$ uma boa ordem. Note que $[AC]$ não é mais necessário para extrair uma estratégia de quasi-estratégias.

**~~#~~** 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,...,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$.



{{  wiki:shift_game.png  }}




<WRAP info>
Uma posição $t \in A^{<\omega}$ é dita {{entry>posicao-defensiva|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 {{entry>quasi-estrategia-def|(quasi)-estratégia defensiva}} de I se todas as suas posições são defensivas para I.
</WRAP>

**~~#~~** 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)$. <wrap tip>[[Solucao:glueStrategies|Dica]]</wrap>

**~~#~~** 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.

**~~#~~** 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 ====

**~~#~~** 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. <wrap help> [[Solucao:determAreNotAlgebra | Solução]]</wrap>


**~~#~~** 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 $.

**~~#.#~~** 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) $. 

**~~#.#~~** 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) $. 

<WRAP info>
No que segue, considere $[AC]$ o {{entry>choice|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 $.
</WRAP>

**~~#~~** Considere $[GS] \doteq $ "jogos abertos e fechados são determinados!". Vamos mostrar que esta afirmação é equivalente ao axioma da escolha.

**~~#.#~~** Mostre que $ [AC] \implies [GS] $ (**Teorema de Gale-Stewart**).

**~~#.#~~** Mostre que $ [GS] \implies [AC] $. <wrap help> [[Solucao:GaleStewartChoice | Solução]]</wrap>
Topologia e conjuntos em exercícios

Ferramentas do usuário

Ferramentas do site

Ferramentas da página
