Ver canal RSS

Demostraciones

Numerando los racionales con la sucesión diatómica de Stern

Calificación: 1 votos, 5,00 de media.
Como ya sabrán muchos por acá, el conjunto de los números racionales es numerable, es decir, existe una función biyectiva entre el conjunto de los números racionales y el conjunto de los números naturales, o más coloquialmente, todos los números racionales se pueden poner en una lista (en una lista infinita, pero en una lista al fin y al cabo), uno se puede convencer de esto con la siguiente imagen:



Vemos que todo número racional positivo aparece en este arreglo bidimensional (el número \frac{p}{q} está en la celda (p,q)), y además se ve que el camino seguido por la flecha alcanza a todos números del arreglo, de ahí se pueden enlistar a los números racionales así:

[1,2 ,\frac12, \frac13, 3, 4, \frac32, \frac23, \frac14,...]

(Los números entre paréntesis en el arreglo no se cuentan ya que ya se han contado, por ejemplo, \frac22 =1, por eso saltamos \frac22)

Meter a todos los racionales en una lista ya teniendo metidos a los racionales positivos es muy fácil, la lista simplemente sería así:
[0,1,-1,2,-2 ,\frac12,- \frac12, \frac13, -\frac13, 3,-3, 4,-4, \frac32, -\frac32, \frac23, -\fra...

Es decir colocar primero el cero, y luego ir intercalando racionales positivos con sus respectivos inversos aditivos.


La Sucesión diatómica de Stern

Se define la sucesión diatómica de Stern de la siguiente manera:
a_0=0
a_1=1

 
\left\{ 
\begin{array}{cl} 
a_{2n} &=a_n \\ 
a_{2n+1}&=a_n+a_{n+1} 
\end{array} 
\right.


Algunos términos de la sucesión:
0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, ...
La gráfica de los primeros 4096 terminos (a_n en el eje vertical, n en eje horizontal)



Teorema: La función n \to \dfrac{a_n}{a_{n+1}} es una biyección de Z_+ en Q_+.

Prueba:
Para demostrar el teorema se prueba que cada par de primos relativos [a,b] aparece exactamente una vez en la lista:
L=[1,1], [1,2], [2,1], [1,3],...,[a_n,a_{n+1}],...

(Podemos pensar a cada pareja en la lista, como un número racional, es decir [a_n,a_{n+1}] representa al número \frac {a_n}{a_{n+1}})
(Los números racionales pueden ser representados de distintas maneras, por ejemplo, \frac12 =\frac24. Así, si [1,2] y [2,4] aparecen en la lista, la función no sería inyectiva. Por esta razón se exige que las parejas de números sean primos relativos, para evitar repeticiones.)


Ahora se define el algoritmo lento de Euclides (SEA) sobre parejas de números positivos: dado un par [a,b] se resta el número más pequeño del más grande, se repite este procedimiento hasta que ambos sean iguales. Por ejemplo:  [8,3] \to [5,3] \to [2,3]  \to [2,1] \to [1,1].

Algunos resultados:

-Este algoritmo siempre termina: Ningún elemento del par puede llegar a ser negativo o cero, ya que el algoritmo resta al más grande el más pequeño, así que lo peor que podría pasar es que uno de los elementos del par llegue a 1 sin que sea igual al otro, pero como 1 es el número más pequeño, empezará a restar de uno en uno al otro número, y claramente ambos números llegarán a ser 1’s y con esto el algoritmo finaliza.

-El máximo común divisor se preserva en cada paso del algoritmo: Para ver que el m.c.d se conserva en cada paso, supongamos que  a < b y g = m.c.d(a, b).
Como g divide a a y a b, es claro que g divide a b-a,luego, g es divisor común de a y b-a. Supongamos que k divide a b - a y a a, es claro entonces que k divide a b, ahora, como g es el máximo común divisor de a y b, tenemos que k \leq  g. Por tanto g=m.c.d(a,b-a).

- El algoritmo aplicado a [a,b] finaliza en [g,g], con g=m.c.d(a,b): Es consecuencia inmediata de los dos 2 últimos resultados.

Sea L_n=[a_n,a_{n+1}], veamos los siguientes resultados:

1) SEA: L_{2n}, L_{2n+1} \to L_n

Sea  L_{2n}=[a_{2n},a_{2n+1}], por la definición de la sucesión tenemos que:  L_{2n}=[a_{n},a_{n}+a_{n+1}], de modo que al aplicar el SEA tenemos que  L_{2n}=[a_{n},a_{n}+a_{n+1}] \to [a_n,a_{n+1}]=L_n.
Para L_{2n+1} se hace igual.

2) Si SEA: [a,b] \to L_n, entonces [a,b]=L_{2n} o [a,b]=L_{2n+1}

