En la 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
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 la altura de t , denotado ht ( t , T ). La altura de T en sí es el menos 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. Los árboles en la teoría de conjuntos a menudo se definen para crecer hacia abajo, lo que hace que la raíz sea el nodo más grande. [ cita requerida ]
Los árboles con una sola raíz pueden verse como árboles enraizados en el sentido de la teoría de grafos en una de dos formas: ya sea como un árbol (teoría de grafos) o como un gráfico 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 ordenadono tiene un diagrama de Hasse, ya que no existe un predecesor para ω. 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 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 solo si tiene una altura κ y cada nivel tiene una 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 una sola raíz forma un encuentro-semirretículo, donde el encuentro (antepasado común) está dado por el elemento máximo de intersección de antepasados, que existe como el conjunto de antepasados no es vacío y finito 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 (no es necesario que dos elementos tengan ancestros comunes), por ejemplodonde 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, dónde no son comparables.
Un subárbol de un árbol es un arbol dónde y está cerrado hacia abajo bajo, es decir, si y luego .
Propiedades de la teoría de conjuntos
Hay algunos problemas planteados de manera bastante simple pero difíciles en la teoría del árbol infinito. 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 . Según 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; estos árboles se conocen como árboles Aronszajn . Dado un número cardinal κ, un κ- árbol de Suslin es un árbol de altura κ que no tiene cadenas o antichains 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 es válido).
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 un antichain de cardinalidad ω 1 o una rama de longitud ω 1 .
Ver también
Referencias
- Jech, Thomas (2002). Establecer teoría . Springer-Verlag. ISBN 3-540-44085-2.
- Kunen, Kenneth (1980). Teoría de conjuntos: una introducción a las pruebas de independencia . Holanda Septentrional. ISBN 0-444-85401-0. Capítulo 2, Sección 5.
- Monk, J. Donald (1976). Lógica matemática . Nueva York: Springer-Verlag. pag. 517 . ISBN 0-387-90170-1.
- Hajnal, András ; Hamburger, Peter (1999). Establecer teoría . Cambridge: Cambridge University Press. ISBN 9780521596671.
- Kechris, Alexander S. (1995). Teoría Clásica Descriptiva de Conjuntos . Textos de Posgrado en Matemáticas 156. Springer. ISBN 0-387-94374-9ISBN 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 (conjunto teórico) de Henry en PlanetMath
- rama de Henry en PlanetMath
- ejemplo de árbol (conjunto teórico) por uzeromay en PlanetMath