Á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 modo que cada prefijo de una secuencia en la colección también pertenece a la colección.

Definiciones

Árboles

La colección de todas las secuencias finitas de elementos de un conjunto. ${\displaystyle X}$ se denota ${\displaystyle X^{<\omega }}$. Con esta notación, un árbol es un subconjunto no vacío${\displaystyle T}$ de ${\displaystyle X^{<\omega }}$, tal que si${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle }$ es una secuencia de longitud ${\displaystyle n}$ en ${\displaystyle T}$, y si ${\displaystyle 0\leq m<n}$, luego la secuencia abreviada ${\displaystyle \langle x_{0},x_{1},\ldots ,x_{m-1}\rangle }$ también pertenece a ${\displaystyle T}$. En particular, eligiendo${\displaystyle m=0}$ muestra que la secuencia vacía pertenece a todos los árboles.

Ramas y cuerpos

Una rama a través de un árbol${\displaystyle T}$ es una secuencia infinita de elementos de ${\displaystyle X}$, cada uno de cuyos prefijos finitos pertenece a ${\displaystyle T}$. El conjunto de todas las ramas a través${\displaystyle T}$ se denota ${\displaystyle [T]}$y llamó al cuerpo del árbol${\displaystyle T}$.

Un árbol que no tiene ramas se llama bien fundamentado ; un árbol con al menos una rama es infundado . Según el lema de Kőnig , un árbol en un conjunto finito con un número infinito de secuencias debe estar necesariamente infundado.

Nodos terminales

Una secuencia finita que pertenece a un árbol. ${\displaystyle T}$se llama nodo terminal si no es un prefijo de una secuencia más larga en${\displaystyle T}$. Equivalentemente,${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T}$ es terminal si no hay elemento ${\displaystyle x}$ de ${\displaystyle X}$ tal que ${\displaystyle \langle x_{0},x_{1},\ldots ,x_{n-1},x\rangle \in T}$. Un árbol que no tiene ningún nodo terminal se llama podado .

Relación con otros tipos de árboles

En teoría de grafos , un árbol enraizado es un grafo dirigido en el que cada vértice excepto un vértice raíz especial tiene exactamente un borde saliente, y en el que la ruta formada siguiendo estos bordes desde cualquier vértice eventualmente conduce al vértice raíz. Si${\displaystyle T}$ es un árbol en el sentido descriptivo de la teoría de conjuntos, entonces corresponde a un gráfico con un vértice para cada secuencia en ${\displaystyle T}$, y un borde de salida de cada secuencia no vacía que la conecta con la secuencia más corta formada al eliminar su último elemento. Este gráfico es un árbol en el sentido teórico de los gráficos. La raíz del árbol es la secuencia vacía.

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

Topología

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

Con frecuencia árboles en productos cartesianos ${\displaystyle X\times Y}$son considerados. En este caso, por convención, consideramos solo el subconjunto${\displaystyle T}$ del espacio del producto, ${\displaystyle (X\times Y)^{<\omega }}$, que contiene solo secuencias cuyos elementos pares provienen de ${\displaystyle X}$ y 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 que la longitud de la primera secuencia es igual o 1 más que la longitud de la segunda secuencia). De esta forma podemos identificar${\displaystyle [X^{<\omega }]\times [Y^{<\omega }]}$ con ${\displaystyle [T]}$para sobre el espacio del producto. 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]\}}$.

Ver también

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

Referencias

• Kechris, Alexander S. (1995). Teoría Clásica Descriptiva de Conjuntos . Textos de Posgrado en Matemáticas 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9 .