Autor Tema: Árbol binario completo

0 Usuarios y 2 Visitantes están viendo este tema.

10 Octubre, 2006, 06:54 pm
Leído 10708 veces

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Un árbol binario completo parte de un nudo del que salen dos ramas; después cada una de estas se bifurca en un nuevo nudo, y así infinitamente. Del primer nudo parten dos ramas nuevas, de cada uno de los demás parte una sola rama nueva y continúa una rama antigua.

El problema es que parece haber una demostración de que el conjunto de las ramas es no numerable y una demostración de que es numerable.

PRIMERO. Cada rama contiene un número infinito de elecciones entre izquierda (I) y derecha (D), de manera que las ramas pueden biyectarse con las secuencias binarias infinitas del tipo <I,D,I,D,D,I,I,I...>. Es claro que el conjunto de tales secuencias es no numerable, de hecho es biyectable con P(N), puesto que cada secuencia define un único conjunto de naturales y cada conjunto de naturales está definido por una única secuencia: supongamos que 'I' significa 'no está' y 'D' significa 'sí está'; entonces la secuencia que define al conjunto de los naturales mayores que 3 es <I,I,I,I,D,D,D,D,D...>. En consecuencia, el conjunto de las ramas es no numerable.

SEGUNDO. Hay una forma sencilla de numerar las ramas: de izquierda a derecha y de arriba a abajo; para ver esto es útil dibujar una parte inicial del árbol, cosa que yo no puedo hacer aquí. Luego el conjunto de las ramas es numerable.
                             
¿Qué me decís?

Saludos


10 Octubre, 2006, 07:02 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 OJO!!! No estoy de acuerdo en el segundo punto. No hay esa forma sencilla de numerar las ramas. De izquierda a derecha y de arriba abajo puedes numerar trocitos de ramas, pero no las ramas completas.

Saludos.

12 Octubre, 2006, 12:09 pm
Respuesta #2

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Respondo a el_manco.

Tienes razón. La enumeración funciona si y sólo si toda rama tiene a partir de un nudo o nodo la forma de una recta; sólo entonces podemos decir que de cada nudo (excepto el primero) nace una sola rama. Pero esto no es así.

Considera lo siguiente.

Tengamos primero en cuenta que el conjunto de los nudos es numerable dado que cada nudo representa un número finito de elecciones y, por tanto, una secuencia binaria finita. Clasifiquemos los nodos en niveles horizontales; habrá un infinito numerable de niveles. En cada nivel el número de ramas se duplica. Puesto que empezamos por dos ramas y tenemos un infinito numerable de niveles, el número de ramas debería ser el límite de la sucesión <2, 4, 8, ..., 2^n, ...>.

Evidentemente esto no funciona así. Este paso al límite no funciona ¿Pero por qué?

Gracias.

13 Octubre, 2006, 08:35 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Simplemente el límite de la sucesión \( 2^n \) es "infinito". Ojo, lo que significa este infinito es que dado cualquier número real, a partir de un cierto n todos los términos de la sucesión son mayores que ese número. Con esto quiero decir que no tiene sentido plantearse desde el punto de vista del límite de una sucesión, si ese infinito es del orden de los naturales, reales, ecétera...

 De hecho esto es similar a si uno coge los conjuntos \( A_n=\{1,2,\ldots,n\} \) y piensa en el cardinal de \( P(A_n) \) que es \( 2^n \). Cuando n tiende a infinito, \( A_n \) "tiende" a todos los números naturales y sin embargo el cardinal de P(N) sabemos que es no numerable. De hecho ese cardinal suele representarse como \( 2^\infty \).

 Es interesante también señalar que, considerando límites conjuntistas:

\(  \displaystyle\lim_{n \to{+}\infty}{A_n}=\cup_{n\in N} A_n=N \)

pero sin embargo:

\(  \displaystyle\lim_{n \to{+}\infty}{P(A_n)}=\cup_{n\in N} P(A_n)\neq P(N) \)

Saludos.


 

13 Octubre, 2006, 09:51 pm
Respuesta #4

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
El_manco escribió:

>Simplemente el límite de la sucesión  es "infinito". Ojo, lo que significa este infinito es que dado >cualquier número real, a partir de un cierto n todos los términos de la sucesión son mayores que >ese número. Con esto quiero decir que no tiene sentido plantearse desde el punto de vista del límite >de una sucesión, si ese infinito es del orden de los naturales, reales, ecétera...

