Usuario:Juan Antonio Cordero/Taller

Á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 asume que los árboles tienen una sola raíz (es decir, un elemento mínimo), debido a que las cuestiones típicas que se investigan en esta disciplina se pueden reducir fácilmente a cuestiones sobre árboles de una sola raíz.

Definición

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 <. 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, y se denota ht(t, T). La altura de T se define como el menor ordinal que es mayor que la altura de todos y cada uno de los elementos de T. Una raíz de un árbol T es un elemento de altura 0. Con frecuencia, se asume que los árboles tienen una sola raíz. En teoría de conjuntos, y por convención, los árboles se consideran crecientes hacia abajo, lo que convierte a la raíz en el mayor nodo.

Los árboles con una sola raíz pueden ser considerados como árboles con raíz en el sentido de la teoría de grafos, en dos aspectos: como árbol (teoría de grafos), o como un grafo trivialmente perfecto. En el primer caso, el grafo es el diagrama de Hasse adireccional del conjunto parcialmente ordenado. En el segundo caso, el grafo es simplemente el grafo subyacente (adirecional) del conjunto parcialmente ordenado. Sin embargo, si T es un árbol de altura > ω, entonces la definición del diagrama de Hasse no aplica. Por ejemplo, el conjunto parcialmente ordenado $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ no tiene un diagrama de Hasse, puesto que ω no tiene predecesor. En este caso, se requiere una altura de como mucho ω.