===== Árvores =====

<WRAP tip>
Provavelmente é melhor fazer a lista de [[lista:BoaOrdem|boa ordem]] antes desta.
</WRAP> 

<WRAP info>
Um conjunto $\langle T, \leq \rangle$ ordenado é dito uma {{entry>árvore}} se, para todo $t \in T$ o conjunto $\{s \in T: s \leq t\}$ é bem ordenado.
</WRAP>

**~~#~~** Seja $\langle T, \leq \rangle$ uma árvore e sejam $p, q \in T$ distintos. Mostre que são equivalentes:
  - $p$ e $q$ são incomparáveis;
  - não existe $r \in T$ tal que $p, q \leq r$.

**~~#~~** Mostre que $\omega^{<\omega} = \bigcup_{n \in \omega}\omega^n$ é uma árvore com a ordem usual (extensão de função).

<WRAP info>
Dada $\langle T, \leq \rangle$ uma árvore, dizemos que $R \subset T$ é um {{entry>ramo}} se é um conjunto maximal de elementos comparáveis.
</WRAP>

**~~#~~** Seja $\langle T, \leq \rangle$ uma árvore e seja $p \in T$. Mostre que existe $R \subset T$ ramo tal que $p \in R$.

**~~#~~** Seja $R \subset \omega^{<\omega}$ um ramo. Mostre que $\bigcup_{r \in R} r$ é uma função de $\omega$ em $\omega$. 

<WRAP tip>
Daqui em diante, talvez seja melhor você já ter feito a lista sobre [[lista:Ordinais|ordinais]].
</WRAP>

<WRAP info>
Seja $\langle T, \leq \rangle$ uma árvore. Dado $p \in T$, definimos a {{entry> altura}} de $p$ ($h(p)$) como o (único) ordinal isomorfo a $\{q \in T: q < p\}$.  
</WRAP>

**~~#~~** Caracterize $h(p)$ em termos de dom$(p)$ para todo $p \in \omega^{<\omega}$. 

<WRAP info>
Seja $\langle T, \leq \rangle$ uma árvore. Dado $\alpha$ um ordinal, definimos o nível $\alpha$ de $T$ como {{entry>$Lev(\alpha)$}} $ = \{p \in T: h(p) = \alpha\}$. Definimos a altura de $T$ como o primeiro ordinal $\alpha$ tal que $Lev(\alpha) = \emptyset$.  
</WRAP>

**~~#~~** Qual a altura de $\omega^{<\omega}$?

**~~#~~** Numa árvore qualquer, note que podem existir $p, q$ distintos tais que $h(p) = h(q)$ é um ordinal limite e $\{r \in T: r < p\} = \{r \in T: r < q\}$. 

<WRAP tip>
Normalmente, pedimos na definição de uma árvore que a situação anterior **não** ocorra (costuma-se dizer que a árvore não bifurca nos níveis limites). Também costuma-se pedir que toda árvore admita uma única {{entry>raiz}} (isto é, elemento minimal). A menos de menção contrária, sempre supomos que as árvores tenham essas propriedades.
</WRAP>

**~~#~~** Quem é a raiz de $\omega^{<\omega}$?
 
<WRAP info>
Seja $\langle T, \leq \rangle$ uma árvore. Dados $p, q \in T$, dizemos que $q$ é um {{entry>sucessor imediato}} de $p$ se $p < q$ e não existe $r \in T$ tal que $p < r < q$. Dizemos que $T$ {{entry>bifurca finitamente}} se, para todo $p$, o conjunto dos sucessores imediatos de $p$ é finito.
</WRAP>

**~~#~~** Este é um roteiro para mostrar o Lema de König. Seja $\langle T, \leq \rangle$ uma árvore infinita que bifurca finitamente.

**~~#.#~~**  Seja $p \in T$ tal que $V_p = \{q \in T: p \leq q\}$ é infinito. Mostre que $p$ admite um sucessor imediato $q$ tal que $V_q$ é infinito.

**~~#.#~~** Mostre que $T$ admite um ramo infinito. 

**~~#~~** Dê um exemplo de uma árvore de altura infinita sem um ramo infinito.