Supongase que a < b, vemos entonces que SEA : [a, b] \to [a, b-a], de esto tenemos que [a, b-a]=L_n=[a_n,a_{n+1}] , con lo que a = a_n y b-a = a_{n+1}, de modo que b = a_n+a_{n+1}, por tanto [a, b] = [a_n, a_n+a_{n+1}] = [a_{2n}, a_{2n+1}] = L_{2n}.
Si b < a se obtiene el otro caso haciendo el mismo procedimiento.

Resultados finales:

A) Para cada número natural n, L_n es un par de primos relativos:

Por los resultados 1) y 2), más el hecho de que el m.c.d se conserve en cada paso y que L_1 = [1, 1] es un par de primos relativos, se tiene que L_2 y L_3 son dos pares de primos relativos, por esa misma razon L_4, L_5, L_6 y L_7 son parejas de primos relativos, etc.
Con esto es facil ver que para todo n se tiene que L_n es un par de primos relativos, esto es, m.c.d(a_n, a_{n+1}) = 1. (se podría probar por inducción fuerte)

Nombre:  Imagen2.png
Vistas: 1397
Tamaño: 12,4 KB
La figura ilustra (sugiere) el hecho de que cualquier L_n está conectado con L_1.

B) Todo par de primos relativos está en la lista L:

Si existe un par de primos relativos [a, b] que no esté en L, entonces todos los sucesores bajo el SEA, incluyendo el [1, 1] no estarían en L. Absurdo.

C)Ningún par de primos relativos aparece más de una vez en la lista L:

Ningún par de primos relativos aparece más de una vez en la lista, de otra manera, se tendría que existe un número más pequeño n tal que L_n = L_m para algún m > n. Aplicando un paso del SEA a L_n y a L_m se tiene que L_{[\frac{n}{2}]}=L_{[\frac{m}{2}]}^{(*)}. Dado que [\frac{n}{2}] <n tenemos que [\frac{n}{2}]=[\frac{m}{2}] (Esto es debido a que n es el número más pequeño tal que existe algún m>n tal que L_n=L_m, de esto se tiente que [\frac{n}{2}] no puede cumplir esa propiedad ya que es más pequeño que n). Una solución posible a esta ultima ecuación es m=n+1, y vemos además que m=n+2 ya no puede ser solución ya que [\frac{m}{2}]=[\frac{n+2}{2}]=[\frac{n}{2}+1]>[\frac{n}{2}]. Claramente m=n+3, n+4, .... no pueden ser soluciones por la misma razón que m=n+2 no lo es.

Por tanto, la única posible solución es m=n+1, pero esto implica que L_{n}=L_{n+1}, es decir, que [a_n,a_{n+1}]=[a_{n+1},a_{n+2}], con lo que se tiene que a_n=a_{n+1}=a_{n+2}, una contradiccion(.^{**})

En conclusión, de A), B) y C), tenemos que todo par de primos relativos aparece una única vez en la lista L (y en la lista no hay parejas que no sean de primos relativos).

QED.

Para ver la prueba original y más cosas curiosas sobre esta sucesión mirar acá.

.^{(*)} Ejercicio.
.^{(**)}. Todos los terminos de la sucesión serían ceros, ejercicio .

Enviar "Numerando los racionales con la sucesión diatómica de Stern" a del.icio.us Enviar "Numerando los racionales con la sucesión diatómica de Stern" a Google Enviar "Numerando los racionales con la sucesión diatómica de Stern" a Yahoo! Enviar "Numerando los racionales con la sucesión diatómica de Stern" a Digg Enviar "Numerando los racionales con la sucesión diatómica de Stern" a Diigo Enviar "Numerando los racionales con la sucesión diatómica de Stern" a StumbleUpon Enviar "Numerando los racionales con la sucesión diatómica de Stern" a Gennio Enviar "Numerando los racionales con la sucesión diatómica de Stern" a Menéame

Actualizado 13/10/2014 a las 19:54:52 por javier m

Categorías
Matemáticas

