El árbol de Stern-Brocot y la numerabilidad de los números racionales

Que el conjunto de los números racionales (esto es, las fracciones) es un conjunto numerable (es decir, que tiene la misma cantidad de elementos que los números naturales) es un hecho bastante conocido. Pero a pesar de ello hay gente que todavía no llega a asimilarlo, que no es capaz de comprenderlo, que (por decirlo de alguna forma) no se cree que haya tantos números naturales como fracciones. Para todos vosotros: pues es cierto, hay tantos números naturales como fracciones. Y lo vamos a demostrar de una manera muy elegante.

Dados dos números racionales, p \over q y r \over s, definimos su mediana como la fracción p+r \over q+s. Es sencillo demostrar que la mediana de dos números racionales es siempre un número racional que está entre ellos. Por poner un ejemplo, la mediana de 2 \over 5 y 6 \over 7 es {8 \over 12}={2 \over 3}, que es un número racional que está entre 2 \over 5 y 6 \over 7.


Un detalle: En este post trabajamos en todo momento con fracciones irreducibles. Es decir, fracciones en las que numerador y denominador no tienen factores comunes.


Partiendo de dos fracciones concretas, y con la ayuda de la mediana, vamos a construir más fracciones. Y vamos a partir de las fracciones 0 \over 1 y 1 \over 0


Vale, sí, 1 \over 0 no es una fracción, no es un número racional. Seguro que más de uno ha dicho cuando la ha visto:

– ¡Pero si eso es infinito!

Bueno, nos vamos a permitir la licencia de tomar esta expresión como fracción, y además esa idea de que esa expresión es infinito no nos vendrá mal.


…para construir las demás. Si calculamos la mediana de estas dos fracciones obtenemos el número 1 \over 1, que por lo que hemos dicho antes está entre las dos fracciones iniciales:

Calculemos ahora las medianas de cada pareja de números consecutivos que llevamos. La mediana de 0 \over 1 y 1 \over 1 es 1 \over 2 y la de 1 \over 1 y 1 \over 0 es 2 \over 1, quedando todos estos números colocados de la siguiente forma:

Volvamos a hacer lo mismo con cada pareja de números consecutivos de la lista, obteniendo ahora los siguientes números colocados de esta forma:

Coloquemos ahora todo en forma de árbol. Comencemos por 1 \over 1. De ella salen dos hijos, que son sus medianas con 0 \over 1 y 1 \over 0. Ahora, de cada una de estas medianas salen otros dos hijos, que son a su vez las medianas de ellas con los dos elementos que tiene a izquierda y derecha en el paso anterior, y así sucesivamente. Obtenemos así el siguiente árbol, denominado árbol de Stern-Brocot:

Y se llama de Stern-Brocot porque lo descubrieron de forma independiente Moritz Stern (en 1858), alemán especialista en teoría de números, y Achille Brocot (en 1861), fabricante de relojes.

Bien, vamos a demostrar que todo número racional positivo aparece exactamente una vez en el árbol de Stern-Brocot y además lo hace como fracción irreducible. Para ello es necesario saber que dadas dos fracciones consecutivas (en el sentido de que una es descendiente de la otra) del árbol, p_1/q_1 y p_2/q_2, se tiene que

p_2 \cdot q_1 - q_2 \cdot p_1=1 (tomándolas en el orden adecuado)

No es difícil de demostrar este hecho, podéis intentarlo en los comentarios (sin mirar las fuentes del final del artículo, no seáis tramposos).

Como hemos comentado antes, la mediana de dos fracciones es un número racional que aparece estrictamente entre esas dos fracciones, por lo que una fracción no puede aparecer dos veces en el árbol.

Veamos ahora que toda fracción irreducible de la forma a/b está en el árbol:

En la raíz del árbol, el mínimo valor de la suma de numerador y denominador de una fracción (a partir de ahora nd-suma) es dos (tenemos la fracción 1 \over 1). En el primer nivel (el siguiente a la raíz), el mínimo valor de la nd-suma es 3. Y, en general, se puede probar por inducción que el mínimo valor de la nd-suma en el nivel n es n+2.

