P2.tex

\documentclass[a4paper]{article}
\usepackage{packages}
\title{Introdução à Teoria dos Conjuntos - Prova 2}
\author{Ariel Serranoni Soares da Silva  - Número USP: 7658024\\
Pedro Felizatto - Número USP:9794531\\
Pietro Mesquita Piccione - Número USP: 4630640\\
Mateus Schmidt Mattos Lopes Pereira - Número USP: 10262892\\
Luís Cardoso - Número USP: 4552403\\
Ariel Campêlo Viana Morais - Número USP: 9302177
Bento Pereira - Número USP: 9783608}
\date{\today}
\begin{document}
\maketitle
\section*{Observações iniciais}

As notas de aula a seguir foram produzidas com base na Seção 3 do Capítulo 12 de
\cite{jech}. A ideia do nosso trabalho é seguir fielmente o conteúdo abordado no
livro, inclusive mantendo a notação e numeração que são usados pelo autor.
Além disso, vamos incluir observações, soluções para os exercícios, e justificar
passos que ficaram em segundo plano no tratamento feito na obra mencionada.

\setcounter{section}{2}
\section{Árvores}

Assim como fizemos anteriormente com partições, vamos agora dedicar uma seção do
nosso trabalho para generalizar mais um objeto originário do
contexto de combinatória finita: árvores.

\begin{definition}
  Uma \emph{árvore} é um conjunto ordenado \((T,\leq)\) tal que:
 \begin{enumerate}[(i)]
  \item \(T\) possui um menor elemento;
  \item para cada \(x\in T\), o conjunto \(\{y\in T\,\colon y<x\}\) é bem
    ordenado sob \(\leq\).
  \end{enumerate}
\end{definition}
Os elementos de \(T\) são chamados de \emph{nós}. Em particular,
o menor elemento de \(T\) é chamado  de \emph{raiz}.
Se \(x,y\in T\) são nós tais que  \(y<x\), dizemos que \(y\) é um
\emph{antecessor} de \(x\) e que \(x\) é um \emph{sucessor} de \(y\).

Seja \(x\in T\) um nó.  A \emph{altura} \(h(x)\) de \(x\) é o único ordinal
isomorfo ao conjunto bem ordenado \mbox{\(\{y\in T\,\colon
y<x\}\),} composto por todos os antecessores de \(x\). Observe que como \(T\) é uma árvore,
então \(\{y\in T\,\colon y<x\}\) é bem ordenado e a altura está bem-definida como função em \(T\).
Além disso, se \(h(x)\) é um ordinal sucessor, dizemos que \(x\) é um
\emph{nó sucessor}. Caso contrário \(x\) é denominado \emph{nó limite}.
O \(\alpha\)-ésimo \emph{nível} de \(T\) é o conjunto
\(T_\alpha=\{x\in T \,\colon h(x)=\alpha\}\). A \emph{altura} \(h(T)\) da árvore
\(T\) é o menor ordinal \(\alpha\) tal que \(T_\alpha=\varnothing\).  

Um \emph{ramo} \(b\) de \(T\) é uma cadeia maximal em \(T\).  O \emph{comprimento}
\(\ell(b)\) de um ramo \(b\) é o tipo da ordem de \(b\). Note que para
todo ramo \(b\) de \(T\) temos \(\ell (b)\leq h(T)\).
Um ramo cujo comprimento é igual a \(h(T)\) é chamado de \emph{cofinal}.
Uma \emph{subárvore} \(T^\prime\) de \(T\) é um subconjunto
\(T^\prime\subseteq T\) tal que, para quaisquer \(x\in T^\prime\) e \(y\in T\),
temos que \(y<x\) implica \(y\in T^\prime\).
Sendo assim, \(T^\prime\) também é uma árvore quando ordenada por \(\leq\).
Ademais, para cada \(\alpha < h(T^\prime)\) temos que o \(\alpha\)-ésimo nível
de \(T^\prime\) é dado por \(T_\alpha^\prime= T_\alpha \cap T^\prime\).

 Para cada \(\alpha\leq h(T)\), o conjunto \(T^{(\alpha)}=\bigcup_{\beta <
   \alpha} T_\beta\) é uma subárvore de \(T\) com  \(h(T^{(\alpha)})=\alpha\).
 Se \(x\in T_\alpha\) então \(\{y\in T\,\colon y < x\}\) é um ramo de \(T^{(\alpha)}\) de
comprimento \(\alpha\); entretanto, se \(\alpha\) é um ordinal limite então
\(T^{(\alpha)}\) pode ter outros ramos de comprimento \(\alpha\).

Finalmente, um conjunto \(A\subseteq T\) é uma \emph{anti-cadeia} em \(T\) se
quaisquer elementos de \(A\) são incomparáveis. Isto é, se \(x,y\in A\) são tais
que \(x\not = y\), então \(x\not \leq y\) e \(y\not \leq x\).

A respeito dos conceitos introduzidos acima, é importante observar que todo
ramo ou subárvore de \(T\) contém a raiz. Também notamos que se \(x,y\in T\)
são nós tais que \(y< x\), então \(h(y) <h(x)\). Além disso, a própria definição
de \(h(T)\) nos dá que \(T_\alpha\not=\varnothing\) para todo ordinal
\(\alpha<h(T)\). A seguir, vamos resolver os
exercícios sugeridos pelo autor neste ponto do texto em \cite{jech}. Tais problemas
exploram algumas das propriedades que surgem imediatamente das
definições que apresentamos:

\begin{exercicio}
  Seja \((T,\leq)\) uma árvore. Mostre que:
  \begin{enumerate}[(i)]
  \item O único elemento \(r \in T\) tal que \(h(r)=0\) é a raiz. Em particular,
    \(T_0\not =\varnothing\);
  \item Se \(\alpha,\beta\) são ordinais tais que \(\alpha\not = \beta\), então \(T_\alpha\cap T_\beta =\varnothing\);
  \item \(T=T^{(h(T))}=\bigcup_{\alpha < h(T)}T_\alpha\);
  \item Um nó \(x\in T\) é um nó sucessor se, e somente se existe um único nó \(y\in T\) tal que
    \begin{equation}\label{propsuc}
      y < x \text{ e não existe } z \text{ tal que } y<z<x.
    \end{equation}
    Se \(x\) é um nó sucessor então o nó
    \(y\) que satisfaz \eqref{propsuc}  é chamado de \emph{antecessor imediato} de
    \(x\), e dizemos que \(x\) é \emph{sucessor imediato} de \(y\).
    Note que cada nó sucessor possui um único antecessor imediato,
    mas pode possuir múltiplos sucessores imediatos;
    \item Se \(x,y\in T\) são nós tais que \(y< x\), então existe um único \(z\in T\) tal que \(y< z\leq x\) e
      \(z\) é um sucessor imediato de \(y\);
    \item \(h(T)=\sup\{\alpha +1\,\colon
      T_\alpha\not=\varnothing\}=\sup\{h(x)+1\,\colon x\in T\}.\)
    \end{enumerate}
  \end{exercicio}
  
