Árvore (teoria dos conjuntos)

Na teoria dos conjuntos , uma árvore é um conjunto parcialmente ordenado ( T , <) tal que para cada tT , o conjunto { sT  : s < t } é bem ordenado pela relação <. Frequentemente assume-se que as árvores têm apenas uma raiz (ou seja, elemento mínimo ), pois as questões típicas investigadas neste campo são facilmente reduzidas a questões sobre árvores com uma única raiz.

Definição

Uma árvore é um conjunto parcialmente ordenado (poset) ( T , <) tal que para cada tT , o conjunto { sT  : s < t } é bem ordenado pela relação <. Em particular, cada conjunto bem ordenado ( T , <) é uma árvore. Para cada tT , o tipo de ordem de { sT  : s < t } é chamado de altura de t , denotado ht( tT). A altura de T em si é o menor ordinal maior que a altura de cada elemento de T . Uma raiz de uma árvore T é um elemento de altura 0. Frequentemente assume-se que as árvores têm apenas uma raiz. As árvores na teoria dos conjuntos são frequentemente definidas para crescer para baixo, tornando a raiz o maior nó. [ citação necessária ]

Árvores com uma única raiz podem ser vistas como árvores enraizadas no sentido da teoria dos grafos de duas maneiras: ou como uma árvore (teoria dos grafos) ou como um grafo trivialmente perfeito . No primeiro caso, o gráfico é o diagrama de Hasse não direcionado do conjunto parcialmente ordenado e, no segundo caso, o gráfico é simplesmente o gráfico subjacente (não direcionado) do conjunto parcialmente ordenado. No entanto, se T for uma árvore de altura > ω , a definição do diagrama de Hasse não funcionará. Por exemplo, o conjunto parcialmente ordenado não possui Diagrama de Hasse, pois não há predecessor para ω. Portanto, uma altura de no máximo ω é necessária neste caso.

Um ramo de uma árvore é uma cadeia máxima na árvore (isto é, quaisquer dois elementos do ramo são comparáveis ​​e qualquer elemento da árvore que não esteja no ramo é incomparável com pelo menos um elemento do ramo). O comprimento de um ramo é o ordinal que é ordem isomorfo ao ramo. Para cada α ordinal, o α-ésimo nível de T é o conjunto de todos os elementos de T de altura α. Uma árvore é uma κ-árvore, para um número ordinal κ, se e somente se tiver altura κ e cada nível tiver cardinalidade menor que a cardinalidade de κ. a largurade uma árvore é o supremo das cardinalidades de seus níveis.

Qualquer árvore de raiz única de altura forma um semilattice, onde o encontro (ancestral comum) é dado pelo elemento maximal de interseção de ancestrais, que existe como o conjunto de ancestrais não é vazio e finito bem ordenado, portanto, tem um máximo elemento. Sem uma única raiz, a interseção dos pais pode ser vazia (dois elementos não precisam ter ancestrais comuns), por exemplo onde os elementos não são comparáveis; enquanto que se houver um número infinito de ancestrais, não precisa haver um elemento maximal – por exemplo, onde não são comparáveis.

Uma subárvore de uma árvore é uma árvore onde e é fechada para baixo sob , ou seja, se e então .

Propriedades teóricas de conjuntos

Existem alguns problemas bastante simples, mas difíceis, na teoria da árvore infinita. Exemplos disso são a conjectura de Kurepa e a conjectura de Suslin . Ambos os problemas são conhecidos por serem independentes da teoria dos conjuntos de Zermelo-Fraenkel . Pelo lema de Kőnig , toda ω-árvore tem um ramo infinito. Por outro lado, é um teorema do ZFC que existem árvores incontáveis ​​sem ramificações incontáveis ​​e sem níveis incontáveis; essas árvores são conhecidas como árvores Aronszajn . Dado um número cardinal κ, uma árvore κ- Suslin é uma árvore de altura κ que não possui cadeias ou anticadeias de tamanho κ. Em particular, se κ for singularentão existe uma árvore κ-Aronszajn e uma árvore κ-Suslin. De fato, para qualquer κ cardinal infinito, toda árvore κ-Suslin é uma árvore κ-Aronszajn (o inverso não vale).

A conjectura de Suslin foi originalmente formulada como uma questão sobre certas ordenações totais , mas é equivalente à afirmação: Toda árvore de altura ω 1 tem uma anticadeia de cardinalidade ω 1 ou um ramo de comprimento ω 1 .

Veja também

Referências

  • Jech, Thomas (2002). Teoria dos Conjuntos . Springer-Verlag. ISBN 3-540-44085-2.
  • Kunen, Kenneth (1980). Teoria dos Conjuntos: Uma Introdução às Provas de Independência . Norte-Holanda. ISBN 0-444-85401-0.Capítulo 2, Seção 5.
  • Monk, J. Donald (1976). Lógica Matemática . Nova York: Springer-Verlag. pág. 517. ISBN 0-387-90170-1.
  • Hajnal, Andrés ; Hambúrguer, Peter (1999). Teoria dos Conjuntos . Cambridge: Cambridge University Press. ISBN 9780521596671.
  • Kechris, Alexander S. (1995). Teoria Clássica dos Conjuntos Descritivos . Textos de graduação em matemática 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9 .   

links externos

  • Sets, Models and Proofs de Ieke Moerdijk e Jaap van Oosten, ver Definição 3.1 e Exercício 56 nas pp. 68–69.
  • tree (conjunto teórico) por Henry em PlanetMath
  • ramo por Henry em PlanetMath
  • exemplo de árvore (conjunto teórico) por uzeromay em PlanetMath