Si a/b es una fracción irreducible que no está en el árbol, entonces la podemos localizar entre dos fracciones consecutivas del mismo (recordad, dos fracciones que cumplen que una es la descendiente de la otra) con la condición de que una de ellas pertenezca al nivel a+b-1. Pongamos que son p_1/q_1 y p_2/q_2. Sabemos entonces que p_2 \cdot q_1 - q_2 \cdot p_1=1.

Bien, tendríamos por tanto que p_1/q_1 < a/b < p_2/q_2. De aquí, operando, obtenemos que q_1 \cdot a - p_1 \cdot b > 0 y que p_2 \cdot b - q_2 \cdot a > 0. Como todos esos números son naturales, tenemos que q_1 \cdot a - p_1 \cdot b \ge 1 y que p_2 \cdot b - q_2 \cdot a \ge 1.

Multiplicando ahora la primera expresión por p_2+q_2 y la segunda por p_1+q_1 y sumándolas obtenemos, después de algunas operaciones y simplificaciones, lo siguiente:

a+b \ge p_1+q_1+p_2+q_2

Pero habíamos dicho que una de las dos fracciones pertenecía al nivel ´a+b-1, nivel en el que como mínimo la nd-suma es a+b-1+2=a+b+1. Tendríamos entonces que:

a+b \ge a+b+1+ \mbox{algo positivo}

lo cual es a todas luces imposible. Por tanto toda fracción irreducible aparece en el árbol de Stern-Brocot.

En particular, esto nos demuestra que el conjunto de los números racionales positivos es numerable, ya que el árbol se ha creado en una cantidad numerable de pasos y todos los racionales positivos están en él. Como hay tantos racionales negativos como racionales positivos, tenemos que el conjunto de los números racionales es numerable.

El árbol de Stern-Brocot también tiene una interesante relación con las fracciones continuas. Para quien esté interesado dejo unos cuantos enlaces con información sobre el tema justo debajo de este párrafo.


Fuentes y enlaces relacionados:

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

