Autor Tema: Árboles de distintos tipos

0 Usuarios y 1 Visitante están viendo este tema.

13 Octubre, 2022, 09:19 pm
Leído 947 veces

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 160
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Planteo algunas cuestiones sobre árboles para confirmar si he entendido los conceptos básicos.

Cuando se define un \( k \)-árbol se dice (lo marco con asterisco porque me refiero a ello más adelante):

(*) Un \( k \)-árbol es un árbol de altura \( k \) cuyos niveles tienen todos cardinal menor que \( k \).

- Un árbol de Suslin es un árbol de altura \( \aleph_1 \) cuyas cadenas y anticadenas tienen todas cardinal menor que \( \aleph_1 \), es decir, son numerables.

- Un árbol de Aronszajn es un \( \aleph_1 \)-árbol cuyas cadenas tienen todas cardinal menor que \( \aleph_1 \), es decir, son numerables. Respecto a las anticadenas, éstas pueden ser numerables o no numerables. En el primer caso, son árboles de Suslin, que son un tipo de árboles de Aronszajn. Pero por ejemplo, si es un árbol de Aronszajn especial se puede descomponer en una unión numerable de anticadenas, con lo que, como el árbol tiene cardinal \( \aleph_1 \), alguna anticadena ha de ser no numerable, y por eso un árbol de Aronszajn especial no puede ser de Suslin. Pero si alguna anticadena es no numerable, ¿eso no contradice (*)? Porque entonces, ¿no es un \( \aleph_1 \)-árbol de altura \( \aleph_1 \) en que no todos los niveles tienen cardinal menor que \( \aleph_1 \)?

- Un árbol de Kurepa es un \( \aleph_1 \)-árbol de altura \( \aleph_1 \) con al menos \( \aleph_1^+ \) caminos. De nuevo, si tiene al menos \( \aleph_1^+ \) caminos, ¿eso no contradice (*)? Porque si hay al menos \( \aleph_1^+ \) caminos, ¿ello no significa que al menos el último nivel no es una anticadena de cardinal \( \aleph_1^+ \)?

Por último, planteo el siguiente ejemplo que creo que puede ser un árbol y tengo la duda de saber qué tipo de árbol sería, si es que es de algún tipo especial:

Tomamos el conjunto de Cantor, que consiste en tomar el intervalo [0,1] e irle sustrayendo el tercio central en cada paso. El nivel 0 sería el intervalo [0,1], el nivel 1 serían los intervalos [0,1/3] y [2/3,1], el nivel 2 serían los intervalos [0,1/9], [2/9,1/3], [2/3,7/9] y [8/9,1], y así sucesivamente (es la construcción del conjunto de Cantor). Consideramos la relación de orden por la inclusión inversa, de forma que si A y B son dos intervalos y \( A\subset{B} \), entonces \( A>B \) y pertenecen a la misma cadena, y evidentemente los intervalos del mismo nivel forman una anticadena porque son incompatibles entre sí, ningún intervalo está contenido en otro del mismo nivel, dado que son disjuntos.

En este conjunto todas las ramas son caminos, que todos son cadenas numerables, y cada camino tiene cardinal \( \aleph_0 \), pero el nivel más alto, el nivel \( \omega \), forma una anticadena de cardinal \( 2^{\aleph_0} \), dado que el conjunto de Cantor, al final del proceso es un conjunto no numerable, como es sabido. ¿Esta estructura sería algún tipo de árbol? Entiendo que sería un árbol de cardinal \( \aleph_1 \), de altura \( \aleph_0 \), unión numerable de anticadenas, con al menos una anticadena de cardinal \( \aleph_1 \), pero creo que no es ninguno de los tres árboles mencionados antes, ¿no?

13 Octubre, 2022, 10:33 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero si alguna anticadena es no numerable, ¿eso no contradice (*)? Porque entonces, ¿no es un \( \aleph_1 \)-árbol de altura \( \aleph_1 \) en que no todos los niveles tienen cardinal menor que \( \aleph_1 \)?

No contradice (*) porque no es lo mismo "nivel" que "anticadena". Los niveles son anticadenas, pero una anticadena no tiene por qué ser un nivel. Por ejemplo, imagina un \( \aleph_1 \)-árbol con una cadena no numerable, si cada nodo \( x_\alpha \)  de la cadena tiene encima otro nodo \( y_\alpha \) que no está en la anticadena, entonces el conjunto \( \{y_\alpha\} \) es una anticadena con elementos de altura arbitrariamente grande, con lo que no es, ni mucho menos, un nivel, en el que todos los elementos tendrían la misma altura.