En esto no puedo estar de acuerdo. Razonas como si los cardinales transfinitos no existiesen. Si hablamos de límites en lo transfinito debemos en principio atenernos a las mismas reglas que cuando hablamos de números finitos. Nadie diría que el límite de <1, 1'5, 1'75,...> es 3. Por la misma razón el límite de <2, 4, 8, ...> no puede ser alef_1 sino alef_0, que a su vez no puede ser c (la potencia del continuo). Además, empezando con una cantidad finita y duplicándola una cantidad numerable de veces, no podemos trascender lo numerable.

Si imaginamos el árbol binario completo terminado, tendremos que sólo hay una cantidad numerable de niveles de nudos, que empezamos con dos ramas y que la cantidad de ramas se duplica en cada nivel. Y a pesar de eso al final nos encontramos con c ramas en lugar de con alef_0 ramas.

La clave puede estar en la falta de correspondencia que aparece en tu segundo ejemplo; el límite de P(An) no es P(N) como parece que debiera ser.

En teoría de conjuntos los límites 'no funcionan bien'. Recordaré dos conocidos ejemplos.

En el saco A tenemos todos los naturales sin repetición. El saco B está vacío. En la primera operación traspasamos al saco B los diez primeros naturales y extraemos de él (y desechamos) el primer natural; en general en la n-ésima operación traspasamos al saco B la n-ésima decena de naturales y extraemos el n-ésimo natural. La cantidad de naturales que va habiendo en el saco B forma la sucesión <9, 18, 27, ..., 9n, ...>. ¿Cuántos números hay en el saco B cuando hemos repetido la operación alef_0 veces? Ninguno; cada uno de ellos habrá sido extraído en alguna operación. En el 'paso al infinito' se quiebra la tendencia; y esto impide calcular mediante el paso al límite.

Sea la familia de comjuntos N, N-{0}, N-{0,1}, etc. ¿Cuál es el cardinal de su intersección? Si intentamos calcularlo al estilo de las series, generando una sucesión de resultados parciales, tenemos la sucesión <alef_0, alef_0, alef_0, ...>, cuyo límite es, claro, alef_0. Y, sin embargo, 'pasando al infinito' obtenemos el cardinal 0.

Igual que en el árbol binario, parece que el 'paso al infinito' rompe la tendencia de la sucesión y por eso el límite no sirve para el cálculo.

Esto de la quiebra de la tendencia me intriga y, la verdad, estoy muy lejos de ver claro en este asunto.

Saludos.

16 Octubre, 2006, 08:36 am
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola



En esto no puedo estar de acuerdo. Razonas como si los cardinales transfinitos no existiesen. Si hablamos de límites en lo transfinito debemos en principio atenernos a las mismas reglas que cuando hablamos de números finitos. Nadie diría que el límite de <1, 1'5, 1'75,...> es 3. Por la misma razón el límite de <2, 4, 8, ...> no puede ser alef_1 sino alef_0, que a su vez no puede ser c (la potencia del continuo). Además, empezando con una cantidad finita y duplicándola una cantidad numerable de veces, no podemos trascender lo numerable.


Reitero lo que dije.

OJO, no razono como si los cardinales trasnfinitos no exisitiesen. A ver si queremos ser precisos hay que concretar que se entiende por "límite". No se a que le estas llamando el límite de <2,4,8,...> o <1,1.5,175,...>. Insisto el límite numérico usual NO DISTINGUE ENTRE CALIDADES DE INFINITO. Es un límite topológico donde en \( R\cup\{\infty\} \) estamos tomando la topología usual unida a los abiertos (a,+\infty]. No hay una buena forma de extender esta topología a todos los "infinitos" porque, estos se comportan como conjnutos discretos. Dicho de otra forma, definir una topología es determinar que entendemos por puntos "cercanos". ¿Cuales serían los puntos cercanos a alef_1, alef_2,alef_3 ?...

Lo más lógico si uno quiere trabajar con límites transfinitos, es trabajar con límites conjuntistas teniendo en cuenta que al fin y al cabo la teoria de los cardinales se refiere a clases de conjuntos salvo biyección.

En cualquier caso está claro que el manejo de los "infinitos" es delicado. Eso hace extremadamente necesario precisar claramente los coneptos que se están manejando, ya que las aproximaciones o intuiciones son confusas. Por tanto es imprescindible que concretes a que le estas llamando "paso al inifinito" o "tendencia de una sucesión". Estás mezclando sucesiones de conjuntos con la sucesión de sus cardinales y como dije eso no funciona bien.

Saludos.





16 Octubre, 2006, 10:01 pm
Respuesta #6

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
El_manco escribió:

