ir para o conteúdo
Topologia e conjuntos em exercícios
Mantido pelo grupo "Topologia do Interior"
Ferramentas do usuário
Entrar
Ferramentas do site
Pesquisar
Ferramentas
Mostrar página
Revisões anteriores
Links reversos
Alterações recentes
Gerenciador de mídias
Índice
Entrar
>
Alterações recentes
Gerenciador de mídias
Índice
Visitou:
lista:arvores
===== Á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.
lista/arvores.txt
· Última modificação: 2020/11/11 13:48 por
aurichi
Ferramentas da página
Mostrar página
Revisões anteriores
Links reversos
Voltar ao topo