===== Árvore de Aronszajn =====

$\def\dom{\text{dom}}$

<WRAP tip>
Provavelmente você vai querer ter feito a lista de [[lista:Arvores|árvores]] antes desta. 
</WRAP>

<WRAP info> Durante toda esta lista, $T$ denota uma árvore satisfazendo
  * $\emptyset \in T$;
  * cada $t \in T$ é uma função estritamente crescente em $\mathbb Q$;
  * se $t \in T$, então $\{t^\smallfrown q: q \in \mathbb Q$ e $\forall x \in \dom(t) \ q > t(x)\} \subset T$.
  
Em $T$, dizemos que $t \leq s$ se $t \subset s$.
</WRAP>


**~~#~~** Note que se $T$ é uma árvore como acima, então $h(T) \geq \omega$.

**~~#~~** Note que se $R \subset T$ é um ramo, então $\bigcup_{t \in R} t$ é uma função de um ordinal $\alpha$ em $\mathbb Q$ estritamente crescente.

**~~#~~** Mostre que $T$ não admite ramos não enumeráveis.


**~~#~~** Suponha $T$ uma árvore como acima, tal que $h(T) = \omega$.

**~~#.#~~** Note que $T$ é enumerável.

**~~#.#~~** Note que $T$ tem uma quantidade não enumerável de ramos.

**~~#.#~~** Note que alguns ramos de $T$ não são estendíveis (isto é, não há como acrescentar um elemento acima dos elementos de um ramo $R$ de forma que a função formada pela união dos elementos de $R$ ainda fique estritamente crescente).

**~~#.#~~** Para cada $q \in \mathbb Q$, mostre que existe um ramo $R$ de forma que $\bigcup R \cup \{(\omega, q)\}$ é uma função estritamente crescente.

**~~#.#~~** Para cada $q \in \mathbb Q$ encontre $R_q$ ramo como no item anterior. Note que $T \cup \{R_q: q \in \mathbb Q\}$ é uma árvore de altura $\omega + 1$ enumerável. 

**~~#.#~~** A árvore construída no item anterior não satisfaz as condições impostas acima. Você consegue arrumar?


**~~#~~** A ideia neste exercício é melhorar o exercício anterior. Comece da mesma maneira, com uma $T$ tal que $h(T) = \omega$. Para cada $t \in T$, seja $q_t = t(n)$, onde $n$ é último elemento do domínio de $t$.

**~~#.#~~** Para cada $t \in T$ e cada $q \in \mathbb Q$ tal que $q_t < q$, mostre que existe um ramo $R$ tal que $t \in R$ e $\bigcup R \cup \{(\omega, q)\}$ é estritamente crescente.

**~~#.#~~** Construa um novo nível $N$ para a árvore $T$ tal que:
  * $N$ é enumerável;
  * todo elemento de $N$ tem altura $\omega$;
  * se $R$ é um ramo em $T \cup N$, então $\bigcup R$ é uma função estritamente crescente em $\mathbb Q$;
  * dados $t \in T$ e $q \in \mathbb Q$ tais que $q_t < q$, existe $n \in N$ tal que $t \leq n$ e $n(\omega) = q$.

<WRAP info>
Dizemos que uma árvore $T$ é {{entry>bem podada}} se, dados $t \in T$, e $\alpha$ ordinal tal que $h(t) < \alpha < h(T)$, temos que existe $s \in T$ tal que $h(s) = \alpha$ e $t \leq s$.   
</WRAP>
  
<WRAP tip>
O próximo exercício é imediato para quem tem experiência com [[lista:confinalidade|cofinalidade]].
</WRAP>

**~~#~~** Seja $\alpha$ ordinal limite tal que $\omega < \alpha < \omega_1$. Mostre que existe $f: \omega \to \alpha$ estritamente crescente tal que $\sup\{f(n): n \in \omega\} = \alpha$.

**~~#~~** Suponha $T$ uma árvore enumerável tal que $\omega < h(T) < \omega_1$ que satisfaça as condições acima e é bem podada.

**~~#.#~~** Note que, como $T$ satisfaz as condições acima, $h(T)$ é limite.

**~~#.#~~** Mostre que podemos estender $T$ para uma árvore $T'$ de altura estritamente maior de forma que $T'$ é enumerável, satisfaz as condições acima e é bem podada.

<WRAP info>
Chamamos de uma {{entry>árvore de Aronszajn}} uma árvore de altura $\omega_1$, sem ramos não enumeráveis e sem níveis não enumeráveis.
</WRAP>

**~~#~~** Mostre que existe uma árvore de Aronszajn.

**~~#~~** Compare o exercício anterior com o enunciado do [[lista:Arvores|Lema de König]]. Note que isso atesta que uma certa generalização do lema é impossível.