>>En cualquier caso está claro que el manejo de los "infinitos" es delicado. Eso hace extremadamente necesario precisar claramente los coneptos que se están manejando, ya que las aproximaciones o intuiciones son confusas. Por tanto es imprescindible que concretes a que le estas llamando "paso al inifinito" o "tendencia de una sucesión". Estás mezclando sucesiones de conjuntos con la sucesión de sus cardinales y como dije eso no funciona bien.<<

Estoy bastante de acuerdo. Salvo que no estoy mezclando conjuntos y cardinales de conjuntos, si relees lo que escribí verás que no hay confusión. Lo que quiero resaltar es que las operaciones de paso al límite que usamos para resolver operaciones con infinitos términos en el caso de los números finitos parecen no funcionar con cardinales transfinitos.

Mientras operamos con números finitos el límite puede verse como la culminación de una tendencia; pero en operaciones conjuntistas con conjuntos infinitos el resultado es sorprendente a veces: el resultado de una operación con infinitos términos que entendemos ha sido totalmente realizada no se presenta como culminación de la sucesión que podemos generar mediante operaciones parciales; eso es lo llamativo en los ejemplos que he ofrecido.

De todas manersa sigo viendo algo extraño en el árbol binario completo: ¿cómo puede llegarse a c duplicando una cantidad numerable de veces un número finito inicial?

El árbol binario no es como, por ejemplo, la conocida tabla usada para demostrar la numerabilidad de los racionales; podemos representarnos esa tabla como extendiéndose indefinidamente sin necesidad de suponerla acabada de hecho. El árbol binario alcanza c sólo cuando está acabado de hecho, como si diese un salto hasta lo no numerable justo en la última etapa, en la que la punta final de cada rama representa una secuencia binaria infinita distinta.

Tal vez lo no numerable no encaje bien con la representación gráfica discreta.

Saludos


17 Octubre, 2006, 11:20 am
Respuesta #7

Numerarius

  • Lathi
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino
LauLuna, a mí se me ha ocurrido un rompecabezas parecido. Consideremos los números reales entre 0 y 1, puestos en base binaria.

Ahora consediremos el siguiente orden:

0'000
0,100
0,010
0,110
0,001
0,101
0,011
0,111
.......

¿No se podrían enumerar en este orden todos los números reales entre 0 y 1?  ;D

Se podría objetar que no podemos llegar a conseguir un número irracional, puesto que tiene una expresión decimal infinita. Pero, según esta objeción, tampoco podríamos encontrar un conjunto infinito numerable simplemente con el método de incrementar en 1 cada número natural a partir de 0.

Este pequeño rompecabezas me tiene perplejo. ???

17 Octubre, 2006, 11:48 am
Respuesta #8

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 El ejemplo es excelente porque es exactamente el mismo que el de las ramas de LauLuna expresado de otra forma.

 Pero NO, en tu lista NO están TODOS los números reales ni mucho menos, sino SOLO los que tienen una expresión decimal finita en binario ("muy pocos").

Citar
"..., tampoco podríamos encontrar un conjunto infinito numerable simplemente con el método de incrementar en 1 cada número natural a partir de 0..."

Supongo que te refieres a esta construcción:

\( A_1=\{0\} \)

\( A_2=\{0,1\} \)

\( A_3=\{0,1,2\} \)

\( A_4=\{0,1,2,3\} \)

ecétera y ahora tomamos la unión de todos ellos:

\( A=\cup{}_{n\in \N} A_n \)

y A resulta ser un conjunto numerable (de hecho N).

Hagamos algo parecido con tu lista de números decimales:

Llamo \( B_i \) al conjunto de números decimales con i decimales:

\( B_1=\{0'0,0'1\} \)

\( B_2=\{0'00,0'01,0'10.0'11\} \)

\( B_3=\{0'000,0'001,0'010,0'011,0'100,0'101,0'110,0'111\} \)

ecétera

Tomo la unión de todos ellos:

\( B=\cup{}_{n\in \N} B_n \)

y de nuevo B resulta ser un conjunto numerable. Como dije antes B NO SON todos los números reales entre 0 y 1 sino sólo aquellos con un número finito de decimales.

Dicho todo esto, no acabo de ver donde está la contradicción, el problema, o el rompecabezas.

Saludos.






 

17 Octubre, 2006, 12:21 pm
Respuesta #9

Numerarius

  • Lathi
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino
Bueno, el rompecabezas surge sólo si suponemos que mediante esa enumeración se obtendrían TODOS los números reales. En ese caso R sería a la vez numerable y no numerable.

Pero, en realidad, como me has explicado, sólo se obtienen los reales con expresión decimal finita. Así que no hay problema. ;D