Árvore (teoria dos conjuntos)

Em teoria dos conjuntos, uma árvore é um conjunto parcialmente ordenado (T, <) tal qual para cada t ∈ T, o conjunto {s ∈ T : s < t} é ordenado pela relação <. Frequentemente árvores são assumidas a ter apenas uma raiz (i.e. elemento minimal), como as questões típicas investigados neste campo são facilmente reduzidos a perguntas sobre árvores de única raiz.

Definição

Uma árvore é uma conjunto parcialmente ordenado (poset) (T, <) tal qual para cada t ∈ T, o conjunto {s ∈ T : s < t} é umarelação bem ordenada pela relação <. Em particular, cada conjunto bem-ordenado (T, <) é uma árvore. Para cada t ∈ T, a o tipo da ordem de {s ∈ T : s < t} é chamado de altura de t (denotado por ht(t, T)). A altura de T ela própria é ao menos ordinalmente maior que a altura de cada elemento de T. Uma raiz da raiz T é um elemento de altura 0. Frequentemente árvores são caracterizadas por terem apenas uma raiz.

Árvores com uma única raiz, em que cada elemento tem altura finita pode ser naturalmente visto como árvores enraizadas no sentido de teoria dos grafos, ou de teoria da ciência da computação: existe uma aresta de x para y se e somente se y é um sucessor direto de x (i.e., x<y,mas não há nenhum elemento entre x and y). De toda forma, se T é uma árvore de altura > ω, então não há nenhuma relação borda natural que vai fazerT uma árvore, no sentido da teoria dos grafos. Por exemplo, o conjunto $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ não tem uma relação natural de ponta, como não há predecessor para ω.

Um ramo de uma árvore é uma cadeia máxima na árvore (ou seja, qualquer dois elementos do ramo são comparáveis, e qualquer elemento da árvore não pertencente ao ramo é incomparável com pelo menos um elemento do ramo). A largura de um ramo é ordinal isso é ordem isomorfa para o ramo. Para cada ordinal α, o nível α-th de T é o conjunto de todos os elementos de T com altura α. Uma árvore é uma árvore-κ, para um número ordinal κ, se e somente se ele tiver altura κ e cada nível tem tamanho menor que a cardinalidade κ. A largura da árvore é o a maior cardinalidade de seus níveis.

Árvores de apenas uma raiz t ≤ ω formam um "meet-semilattice", onde o conhecedor (ancestral comum) é dada pelo elemento maximal de intersecção dos antepassados, que existe pois o conjunto de ancestrais não é vazio e finito bem ordenada, portanto, tem um elemento maximal. Sem uma única raiz, a intersecção dos ancestrais pode ser vazio (dois elementos não precisam ter antepassados comuns), por exemplo $\left\{a,b\right\}$ onde os elementos não são comparáveis; enquanto que, se há um número infinito de antepassados não há um elemento máximo– por exemplo, $\left\{0,1,2,\dots ,\omega _{0},\omega _{1}\right\}$ where $\omega _{0},\omega _{1}$ não são comparáveis.

Propriedades

Existem alguns problemas difíceis formulados recentemente na teoria da árvore infinita. Exemplos disto são a conjectura de Kurepa e a conjectura de Suslin. Ambos estes problemas são conhecidas por ser independente dos axiomas de Zermelo-Fraenkel. O lema de Konig afirma que cada árvore-ω tem um ramo infinito. Por outro lado, é um teorema de ZFE que há inúmeras árvores com ramos não há inúmeras e não há níveis incontáveis; tais árvores são conhecidas como árvores de Aronszajn. A κ-árvore de Suslin é uma árvore de altura κ que contem cadeia ou anticadeias de tamanho k. Em particular, se κ é singular (i.e. não regular) então existe uma árvore κ-Aronszajn e uma árvore κ-Suslin. Em fato, para um cardinal infinito κ, toda árvore κ-Suslin is uma árvore κ-Aronszajn (a "volta" dessa implicação não é verdadeira).