\begin{proof}[Solução]\hfill
  \begin{enumerate}[(i)]

  \item Seja \(r\in T\) tal que \(h(r)=0\), então temos que \(\{x\in T\,\colon
    x<r\}=\varnothing\), da onde segue que \(r\) é o menor elemento de \(T\), a raiz.
    Agora suponhamos \(r_1\, r_2\in T\), de modo que \(h(r_1)=h(r_2)=0\). Então \(r_1\) e
    \(r_2\) são raízes de \(T\). Neste caso,  para todo \(x\in T\) temos que
    \(r_1\leq x\). Em particular temos que \(r_1\leq r_2\).
    Analogamente, obtemos que \(r_2\leq r_1\). Como \(\leq\) é
    uma ordem, segue que \(r_1=r_2\). Para \(r\in T\) raiz, temos \(h(r)=0\) e portanto
    \(r\in T_0\). Logo, \(T_0\not=\varnothing\).
    
  \item Suponha que existe \(x\in T_\alpha\cap T_\beta\). Neste caso, temos que
    \(\alpha=h(x)=\beta\), o que contradiz a unicidade de \(h(x)\).

  \item Para a primeira igualdade, note que \(T^{(h(T))}\subseteq T\) uma vez
    que \(T^{(h(T))}\) é definido como uma união de subconjuntos de \(T\). Por
    outro lado, seja \(x\in T\) e suponha que \(x\not\in T^{(h(T))}\). Daí,
    segue da definição de \(T^{(h(T))}\) que não existe \(\alpha < h(T)\) tal
    que \(h(x)=\alpha\). Isso implica
    que \(h(x)\geq h(T)\). Absurdo. Como a segunda igualdade segue diretamente da
    definição de \(T^{(h(T))}\), a prova está completa. 

  \item Suponha que \(x\) é um nó sucessor. Neste caso, temos por definição
    que \(h(x)=S(\alpha)\) para algum ordinal \(\alpha\). Vamos mostrar que
    existe \(y\in T_\alpha\) tal que \(y < x\). Assumindo o contrário, teremos
    que o ramo da subárvore \(b\coloneqq\{y\in T^{(h(x))}\,\colon y<x\}\) não possui elemento em
    \(T_\alpha\). Daí, segue que \[S(\alpha)=h(x)=\ell(b)\leq\alpha,\] que é um absurdo. 
    Assim, tome \(y\in T_\alpha\) tal que \(y<x\) qualquer. Se
    existe \(z\) tal que \(y<z<x\), então obtemos
    que \[h(y)=\alpha<h(z)<S(\alpha)=h(x),\] 
    absurdo. Finalmente, suponha que existem \(y_1\) e \(y_2\) distintos satisfazendo
    \eqref{propsuc}. Neste caso, o conjunto \(S=\{w\in
    T\,\colon w <x\}\) não é bem ordenado pois o subconjunto
    \(\{y_1,y_2\}\not = \varnothing\) de \(S\) não possui um menor elemento.

    Para verificar a implicação reversa, observamos que se existe \(y\) satisfazendo
    \eqref{propsuc}, então \(h(x)=S(h(y))\). Do contrário, existe \(z\in T\) tal
    que \(h(y)<h(z)<h(x)\), implicando que \(y<z<x\). Absurdo.

  \item 
Vamos primeiro mostrar a existência de tal elemento \(z\): se \(x\) é sucessor
imediato de \(y\) então basta tomar \(z=x\). Caso contrário,
existe \(w\) com \(y < w < x\). Sabendo que o conjunto \(\{t \in T\,\colon t
<x\}\) é bem ordenado, concluímos que \(A = \{ t \in T
\,\colon y < t < x\}\), que é não vazio pois \(w\in A\), tem um menor elemento. Seja
\(z\) o mínimo de \(A\). Afirmamos que \(z\) é sucessor imediato de \(y\).
De fato, temos que \(y < z < x\) pois \(z \in A\). Além disso, se \(z\) não
fosse sucessor imediato de \(y\), existiria \(w^\prime\) com
\(y< w^\prime<z<x\), implicando que \(w^\prime\in A\). Absurdo, pois \(z\) é o mínimo de \(A\).


Para a unicidade de \(z\), basta notar que se existem \(z_1,z_2\) satisfazendo
as propriedades dadas no enunciado, então o conjunto
\(\{z_1,z_2\}\) não tem um menor elemento uma vez que \(h(z_1)=h(z_2)\). Como
\(\varnothing\not=\{z_1,z_2\}\) está contido em \(\{t \in T\,\colon t
<x\}\), que é bem ordenado, temos um absurdo.

  \item  Por definição, \(h(T)\) é o menor ordinal
    \(\alpha\) tal que \(T_\alpha=\varnothing\). Sendo assim, podemos ver que
    \[h(T)\geq \alpha +1 \text{ para cada } \alpha \text{ tal que }
      T_\alpha\not=\varnothing,\]
    e que
    \[h(T)\geq h(x)+1\text{ para cada } x\in T.\]
    Daí segue que
    \[h(T)\geq \sup\{\alpha+1\,\colon T_\alpha\not=\varnothing\}\text{ e que }
      h(T)\geq\sup\{h(x)+1\,\colon x\in T\}.\]
    Por fim, suponha que
    \[h(T)> \sup\{\alpha+1\,\colon T_\alpha\not=\varnothing\}\text{ ou } h(T)
      >\sup\{h(x)+1\,\colon x\in T\}\]
    e note que em ambos os casos, segue que \(T_\beta=\varnothing\) para algum \(\beta<
    h(T)\). Absurdo.\qedhere
\end{enumerate}
\end{proof}
\begin{exercicio}
    Seja \((T,\leq)\) uma árvore. Mostre que:
    \begin{enumerate}[(i)]
    \item Cada cadeia em \(T\) é bem-ordenada;
    \item Se \(b\) é um ramo de \(T\) e \(x\in b\), e \(y<x\), então \(y\in b\);
    \item Se \(b\) é um ramo em \(T\), então \(\card{b\cap T_\alpha}=1\) para
      \(\alpha <\ell (b)\) e \(\card{b\cap T_\alpha}=0\) para \(\alpha
      >\ell (b)\). Conclua que \(\ell (b)\leq h(T)\);
    \item \(h(T)=\sup\{\ell (b)\,\colon b \text{ é um ramo de } T\}\);
    \item \(T_\alpha\) é uma anticadeia para cada \(\alpha < h(T)\).
     \end{enumerate}
  \end{exercicio}
  \begin{proof}[Solução]\hfill
    \begin{enumerate}[(i)]
      \item  Seja \(C\subseteq T\) uma cadeia e seja
        \(\varnothing\not = S\subseteq C\). Vamos provar que \(S\) possui um menor
        elemento.

        Seja \(y\in S\). Se \(y\) é o menor elemento de \(S\) então a prova está
        completa. Caso contrário, temos que existe \(x\in S\) tal que \(x<y\). Assim,
         o conjunto \(S_{y} =\{z\in S\,\colon z<y\}\) é não vazio. Além disso, como
         \(S_y\) está contido em \(\{z\in T\,\colon z<y\}\), que é bem ordenado por
         definição, obtemos que \(S_y\) possui um menor elemento \(m\).

         Por fim, vamos mostrar que \(m\) é o menor elemento de \(S\). De fato, se
         \(s\in S\) então ou \(y \leq s\) ou \(s<y\), pois \(S\subseteq C\), que é uma cadeia.
         Se \(y \leq s\) então \(m<y\leq s\). Por outro lado se
         \(s<y\) então \(s\in S_{y}\), e assim \(m\leq s\). De toda forma, temos que
         \(m\leq s\). Logo,  \(m\) é o menor elemento de \(S\).

       \item Suponha que \(y\not\in b\). Vamos mostrar que \(y\) é comparável
        a todos os elementos de \(b\). Se \(z\in b\) e \(z < x\), temos que
        \(y\) e \(z\) são comparáveis pois ambos pertencem ao conjunto \(\{w\in
        T\,\colon w< x \}\), que é bem ordenado, e em particular, linearmente
        ordenado. Caso \(x<z\), obtemos que \(y<z\) por transitividade. Assim,
        concluímos que \(b\cup\{y\}\) é uma cadeia e portanto \(b\) não é
        maximal. Absurdo.

 
        \item Vamos começar mostrando que \(\card{b \cap T_\alpha} \leq 1\), para cada
