En teoría de conjuntos , un árbol es un conjunto parcialmente ordenado ( T , <) tal que para cada t ∈ T , el conjunto { s ∈ T : s < t } está bien ordenado por la relación <. Con frecuencia se supone que los árboles tienen solo una raíz (es decir, elemento mínimo ), ya que las preguntas típicas investigadas en este campo se reducen fácilmente a preguntas sobre árboles de raíz única.
Un árbol es un conjunto parcialmente ordenado (poset) ( T , <) tal que para cada t ∈ T , el conjunto { s ∈ T : s < t } está bien ordenado por la relación <. En particular, cada conjunto bien ordenado ( T , <) es un árbol. Para cada t ∈ T , el tipo de orden de { s ∈ T : s < t } se denomina altura de t , denotada ht( t , T ). La altura de T en sí es el ordinal menos grande que la altura de cada elemento de T . Una raíz de un árbol T es un elemento de altura 0. Con frecuencia se supone que los árboles tienen una sola raíz. Los árboles en la teoría de conjuntos a menudo se definen para crecer hacia abajo, haciendo que la raíz sea el nodo más grande. [ cita requerida ]
Los árboles con una sola raíz pueden considerarse árboles con raíz en el sentido de la teoría de grafos de una de dos maneras: como un árbol (teoría de grafos) o como un grafo trivialmente perfecto . En el primer caso, el grafo es el diagrama de Hasse no dirigido del conjunto parcialmente ordenado, y en el segundo caso, el grafo es simplemente el grafo subyacente (no dirigido) del conjunto parcialmente ordenado. Sin embargo, si T es un árbol de altura > ω , entonces la definición del diagrama de Hasse no funciona. Por ejemplo, el conjunto parcialmente ordenado no tiene un diagrama de Hasse, ya que no hay predecesor de ω . Por lo tanto, en este caso se requiere una altura de ω como máximo.
Una rama de un árbol es una cadena máxima en el árbol (es decir, dos elementos cualesquiera de la rama son comparables, y cualquier elemento del árbol que no esté en la rama es incomparable con al menos un elemento de la rama). La longitud de una rama es el ordinal que es isomorfo en orden a la rama. Para cada ordinal α, el α-ésimo nivel de T es el conjunto de todos los elementos de T de altura α. Un árbol es un κ-árbol, para un número ordinal κ, si y solo si tiene altura κ y cada nivel tiene cardinalidad menor que la cardinalidad de κ. El ancho de un árbol es el supremo de las cardinalidades de sus niveles.
Cualquier árbol de una sola raíz de altura forma un semirretículo de encuentro, donde encuentro (ancestro común) está dado por el elemento máximo de la intersección de los ancestros, que existe como el conjunto de ancestros no está vacío y es finito y bien ordenado, por lo tanto tiene un elemento máximo. Sin una sola raíz, la intersección de los padres puede estar vacía (dos elementos no necesitan tener ancestros comunes), por ejemplo, donde los elementos no son comparables; mientras que si hay un número infinito de ancestros no necesita haber un elemento máximo, por ejemplo, donde no son comparables.
Un subárbol de un árbol es un árbol donde y está cerrado hacia abajo bajo , es decir, si y entonces . [ cita requerida ]
Existen algunos problemas bastante simples pero difíciles en la teoría de árboles infinitos. Ejemplos de esto son la conjetura de Kurepa y la conjetura de Suslin . Se sabe que ambos problemas son independientes de la teoría de conjuntos de Zermelo-Fraenkel . Por el lema de Kőnig , cada ω-árbol tiene una rama infinita. Por otro lado, es un teorema de ZFC que hay árboles incontables sin ramas incontables ni niveles incontables; tales árboles se conocen como árboles de Aronszajn . Dado un número cardinal κ, un árbol κ- Suslin es un árbol de altura κ que no tiene cadenas o anticadenas de tamaño κ. En particular, si κ es singular , entonces existe un árbol κ-Aronszajn y un árbol κ-Suslin. De hecho, para cualquier cardinal infinito κ, cada árbol κ-Suslin es un árbol κ-Aronszajn (lo inverso no se cumple).
La conjetura de Suslin fue planteada originalmente como una pregunta sobre ciertos ordenamientos totales , pero es equivalente a la afirmación: Todo árbol de altura ω 1 tiene una anticadena de cardinalidad ω 1 o una rama de longitud ω 1 .
Si ( T ,<) es un árbol, entonces el cierre reflexivo ≤ de < es un orden de prefijo en T . Lo inverso no se cumple: por ejemplo, el orden usual ≤ en el conjunto Z de números enteros es un total y por lo tanto un orden de prefijo, pero ( Z ,<) no es un árbol de teoría de conjuntos ya que, por ejemplo, el conjunto { n ∈ Z : n < 0} no tiene ningún elemento mínimo.
