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, y
, definimos su mediana como la fracción
. 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
y
es
, que es un número racional que está entre
y
.
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 y
…
Vale, sí,
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 , 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 y
es
y la de
y
es
, 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 . De ella salen dos hijos, que son sus medianas con
y
. 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, y
, se tiene que
(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 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
). 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
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
. Pongamos que son
y
. Sabemos entonces que
.
Bien, tendríamos por tanto que
. De aquí, operando, obtenemos que
y que
. Como todos esos números son naturales, tenemos que
y que
.
Multiplicando ahora la primera expresión por
y la segunda por
y sumándolas obtenemos, después de algunas operaciones y simplificaciones, lo siguiente:
Pero habíamos dicho que una de las dos fracciones pertenecía al nivel ´
, nivel en el que como mínimo la nd-suma es
. Tendríamos entonces que:
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:
- El árbol de Calkin-Wilf, un árbol parecido a éste del que ya hemos hablado en Gaussianos.
- Trees, Teeth, and Time: The mathematics of clock making, de David Austin.
- Stern-Brocot tree en la Wikipedia en inglés.
- Stern-Brocot Tree and Continuous Fractions en Math Research, Tips and Tricks.
- Stern-Brocot tree en Cut The Knot.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
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… Lee más »
Información Bitacoras.com…
Valora en Bitacoras.com: 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……
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… Lee más »
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… Lee más »
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… Lee más »
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… Lee más »
Francesc, quizás faltaría decir que
es descendiente de
. 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 :).
Pensando en esto, se me ocurrió hace tiempo una aplicación biyectiva de en bastante sencilla. La idea consiste en conseguir primero una aplicación biyectiva de en , así: Si el elemento de , es cero, su elemento imagen en , es también cero. Si es un entero diferente de cero, se descompone en sus factores primos: Después, para cada factor , y partiendo del racional , se hace lo siguiente: – Si es par, añadimos el factor al numerador de r. – Si es impar, añadimos el factor al denominador de r. Y finalmente, asignamos a r el mismo signo… Lee más »
@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.
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… Lee más »
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… Lee más »
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… Lee más »
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».
Francesc, tienes razón con el tema del valor absoluto, no me había dado cuenta. Voy a aclararlo.
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… Lee más »
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
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.
Encontré esto: http://funes.uniandes.edu.co/3428/1/Kindt2005FraccionesNumeros60.pdf