\(\alpha\) ordinal. De fato, suponhamos por absurdo que \(\card{b \cap T_\alpha} \geq
2\) para algum \(\alpha\). Tome \(x,y \in b \cap T_\alpha\) tais que \(x \neq
y\). Como \(b\) é uma cadeia, temos que \(x<y\) ou \(y<x\). Assumindo sem perda
de generalidade que \(x < y\), segue que \(\{t \in T\,\colon t < x\} \subsetneq
\{t \in T\,\colon t < y\}\) e então  \(\alpha = h(x) < h(y) = \alpha\), absurdo.

Agora seja \(\alpha > \ell(b)\) e suponhamos por absurdo que \(\card{b \cap T_\alpha} = 1\).
Logo existe \(u \in T_\alpha\) tal que \(u \in b\), pelo item (ii) do Exercício
3.2, segue que \(\{t \in T\,\colon t < u\} \subset b\), donde \(h(u) \leq
\ell(b)\), mas \(u \in T_\alpha\) e então \(\alpha = h(u) \leq \ell(b)\), impossível.
Assim, como \(\card{b \cap T_\alpha}\leq 1\) e \(\card{b \cap T_\alpha} \not
=1\), devemos ter \(\card{b \cap T_\alpha} = 0\).

Para o caso \(\alpha<\ell(b)\) faremos por indução%\footnote{Para formalizar
%  melhor, aqui nos faltou alguma
%técnica que nos possibilitasse usar recursão quando \(\alpha\) é ordinal limite.
%Em todas nossas outras demonstrações, buscamos usar técnicas que contornassem
%esse problema}.

Claramente quando \(\alpha = 0\) é verdade. Seja \(\alpha < \ell(b)\) fixado e
\(\card{b \cap T_\beta} = 1\), para \(\beta < \alpha\).
Definimos \(r(\beta)\in T_\beta\cap b\). Logo temos uma função \(r\colon\alpha\to T^{(\alpha)}\cap b\) que é bijetora
pois se \(r(\beta)=r(\lambda)\doteq y\), temos que \(y\in T_\beta\cap T_\lambda\cap b\)
\red{TERMINAR} Concluímos que \(r\) é injetora. 
Vejamos a sobrejetividade: se \(x\in
T_\alpha\cap b=\bigcup_{\beta<\alpha}T_\beta\cap b,\) logo existe \(\beta\) tal que \(x\in
T_\beta\cap b\) e assim \(x=r(\beta)\).

Evidentemente, para todo \(\lambda<\alpha,h(r(\lambda))=\lambda\). Desta forma, \(r\) é um
isomorfismo. Como \(\alpha<\ell(b)\), então \(b\setminus (T^{(\alpha)}\cap b)\neq\varnothing\).
Existe assim \(z\in b\cap T_\gamma\) para algum \(\gamma\geq\alpha\). Se \(\gamma>\alpha,\)
então existe \(p\in \{\zeta\in T:\zeta<z\}\) tal que \(\{\zeta\in T:\zeta<p\}\) é isomorfo à
\(\alpha\), observe que isso é possível pois \(\{\zeta\in T:\zeta<z\}\) e \(\alpha\) são bem
ordenados. Portanto \(p<z\in b\) implica que \(p\in b\). Além do mais, \(h(p)=\alpha\).
Se \(\gamma=\alpha\), tome \(p\doteq z\) e teremos que \(p\in b\) e \(h(p)=\alpha\).


\par 
%\textit{Caso 1}
%Quando \(\alpha\) é limite.
%Da identidade \(b = \bigcup_{y \in b} \succc{y}\) e pelo fato de estarem
%encaixados,\(\ell(b) = \sup_{y \in b}h(y)\), donde existe \(y \in b\) com \(\alpha < h(y)\).
%Mas \(\succc{y} \subset b\). Como vale a identidade \(b = \bigcup_{y \in b}
%\succc{y}\) e esses conjuntos são
%encaixados e cada um é bem ordenado, segue que que os antecessores de \(y\) com
%nível \(h(y) > \alpha\) tem intersecção não vazia com \(T_\alpha\). 
%\par 
%\textit{Caso 2}
%Digamos \(\alpha = \gamma+1\) e portanto, \(\card{b \cap T_\gamma} = 1\).
%Tome \(y \in b \cap T_\gamma\), de modo que \(\{t \in T\,\colon t \leq y\}
%\subset b\). Mas \(\ell(b) > \alpha >\gamma\), donde existe \(x \in b, x > y\).
%Pelo item (v) do  Exercício 3.1, existe um único \(z \in T\) tal que \(y < z
%\leq x\) e \(z\) é sucessor imediato de \(y\).
%Como \(b\) é maximal, segue que \(z \in b\).
%Além disso, \(h(z) = h(y) + 1 = \gamma + 1 = \alpha\), donde \(z \in b \cap T_\alpha\).
%Segue que \(\card{b \cap T_\alpha} = 1\).

Se \(\alpha\geq h(T)\), então \(T_\alpha=\varnothing\). Logo não pode valer que
\(\alpha<\ell(b)\), e então \(\alpha\geq\ell(b)\) donde \(h(T)\geq\ell(b)\).

% O caso \(\alpha<\ell(b)\) será feito por indução. Claramente quando \(\alpha = 0\) é
% verdade. Seja \(\alpha < \ell(b)\) fixado e \(\card{b \cap T_\beta} = 1\), para
% \(\beta < \alpha\).
% \textbf{Caso \(\alpha\) é ordinal sucessor:}
% Digamos \(\alpha = \gamma+1\) e portanto, \(\card{b \cap T_\gamma} = 1\). Tome
% \(y \in b \cap T_\gamma\), de modo que \(\{t \in T\,\colon t \leq y\} \subset
% b\). Mas \(\ell(b) > \alpha > \gamma\), donde existe \(x \in b, x > y\). Pelo
% item (iv) do Exercício 3.1, existe um único \(z \in T\) tal que \(y < z \leq x\)
% e \(z\) é sucessor imediato de \(y\). Pela maximidade de \(b\), segue que \(z
% \in b\). Além disso, \(h(z) = h(y) + 1 = \gamma + 1 = \alpha\), donde \(z \in b
% \cap T_\alpha\). Segue que \(\card{b \cap T_\alpha = 1}\).\\

