Autor Tema: Árboles - Teoría de Conjuntos (Carlos Ivorra)

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

03 Octubre, 2022, 11:16 am
Leído 1095 veces

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 160
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Me surgen algunas dudas en el apartado 9.2 del libro, que va sobre el problema de Suslin.

Planteo la primera duda porque en función de la respuesta se derivan unas preguntas u otras.

En la página 348 se define que un k-árbol A está bien podado siempre que

\( |Niv_0A|=1 \)
y
\( \wedge{x}\in{A}\wedge{\alpha}<k\space(alt_Ax<\alpha\rightarrow{\vee{y}\in{Niv_{\alpha}A}\space x<y}) \)

Es decir, que un k-árbol está bien podado si tiene una única raíz y desde cualquiera de sus puntos se puede ascender hasta cualquier altura.

Pero eso entonces significa que toda rama es un camino, ¿no? Es decir, toda rama llega hasta la misma altura que el árbol. Porque si, por ejemplo, hay una rama que llega al nivel 3, y llamemos x al elemento más alto de esa rama (el que está en el nivel 3), entonces tendremos un x que pertenece a A y un nivel 4, que es mayor que el nivel de x, pero no hay ningún y que esté en el nivel 4 y sea mayor que x (que sea compatible con x). Puede haber algún y en el nivel 4 pero en otra rama, y entonces es incompatible con x.

¿Es correcto?

03 Octubre, 2022, 11:37 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero eso entonces significa que toda rama es un camino, ¿no? Es decir, toda rama llega hasta la misma altura que el árbol.

No, no es correcto. Es consistente que existan árboles de Suslin, y en tal caso podemos tomarlos bien podados, y un árbol de Suslin bien podado tiene ramas, pero no tiene caminos.

Porque si, por ejemplo, hay una rama que llega al nivel 3, y llamemos x al elemento más alto de esa rama (el que está en el nivel 3),

Ahí está el fallo, que una rama no tiene por qué tener un elemento más alto. Lo que estás probando es que en un árbol bien podado las ramas no tienen máximo, pero eso no significa que sean caminos.

Imagina que estás en una posición del árbol. Desde ahí, puedes ascender por distintas ramas, tienes una rama que te lleva hasta cierto nivel, otra que te permite llegar más alto, y otra más alto aún, pero no tiene por qué haber ninguna rama que te permita llegar hasta cualquier altura. Dependiendo de lo alto que quieras ascender, tendrás que elegir una rama u otra.

03 Octubre, 2022, 03:12 pm
Respuesta #2

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 160
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Vale, entonces entiendo que no hay caminos porque al ser un árbol de altura infinita no podemos definir máximos (como pasa con un ordinal límite, que no podemos tomar el elemento máximo “anterior” al ordinal límite).

Pero para entender el concepto, ¿el árbol finito de la página 348 estaría bien podado? ¿O en árboles finitos no se aplica este concepto?

¿Cómo sería un árbol mal podado? (Sin contar el caso trivial de que tenga más de una raíz)

03 Octubre, 2022, 03:21 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Vale, entonces entiendo que no hay caminos porque al ser un árbol de altura infinita no podemos definir máximos (como pasa con un ordinal límite, que no podemos tomar el elemento máximo “anterior” al ordinal límite).

No sé si te entiendo. Parece que estés argumentando que un árbol de altura infinita no puede tener caminos, pero sí puede tenerlos. Tal vez lo que quieres decir es que por eso no podemos asegurar que los tiene.

Pero para entender el concepto, ¿el árbol finito de la página 348 estaría bien podado? ¿O en árboles finitos no se aplica este concepto?

No estaría bien podado, porque a la izquierda tienes un punto de altura 2 desde el que no se puede ascender hasta puntos de altura 4.

¿Cómo sería un árbol mal podado? (Sin contar el caso trivial de que tenga más de una raíz)

Pues es un árbol en el que, si te metes por la rama equivocada, te encuentras con que por encima tienes sólo nodos que llegan hasta un nivel inferior al nivel de todo el árbol. Coge un árbol bien podado y añádele un ramillete en cualquier nodo desde el que no se pueda subir mucho y tendrás un árbol mal podado.

