Ferramentas do usuário
Árvores
Provavelmente é melhor fazer a lista de boa ordem antes desta.
Um conjunto $\langle T, \leq \rangle$ ordenado é dito uma árvore se, para todo $t \in T$ o conjunto $\{s \in T: s \leq t\}$ é bem ordenado.
1 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$.
2 Mostre que $\omega^{<\omega} = \bigcup_{n \in \omega}\omega^n$ é uma árvore com a ordem usual (extensão de função).
Dada $\langle T, \leq \rangle$ uma árvore, dizemos que $R \subset T$ é um ramo se é um conjunto maximal de elementos comparáveis.
3 Seja $\langle T, \leq \rangle$ uma árvore e seja $p \in T$. Mostre que existe $R \subset T$ ramo tal que $p \in R$.
4 Seja $R \subset \omega^{<\omega}$ um ramo. Mostre que $\bigcup_{r \in R} r$ é uma função de $\omega$ em $\omega$.
Daqui em diante, talvez seja melhor você já ter feito a lista sobre ordinais.
Seja $\langle T, \leq \rangle$ uma árvore. Dado $p \in T$, definimos a altura de $p$ ($h(p)$) como o (único) ordinal isomorfo a $\{q \in T: q < p\}$.
5 Caracterize $h(p)$ em termos de dom$(p)$ para todo $p \in \omega^{<\omega}$.
Seja $\langle T, \leq \rangle$ uma árvore. Dado $\alpha$ um ordinal, definimos o nível $\alpha$ de $T$ como $Lev(\alpha)$ $ = \{p \in T: h(p) = \alpha\}$. Definimos a altura de $T$ como o primeiro ordinal $\alpha$ tal que $Lev(\alpha) = \emptyset$.
6 Qual a altura de $\omega^{<\omega}$?
7 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\}$.
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 raiz (isto é, elemento minimal). A menos de menção contrária, sempre supomos que as árvores tenham essas propriedades.
8 Quem é a raiz de $\omega^{<\omega}$?
Seja $\langle T, \leq \rangle$ uma árvore. Dados $p, q \in T$, dizemos que $q$ é um sucessor imediato de $p$ se $p < q$ e não existe $r \in T$ tal que $p < r < q$. Dizemos que $T$ bifurca finitamente se, para todo $p$, o conjunto dos sucessores imediatos de $p$ é finito.
9 Este é um roteiro para mostrar o Lema de König. Seja $\langle T, \leq \rangle$ uma árvore infinita que bifurca finitamente.
9.1 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.
9.2 Mostre que $T$ admite um ramo infinito.
10 Dê um exemplo de uma árvore de altura infinita sem um ramo infinito.
Ferramentas da página