- Un árbol de Kurepa es un \( \aleph_1 \)-árbol de altura \( \aleph_1 \) con al menos \( \aleph_1^+ \) caminos. De nuevo, si tiene al menos \( \aleph_1^+ \) caminos, ¿eso no contradice (*)? Porque si hay al menos \( \aleph_1^+ \) caminos, ¿ello no significa que al menos el último nivel no es una anticadena de cardinal \( \aleph_1^+ \)?

Es que no hay un último nivel. Para cada \( \alpha<\omega_1 \), el nivel \( \alpha \) es numerable, y los \( \aleph_1^+ \) restringidos a esa altura \( \alpha \) son numerables. Hay muchos con la misma restricción, que se separan en alturas posteriores.

La situación es parecida a la del ejemplo que pones a continuación:

Por último, planteo el siguiente ejemplo que creo que puede ser un árbol y tengo la duda de saber qué tipo de árbol sería, si es que es de algún tipo especial:

Tomamos el conjunto de Cantor, que consiste en tomar el intervalo [0,1] e irle sustrayendo el tercio central en cada paso. El nivel 0 sería el intervalo [0,1], el nivel 1 serían los intervalos [0,1/3] y [2/3,1], el nivel 2 serían los intervalos [0,1/9], [2/9,1/3], [2/3,7/9] y [8/9,1], y así sucesivamente (es la construcción del conjunto de Cantor). Consideramos la relación de orden por la inclusión inversa, de forma que si A y B son dos intervalos y \( A\subset{B} \), entonces \( A>B \) y pertenecen a la misma cadena, y evidentemente los intervalos del mismo nivel forman una anticadena porque son incompatibles entre sí, ningún intervalo está contenido en otro del mismo nivel, dado que son disjuntos.

Como árbol, el árbol que acabas de describir es isomorfo a \( 2^{<\omega} \), es decir, es un árbol de altura \( \omega \) en el que por encima de cada nodo hay exactamente dos nodos.

Ahí tienes un ejemplo de árbol con niveles finitos que tiene \( 2^{\aleph_0} \) caminos, y no es ni más ni menos contradictorio que la existencia de un árbol de Kurepa. Si cortas todos los números reales (digamos entre 0 y 1) por su n-sima cifra decimal, obtienes una cantidad finita de decimales. No hay contradicción en que los números decimales entre 0 y 1 de una longitud dada sean un número finito y que los decimales infinitos sean un conjunto no numerable.

En este conjunto todas las ramas son caminos, que todos son cadenas numerables, y cada camino tiene cardinal \( \aleph_0 \), pero el nivel más alto, el nivel \( \omega \), forma una anticadena de cardinal \( 2^{\aleph_0} \), dado que el conjunto de Cantor, al final del proceso es un conjunto no numerable, como es sabido.

Pero no hay un nivel más alto. El nivel \( \omega \) es vacío. Todo elemento de ese árbol tiene altura finita, y por eso es un árbol de altura \( \omega \). Si el nivel \( \omega \) no fuera vacío el árbol tendría altura \( \omega+1 \). Creo que esa tendencia a pensar en un "último nivel" inexistente te confunde bastante y te confundía ya en algún hilo anterior.

Otra cosa es que si quisieras añadir un nivel \( \omega \) al árbol, podrías hacerlo no numerable si quisieras, situando cada nuevo nodo sobre uno cualquiera de los \( 2^{\aleph_0} \) caminos posibles.

¿Esta estructura sería algún tipo de árbol? Entiendo que sería un árbol de cardinal \( \aleph_1 \), de altura \( \aleph_0 \), unión numerable de anticadenas, con al menos una anticadena de cardinal \( \aleph_1 \), pero creo que no es ninguno de los tres árboles mencionados antes, ¿no?

No, no hay ninguna anticadena de cardinal \( \aleph_1 \). El árbol es numerable, y todos sus subconjuntos son numerables (tanto las cadenas, como las anticadenas como cualquier otro), sin perjuicio de que admita una cantidad no numerable de caminos.

Todos los árboles que has citado antes son de altura \( \aleph_1 \), así que éste no es de ninguno de esos tipos. Pero este árbol es simplemente el árbol binario completo \( 2^{<\omega} \).

13 Octubre, 2022, 11:05 pm
Respuesta #2

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 160
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Entendido. Muchas gracias.