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 .

[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

[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[Error LaTeX: Compilación LaTeX fallida] ol, 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

[javier m]

Bueno

Saludos.