Árbol (teoría descriptiva de conjuntos)

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

Definiciones

Árboles

La colección de todas las secuencias finitas de elementos de un conjunto se denota . Con esta notación, un árbol es un subconjunto no vacío de , tal que si es una secuencia de longitud en , y si , entonces la secuencia acortada también pertenece a . En particular, la elección 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 de 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 se llama mal fundado . Según el lema de König , un árbol sobre un conjunto finito con un número infinito de sucesiones debe ser necesariamente mal fundado.

Nodos terminales

Una secuencia finita que pertenece a un árbol se denomina 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 . Un árbol que no tiene ningún nodo terminal se denomina 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 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 eventualmente al vértice raíz. Si es un árbol en el sentido de la teoría de conjuntos descriptivos, entonces corresponde a un grafo con un vértice para cada secuencia en , 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. ${\displaystyle T}$ ${\displaystyle T}$

En la 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 propio de . 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 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 sucesiones infinitas sobre (denotado como ) se le puede dar la topología de producto , tratando a X como un espacio discreto . En esta topología, cada subconjunto cerrado de es de la forma para algún árbol podado . Es decir, sea consiste en el conjunto de prefijos finitos de las sucesiones infinitas en . A la inversa, 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 de productos, , que contiene solo secuencias cuyos elementos pares provienen de y los elementos impares provienen de (por ejemplo, ). Los elementos en este subespacio se identifican de manera 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 más que la longitud de la segunda secuencia). De esta manera podemos identificar con para sobre el espacio de productos. Podemos entonces 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]\}}$.

Véase 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 clásica de conjuntos descriptivos . Textos de posgrado en matemáticas 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9 .