Árbol (teoría descriptiva de conjuntos)

En la teoría descriptiva de conjuntos , un árbol en un conjunto${\displaystyle X}$es una colección de secuencias finitas de elementos de${\displaystyle X}$de tal manera que cada prefijo de una secuencia en la colección también pertenezca a la colección.

En teoría de grafos , un árbol con raíz es un grafo dirigido en el que cada vértice, excepto un vértice raíz especial, tiene exactamente una arista saliente, y en el que el camino formado al seguir estas aristas desde cualquier vértice conduce finalmente al vértice raíz.${\displaystyle T}$es un árbol en el sentido de la teoría de conjuntos descriptiva, entonces corresponde a un grafo con un vértice para cada secuencia en${\displaystyle T}$y una arista saliente desde cada secuencia no vacía que la conecta con la secuencia más corta formada al eliminar su último elemento. Este grafo es un árbol en el sentido de la teoría de grafos. La raíz del árbol es la secuencia vacía.

En la teoría del orden , se utiliza una noción diferente de árbol: un árbol de la teoría del orden es un conjunto parcialmente ordenado con un elemento mínimo en el que cada elemento tiene un conjunto bien ordenado de predecesores. Todo árbol en la teoría descriptiva de conjuntos es también un árbol de la teoría del orden, utilizando un orden parcial en el que dos secuencias${\displaystyle T}$y${\displaystyle U}$están ordenados por${\displaystyle T<U}$si y solo si${\displaystyle T}$es un prefijo adecuado de${\displaystyle U}$La secuencia vacía es el único elemento mínimo, y cada elemento tiene un conjunto finito y bien ordenado de predecesores (el conjunto de todos sus prefijos). Un árbol de teoría del orden puede representarse mediante un árbol isomorfo de secuencias si y solo si cada uno de sus elementos tiene altura finita (es decir, un conjunto finito de predecesores).

El conjunto de secuencias infinitas sobre${\displaystyle X}$(denominado como${\displaystyle X^{\omega }}$) se le puede dar la topología de producto , tratando a X como un espacio discreto . En esta topología, cada subconjunto cerrado${\displaystyle C}$de${\displaystyle X^{\omega }}$es de la forma${\displaystyle [T]}$para algún árbol podado${\displaystyle T}$. Es decir, dejemos${\displaystyle T}$consisten en el conjunto de prefijos finitos de las secuencias infinitas en${\displaystyle C}$Por el contrario, el cuerpo${\displaystyle [T]}$de cada árbol${\displaystyle T}$En esta topología, forma un conjunto cerrado .

Con frecuencia, los árboles se encuentran en productos cartesianos.${\displaystyle X\times Y}$se consideran. En este caso, por convención, consideramos solo el subconjunto${\displaystyle T}$del espacio de productos,${\displaystyle (X\times Y)^{<\omega }}$, que contiene únicamente secuencias cuyos elementos pares provienen de${\displaystyle X}$y los elementos extraños provienen de${\displaystyle Y}$(p.ej,${\displaystyle \langle x_{0},y_{1},x_{2},y_{3}\ldots ,x_{2m},y_{2m+1}\rangle }$). Los elementos de este subespacio se identifican de forma natural con un subconjunto del producto de dos espacios de secuencias,${\displaystyle X^{<\omega }\times Y^{<\omega }}$(el subconjunto para el cual la longitud de la primera secuencia es igual o 1 más que la longitud de la segunda secuencia). De esta manera podemos identificar${\displaystyle [X^{<\omega }]\times [Y^{<\omega }]}$con${\displaystyle [T]}$para todo el espacio de productos. Entonces podemos formar la proyección de${\displaystyle [T]}$,

${\displaystyle p[T]=\{{\vec {x}}\in X^{\omega }|(\exists {\vec {y}}\in Y^{\omega })\langle {\vec {x}},{\vec {y}}\rangle \in [T]\}}$.

• Árbol de Laver , un tipo de árbol utilizado en la teoría de conjuntos como parte de una noción de forzamiento.

• 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.