Comentarios

  1. Avatar de Weip
    Interesante artículo, nunca había visto este tema en profundidad. Cuando tenga más tiempo leeré el documento del link y veré si puedo hacer los dos ejercicios. Por cierto, la gráfica de la sucesión me recuerda a unos pulmones. O a la fachada de la Sagrada Familia, con imaginación jajaja.
    Actualizado 24/09/2014 a las 19:12:00 por Weip
  2. Avatar de javier m
    Hola, gracias por comentar, el articulo me salió algo largo y no estaba seguro de que alguien se animara a leerlo.

    A mi la gráfica me recuerda a la autosemejanza caracteristica de los fractales, y en cada "paquete" veo la cara de un perro, donde los 2 picos son las orejas (o a este)
  3. Avatar de angel relativamente
    Muy muy interesante Javier, conocía la idea intuitiva de la primera ilustración pero nunca había visto demostrado el isomorfismo. La verdad es que \mathbb{Q} es un conjunto muy bonito por ser numerable y denso, nunca dejará de sorprenderme esa propiedad
  4. Avatar de javier m
    Gracias.
    Lo cierto es que esta demostración no es muy conocida y además en el articulo la dan muy resumida, así que decidí escribir sobre ella y desarrollar un poco más la prueba.
  5. Avatar de Jose D. Escobedo
    En el intervalo cerrado [0,1], se define 0=\dst \frac{0}{1} y 1=\dst \frac{1}{1} como los elementos racionales que originan a los otros, luego tambien se define la operación de "el mediante" como \dst \frac{a+c}{b+d} de donde \dst \frac{a}{b} < \dst \frac{c}{d} con b, c, d \in \mathbb{N} y a \in \mathbb{N} \cup {0}.

    \dst \frac{1}{ 2}=\frac{0+1}{1+2 }, luego \dst\frac{1}{3 }=\frac{0+1}{1+2 } , posteriormente \dst \frac{2}{3 }=\frac{1+1}{1+2 }, y así sucesivamente... de este modo no tendré el problema de generar cosas como: \dst\frac{2}{4 }

    Luego empiezo a enlistarlos 1 a 1 con los naturales,
    \dst\frac{0}{1 }\to 1, \dst\frac{1}{1 }\to 2, \dst \frac{1}{ 2} \to 3,\dst\frac{1}{ 3} \to 4 y así sucesivamente.

    Y al final ¿qué se a probado?, pues que los racionales en el intervalo cerrado [0,1] tienen el mismo cardinal que los naturales. ¿Qué pasa ahora con el semi-intervalo cerrado (1,2] con los elementos como \dst \frac{3}{2 }, que se genera de "el mediante" \dst \frac{1+2}{1+1}

    Al final que me permite hacer semejante enunciado, pues el "axioma de elección" y que los racionales son "densos."

    Creo que el "mainsteam" de los matemáticos necesita cambiar su acercamiento a las matemáticas.

    Saludos Javier, buen articulo, pero no estoy de acuerdo con el.
    Actualizado 25/09/2014 a las 22:33:56 por Jose D. Escobedo (deletreo)
  6. Avatar de javier m
    Lo siento Jose, pero no consigo ver tu punto.
  7. Avatar de Jose D. Escobedo
    Mi punto es que, no tienen el mismo cardinal los racionales y naturales . Cuando se habla de conjuntos infinitos se llega a muchas paradojas. La teoria de conjuntos que trabaja bien es unicamente para los conjuntos finitos. Ademas los argumentos no son claros en estos temas (los matemáticos del "mainstream" usan la palabra "riguroso" sino me equivoco.)

    saludos
  8. Avatar de javier m
    Lo siento pero no justificas tus afirmaciones y no estoy de acuerdo
    ¿Como argumentas que el cardinal de ambos conjuntos es distinto, ya habiendo varias pruebas de que son iguales?
    No conozco bien el tema, pero que yo sepa, con los axiomas de ZF ya no hay paradojas conocidas.
  9. Avatar de Jose D. Escobedo
    Aquí esta una justificación javier, cito esto: "(los números entre paréntesis en el arreglo no se cuentan ya que ya se han contado, per ejemplo, \frac{2}{ 2}=1,, por eso saltamos \frac{2}{2 }). Digamos que sigo el arreglo y no me importa y cuento \frac{1}{ 1}\to 1, \frac{2}{ 1}\to 2, \frac{1}{2 }\to 3, \frac{1}{ 3}\to 4, \frac{2}{2 } \to 5, así sucesivamente... . Es decir que los naturales son mas infinitos que los racionales positivos porque me alcaza hasta para para contar fraciones equivalentes y el número 1=\frac{1}{ 1}=\frac{2}{2 }=\frac{3}{3 }=... uno infinta veces. Pregunta ¿tiene sentido contar tantos infinitos?

    Otra justificación, cito esto otro: " Meter a todos los racionales en una lista ya teniendo metidos a los racionales positivos es muy fácil, la lista simplemente sería así: [0, 1, -1, 2, -2, \frac{1}{ 2}, -\frac{1}{ 2},...]" Bueno pues para que yo no me quede con las ganas voy a meter mas números.

    [0, -1, 1, 2, -2, \sqrt{2}, -\sqrt{ 2}, \frac{1}{2 }, -\frac{1}{2 }, \frac{1}{\sqrt{2} }, -\frac{1}{ \sqrt{2}},... ], pues los naturales me alcanzan para enumerar a los \Mathbb{Q} unión \Mathbb\sqrt{Q}, al final a mi alcanzó hasta para incluir "algunos" irracionales, es decir me alcanzó para mas.

    Otra justificación, a veces tengo por manía contar los racionales de esta forma \frac{1}{k } con k>1 y en los naturales, luego cuento lo de esta forma \frac{2}{ m} con m>2 y en los naturales, y así sucesivamente. Es decir que [\frac{1}{ 2} \to 1,\frac{1}{3 }\to 2,...,\frac{1}{ n+1}\to n,.... con esta manera de contar los naturales y los racionales (relaconandolos 1 a 1) de la forma \frac{1}{ k}, puedo afirmar que tienen el mismo cardinal, pero todavía necesito contar los de esta forma \frac{2}{m }, (claro esta que tengo que evitar las fracciones equivalentes, apelando a lo que hizo javier anteriormente. Luego los de la forma \frac{3}{ l} con l>3 y en los naturales. Siguiendo este procedimiento los racionales son mas numérosos. Ah! y despues lo mismo con los negativos.

    Finalmente, dependiendo como cuente los racionales a veces son, "mas infinitos," numerosos que los naturales, y a veces lo son los racionales. No hay contradicción alguna, no para nada todo muy claro y "riguroso"

    Saludos
  10. Avatar de javier m
    hola Jose, mira, se dice que dos conjuntos tienen el mismo cardinal si existe una función biyectiva entre ellos, de modo que para justificar la afirmación de que dos conjuntos tienen distinto cardinal, se debe probar que no existe ninguna biyección entre ellos, y eso tus ejemplos no lo hacen. Lo que tu dices es que los siguientes conjuntos son equipotentes N, Q,Q_+, Q_+ \cup \sqrt{Q_+}, \{ \frac{1}{k}: k \in N \}, pero eso por raro que sea no es contradictorio.

    El problema que me parece que tienes con los conjuntos infinitos, es en esencia que encuentras contradictoria esta propiedad:

    Un conjunto A es infinito si y solo si existe un subconjunto propio de A con el mismo cardinal de A.

    Claro, eso es raro. Que Q_+ sea subconjunto propio de Q_+ \cup \sqrt{Q_+}, pareciera sugerir que Q_+ tiene menos elementos, porque pues, no tiene todo lo que tiene Q_+ \cup \sqrt{Q_+}, y por eso es raro que tengan el mismo cardinal, pero yo no tengo culpa de eso . Eso es raro, es contraintuitivo, pero no es contradictorio, por lo menos no lo es con la definición de igualdad de cardinales que doy.

    En cuanto a lo del rigor no se que decirte. Saludos
    Actualizado 02/10/2014 a las 16:13:48 por javier m
  11. Avatar de Jose D. Escobedo
    Javier no te sientas mal, no estoy tratando de molestarte, simplemente estoy tratando de que a las matemáticas se les vea de una manera mas crítica.

    Volviendo al tema, en la wikipedia en espa\~ nol, en el número cardinal, empieza diciendo: "El cardinal indica el número o cantidad de elementos de un conjunto, sea esta ...."

    Pues eso es lo que estaba haciendo, pero llegué a diferentes concluciones.

    En inglés, en la wikipedia, dice: "In mathematics, cardinal numbers, or cardinals for short, are generalizatons of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a number - the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite sets." Pues hasta aquí en cuanto "finite sets" todo muy claro, pues nada mas se cuenta el número de elementos y eso es todo, pero cuando hablamos de infinite sets se mide diferente, ahora hay que tomar en cuenta el término "transfinite" le das "click" al termino (en la misma wikipedia) y parafraseando te dice que es un término que es algo mas grande que "finito" (que descubrimiento tan grande!!) y que ese término fue inventado (coined) por Cantor (claro para justificarse.)

    Luego, siguiendo en la wikipedia en inglés, "Cardinality is defined in terms of bijective functions. Two sets have the same cardinality if and only there is a one to one correspondence(bijection) between the elements of the two sets, In the case of finite sets, this agrees with the intuitive notion of size." Hasta a aquí nada nuevo para conjuntos finitos todo muy comprensible, pero cuando empieza hablar de conjuntos infinitos, " In the case of infinite sets, the behavior is more complex.." pues claro que el comportamiento es ma complejo, tanto así que...

    Bueno Javier escribí mucho mas, pero no se que pasó que se borró todo. Luego,
    me dió pereza volver a escribir todo de nuevo. Te diré que toqué desde discrepancias de definiciones en algunas teorías, hasta el cambio de usar "set" a "class" como excusa, tambien cité como usar el axioma de "choice" para favorecer uno u otro punto de vista. Ademas, mencioné lo repetitivo e inoperante de las definiciones de cardinality y el teorema de Cantor que parece ser lo mismo que la misma definicion de cardinality.

    Saludos
  12. Avatar de javier m
    Bueno

    Saludos.
  13. Avatar de visitante20160513
    Quisiera incidir en el debate en relación con el asunto de la cardinalidad. Ya he participado en otros debates similares y la verdad es que existe algo extraño en el concepto de cardinalidad cuando se aplica a conjuntos infinitos, aunque la verdad es que los argumentos que esgrimen los matemáticos parecen irrefutables, cuando se basan en los números transfinitos de Cantor. Viendo el problema de una forma más general parecería paradógico o más bien contradictorio con la intuición el hecho de que puedan construirse pares de conjuntos (siempre infinitos) que satisfagan las tres premisas siguientes:


    [CENTER][TEX]A\neq B\qquad\quad A\subset B\qquad\qquad \#A=\#B[/TEX][/CENTER]


    Por ejemplo los números naturales en los enteros, o los naturales en los racionales. El hecho de que ambos conjuntos tengan el mismo cardinal obliga a que ambos conjuntos sean biyectivos, lo que aparentemente contradice el hecho de que uno de los conjuntos esté estrictamente incluido en el otro.

    Cuando llego a esa conclusión a mi me chirrían todas las tuercas pero la verdad es que los argumentos matemáticos para concluir con tal cosa parecen ser irrefutables. Un ejemplo claro de esto podría ser por ejemplo la afirmación perfectamente demostrable de que el conjunto de los puntos de una esfera tiene la misma cardinalidad que el conjunto de puntos de su superficie y por lo tanto ambos conjuntos son biyectivos. Pues a pesar de todos los argumentos matemáticos a favor de tal cosa, irrefutables por otra parte, a mi me siguen chirriando todas las tuercas. Pero no hay una explicación suficiente, por lo menos hasta hoy nadie la ha encontrado.

    Salu2, Jabato. :)
    Actualizado 03/10/2014 a las 21:03:31 por visitante20160513
  14. Avatar de beliytxuri
    Bueno, veo que hay gente que no se siente muy cómoda con la definición de cardinalidad cantoriana (card(A)=card(B) si y sólo si A y B son biyectivos), que produce las paradojas (que también asombraron al propio Cantor) comentadas anteriormente.

    Animo a que se plantee una definición alternativa de cardinalidad para que, por ejemplo, se produzcan resultados como card(Z) = 2{\aleph}_{0 }, o que, card({Q}^{+ })={{\aleph}_{0 }}^{2 }, que creo provocarían mayor simpatía entre la afición.

    Por cierto, muy interesante el artículo.

    Salud.
    Actualizado 08/04/2015 a las 12:07:00 por beliytxuri
  15. Avatar de javier m
    Hola, pues, esas tales paradojas no son paradojas realmente

    Y en cuanto a lo otro que dices, tal vez los ordinales ayuden un poco (no exactamente como lo pones)

    Por ejemplo, si ordenas los naturales así:

    0,1,2,3,....
    y los enteros así:
    0,1,2,3.....-1,-2,-3....

    tienes que ord(Z)=ord(N) \cdot 2

    Y si ordenas Q^+ así

    1, \frac12 , \frac 13 ,...., 2, \frac23 , \frac25,...., 3, \frac32 ,\frac34 ,\frac35,....., 4, \f... etc etc etc

    tienes que ord(Q^+)=(ord(N))^2

    Pero en todo caso depende del orden particular que le des a los conjuntos....

    PD: Veo que eres licenciado en matematicas , así que todo lo que dije sobra xD
    Gracias por el comentario
    Actualizado 08/04/2015 a las 19:06:58 por javier m

Trackbacks

Trackbacks totales 0
URL de trackback: