¿Por qué este conjunto ordenado es isomorfo a $\mathbb{Q}$?

Question

Sea $H_0$ el conjunto de los números que tienen expresión finita en base 2. Es decir $H_0=\{m/2^n:m,n\in\mathbb{Z}\}$. Demostrar que $H_0$ es isomorfo al conjunto de los racionales $\mathbb{Q}$ como conjunto ordenado, es decir, que existe una función $f:H_0\to\mathbb{Q}$ que es monótona y biyectiva.

Lo que he podido hacer es ver que puedo meter cada conjunto en el otro con una función monótona e inyectiva, pero no veo como hacerla sobre.

Answer 1

Tanto $\mathbb{Q}$ como $H_0$ son numerables, elige una numeración fija de cada uno: $\mathbb{Q} = \{q_0, q_1, \ldots\}$ y $H_0 = \{h_0, h_1, h_2, \ldots\}$, ahora definimos de a poquitos una biyección monótona $f : \mathbb{Q} \to H_0$ entre ellos:

1. Sea $q_j$ el elemento de $\mathbb{Q}$ con $j$ mínimo que todavía no esté en el dominio de $f$; extendemos la definición de $f$ declarando que $f(q_j) = h_k$ donde $h_k$ es cualquier elemento de $H_0$ tal que (a) no esté en la imagen de $f$ hasta el momento, (b) la $f$ así extendida sea monótona.
2. Sea $h_j$ el elemento de $H_0$ con $j$ mínimo que aún no está en la imagen de $f$; declaramos que $f(q_k)=h_j$ donde $q_k$ es cualquier elemento de $\mathbb{Q}$ que (a) todavía no está en el dominio de $f$, (b) la $f$ así extendida siga siendo monótona.
3. Regresa al paso 1.

Siempre podemos hallar los elementos $h_k$ requeridos en el paso 1 y los elementos $q_k$ requeridos en el paso 2 porque tanto $\mathbb{Q}$ como $H_0$ cumplen que no tienen elemento mínimo, ni elemento máximo y son densos: entre cualesquiera dos de sus elementos hay más elementos.

Como son numerables, es fácil ver que gracias al paso 1 todo $\mathbb{Q}$ acaba en el dominio de $f$ y gracias al paso 2, todo $H_0$ acaba en el codominio de $f$.

Este argumento prueba más en general que cualquier conjunto numerable totalmente ordenado, denso y sin máximo ni mínimo es isomorfo a los racionales con el orden usual. Creo que ese resultado lo probó por primera vez Cantor. El método que describí arriba se llama "back and forth method" en inglés, varios otros resultados se prueban así, por ejemplo el que las gráficas aleatorias numerables en el modelo de Erdos-Renyi con probabilidad $1$ son isomorfas a una gráfica fija (llamada la gráfica aleatoria numerable).

Answer 2

La función Signo de Interrogación de Minkowsky hace la gracia. La puedes definir usando la serie de Farey y la suma de quebrados que no permitían usar en la secundaria: los mediantes.

Define $?(0)=0$, $?(1)=1$ y define, en orden, para cada $F_n$ de la serie de Farey: dados  $\frac{p}{q}$ y $\frac{r}{s}$ en $F_n$ dos términos sucesivos de la siguiente manera:
$$?\left(\frac{p+r}{q+s}\right)= \frac{1}{2}\left[? \left(\frac{p}{q}\right)+?\left( \frac{r}{s}\right)\right].$$

Esta función se extiende a un homeomorfismo del intervalo tal que $?(\mathbb{Q}) = H_0$ y tal que $?^{-1}(\mathbb{Q})$ es precisamente el conjunto de los irracionales cuadráticos.

...por supuesto, todo contenido dentro del intervalo [0,1].