Definición de árbol infinito en teoría de conjuntos

Question

Pregunta realmente básica sobre árboles en teoría de conjuntos.

¿Cuál es la definición de un árbol infinito?

Hago la pregunta porque, bastante peculiarmente, ni en el libro clásico de Kechris sobre teoría descriptiva de conjuntos, ni en el libro de Srivastava sobre el mismo tema, hay una definición explícita, incluso si ambos utilizan el concepto (por ejemplo, Srivastava utiliza la infinitud de un árbol para el lema de infinitud de Koenig, p.28).

Gracias de antemano.

---

Edit después de las respuestas:
Gracias a todos por la cantidad de respuestas y la calidad detrás de ellas.

Answer 1

Recuerda que un árbol es un orden parcial tal que para cada punto $x$, el cono debajo de $x$ está bien ordenado.

Un árbol infinito es un árbol con infinitos nodos.

A veces, sin embargo, es más fácil trabajar con árboles "invertidos". Con el ordenamiento invertido, estar bien fundamentado es equivalente a no tener una rama infinita. Y eso es algo que surge a menudo en la teoría descriptiva de conjuntos.

Answer 2

Típicamente, en lenguaje de teoría de conjuntos, un "árbol" (posiblemente infinito) significa un conjunto no vacío de secuencias de símbolos (por ejemplo, enteros), el cual está cerrado bajo la toma de prefijos.

¿Qué tiene que ver esto con el concepto de árbol en teoría de grafos? Supongamos que estás etiquetando todas las aristas en el árbol con un símbolo tal que ningún nodo tiene dos aristas salientes con la misma etiqueta. La representación de los teóricos en conjunto del árbol consiste entonces en una "dirección" de cada nodo en el árbol, la cual es la secuencia de etiquetas de las aristas en el camino (único) desde la raíz hasta el nodo en cuestión.

El nodo raíz tiene como dirección la secuencia vacía.

El árbol binario completo con 7 nodos sería $$\{(), (0), (0,0), (0,1), (1), (1,0), (1,1) \}$$ y un árbol unario infinito sería $$\{(), (0), (0,0), (0,0,0), \ldots \}$$

El árbol es infinito si tiene infinitos nodos.

Se pueden definir restricciones adicionales en el árbol, como que cada nodo debe tener finitos sucesores, o que hay un límite finito global en el número de sucesores para un nodo.

---

Como señala Asaf, a veces es útil permitir secuencias transfinitamente largas (pero aún bien ordenadas) como direcciones. Esto da lugar a árboles que no corresponden directamente a árboles teóricos de grafos (porque los nodos cuya dirección está indexada por un ordinal límite no tendrán padres inmediatos).

Answer 3

Como se pidió, en realidad necesitas especificar un poco más para ser preciso. Primero asumiré que estás preguntando sobre árboles de ramificación binaria infinitos. Un árbol de ramificación binaria $T$ es una colección de cadenas finitas de ceros y unos, llamadas nodos, de tal manera que, cuando una cadena $\sigma$ está en $T$, todos sus prefijos también están en $T$. Un árbol de ramificación binaria infinito es un árbol de ramificación binaria con un número infinito de cadenas en él (cada cadena individual es finita).

Más generalmente, puedes hablar sobre árboles de ramificación en un conjunto arbitrario $A$. Entonces, en lugar de considerar (conjuntos de) cadenas de ceros y unos, consideras (conjuntos de) cadenas de elementos de $A$. La definición de un árbol infinito es la misma: un árbol que contiene un número infinito de cadenas.