Es sencillo ver que, para mostrar que {\mathbb Q} es numerable, es suficiente mostrar la numerabilidad de {\mathbb Q^+} o incluso de {\mathbb Q\cap(0,1]}.

   Hay una manera sencilla de enumerar este último: primero las fracciones con denominados {1}, luego aquellos con denominador {2} (obviando los que ya fueron listados), luego aquellos con denominador {3} (nuevamente, evitando repeticiones), etc. Esta lista empieza con

\displaystyle \frac11;\frac12;\frac13,\frac23;\frac14,\frac34;\frac15,\frac25,\frac35,\frac45;\dots

   La primera prueba de Cantor de la no numerabilidad de los reales (el argumento de los intervalos anidados) de 1874 procede como sigue:

   Dado cualquier sucesión (inyectiva) {a_1,a_2,\dots} de números reales, deseamos mostrar un número real que no es listado. Tenemos dos casos: hay {i\ne j} con {a_i<a_j}, y tal que no hay {k} con {a_k\in(a_i,a_j)}, en cual caso obviamente se ha culminado; o (más interesante), siempre que {a_i<a_j}, podemos hallar un {a_k} estrictamente entre ellos (el rango de la sucesión es dense sobre sí mismo). Asumamos que estamos en esta situación.

   Definimos dos sucesiones {b_1,b_2,\dots} y {c_1,c_2,\dots} como sigue:

  1. Primero, {b_1=a_1} y {c_1=a_2}.
  2. Por definición, suponer que {a_1>a_2}. El otro caso es tratado similarmente. Sea {b_2=a_i}, donde {i} es el menor tal que {a_i\in(c_1,b_1)}. Entonces definimos {c_2} como {a_j}, donde {j} es el menor tal que {a_j\in(c_1,b_2)}.
  3. En general, dado {c_n<b_n}, definimos {b_{n+1}} como {a_k}, donde {k} es el menor tal que {a_k\in(c_n,b_n)}, y luego definimos {c_{n+1}} como {a_m}, donde {m} es el menor tal que {a_m\in(c_n,b_{n+1})}. Notar que estas sucesiones están bien definidas debido a nuestra hipótesis de densidad.

   La construcción que se acaba de describir asegura que si {I_n=[c_n,b_n]}, entonces:

  1. Para cualquier {n}, tenemos que {a_n\notin I_{n+1}}, y
  2. Los intervalos están anidados y son decrecientes: {I_1\supsetneq I_2\supsetneq I_3\dots}

   Se sigue (de la completitud de los reales) que {\bigcap_n I_n\ne\emptyset}, y (de a.) que cualquier número real en esta intersección no está en el rango de la sucesión {a_1,a_2,\dots}

   Resulta que si llevamos a cabo la construcción de Cantor cuando la sucesión de {a_i} es la enumeración de los números racionales en {(0,1]} con los que comenzamos, entonces {\bigcap_n I_n=\{1/\phi\}}, donde {\phi} es la proporción áurea.

   Hay una agradable enumeración de {\mathbb Q^+} con un significado de combinatoria.

   Los racionales son usados para etiquetar los nodos de un árbol binario completo infinito, y la enumeración resultante simplemente sigue los nodos del árbol lexicográficamente.

\displaystyle \begin{array}{ccccccccccccccc} & & & & & & & \frac11 \\\\ & & & \frac12 & & & & & & & & \frac21 \\\\ & \frac13 & & & & \frac32 & & & & \frac23 & & & & \frac31 \\\\ \frac14 & & \frac43 & & \frac35 & & \frac52 & & \frac25 & & \frac53 & & \frac34 & & \frac41 \end{array}

Empezamos poniendo {1/1} en la raíz del árbol. Una vez que un nodo ha sido etiquetado con {m/n}, su sucesor izquierdo es etiquetado {m/(m+n)}, y su sucesor derecho es {(m+n)/n}.

¡Y eso es todo! La lista así producida empieza

\displaystyle \frac11;\frac12,\frac21;\frac13,\frac32,\frac23,\frac31;\dots

   La prueba de que esta es en efecto una lista biyectiva de {\mathbb Q^+} es muy simple; se verifica en el siguiente orden de afirmaciones:

  1. El numerado y el denominador de cualquiera de las fracciones asignadas son primos relativos.
  2. Todo racional positivo es asignado a algún nodo.

   Para esto, procedemos por inducción. Por ejemplo, si hay una fracción {m/n} no en su forma reducida, y usado como una etiqueta, escoger esa fracción que aparece en el menor nivel posible, y notar que la fracción no puede ser {1/1}. Una contradicción es ahora alcanza señalando que {\mathrm{gcd}(m,n)=\mathrm{gcd}(m-n,n)=\mathrm{gcd}(m,n-m)}.

   Similarmente, si {m/n} aparece en más de un nodo, entonces {m\ne n}, y su predecesor inmediato (bien {(m-n)/n} o {m/(n-m)}, dependiendo de si {m>n} o {m<n}) debe también aparecer en más de una vez.

   Finalmente, si alguna fracción no está listada, podemos elegir su denominador {n} menos entre los denominadores de todos las fracciones omitidas, y entonces elegimos su numerador {m} menos entre los numeradores de todas las fracciones omitidas con denominador {n}. Una contradicción sigue debido a que {m\ne n}, y si {m>n}, entonces {(m-n)/n} también debe haber sido omitido, pero {m-n<m}, mientras que si {m<n}, entonces {m/(n-m)} deben haber sido omitida, pero {n-m<n}

   También se muestran las siguientes las siguientes propiedades combinatorias interesantes:

  1. Hay una sucesión {b(0),b(1),b(2),\dots} de enteros positivos tal que la {n}-ésima fracción en la enumeración es sólo {\displaystyle\frac{b(n)}{b(n+1)}} (en su forma reducida). En particular, el denominador de una fracción es el numerador de su sucesor en la enumeración. De manera que {b(0)=1}, {b(1)=1}, {b(2)=2}, {b(3)=1}, {b(4)=3}, {b(5)=2}, {b(6)=3}, etc.
  2. De hecho, {b(n)} es precisamente el número de maneras de escribir {n} como una suma de potencias de {2}, donde cada potencia puede ser usada a lo sumo dos veces. Por ejemplo, {b(6)=3}, debido a que podemos escribir {6} como {2^2+2^1}, como {2^2+2^0+2^0}, o como {2^1+2^1+2^0+2^0}.

   Algunas preguntas naturales:

  1. ¿Qué podemos decir acerca del real (o los reales) que salen cuando el procedimiento de la prueba de Cantor es aplicado para esta enumeración?
  2. ¿Cualquier camino infinito a través del árbol binario define una sucesión de racionales? ¿Qué números reales aparecen como puntos límites de estas sucesiones?