16 Comentarios

  1. Una chorradita… en la fórmula p2*q1-q2*p1=1, no ¿falta el valor absoluto?

    Vamos a definir como “madres” a las fracciones que usamos para calcular la mediana (en el gráfico no queda muy claro, por ejemplo, si se considera 2/3 descendiente de 1/1. En esta demostración sí lo es).
    Por inducción, sea p1/q1 descendiente de p2/q2 que a su vez es descendiente de p3/q3 que a su vez desciende de p4/q4. Si abs(p3*q2-q3*p2)=1 y abs(p4*q2-q4*p2)=1 [nota: p2/q2 desciende de p3 y p4 por lo que la hipótesis de inducción es que se cumplen ambas] veamos que abs(p2*q1-q2*p1)=1
    Caso1: p1/q1 desciende de p2/q2 y p3/q3. p1=p2+p3; q1=q2+q3.
    abs(p2*q1-p1*q2)=abs( p2*(q2+q3) – q2*(p2+p3) ) = abs(p2*q3-p3*q2) = 1 por hipótesis de inducción.

    Caso2: p1/q1 desciende de p2 y p4. p1=p2+p4; q1=q2+q4
    abs(p2*q1-p1*q2)=abs( p2*(q2+q4) – q2*(p2+p4) ) = abs(p2*q4-p4*q2) = 1
    por hipótesis de inducción, al descender p2/q2 de p4/q4

    Publica una respuesta
  2. Totalmente de acuerdo con el acuerdo de la numerabilidad de los racionales con esta y otras demostraciones (alguna vista en este mismo blog)

    El problema no estriba ahí, sino en el propio concepto de la numerabilidad.

    Por ejemplo, el conjunto {1,2,3} decimos que tiene una cardinalidad 3 (no que tiene 3 elementos)

    El conjunto [1,2,3,4,5] decimos que tiene una cardinalidad 5 (no que tiene 5 elementos)

    En cambio del conjunto N solo decimos que tiene una cardinalidad N(0) y no decimos cuantos elementos tiene (o decimos, en nuestro desconocimiento, infinitos).

    No es lo mismo el Nº de elementos de un conjunto finito que la cardinalidad ni el nº de elementos de un conjunto no finito (y es adrede para no poner infinito). Son conceptos tangibles en la vida (o linguistica) contra modelos matematicos.

    Podríamos fácilmente demostrar que para todo subconjunto de N tal que n€N si n<M con M €N el número de elementos pares es menor que el nº de elemetos del conjunto (no hay biyectiva) y al aplicar inducción completa llegar al absurdo de que no hay biyectiva en todo N.

    Yo creo que no es lo mismo contar elementos de un conjunto en un conjunto finito o no finito y por tanto tampoco ha lugar ha expresiones del tipo tiene el mismo nº de elementos cuando no somos capaces decir cual es ese Nº.

    Otra cuestión diferente es que dentro de los conjuntos no finitos existan algunos en los que podemos encontrar modelos matemáticos que nos hablen de su cardinalidad (no finita) que sea la misma por encontrar funciones biyectivas entre sus elementos (casualmente la solución es que un no número natural definido como infinito resuelva este problema).

    En resumen, para mi infinito es un concepto matematico no mesurable y la cantidad de elementos de un conjunto es mesurable o no. De ahí a decir que el nº de elementos de un conjunto no finito (concepto no matemático, su cardinalidad si) es el mismo, mayor o menor que el de otro no mesurable (su cardinalidad si) me parece no solo absurdo sino incluso discutible.

    Hay los mismos pares que impares y que naturales.

    Absurdo, pares = impares
    Naturales el doble
    Cardinalidad de pares, impares y naturales = N(0) (esta es la magia del infinito, cuando llegamos a no saber sumar el nº de elementos, nos valemos de la cardinalidad, concepto matematico, y no de la cantidad concepto voy ha llamar humano

    Publica una respuesta
  3. Juanjo, ¿cómo sabes que hay el mismo número de pares que de impares? Pues ves que a cada par le corresponde un impar, es decir, creas una aplicación biyectiva entre ellos (consciente o inconscientemente) Pues lo mismo para ver que hay los mismos pares que números naturales, o los mismos naturales que números enteros, o en este caso los mismos naturales que racionales.

    En el ejemplo que pones para ver que en cualquier subconjunto [0,n] hay menos pares, por inducción demostrarías que vale para cualquier n, y por lo tanto para subconjuntos finitos. La inducción bien aplicada no te llevaría al absurdo del conjunto infinito.

    Que la cantidad de elementos de un conjunto sea “mesurable o no” no nos basta para multitud de casos de la vida real. En general también es valioso saber si es numerable o no lo es, por distinguir los infinitos más comunes.

    Publica una respuesta
  4. Estoy de acuerdo con Juanjo Escribano y la magia del infinito.
    Además se puede “demostrar” que hay igual número de pares que de impares, y a la vez demostrar que hay infinitamente más pares que impares:
    1. Por cada impar, simplemente sumo 1 y obtengo un par. Entonces pares = impares
    2. Por cada impar, multiplico por 2 y obtengo un par. Ya tengo todos los impares asociados a un par y todavía me sobran todas las potencias de 2, o sea infinitos pares sin asociar a un impar. Entonces hay infinitamente más pares que impares,

    Por cierto, aunque no invalida en absoluto el artículo, en el se habla de 1/0 = infinito. Esto es un error. 1/0 no es ni finito ni infinito ni nada de nada. 1/0 no vale, no se puede o no esta definido. No se debe confundir con lim 1/e , con e->0.

    Publica una respuesta
  5. Voy a contar una historia real.
    Cuando era muy pequeño mi madre me inició en los números me explicó con sus palabras lo que representaba el cero y, poco a poco, me enseñó a hacer sumas sencillas, restas y hasta multiplicaciones. La cosa fue bastante bien.
    Después trató (y casi consiguió) enseñarme a dividir.

    Sus palabras: “Tienes seis caramelos y dos bolsillos. ¿Cuántos caramelos puedes guardar en cada bolsillo?”
    Las mías tras mirarme los dedos de las manos: “Tres en cada bolsillo”.
    Mi madre: “¿Y si tuvieras solo un bolsillo?”
    Yo, con relativa rapidez: “Los seis caramelos”.
    Mi madre: “Pues eso significa que seis dividido por dos da tres y que seis dividido por uno da seis”.
    Yo, mirando el vestido de mi madre y mostrando desde temprana edad ser un auténtico anti-Gauss: “Pues como tu no tienes ningún bolsillo no puedes guardarte ningún caramelo así que seis dividido por cero tiene que dar cero”.
    Mi madre, que aunque había hecho el bachillerato era pianista profesional y profesora de música contestó: “Tu nunca tendrás que dividir por cero”.
    Por esa época mi madre y yo teníamos el acuerdo de que yo sería escritor cuando fuera mayor.

    Publica una respuesta
  6. Francesc, quizás faltaría decir que p_2/q_2 es descendiente de p_1/q_1. Así se soluciona, ¿no?

    Cartesiano Caótico, yo no he dicho que 1/0 sea infinito. Simplemente he dicho que “tener esa idea” podría no venirnos mal :).

    Publica una respuesta
  7. Pensando en esto, se me ocurrió hace tiempo una aplicación biyectiva de \mathbb{N} en \mathbb{Q} bastante sencilla.

    La idea consiste en conseguir primero una aplicación biyectiva de \mathbb{Z} en \mathbb{Q} , así:

    Si el elemento de \mathbb{Z} , es cero, su elemento imagen en \mathbb{Q} , es también cero.

    Si a es un entero diferente de cero, se descompone en sus factores primos:

    a = p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdots p_n^{e_n}

    Después, para cada factor p_i^{e_i} , y partiendo del racional r = 1/1 , se hace lo siguiente:

    – Si e_i es par, añadimos el factor p_i^{e_i/2} al numerador de r.

    – Si e_i es impar, añadimos el factor p_i^{(e_i+1)/2} al denominador de r.

    Y finalmente, asignamos a r el mismo signo que tenga a.

    Si observamos que la fracción obtenida es irreducible, puesto que los factores que se van añadiendo arriba y abajo son primos entre sí, es muy fácil ver que a cada entero le corresponde un único racional. Y también es fácil ver que, si se calcula la función inversa, a cada racional le corresponde un único entero.

    Para obtener una aplicación biyectiva de \mathbb{N} en \mathbb{Q} , basta con componer esta función con la archiconocida aplicación biyectiva de \mathbb{N} en \mathbb{Z} y ya está.

    Sé que es mucho más fácil que esto demostrar que \mathbb{Q} es numerable, inyectando \mathbb{Q} en \mathbb{N} , pero, por lo menos a mí, me cuesta mucho menos acomodar esta idea en las neuronas sí tengo un ejemplo de una función biyectiva.

    Publica una respuesta
  8. @Sive Me encanta!
    @Gaussianos. Me lo pareció al principio, pero si nos fijamos, 2/5 y 1/4 son descendientes ambos de 1/3 y en un caso la ecuación te da 1 y en el otro -1. Si operamos la fórmula (dividimos por q2, aislamos p2/q2 y pasamos p1/q1 a la izquierda) nos queda p2/q2 – p1/q1 = 1/(q1*q2); esta ecuación sólo puede ser cierta cuando p2/q2 > p1/q1 y los “hijos” siempre son uno mayor y otro menor que la fracción madre.

    Publica una respuesta
  9. Francesc

    Mi intento era únicamente establecer que en conjuntos finitos existe un natural que nos dice cual es ese número y por tanto podemos hablar de la igualdad o desigualdad del número de elementos de una manera coloquial y tenerlo todos claro.

    En conjuntos no finitos entra un concepto mas abstracto que llamamos infinito y creamos la cardinalidad conforme a una biyección con otros conjuntos no finitos y (en mi opinión un error) hablamos del mismo número de elementos.

    En concreto para mi siempre habrá el doble número de naturales que de pares, y mas racionales que naturales, … ,lo cual no me choca con que tengan la misma cardinalidad. Lo mismo que en limites de división de infinitos nadie se sorprende de que casi nunca de como resultado un 1

    Publica una respuesta
  10. Bueno, trabajar con el infinito se presta a muchas “paradojas” como hemos aprendido aquí en gaussianos. Aprovechando el ejemplo de cartesiano, consideremos M(k):={m € N / m < k}, T(k):={ t€N /t < 2^k} y el conjunto de las partes de M P(k). Resulta que para todo k, T(k) tiene 2^k elementos, M(k) tiene k elementos y P(k), por consiguiente, 2^k elementos. Así que para todo k existe una aplicación biyectiva entre T(k) y P(k). ¿Pero qué pasa cuando llevo k hasta infinito? Resulta que el cardinal de T(k) es aleph0 (biyectiva con los naturales) y el de P(k) es 2^aleph0 que es distinto. ¿Por qué pasa eso? ¿Por qué no puedo extender la aplicación entre T(k) y P(k) hasta el infinito numerable?
    Dicha aplicación sería algo tal que así:
    1.- A un conjunto de naturales le asigno el menor sitio en el que puede aparecer. Llamemos k a este orden. Por ejemplo {0,3,4} estará entre 2^4 (2^k, dónde sólo aparecería hasta el 3) y 2^5
    2.- Ahora ordeno los de este grupo: se descartan los que ya estuvieran anteriormente (todos los que no incluyan un 4) y el resto se ordenan por el menor número de elementos, el menor primer término, el segundo menor término, etc. Sea t esta posición. Nuestro ejemplo estaría justo detrás del {0,2,4} y antes del {0,1,2,4}.
    3.- Por lo tanto al conjunto le corresponde el número natural 2^k+t.

    La pregunta es, ¿por qué esta sencilla aplicación no es biunívoca?

    Publica una respuesta
  11. Me contesto a mí mismo, porque he cometido un error similar al que antes le atribuía a Juanjo. En la aplicación que definía antes, por construcción, todos los subconjuntos finitos de N tenían imagen, es decir el cardinal de {P € P(N)/ card(P) € N} = card(N) numerable. Sin embargo la imagen de los conjuntos infinitos (por ejemplo, el de los pares) no está definida. Así que “hay” muchos más conjuntos infinitos en N que finitos (¿tantos como card(R)-card(N)? ) lo cual es curioso porque por cada subconjunto infinito de N hay infinitos subconjuntos finitos de ese subconjunto (las partes de P(2N) tienen el mismo cardinal que P(N) ) pero todos ellos están contenidos en infinitos subconjuntos infinitos de N, claro.

    Es decir, tengo un huevo de conjuntos, cada uno de ellos con infinitos miembros, y aún así tengo muchísimos más conjuntos que miembros; siendo todos los conjuntos diferentes. Esto sólo puede pasar en matemáticas.

    Publica una respuesta
  12. Francesc, lo siguiente está dicho en broma:
    El concepto matemático “un huevo” puede representar indistintamente una gran cantidad finita o infinita. Para ser más preciso deberías haber dicho “tengo infinitos conjuntos”.

    Publica una respuesta
  13. Tal vez un poco fuera de tema y porque soy apenas un principiante, pero la division por 0 no se encuentra indefinida?, por que si se toma que es infinito eso crearía una contradicción, en la que todos los numeros enteros serían iguales como que 2=1 y 1=2.Por que si la razon entre a/b satisface la propiedad a=r*b, entonces si sutituimos r por 0, b tendría que ser un 0 y no otro número.

    Es solo una duda, pero estoy tratando de adquirir conocimientos matemáticos y tengo unos conocimientos muy limitados en la materia, por desgracia.

    Saludos

    P.D. Gran post y excelente blog.

    Publica una respuesta
  14. Si Eduardo, la división se define siempre con denominador distinto de 0.

    En este caso no lo trabajamos,pero la solución es muy sencilla:

    Si consideramos 0€N le asociamos el 0€Q
    Si no lo consideramos natural le asignamos el 1 y desplazamos la biyección un elemento en los naturales

    Publica una respuesta
  15. Muchas gracias por tu respuesta, Juanjo; ahora ya todo me quedo mas claro. A veces me confundo con este tipo de conceptos y no siempre estoy seguro si es correcto o no.

    Saludos.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Que el conjunto de los números racionales (esto es, las fracciones) es un conjunto…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *