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

[QED]

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, -\frac23, \frac14, -\frac14,...]$

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$

$<br /> \left\{<br /> \begin{array}{cl}<br /> a_{2n} &=a_n \\<br /> a_{2n+1}&=a_n+a_{n+1}<br /> \end{array}<br /> \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)


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 .

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:

$A\neq B\qquad\quad A\subset B\qquad\qquad \#A=\#B$

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.

[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.

[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, \frac43 ,.....$ 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