A conjectura Suslin foi inicialmente indicado como uma pergunta sobre determinada relação de ordem mas é equivalente à afirmação: Toda a árvore de altura ω₁ possui uma anticadeia de cardinalidade ω₁ ou um ramo de comprimento ω₁.

Árvore (teoria dos autômatos)

Seguir a definição de uma árvore é um pouco diferente do formalismo acima.Por exemplo, cada nó da árvore é uma palavra sobre o conjunto de número naturais (ℕ),que ajuda a esta definição a ser utilizado em Teoria dos autômatos.

Uma árvore é um conjunto T ⊆ ℕ^* tal que se t.c ∈ T, com t ∈ ℕ^* e c ∈ ℕ, então t ∈ T e t.c₁ ∈ T para todo 0 ≤ c₁ < c. Os Elementos de T são conhecidos como nós, e a palavra vazia ε é a (única) raiz de T. Para cada t ∈ T, o elemento t.c ∈ T é um sucessor de t em direção c. O número de sucessores de t é chamado de degrau, é representado como d(t). Um mó é a folha se ele não tem sucessores. Se cada nó de uma árvore tem um número finito de sucessores, então ele é chamado de 'finito' , caso contrário, um 'infinita ramificação' de árvore . Um caminho π é um subconjunto de T tal que ε ∈ π e para cada t ∈ T, ou t é uma folha ou existe um único c ∈ ℕ tal que t.c ∈ π. Um caminho pode ser um conjunto finito ou infinito. Se todos os caminhos de uma árvore são finitos, em seguida, a árvore é chamado finito, caso contrário, infinito.Uma árvore é chamado de 'totalmente infinito' se todos os seus caminhos são infinitos. Dado um alfabeto Σ, uma árvore Σ-rotulada é um par (T,V), onde T é uma árvoreV: T → Σ mapeia cada nó de T para um símbolo em Σ. Uma árvore rotulada define formalmente termos de estruturas de árvores usados comumente. Um conjunto de árvores rotuladas é chamado de 'linguagem árvore' .

Uma árvore é chamada ranqueada se houver uma ordem entre os sucessores de cada um de seus nós. A Definição acima de árvore sugere naturalmente uma ordem entre os sucessores, que podem ser usados para fazer a árvore classificada. As vezes, uma função extra Ar: Σ → ℕ é definida. Esta função associa um aridade fixo para cada símbolo do alfabeto. Nesse caso, cadat ∈ T tem que satisfazer Ar(V(t)) = d(t).

Por exemplo, a definição acima é utilizado na definição de uma autômato finito de árvore.

Exemplo

Seja T = {0,1}^* e Σ = {a,b}. Definimos uma rotulação V como segue: a rotulação de uma nó raiz é V(ε) = a e, para cada outro nó t ∈ {0,1}^*, os rotulados para seus nós sucessores são V(t.0) = a e V(t.1) = b. É evidente a partir da imagem que T forma uma (completa) árvore binária finita.

Referências

• Jech, Thomas (2002). Set Theory. [S.l.]: Springer-Verlag. ISBN 3-540-44085-2 
• Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. [S.l.]: North-Holland. ISBN 0-444-85401-0  Chapter 2, Section 5.
• Monk, J. Donald (1976). Mathematical Logic. New York: Springer-Verlag. 517 páginas. ISBN 0-387-90170-1 
• Hajnal, András; Hamburger, Peter (1999). Set Theory. Cambridge: Cambridge University Press. ISBN 9780521596671 

Ligações externas

• Sets, Models and Proofs by Ieke Moerdijk and Jaap van Oosten, see Definition 3.1 and Exercise 56 on pp. 68–69.
• tree (set theoretic) by Henry on PlanetMath
• branch by Henry on PlanetMath
• example of tree (set theoretic) by uzeromay on PlanetMath