En un árbol bien podado, estés donde estés, siempre tienes la opción de subir tan alto como quieras, mientras que en un árbol mal podado tienes callejones sin salida, que si entras en ellos ya limitas tus posibilidades de ascenso.

03 Octubre, 2022, 05:22 pm
Respuesta #4

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 160
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Sí, lo he expresado mal. Entiendo que un k-árbol de altura infinita k puede tener caminos, pero no podemos definir con exactitud todos y cada uno de los elementos del camino, ni tampoco saber cuántos caminos hay. Porque puede haber más de uno.

Preguntas:

1. Dado que el árbol tiene altura k, ¿no debe existir como mínimo un camino que lleve hasta la altura k? Si no, el árbol no tendría altura k, ¿no?

2. Si es un árbol bien podado, no hay ninguna rama que acabe en un “callejón sin salida”, con lo que desde todo punto se puede seguir ascendiendo aunque más arriba se produzcan ramificaciones diversas que permitan opciones alternativas. ¿Es así?

3. Si el árbol es un k-árbol de Suslin, en ningún nivel puede haber k o más de k ramificaciones porque entonces en ese nivel tendríamos una anticadena de cardinal \( \geq{k} \). ¿Es así?

4. En la página 354 al final, se plantea una cadena maximal C en un k-árbol de Suslin de manera que la altura de la cadena C es menor que \( \alpha \) siendo \( \alpha<k \). Pero eso significa que esa cadena, por ser maximal, no puede estar contenida en una cadena de altura \( \alpha \), con lo que entonces C es una rama que es un “callejón sin salida” por el que no se puede seguir ascendiendo hasta k y ello contradice que el árbol esté bien podado, ¿no?

03 Octubre, 2022, 09:21 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Sí, lo he expresado mal. Entiendo que un k-árbol de altura infinita k puede tener caminos, pero no podemos definir con exactitud todos y cada uno de los elementos del camino, ni tampoco saber cuántos caminos hay. Porque puede haber más de uno.

Bueno, eso es muy relativo. Todo dependerá de lo bien o mal que conozcamos al árbol en cuestión. Por ejemplo, en la sección 9.5 verás resultados sobre el número de caminos de un árbol.

Preguntas:

1. Dado que el árbol tiene altura k, ¿no debe existir como mínimo un camino que lleve hasta la altura k? Si no, el árbol no tendría altura k, ¿no?

No, si por k te refieres a un cardinal infinito \( \kappa \), entonces todos los nodos del árbol tienen altura menor que \( \kappa \), luego necesitas que, para cada ordinal \( \alpha <\kappa \), haya una rama que lleve hasta el nivel \( \alpha \), pero dicha rama no tiene por qué ser un camino, puede tener altura menor que \( \kappa \), siempre y cuando haya otras ramas de alturas arbitrariamente grandes, de modo que, eligiendo la adecuada, siempre puedas llegar hasta el nivel que quieras.

Imagina, por ejemplo, un árbol que tenga una rama de altura \( \omega_1 \), otra de altura \( \omega_2 \), etc. Entonces la altura del árbol es \( \omega_\omega \), pero ninguna rama tiene esa altura, ninguna es un camino.

2. Si es un árbol bien podado, no hay ninguna rama que acabe en un “callejón sin salida”, con lo que desde todo punto se puede seguir ascendiendo aunque más arriba se produzcan ramificaciones diversas que permitan opciones alternativas. ¿Es así?

No exactamente. Depende de lo que entiendas por "una rama acaba en un callejón sin salida". Por ejemplo, si estás en un árbol de Suslin, no hay caminos, luego, en cierto sentido, toda rama "es" un callejón sin salida, que te permite ascender hasta cierta altura y no más. Eso no contradice que el árbol esté bien podado. Es lo que decía antes. Si desde un punto quieres ascender más arriba de lo que te permite una rama, el truco es no seguir esa rama, sino otra. Que el árbol esté bien podado significa que siempre tendrás una rama adecuada por la que ascender todo lo que quieras, pero cada rama en particular se acabará en un momento dado y no te permitirá subir más.