% \textcolor{red}{Falta o quando \(\alpha\) é ordinal limite.}
        
      \item Como observamos anteriormente, temos que  \(\ell (b)\leq h(T)\) para
        todo ramo \(b\) de \(T\). Este fato nos permite concluir que
        \[h(T)\geq\sup\{\ell(b)\,\colon b \text{ é um ramo de } T\}\]
        Assim nos resta verificar que \(h(T)\) é de fato o menor dos majorantes
         de \(\{\ell(b)\,\colon b \text{ é um ramo de } T\}\). Isto é, vamos
         provar que se \(\alpha\geq  \ell (b)\)
        para todo ramo \(b\) de \(T\), então \(\alpha\geq h(T)\).
        
        De fato, se \(x\in T\), tome \(b_x\) um ramo de \(T\) tal que \(x\in b_x\) \red{pelo lema
        de zorn né?}. Como \(\{\zeta\in T:\zeta<x\}\subsetneq b_x\), temos que \[h(x)<h(x)+1\leq
        \ell(b_x)\leq\alpha\]
        Assim, pleo exercício 3.1.(vi), \(h(T)\leq\alpha\).
        

      \item Seja \(\alpha < h(T)\) e assuma que existem \(x,y\in T_\alpha\)
          distintos tal que \(x\) e \(y\) são comparáveis.
          Suponha sem perda de generalidade que
          \(x<y\). Neste caso, temos que \(x<y\) mas \(h(x)=h(y)\). Absurdo, pois
          \(x<y\) implica que \(h(x) < h(y)\).\qedhere

    \end{enumerate}
  \end{proof}

  Agora vamos olhar para alguns exemplos de árvores:
  \begin{exemplo}\hfill
    \begin{enumerate}[(a)]
    \item Todo conjunto bem-ordenado \((W,\leq)\) é uma árvore. Sendo assim,
      podemos pensar em árvores como generalizações de boas ordens. A altura
      \(h(W)\) é o tipo de ordem de \(W\), e o único ramo de \(W\) é o próprio
      \(W\), que é cofinal.
    \item Seja \(\lambda\) um número ordinal e seja \(A\) um conjunto não-vazio.
      Defina \(A^{< \lambda}=\bigcup_{\alpha < \lambda} A^\alpha\) como o
      conjunto de todas as sequências transfinitas de elementos de \(A\) com
      comprimento menor que \(\lambda\). Considere \(T=A^{< \lambda}\) e o
      ordene segundo \(\subseteq\). Assim, para quaisquer \(f,g\in T\),
      temos \(f\leq g\) se, e somente se \(f\subseteq g\), o que significa que
      \(f=\rest{g}{\dom(f)}\). É fácil verificar que \((T,\subseteq)\) é uma árvore:
      Primeiro, note que a sequência vazia é o menor elemento de \(T\). Além
      disso, para cada \(f\in T\), o conjunto \(\{x\in T\,\colon x < f\}\) é
      bem-ordenado pois, para qualquer um de seus subconjuntos, a sequência de
      menor comprimento é o menor elemento.

      Também é imediato que para cada \(f\in T\),
      temos que \(h(f)=\alpha\) se, e somente se \( f\in A^\alpha\). Isto é,
      \(T_\alpha =A^\alpha\). Ademais, se \(\alpha\) e \(\beta\) são ordinais
      tais que \(\alpha =\beta +1\) e \(f\in A^\alpha\), a sequência
      \(\rest{f}{\beta}\) é o antecessor imediato de
      \(f\) e os elementos de \(f\cup \{\langle \beta ,\alpha \rangle\}\) são
      sucessores imediatos de \(f\).

      Por fim, observemos que existe uma  correspondência biunívoca entre os
      ramos de \(T\) e as funções de \(\lambda\) em \(A\):
      se \(f\in A^\lambda\) então \(\{{\rest{f}{\alpha}\,\colon\alpha <\lambda}\}\) é
      um ramo em \(T\). Por outro lado, se \(b\) é um ramo em
      \(T\) então \(b\) é um sistema compatível de funções
      e \(f=\bigcup_{g\in b} g\in A^\lambda\). Vale notar que todos os ramos de \(T\) são
      cofinais, uma vez que possuem comprimento \(\lambda=h(T)\).
      
    \item Generalizando o exemplo anterior, se
      \(T\subseteq A^{<\lambda}\) é uma subárvore de 
      \((A^{<\lambda},\subseteq)\) com altura \(h(T)=\alpha\), então existe uma
      correspondência biunívoca entre os ramos de \(T\) e as funções
      \(f\in A^{<\lambda}\cup A^\lambda\) satisfazendo cada uma das seguintes
      propriedades:
      \begin{enumerate}[(i)]
      \item \(\rest{f}{\alpha}\in T\) para todo \(\alpha \in \dom(f)\);
      \item \(f\not\in T\) ou \(f\in T\) e \(f\) não possui sucessores em \(T\). 
      \end{enumerate}
     Nessa situação, costuma-se identificar um  ramo utilizando sua função correspondente.

   \item Consideremos o conjunto
    \(T\subseteq \Naturals^{<\omega}\)
     das sequências de números naturais que são finitas e
    decrescentes, ou seja, \(f\in T \) se, e somente se  \(f(i)>f(j)\)  para todo
    \(i<j<\dom(f)\in\Naturals\).  Então \((T,\subseteq)\) é uma subárvore de
    \((\Naturals^{<\omega},\subseteq)\). Note que a altura de  \(T\) é 
    \(\omega\). Além disso, temos pelo Exercício 2.8 do Capítulo 3 que não
    existe uma sequência de números naturais que seja infinita e decrescente.
    Assim conseguimos concluir que todos os ramos de \(T\) são finitos, o
    que implica que \(T\) não possui ramos cofinais.

  \item Seja \((R,\leq)\) um conjunto linearmente ordenado.
    Uma \emph{representação} de uma árvore \((T,\preceq)\)
    \emph{por intervalos} em \((R,\leq)\) é uma função \(\Phi\) tal que para
    quaisquer \(x,y\in T\),
    suas imagens \(\Phi(x)\) e \(\Phi(y)\) são intervalos em \((R,\leq)\) satisfazendo:
    \begin{enumerate}[(i)]
    \item \(x\preceq y\) se, e somente se \(\Phi(x)\supseteq\Phi(y)\); 
    \item \(x\) e \(y\) são incomparáveis se, e somente se \(\Phi(x)\cap\Phi(y) =\varnothing\).
    \end{enumerate}
    Em particular, as propriedades acima implicam que \((\Phi[T],\supseteq)\) é
    uma árvore isomorfa a \((T,\preceq)\). Por exemplo, se considerarmos
    a árvore \(S=\text{Seq}(\{0,1\})=\{0,1\}^{<\omega}\) ordenado por \(\subseteq\),
    então o sistema do conjunto de Cantor \(\langle D_s \,\colon s\in S\rangle\) construído no Exemplo
    3.18 do  Capítulo 10 é uma representação de \((S,\subseteq)\) por intervalos
    fechados na reta real.
    \end{enumerate}
  \end{exemplo}
  
  O estudo de árvores finitas é um dos  principais conceitos que aparecem em
  combinatória. Entretanto, não vamos nos aprofundar muito no tema. Ao invés
  disso, vamos investigar algumas propriedades árvores infinitas, nos preocupando
  especialmente com condições suficientes para que uma árvore possua um ramo cofinal.

  Para árvores cuja altura é um ordinal sucessor a resposta é óbvia: se \(h(T)=\alpha +1\),
  então \(T_\alpha\neq\varnothing\) e para qualquer \(x\in T_\alpha\) temos que
  \({{y\in T \,\colon y\leq x}}\) é ramo cofinal de \(T\). Assim, focaremos em
  árvores cuja altura é um limite. Por outro lado, o item (d) do Exemplo 3.2 nos diz que
  existem árvores de altura \(\omega\) que possuem apenas ramos finitos. O
  próximo teorema mostra que,  pensando na largura de uma árvore como um
  majorante para a cardinalidade de seus níveis, se uma aŕvore \(T\) de altura
  enumerável é suficientemente "esguia", então \(T\) possui um ramo cofinal.

  \begin{teo}[Lema de König]
  Seja \((T,\leq)\) uma árvore de altura \(\omega\). Se todos os níveis de \(T\) são finitos, então
  \(T\) admite um ramo de altura \(\omega\).
  \end{teo}
