Árbol (teoría de conjuntos)

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. ${\displaystyle \omega +1=\left\{0,1,2,\puntos ,\omega \right\}}$

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. ${\displaystyle \leq \omega}$${\displaystyle \izquierda\{a,b\derecha\}}$${\displaystyle \left\{0,1,2,\puntos ,\omega _{0},\omega _{0}'\right\}}$${\displaystyle \omega _ {0}, \ omega _ {0}'}$

Un subárbol de un árbol es un árbol donde y está cerrado hacia abajo bajo , es decir, si y entonces . ^{[ cita requerida ]}${\estilo de visualización (T,<)}$${\estilo de visualización (T',<)}$${\displaystyle T'\subseteq T}$${\estilo de visualización T'}$${\estilo de visualización <}$${\displaystyle s,t\en T}$${\displaystyle s<t}$${\displaystyle t\en T'\implica s\en T'}$

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 ω ₁ tiene una anticadena de cardinalidad ω ₁ o una rama de longitud ω ₁ .

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.

• Sea un número ordinal y sea un conjunto. Sea un conjunto de todas las funciones donde . Defina si el dominio de es un subconjunto propio del dominio de y las dos funciones coinciden en el dominio de . Entonces es un árbol de teoría de conjuntos. Su raíz es la única función en el conjunto vacío y su altura es . La unión de todas las funciones a lo largo de una rama produce una función de a , es decir, una secuencia generalizada de miembros de . Si es un ordinal límite , ninguna de las ramas tiene un elemento maximalista (" hoja "). La imagen muestra un ejemplo para y .${\estilo de visualización \kappa}$${\estilo de visualización X}$${\estilo de visualización T}$${\displaystyle f:\alpha \mapsto X}$${\displaystyle \alpha <\kappa}$${\displaystyle f<g}$${\estilo de visualización f}$${\estilo de visualización g}$${\estilo de visualización f}$${\estilo de visualización (T,<)}$${\estilo de visualización \kappa}$${\estilo de visualización \kappa}$${\estilo de visualización X}$${\estilo de visualización X}$${\estilo de visualización \kappa}$${\displaystyle \kappa =\omega \cdot 2}$${\displaystyle X=\{0,1\}}$

• Cada estructura de datos de árbol en informática es un árbol de teoría de conjuntos: para dos nodos , defina si es un descendiente propio de . Las nociones de raíz , altura de nodo y longitud de rama coinciden, mientras que las nociones de altura de árbol difieren en uno.${\estilo de visualización m,n}$${\displaystyle m<n}$${\estilo de visualización n}$${\estilo de visualización m}$

• Los árboles infinitos considerados en la teoría de autómatas (ver, por ejemplo, árbol (teoría de autómatas) ) también son árboles de teoría de conjuntos, con una altura de árbol de hasta .${\displaystyle \omega }$

• Un árbol de teoría de grafos se puede transformar en uno de teoría de conjuntos eligiendo un nodo raíz y definiendo si y se encuentra en la ruta (única) no dirigida de a .${\displaystyle r}$${\displaystyle m<n}$${\displaystyle m\neq n}$${\displaystyle m}$${\displaystyle r}$${\displaystyle n}$

• Cada árbol de Cantor , cada árbol de Kurepa y cada árbol de Laver es un árbol de teoría de conjuntos.

• Árbol (teoría descriptiva de conjuntos)
• Gráfico continuo

• Conjuntos, modelos y pruebas de Ieke Moerdijk y Jaap van Oosten, consulte la Definición 3.1 y el Ejercicio 56 en las págs. 68–69.
• árbol (teórico de conjuntos) por Henry en PlanetMath
• rama de Henry en PlanetMath
• Ejemplo de árbol (teoría de conjuntos) de uzeromay en PlanetMath