3. Si el árbol es un k-árbol de Suslin, en ningún nivel puede haber k o más de k ramificaciones porque entonces en ese nivel tendríamos una anticadena de cardinal \( \geq{k} \). ¿Es así?

Sí.

4. En la página 354 al final, se plantea una cadena maximal C en un k-árbol de Suslin de manera que la altura de la cadena C es menor que \( \alpha \) siendo \( \alpha<k \). Pero eso significa que esa cadena, por ser maximal, no puede estar contenida en una cadena de altura \( \alpha \), con lo que entonces C es una rama que es un “callejón sin salida” por el que no se puede seguir ascendiendo hasta k y ello contradice que el árbol esté bien podado, ¿no?

No. Es lo que estoy repitiendo en este mensaje ya varias veces. Por esa cadena no puedes ascender más de \( \alpha \), pero eso no contradice que el árbol esté bien podado, pues nada impide que desde cualquier punto de esa cadena puedas pasar a otras cadenas por las que puedas ascender más alto. No hay problema en que toda cadena se acabe antes de llegar a la altura completa del árbol siempre y cuando desde puntos arbitrariamente altos de la cadena salgan otras cadenas que te permitan llegar más arriba.

Soy consciente de que es algo muy sutil. No dudes en darle todas las vueltas que necesites y preguntar lo que haga falta.

04 Octubre, 2022, 10:58 am
Respuesta #6

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 160
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Le he dado una vuelta con la almohada esta noche y a ver si ahora el planteamiento es correcto intuitivamente hablando.

Si tomamos un árbol finito, está claro que un árbol bien podado no tiene ramas que acaban en niveles inferiores al máximo.

Ahora bien, cuando hablamos de árboles infinitos, la idea es que subimos por una rama, y supongamos que esa rama tiene altura máxima \( \omega_1 \). Eso quiere decir que nunca vamos a dejar de ascender por esa rama porque hay infinitos elementos, con lo que siempre se cumple la definición de árbol bien podado porque, dado un x, siempre hay un y>x en el nivel siguiente en esa misma rama.

Pero por otro lado, en esa misma rama podemos encontrarnos que en algún nivel, de los infinitos que tiene, hay una bifurcación hacia otra rama que tiene altura \( \omega_2 \), por ejemplo. De forma que si seguimos en la rama en la que estamos seguiremos ascendiendo de forma infinita sin nunca llegar a \( \omega_1 \), a no ser que más adelante haya otra bifurcación hacia otra rama con otra altura. Y si nos desviamos a la otra rama seguiremos ascendiendo de forma infinita sin nunca llegar a \( \omega_2 \), a no ser que más adelante haya otra bifurcación a otra rama con otra altura.

De esta forma, la rama de altura \( \omega_1 \) es una cadena maximal, dado que no está contenida en la cadena maximal que constituye la rama de altura \( \omega_2 \), que asciende más arriba.

Así, en un árbol de este tipo sí que hay ramas que acaban en una especie de “callejón sin salida”, de ascenso infinito, pero que nunca llegan a la altura máxima del árbol ni son, por tanto, un camino.

04 Octubre, 2022, 11:48 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Bueno, parece que le vas cogiendo el truco. Aun así, no te confíes, que los árboles tienen muchas sutilezas.

Por concretar la clase de situaciones que describes: imagina un árbol que tiene una rama infinita de altura \( \omega \), digamos con nodos \( x_0, x_1, x_2, \ldots \), pero de \( x_0 \) sale una rama de altura \( \omega_1 \) y de \( x_1 \) sale otra rama también de altura \( \omega_1 \), y otra de \( x_2 \), etc.

Se trata de un árbol bien podado. Si vas ascendiendo por la primera rama, en cualquier momento estás a tiempo de pasarte a otra que te permita subir todo lo que quieras, pero si recorres toda la rama \( x_0, x_1, x_2, \ldots \) te encuentras con que no se puede prolongar más y te has quedado atrapado en el nivel \( \omega \).

04 Octubre, 2022, 02:13 pm
Respuesta #8

JordiMath

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

Realmente es un tema fascinante todo lo relacionado con los ordinales y cardinales transfinitos.