Árbol (teoría de conjuntos)

Una rama (resaltada en verde) de un árbol teórico de conjuntos. Los puntos representan elementos, las flechas representan la relación de orden y las elipses y flechas discontinuas representan elementos y relaciones no representados.

En teoría de conjuntos, un árbol (A, ${\displaystyle <_{r}}$) es un conjunto parcialmente ordenado constituido por una serie de elementos y una relación de orden parcial transitiva, ${\displaystyle <_{r}}$, definida sobre A, de tal modo que, para cada q ∈ A, el conjunto de predecesores de q en A, ${\displaystyle \{p\in A:p<_{r}q\}}$, está bien ordenado. Los elementos de un árbol A suelen denominarse nodos.

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 x₂ (línea discontinua naranja).

Típicamente, se asume que los árboles tienen un solo elemento mínimo, al que se le denomina raíz o nodo raíz. Los árboles con una sola raíz pueden considerarse árboles á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. En el segundo caso, el grafo es simplemente el grafo subyacente (no dirigido) del conjunto parcialmente ordenado.

Una rama del árbol es una cadena máxima en el árbol (es decir, un subconjunto tal que dos elementos de la rama son comparables, y cualquier elemento del árbol no contenido en la rama es incomparable con, al menos, un elemento de la rama).

Véase también

• Árbol (teoría de grafos)
• Árbol (programación)

Referencias

• Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. North-Holland. ISBN 0-444-85401-0.  Capítulo 2, Sección 5.

Enlaces externos

• Versiones definibles en teoría combinatoria de conjuntos, por Diana Carolina Montoya Amaya, definición 1, pág. 2.

• Datos: Q2859736