Árbol (teoría descriptiva de conjuntos)

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

Definiciones

Árboles

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

Ramas y cuerpos

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

Un árbol que no tiene ramas se llama bien fundado ; 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 necesariamente estar infundado.

Nodos terminales

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

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 el camino formado siguiendo estos bordes desde cualquier vértice eventualmente conduce al vértice raíz. Si 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 y un borde saliente 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 grafos. La raíz del árbol es la secuencia vacía. ${\displaystyle T}$ ${\displaystyle T}$

En teoría del orden , se utiliza una noción diferente de árbol: un árbol de 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. Cada árbol en la teoría descriptiva de conjuntos es también un árbol de teoría del orden, que utiliza un ordenamiento parcial en el que dos secuencias y están ordenadas por si y solo si es un prefijo adecuado de . La secuencia vacía es el elemento mínimo único, 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 sólo si cada uno de sus elementos tiene una altura finita (es decir, un conjunto finito de predecesores). ${\displaystyle T}$ ${\displaystyle U}$ ${\displaystyle T<U}$ ${\displaystyle T}$ ${\displaystyle U}$

Topología

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

Con frecuencia se consideran árboles sobre productos cartesianos . En este caso, por convención, consideramos solo el subconjunto del espacio producto, que contiene solo secuencias de cuyos elementos pares provienen y de donde provienen los elementos impares (por ejemplo, ). Los elementos de este subespacio se identifican de forma natural con un subconjunto del producto de dos espacios de secuencias (el subconjunto para el cual la longitud de la primera secuencia es igual o 1 mayor que la longitud de la segunda secuencia). De esta manera podemos identificarnos con más del espacio del producto. Entonces podemos formar la proyección de , ${\displaystyle X\times Y}$ ${\displaystyle T}$ ${\displaystyle (X\times Y)^{<\omega }}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \langle x_{0},y_{1},x_{2},y_{3}\ldots ,x_{2m},y_{2m+1}\rangle }$ ${\displaystyle X^{<\omega }\times Y^{<\omega }}$ ${\displaystyle [X^{<\omega }]\times [Y^{<\omega }]}$ ${\displaystyle [T]}$ ${\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

• Árbol de Laver , 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 descriptiva clásica de conjuntos . Textos de Posgrado en Matemáticas 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9 .