Árbol (teoría de conjuntos)

Una rama (resaltada en verde) de un árbol de teoría de conjuntos. Aquí los puntos representan elementos, las flechas representan la relación de orden y las elipses y las flechas discontinuas representan (posiblemente infinitos) elementos y relaciones no representados.

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 una sola raíz (es decir, un elemento mínimo ), ya que las preguntas típicas investigadas en este campo se reducen fácilmente a preguntas sobre árboles de una sola raíz.

Definición

Pequeños ejemplos finitos: los tres conjuntos parcialmente ordenados de la izquierda son árboles (en azul); una rama de uno de los árboles está resaltada (en verde). El conjunto parcialmente ordenado de la derecha (en rojo) no es un árbol porque x ₁ < x ₃ y x ₂ < x ₃ , pero x ₁ no es comparable a x ₂ (línea discontinua naranja).

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 llama altura de t , denotada ht( t ,  T ). La altura de T en sí es el mínimo ordinal mayor que la altura de cada elemento de T. La raíz de un árbol T es un elemento de altura 0. Con frecuencia se supone que los árboles tienen una sola raíz. En la teoría de conjuntos, los árboles a menudo se definen para crecer hacia abajo, haciendo de la raíz el nodo más grande. ^{[ cita necesaria ]}

Los árboles con una sola raíz pueden verse como árboles enraizados en el sentido de la teoría de grafos de una de dos maneras: ya sea como un árbol (teoría de grafos) o como un grafo trivialmente perfecto . En el primer caso, el gráfico es el diagrama de Hasse no dirigido del conjunto parcialmente ordenado, y en el segundo caso, el gráfico es simplemente el gráfico 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 existe un predecesor de ω. Por lo tanto, en este caso se requiere una altura de como máximo ω. ${\displaystyle \omega +1=\left\{0,1,2,\dots ,\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 de orden isomorfo 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 sólo 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 altura de raíz única forma una semirretícula de encuentro, donde el encuentro (ancestro común) está dado por el elemento máximo de intersección de ancestros, que existe ya que el conjunto de ancestros no está vacío y es finito y bien ordenado, por lo tanto, tiene un máximo elemento. Sin una única raíz, la intersección de los padres puede estar vacía (dos elementos no necesitan tener ancestros comunes), por ejemplo cuando los elementos no son comparables; mientras que si hay un número infinito de antepasados ​​no es necesario que haya un elemento máximo (por ejemplo, cuando no son comparables). ${\displaystyle \leq \omega }$ ${\displaystyle \left\{a,b\right\}}$ ${\displaystyle \left\{0,1,2,\dots ,\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 debajo de , es decir, si y entonces . ^{[ cita necesaria ]} ${\displaystyle (T,<)}$ ${\displaystyle (T',<)}$ ${\displaystyle T'\subseteq T}$ ${\displaystyle T'}$ ${\displaystyle <}$ ${\displaystyle s,t\in T}$ ${\displaystyle s<t}$ ${\displaystyle t\in T'\implies s\in T'}$

Propiedades de la teoría de conjuntos

Hay algunos problemas bastante simples pero difíciles en la teoría del árbol infinito. Ejemplos de ello 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 . Según el lema de Kőnig , cada árbol ω tiene una rama infinita. Por otro lado, es un teorema de ZFC que hay incontables árboles sin incontables ramas ni incontables niveles; Estos árboles se conocen como árboles de Aronszajn . Dado un número cardinal κ, un árbol κ- Suslin es un árbol de altura κ que no tiene cadenas ni 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 contrario no se cumple).

La conjetura de Suslin se planteó 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 ω ₁ o una rama de longitud ω ₁ .

Si ( T ,<) es un árbol, entonces el cierre reflexivo ≤ de < es un orden de prefijo en T . Lo contrario no se cumple: por ejemplo, el orden habitual ≤ en el conjunto Z de números enteros es un total y, por 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.

Ejemplos de árboles infinitos

Árbol teórico de conjuntos de altura y ancho . Cada nodo corresponde a un punto de unión de una línea roja y una verde. Debido a restricciones de espacio, solo las ramas con un prefijo ( 0 , 0 , 0 ,...) o ( 1 , 1 , 1 ,...) se muestran en su longitud completa. ${\displaystyle \omega \cdot 2}$ ${\displaystyle 2^{\omega \cdot 2}}$

• Sea un número ordinal y sea un conjunto. Sea el conjunto de todas las funciones donde . Defina si el dominio de es un subconjunto propio del dominio de y las dos funciones concuerdan en el dominio de . Entonces es un árbol de teoría de conjuntos. Su raíz es la función única 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 desde hasta , es decir, una secuencia generalizada de miembros de . Si es un ordinal límite , ninguna de las ramas tiene un elemento maximal (" hoja "). La imagen muestra un ejemplo de y . ${\displaystyle \kappa }$ ${\displaystyle X}$ ${\displaystyle T}$ ${\displaystyle f:\alpha \mapsto X}$ ${\displaystyle \alpha <\kappa }$ ${\displaystyle f<g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle (T,<)}$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \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 adecuado 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. ${\displaystyle m,n}$ ${\displaystyle m<n}$ ${\displaystyle n}$ ${\displaystyle 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 convertir en uno de teoría de conjuntos eligiendo un nodo raíz y definiendo if y se encuentra en la ruta (única) no dirigida desde hasta . ${\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.

Ver también

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

Referencias

• Jech, Thomas (2002). Teoría de conjuntos . Springer-Verlag. ISBN 3-540-44085-2.
• Kunen, Kenneth (1980). Teoría de conjuntos: una introducción a las pruebas de independencia . Holanda del Norte. ISBN 0-444-85401-0.Capítulo 2, Sección 5.
• Monje, J. Donald (1976). Lógica Matemática . Nueva York: Springer-Verlag. pag. 517.ISBN​ 0-387-90170-1.
• Hajnal, András ; Hamburguesa, Peter (1999). Teoría de conjuntos . Cambridge: Prensa de la Universidad de Cambridge. ISBN 9780521596671.
• Kechris, Alexander S. (1995). Teoría descriptiva clásica de conjuntos . Textos de Posgrado en Matemáticas 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9 .   

enlaces externos

• 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órica de conjuntos) por Henry en PlanetMath
• rama de Henry en PlanetMath
• ejemplo de árbol (teórica de conjuntos) de uzeromay en PlanetMath