\begin{proof}
  Em primeiro lugar, observamos que se  \(T\) é uma árvore, então cada nó de \(T\) possui
  um número finito de sucessores imediatos se, e somente se todos os níveis de
  \(T\) são finitos. Ancorados neste fato, vamos mostrar que se \(T\) é uma
  árvore de altura \(\omega\) tal que cada nó tem um número finito de sucessores
  imediatos,  então \(T\) tem um ramo infinito. De fato, vamos utilizar recursão
  para  construir uma sequência \(\langle c_n\rangle_{n=0}^{\infty}\)  de nós de
  \(T\) tal que, para todo \(n<\omega\), o conjunto \(\{a\in T\,\colon c_n\leq a\}\) é
  infinito.

  Seja \(c_0\) a raiz de T e  note que \(\{a \in T\,\colon c_{0} \leq a \}= T\)
  é infinito. Além disso, se \(\{a\in T\,\colon c_n\leq a\}\) é infinito para
  \(n<\omega\) e consideramos  o
  conjunto \(S_n\) dos sucessores imediatos de \(c_n\), então
  \[
  \{a\in T\,\colon c_n\leq a\} = \{c_n\} \cup\bigcup_{b\in S_n} \{a\in T\,\colon b\leq a\}.
  \]
 Daí segue que existe \(b\in S_n\) tal que o conjunto \(\{a\in T\,\colon
 b\leq a\}\) é infinito, assim podemos utilizar o Axioma da Escolha para
 tomar \(c_{n+1}\) um tal \(b\). 
 Finalmente, temos que
  \[r\doteq\{a\in T\,\colon a\leq c_n \text{ para algum }
    n\in\Naturals\}=\bigcup_{n <\omega}\{a\in T\,\colon a\leq c_n\}\]
  é um ramo infinito de \(T^{(\omega)}=T\).
  Com efeito, sejam \(x,y\in r\), então
  \(x\leq c_n\) e \(y\leq c_m\) para algum \(n,m\in\Naturals\).
  Tomemos \(p=\max\{n,m\}\) e temos \(x,y\leq c_p\), portanto ou \(x\leq y\) ou
  \(y\leq x\) pois \(T^{(p)}\) é uma árvore. \(r\) é maximal pois seja
  \(r\subsetneq C\) cadeia, assim se \(z\in C\setminus r\), \(z>c_n\) para todo \(n\in\Naturals\).
  Desse modo, \(h(z)\geq n\) para todo \(n\in\Naturals\) e temos
  \(h(z)\geq\omega=h(T)\), absurdo.
  \end{proof}

    Em especial, observe que usamos o Teorema da Recursão sem
    explicitamente especificar uma função \(g\) para
    calcular \(c_{n+1}\) a partir de \(c_n\). De fato, para construir tal função precisamos
    aplicar o Axioma da Escolha: se \(k\) é uma função escolha para
    \(\mathcal{P}(T)\) e \(S_c\) é o conjunto de todos os sucessores imediatos
    de \(c\), então definindo \(g(c,n) \coloneqq k\big ( \{b\in S_c\,\colon
    \{a\in T: b\leq a\} \text{ é infinita}\}\big )\) temos que \(c_{n+1} =
    g(c_n, n)\). Nesse  cenário, estamos
    de acordo com o Teorema da Recursão que vimos. No próximo exercício veremos que,
    se \(T\) é uma árvore com `largura finita', então \(T\) possui um ramo
    cofinal não importando sua altura. Nesse sentido, o resultado a seguir é uma
    generalização do Lema de König.
  
\begin{exercicio}
  Seja \(\kappa\) um cardinal infinito e seja \((T,\leq)\) uma árvore de altura
  \(\kappa\). Prove que se todos os níveis de \(T\) são finitos, então \(T\)
  possui um ramo de tamanho \(\kappa\).
  
  \emph{Dica: Seja \(U_\alpha=\{x\in T_\alpha\,\colon\card{\succc{x}}=\kappa\}\). Prove que
  \(\{\card{U_\alpha},\alpha<\kappa\}\subset\Naturals\) é limitado. Seja M o seu
  máximo, mostre que \(T\) possui exatamente M ramos de tamanho \(\kappa\)}.
\end{exercicio}
\begin{proof}[Solução]
    Observamos que a dica não vale em geral: Seja
    \(T\) a árvore cujos nós possuem somente 2 sucessores imediatos.
    \(h(T)=\omega\) e cada nível \(T_n\) é   tal que \(\card{T_n}=2^n\),
    então \(U_n=\{x\in T_n\,\colon\card{y\in T\,\colon x\leq y}=\kappa\} =T_n\)
      de modo que \(\card{U_n}=\card{T_n}=2^n\) iremos demonstrar por partes:
  \begin{enumerate}[(i)]
      \item Para \(\text{cf}(\kappa)<\omega\)
      
      Agora como \(\text{cf}(\kappa)<\omega\), tomemos \((\alpha_n)_\Naturals\)
      sequência crescente cofinal, podemos tomar \(\alpha_0=0\).
      Por indução, construímos \(c_n\in T{\alpha_n}\) crescente tal que
      \(\card{\succc{c_n}}=\kappa\). Uma vez feito isso, definamos
      \(b=\{y\in T\,\colon y<c_n\text{ para algum
      }n\in\Naturals\}=\bigcup_{i<n}c_i\). Então \(b\) será ramo
      (não é difícil mostrar que b é maximal) e o  comprimento
      \(\ell(b)=\kappa\). Seja \(c_0\) a raiz de \(T\), então observemos que \mbox{\(S_n\coloneqq\{y\in
      T\,\colon y\geq c_n\}\cap T_{\alpha_{n+1}}\neq\varnothing\),}
      pois pelo exercício anterior, se fosse vazio, então
      \mbox{\(\{y\in T\,\colon c_n\leq y\}\subset T^{(\alpha_{n+1})}\)} e como todos os
      níveis são finitos e \(\alpha_{n+1}<\kappa\) então
      \(\card{T^{(\alpha_{n+1})}}<\kappa\), o que não pode ser pela definição de
      \(c_n\). Observamos que existe \(y\in S_n\) tal que
      \(\card{\succc{y}}=\kappa\) pois caso contrário
      \(\succc{c_n}=\big(\succc{c_n}\cap T^{(\alpha_{n+1})}\big)\cup\{\zeta\in
      T\,\colon x <\zeta\text{ para
        algum }x\in S_n\}\) e portando\(\card{\succc{c_n}}\neq\kappa\).
      Assim tome \(c_{n+1}\in S_n\) tal que \(\card{\succc{c_{n+1}}}=\kappa\).

      \item Para \(\text{cf}(\kappa)>\omega\), mostraremos que o conjunto
      \(\{\card{U_\alpha\,\colon\alpha<\kappa}\}\) é limitado em \(\Naturals\). Suponha que
      \mbox{\(\{\card{U_\alpha\,\colon\alpha<\kappa}\}\)} não é limitado, tome
      \(\alpha_n\) tal que \(\alpha_n\) é a menor solução para
      \(\card{U_\alpha}\geq n\). Vejamos que \(\alpha_n\) é sequência cofinal em \(\kappa\)
      pois para todo \(\lambda<\kappa\), \(U_\lambda\) é finito e para
      \(l=\card{U_\lambda},\alpha_{l+1}>\lambda\) por construção.
      Estabelecida a dica, seja \(M=\max\{\card{U_\beta},\beta<\kappa\}\) e
      \(\overline{\alpha}\) tal que
      \(\card{U_{\overline{\alpha}}}=M\). Mostraremos que para
      todo \(\alpha>\overline{\alpha}\), existe \(
      f=f_{\overline{\alpha},\alpha}\colon U_{\overline{\alpha}}\rightarrow U_\alpha\) bijeção tal que
      \(f(x)\geq x,\forall x\). Fixado \(x\in U_{\overline{\alpha}}\),
      observemos que analogamente ao que foi
      feito anteriormente
      (\(c_n=x, c_{n+1}=f(x),\alpha_n=\overline{\alpha}, \alpha_{n+1}=\alpha\)), temos f
      com as propriedades. Agora vamos mostrar \(f\) injetora. Supõe
      \(f(x)=f(y)=z\implies z\geq x, z\geq
      y\implies x=y\) pois \(x,y\in T_{\overline{\alpha}}\) e \(T\) é uma
      árvore. \(f\) é sobrejetora pois
      \(\card{U_{\overline{\alpha}}}\geq\card{U_\alpha}\in\Naturals\).
      Por fim, para \(x\in U_{\overline{\alpha}}\) defina \[b_x\coloneqq
      \{f_{\overline{\alpha},\beta}(x)\,\colon\beta>\overline{\alpha}\}\cup\{y\in T\,\colon y\leq x\}\].
      Observe que \(b_x\) é ramo pois \(\overline{\alpha}<\beta<\gamma\) implica que
      \(f_{\beta,\gamma}(f_{\overline{\alpha},\beta}(x))=f_{\overline{\alpha},\gamma}(x)\)
      pois ambos são  maiores que \(x\) e
      \(\card{U_{\overline{\alpha}}}=\card{U_\gamma}\) e  \(T\) é uma árvore.
      
      Assim provamos e observe que \(\ell(b_x)=\kappa\), nos permitindo
      finalmente concluir que existe um ramo com as
      propriedades desejadas e na verdade existem \(M\) deles.\qedhere
    \end{enumerate}
    \end{proof}
    
    \begin{proof}[Uma ideia alternativa usando conceitos de topologia]
      \footnote{Esta solução foi uma tentativa
    de usar o Teorema de Tychonoff
    neste contexto porém esta ideia não está completa e
    não deve ser considerada como uma demonstração e
    apenas um devaneio lúdico sobre uma possível aplicação deste
    resultado interessante de topologia.}
  
   Para demonstrar tal resultado, iremos visualizar os ramos dessa árvore como
   compactos contidos num espaço topológico produto.
   De fato, temos que se \(X=\Pi_{\alpha<\kappa}(T_\alpha\cup\{0\})\),
   onde \(0\) é um elemento que não faz parte do ambiente de \(T\),
   serve simplesmente para identificar a falta de nós sucessores, munido do
   produto  das topologias discretas, então o conjunto \(C\) dos ramos da árvore
   é identificado como
   \[C=\{(x_\alpha)_{\alpha<\kappa}\in X \,\colon x_\beta<x_{\beta+1}\text{ pra
     todo }\beta\},\] onde definimos \(0>x\text{ pra todo }x\in T\). Não é
 difícil ver que \(X\setminus C\) é aberto, pois seu complementar é formado
 pela união dos conjuntos  cujos elementos tem duas ``coordenadas'' seguidas em
 ordem decrescente.
   Portanto como \(X\) é compacto pelo
   Teorema de Tychonoff, \(C\) é compacto. Agora, queremos construir
   \(F_\lambda\subset C\) fechados encaixantes, então teremos que
   \(\bigcap F_\lambda\neq\varnothing\), e assim \(x\in\bigcap F_\lambda\) será o
   ramo que desejamos.
  
   Defina \(F_0\doteq C\). Indutivamente suponhamos \(F_\alpha\) bem definido
   para \(\alpha<\lambda\), de maneira tal que \mbox{\(\sup\{\ell(b)\,\colon b\in
   F_\alpha\}=\kappa\)} (Como visto n item (iv) do  Exercício 3.2).
   %falta definir ell(b)
   Como todo nó possui somente finitos sucessores imediatos, temos que
    existe \(a_\lambda\in T_\lambda\) de modo que quando definimos
   \[F_\lambda\doteq\{(x_\beta)\in C\,\colon
     x_\lambda=a_\lambda\}\bigcap_{\alpha<\lambda} F_\alpha\] temos que
   \(\sup\{\ell(b)\,\colon b\in F_\lambda\}=\kappa\), e não é difícil ver que 
   \(F_\lambda\) é fechado. Então temos que existe \(x\in\bigcap F_\lambda\), que
   será claramente o ramo de comprimento \(\kappa\).
  \end{proof}

  Os dois últimos resultados nos mostram que para uma árvore \((T,\leq)\) cuja altura é um
  ordinal limite maior ou igual a \(\omega\) com níveis finitos, então \(T\)
  possui um ramo cofinal. A partir deste ponto, podemos pensar em generalizações
  desta condição. Por exemplo, é natural que nos perguntemos se $T$ é uma árvore
  de altura $\kappa$, onde cada nível tem cardinalidade estritamente menor de
  que \(\kappa\), é verdade que $T$ tem um
  ramo de comprimento $\kappa$?  A resposta para tal pergunta é \textbf{NÃO!}

  \begin{definition}
    Seja \(\kappa\) um cardinal não enumerável.
    Uma árvore de altura $\kappa$ é uma \textit{árvore de Aronszajn} se
    todos os os seus níveis tem cardinalidade estritamente menor do que \(\kappa\)
    e se não possui ramos de comprimento $\kappa$.
  \end{definition}

 A seguir, vamos estudar mais a fundo o caso em que \(\kappa=\omega_1\). Nesta
  situação, conseguimos construir árvores de Aronszajn, que servem como
  contra-exemplo  para a indagação que propusemos acima.
  
    \begin{teo}
  Existem árvores de Aronszajn de altura \(\omega_1\).
    \end{teo}

\begin{proof}
  Vamos construir uma árvore \(T\) de Aronszajn construindo, para cada
  \(\alpha<\omega_1\), o nível \(T_\alpha\). Queremos que cada nível satisfaça:
  \begin{enumerate}[(i)]
    \item \(T_{\alpha} \subseteq \omega^{\alpha}\) e \(\card{T_{\alpha}} \le \aleph_0\);
    \item Se \(f \in T_{\alpha}\), então \(f\) é injetora e \(\omega\setminus \ran f\) é infinito;
    \item Se \(f \in T_{\alpha}\) e \(\beta < \alpha\) então \(\rest{f} {\beta} \in T_{\beta}\);
    \item Para qualquer \(\beta < \alpha\), qualquer \(g \in T_{\beta}\), e
    qualquer \(X \subseteq \omega\setminus \ran g\) finito, existe uma \(f \in
    T_{\alpha}\) tal que \(g \subseteq f\) de \(\ran f \cap X = \varnothing\).
    \end{enumerate}

    Em primeiro lugar, observe que uma vez demonstrada a existência de uma tal
    família se \(T=\bigcup_{\alpha<\omega_1} T_\alpha\), mostraremos que \(T\) é
    a árvore  de Aronszajn que desejamos. De fato, \((T,<)\) é um conjunto
    ordenado de acordo com a contenção de funções usual.
    
    Mostremos que \(T\) possui menor elemento. Se \(f\in T\), então
    \(\rest{f}{0}=\varnothing\) e temos que \(f\geq\varnothing\in T_0\subset
    T,\) além disso,  se \(x\in T\), então mostremos que \(A_x\coloneqq\{y\in
    T\,\colon y<x\}\) é bem ordenado. Para facilitar a notação, considere
    \(o\colon T\rightarrow \{\alpha<\omega_1\}\) tal que \(x\in T_{o(x)}\). Seja
    \(A\subset A_x\), assim defina \(A^\ast\coloneqq \{\alpha<\omega_1\,\colon
    x\in T_\alpha\cap A\}\). 
    Como os ordinais são bem ordenados, existe \(\beta\in A^\ast\) menor
    elemento de \(A^\ast\).
    Logo, se \(m\in T_\beta\cap A\), então para todo \(g\in A\) temos
    \(o(g)\geq\beta\),  e como \(\rest{f}{o(g)}=g\) e \(\rest{f}{\beta}=m\),
    \(\rest{g}{\beta}=\rest{f}{\beta}=m\). Portanto \(g\geq m\) e \(m\) é o
    menor elemento de \(A\).
    
    Para verificar que \(T\) é uma árvore de Aronszajn de altura \(\omega_1\),
    vejamos que, por (i), os níveis são enumeráveis. Por (iv), para todo
    \(\alpha<\omega_1, T_\alpha\neq\varnothing\), basta tomar \(\beta=0\) e
    \(X\) qualquer,  então \(h(T)=\omega_1\). Precisamos verificar que \(T\) não
    possui ramo de comprimento \(\omega_1\). De fato, se \(b\) fosse ramo com
    \(\ell(b)=\omega_1\), se \(F=\bigcup_{f\in b} f\), então mostraremos \(F\) é
    função injetora de \(\dom F=\bigcup_{\alpha<\omega_1}\alpha=\omega_1\) em
    \(\omega\):  \(F\) é função pois se \(\langle x,p\rangle,\langle
    x,q\rangle\in F,  \langle x,p\rangle\in f_p\in b\) e \(\langle x,q\rangle\in
    f_q\in b\). Como \(b\) é uma cadeia, temos que, sem perda de generalidade,
    \(f_p>f_q\). Assim \(\rest{(f_p)}{o(f_q)}=f_q\) então \(p=q\). Analogamente
    \(F\) é injetora. Absurdo.
    
    
    Seja \(T_0=\{\varnothing\}\). Assumindo que para todo \(\beta<\lambda,
    T_\beta\) satisfaz (i)-(iv), Então, se \(\lambda\) for ordinal sucessor,
    \(\lambda=\alpha+1\), para algum \(\alpha\), definimos
    \[T_{\alpha+1}=\{g\cup\{\langle \alpha, a\rangle\}\,\colon g\in
    T_\alpha \text{ e } a\in \omega\setminus\ran g\}\]
    
    Vamos verificar que \(T_{\alpha+1}\) satisfaz (i)-(iv):
    \begin{enumerate}[(i)]
    \item \(T_{\alpha+1}\subseteq\omega^{\alpha+1}\) por construção, e
      \(\card{T_{\alpha+1}}\leq\card{T_\alpha}\card{\omega} \le \aleph_0^2=\aleph_0\)
      \item Seja \(f\in T_{\alpha+1}\), então temos
        \(f=g\cup\{\langle\alpha,a\rangle\}\) 
        para alguma \(g\in T_\alpha \text{ e } a\in \omega\setminus\ran g\). Sabemos
        que \(g\) é injetora, assim, basta mostrarmos que \(a\neq g(\beta)\)
        para todo \(\beta<\alpha\), o que é verdade pela definição de \(a\)
      \item Seja \(f\in T_{\alpha+1}\), então temos
        \(f=g\cup\{\langle\alpha,a\rangle\}\) para
        alguma \(g\in T_\alpha \text{ e } a\in \omega\setminus\ran g\). Se
        \(\beta<\alpha+1,\) então \(\rest{f}{\beta}=\rest{g}{\beta}\in T_\beta\)
        pois \(\beta\leq\alpha\)
      \item Para qualquer \(\beta < \alpha+1\), qualquer \(g \in T_{\beta}\), e
    qualquer \(X \subseteq \omega\setminus \ran g\) finito, existe uma \(f \in
    T_{\alpha}\) tal que \(g \subseteq f\) de \(\ran f \cap X = \varnothing\).
    Seja \(a\in\omega\setminus(\ran f\cup X)\) (observe que isto
    é possível pois \(X\) é finito e \(\omega\setminus\ran f\) é infinito).
    Então teremos  que \(f\cup\{\langle\alpha,a\rangle\}\in T_{\alpha+1}\) é a
    funçãoque  desejamos
    \end{enumerate}
      
   Agora, vamos construir \(T_{\lambda}\) no caso em que \(\lambda\) é um ordinal
   limite. Considere um ordinal \(\beta< \lambda\), um nó \(g \in T_{\beta}\) e
   um conjunto \(X \subseteq \omega\setminus \ran g\) finito. Vamos construir uma
   função \(f = f(g, X)\) da seguinte maneira: fixe uma sequência
   crescente \(\langle \lambda_n \rangle_{n=0}^{\infty}\) tal que \(\lambda_0  =\beta\)
   e \(\sup\{\lambda_n\,\colon n \in \mathbb{N}\} = \lambda\). Seja
   \(f_0 = g \in T_{\lambda_0}\) e \(X_0 = X \subseteq \omega\setminus \ran f_0\). Tendo
   definido \(f_n \in T_{\lambda_n}\) e \(X_n\subseteq \omega\setminus \ran f_n\)
   finito, nós primeiro tomamos um conjunto \(X_{n+1} \supsetneq X_n\) finito tal
   que \(X_{n+1} \subseteq \omega\setminus \ran f_n\) (Note que por (ii) este último passo é
   possível porque o conjunto \(\omega\setminus\ran f_n\) é infinito).
   Feito isso, escolhemos \(f_{n+1} \in T_{\lambda_{n+1}}\) tal que \(f_{n+1}
   \supseteq f_n\) e  \(X_{n+1} \cap ranf_{n+1} = \varnothing\), o que é possível
   por (iv).
   
   Seja \(f = \bigcup_{n = 0}^{\infty}f_n\). Claramente \(f\colon \lambda\to
   \omega\) e  \(f\)  é injetora pois, como visto anteriormente, união de
   funções injetoras  encadeadas também é função injetora. Além disso, temos que
   \(\ran f \cap (\bigcup_{n = 0}^{\infty} X_n)= \varnothing\) pois se \(X\in
   X_k\) e  \(y\in X_k\cap\ran f_n,\) então seja \(m=\max\{k,n\}\), e temos que
   \(y\in X_m\cap\ran f_m=\varnothing\) (\(f_n\) e \(X_n\) estão encadeados).
   Portanto  \(\omega\setminus\ran f\) é infinito e \(\ran f \cap X
   =\varnothing\). Assim concluímos que \(f\) satisfaz (ii). Ademais, se  \(\beta <
   \lambda\), tome \(n\) tal que \(\beta < \lambda_n\), e teremos
   \(\rest{f} {\beta}= \rest{(f_{n})}{\beta}\in T_\beta\) e portanto (iii)
   também é satisfeito (Perceba que \(f_n\in T_{\lambda_n}\) e \(\lambda_n<\lambda\)).
   
   Definimos \(T_\lambda\coloneqq\big\{f(g,X)\,\colon g\in\bigcup_{\beta <
     \lambda} T_{\beta} \text{ e cada } X \subseteq \omega\setminus\ran
   g\big\}\). Portanto  (iv) também é satisfeito por construção. Falta verificar
   (i). Com efeito,
   \(\card{T_\lambda}\leq\card{\bigcup_{\beta<\lambda}T_{\beta}}\card{\mathcal
     P^f(\omega)} \le \card{\omega}\sum_{\beta<\lambda}\card{T_{\beta}}
   \le \aleph_0^2=\aleph_0\), onde \(\mathcal P^f\) indica o conjunto das partes finitas.
   
   Temos assim \(T\) árvore de Aronszajn de altura \(\omega_1\).
\end{proof}

 A questão da existência de árvores de Aronszajn é muito complicada e ainda não
 foi totalmente resolvida. De modo geral, dizemos que cardinais \(\kappa\)
 não-contáveis para os quais vale um  análogo do Lema de Kőnig, i.e., não
 existem árvores  de Aronszajn de altura \(\kappa\); dizemos que tais cardinais
 possuem a  \textit{propriedade de árvore}. O exercício a seguir nos mostra que
 cardinais singulares não satisfazem tal requisito.

 \begin{exercicio}
  Construa uma árvore de Aronszajn de altura \(\aleph_{\omega}\). Generalize
  para um cardinal singular \(\kappa\) qualquer.
\end{exercicio}
\begin{proof}[Solução]
Vamos demonstrar diretamente para \(\kappa\) cardinal singular.
 Primeiramente daremos a ideia da demonstração: Fixado \(\kappa\), queremos
 encontrar uma árvore \(T\) de altura \(\kappa\), cujos ramos têm comprimento
 estritamente  menor que \(\kappa\) mas que \(\sup \{\ell(b), b\text{ ramo de
 }T\}=h(T)=\kappa\). Faremos isso da seguinte maneira: Como \(\kappa\) é singular,
 então existe \(\{\alpha_\eta\,\colon\eta<\lambda\}\) onde \(\lambda<\kappa\)
 com \mbox{\(\sup\{\alpha_\eta\}=\kappa\)}. Assim basta construir uma árvore formada
 por  ramos ``disjuntos''  (cuja única intersecção é a raiz) com altura
 \(\alpha_\eta\)  para todo \(\eta<\lambda\). Agora construiremos tal árvore.
 
 Seja \(\kappa\) ordinal singular, e \(\lambda=cf(\kappa)<\kappa\). Então existe
 \(\{\alpha_\eta\,\colon \eta<\lambda\}\) subconjunto cofinal de \(\kappa\).
 Vamos considerar o seguinte
 conjunto: \[T\doteq\big\{f_{\eta,\beta}\text{ | }\eta<\lambda\text{ e
   }\beta<\alpha_{\eta}\}\cup\big\{\varnothing\big\}\]
   Onde \(f_{\eta,\beta}\colon\beta\to\kappa,\, f_{\eta,\beta}(0)=\eta,\, f_{\eta,\beta}(\gamma)=0\) para todo \(\gamma\neq0\). 
 Observe que \(T\) é ordenado pela ordem usual de funções e que para
 \(\varnothing\neq f,g\in T, f\leq g\) se, e somente se  \(f(0)=g(0)\) e
 \(\dom f\subseteq\dom g\).
 Vamos provar que \(T\) é uma árvore:  \(\{\varnothing\}\) é o menor elemento de
 \(T\). Seja \mbox{\(A_x=\{y\in T\,\colon y<x\}\)} e observe que \(A_x\) possui o mesmo
 tipo de ordem de  \(\dom x\), que é bem ordenado. Assim \(T\) é uma árvore. 
 
 Afirmamos que seus ramos são da forma \(b_\eta=\{f\in T\,\colon f(0)=\eta\}\) para algum
 \(\eta<\lambda\). Pois se \mbox{\(b_\eta=\{f\in T\,\colon f(0)=\eta\}\)} para algum
 \(\eta<\lambda\), sejam \(f,g\in b_\eta\), então \(f(0)=g(0)\) e como
 \(\dom g,\dom f<\alpha_\eta\), sem perda de generalidade,
 temos \(\dom f\subseteq\dom g\), logo \(f\leq g\). Além disso,
 note que \(b_\eta\) é
 maximal pois supondo \(b_\eta\subsetneq c\) com \(c\) cadeia, então segue que existe
 \(f\in c\) com \(f(0)\neq\eta\). Logo, \(f\) não é comparável com qualquer
 elemento de \(b_\eta\). Agora se \(b\) é ramo qualquer de \(T\), vamos provar
 que \(b\subset b_\xi\) para algum \(\xi<\eta\): De fato tome \(f\in b\) e
 \(\xi\doteq \eta_f=f(0)\), então se \(g\in b\), ou \(g\leq f\) ou \(g\geq f\)
 pois  \(b\) é uma cadeia. De toda forma, \(g(0)=f(0)=\xi\) implica que \( g\in
 b_\xi\). Como \(b\) é maximal e \(b\subset b_\xi\), obtemos que \(b=b_\xi\) pois
 \(b_\xi\) é ramo (maximal). 
 
 Observe que construímos \(T\) para que \(b_\eta=\{f\in T\,\colon f(0)=\eta\}\) tenha
 tipo de ordem \(\ell(b_\eta)=\alpha_\eta<\kappa\). Além disso
 \(h(T)=\sup\{\alpha_\eta\,\colon\eta<\lambda\}=\kappa\) e portanto \(T\) é
 árvore de Aronszajn de cardinalidade \(\kappa\) cardinal singular.
 
\end{proof}

Assim encerra-se a Seção 3 sobre árvores.
  \bibliographystyle{plain}
  \bibliography{sample}
\end{document}