Recuerdo que mi profesor en la universidad me reto con esta pregunta que no podía responder de manera satisfactoria: sé que existe un bijection entre los números racionales y los números naturales, pero ¿alguien puede producir una fórmula explícita para un bijection?
Respuestas
¿Demasiados anuncios?
HappyEngineer
Puntos
111
Voy a asumir que $\mathbb N$ incluye $0$.
Definir el un bijection $s:\mathbb N\to \mathbb Z$ como:
$$s(n)=\begin{casos} 0 y n=0\\ (-1)^n\left\lfloor\frac{n+1}{2}\right\rfloor&n>0 \end{casos} $$
Así, la secuencia sería de $0,-1,1,-2,2\dots$.
Entonces para cualquier $n$, definir $\rho(n)=p_1^{s(a_1)}p_2^{s(a_2)}\cdots p_k^{s(a_k)}$, donde:
$$n+1=p_1^{a_1}\cdots p_k^{a_k}$$
Donde $a_i$ son posiblemente cero.
Este es un bijection de los números naturales con $\mathbb Q^+$.
Definir entonces $$\rho_1(n)=\begin{casos} 0 y n=0\\ (-1)^n\rho\left(\left\lfloor\frac{n-1}{2}\right\rfloor\right) + n>0 \end{casos} $$
para un bijection entre $\mathbb N$ y $\mathbb Q$.
Por ejemplo, si $n=19$, entonces $n+1=2^2\cdot 3^0\cdot 5^{1}$ y $\rho(19)=2^{-1}\cdot 3^0\cdot 5^{1} = \frac{5}{2}$.
(Definición positiva de $n$ la función $f(n)=\rho(n-1)$, en realidad, tenemos que $f$ es multiplicativo - $f(mn)=f(m)f(n)$ de $m,$ n relativamente primos. Así, obtenemos que $f(p^{2k})=p^k$ y $f(p^{2k-1})=p^{-k}$.)
Básicamente, cada entero positivo tiene una representación única como:
$$p_1^{a_1}p_2^{a_2}\dots$$
donde $p_i$ son todos los números primos, el $a_i$ son enteros no negativos, y todos, excepto un número finito de la $a_i$ son cero.
Los números racionales tienen la misma representación, con el único cambio de que los $a_i$ son números enteros, posiblemente no negativo.
dogtato
Puntos
191
Vamos a crear primero un bijection de $\mathbb{N}$ $\mathbb{Q}^{+}$ y, a continuación, utilice esta opción para crear un bijection de $\mathbb{N}$ $\mathbb{Q}$.
Paso Uno: primero Vamos a definir Stern diatómicas de la serie. Este proceso se formaliza la de Stern-Brocot árbol se mencionó anteriormente.
$a_{1} = 1 \\ a_{2k}=a_{k} \\ a_{2k+1}=a_{k}+a_{k+1}$
Para tener una idea de esta serie, nos vamos a la lista de los primeros términos.
$a_{1}=1 \\ a_{2}=a_{1}=1 \\ a_{3}=a_{1}+a_{2}=1+1=2 \\ a_{4}=a_{2}=1 \\ a_{5}=a_{2}+a_{3}=1+2=3 \\ a_{6}=a_{3}=2 \\ a_{7}=a_{3}+a_{4}=2+1=3 \\ a_{8}=a_{4}=1$
Ahora para obtener el $n^{th}$ número racional, definimos $f: \mathbb{N} \rightarrow \mathbb{Q}^ {+}$, $f(n)= \dfrac{a_{n}}{a_{n+1}}$.
Nos deja la lista de los primeros términos.
$f(1)= a_{1}/a_{1+1} = 1/1 \\ f(2)= a_{2}/a_{2+1} = 1/2 \\ f(3)= a_{3}/a_{3+1} = 2/1 \\ f(4)= a_{4}/a_{4+1} = 1/3 \\ f(5)= a_{5}/a_{5+1} = 3/2 \\ f(6)= a_{6}/a_{6+1} = 2/3 \\ f(7)= a_{7}/a_{7+1} = 3/1 $
Esta función nos permite decir que los $6^{th}$ número racional es de $2/3$. Por otra parte, esta función es un bijection. Para prueba de esto, véase el Teorema 5.1 aquí http://faculty.plattsburgh.edu/sam.northshield/08-0412.pdf.
Dado que $f$ es un bijection esto implica que $f^{-1}$ existe. Esto significa que dado un número racional podemos encontrar el correspondiente número natural. Por ejemplo, suponga que tiene una fracción, dicen que es de $1/4$. Podemos determinar el $n$ tal que $f(n)=1/4$? La respuesta es un rotundo sí. Dado un número racional positivo, $p \in \mathbb{Q}$, $n$ tal que $f(n)=q$ se encuentra en $n=f^{-1}(q)$. Esta función $f^{-1}$, está dada de la siguiente manera:
$f^{-1}(1)=1 \\ f^{-1}(q)= 2f^{-1} \bigg(\dfrac{p}{1-p} \bigg) ~ \text{si} ~ q<1 \\ f^{-1}(q) = 2f^{-1}(q-1)+1 ~\text{si}~ q>1$
Como ejemplo, podemos ver desde arriba que $f(5)={3/2}$. Deje que nos conecte $(3/2)$ en $f^{-1}$ y a ver si conseguimos 5.
$f^{-1}(3/2)=2f^{-1} \bigg(\dfrac{3/2}{1-(3/2)} \bigg)+1=2f^{-1} \bigg(\dfrac{1}{2} \bigg)+1.$ Un cálculo rápido de los rendimientos que $f^{-1} \bigg(\dfrac{1}{2} \bigg)=2$ y así obtenemos $f^{-1}(3/2)=2f^{-1} \bigg(\dfrac{1}{2} \bigg)+1=2(2)+1=5$.
Paso Dos: Se demostró que no existe un bijection entre $\mathbb{N}$ y $\mathbb{Q}^{+}$. Ahora tratamos de mostrar que existe una explícita bijection entre $\mathbb{N}$ y $\mathbb{Q}$. Mediante el trabajo realizado en el Paso Uno, parece más fácil que crear primero un bijection entre $\mathbb{Z}$ y $\mathbb{Q}$. La razón de hacerlo así es porque ya hemos creado un bijection de los enteros positivos (números naturales) a los racionales positivos. Tan sólo parece natural que mediante la adición de los números enteros negativos, podemos asignarlos a la negativa racionales y de esta manera obtener un bijection. Podemos hacerlo de la siguiente manera:
$$ g(z) = \begin{casos} \dfrac{a_{z}}{a_{z+1}}, & \text{si } z>0 \\ \\ - \dfrac{a_ {z}}{a_{-(z-1)}}, & \text{si } z<0 \\ \\ 0, & \text{si } z=0 \end{casos} $$ donde $a_{i}$ término se refiere a la $i^{th}$ plazo en Popa diatómicas de la serie.
Nosotros ya hace referencia a una prueba por Northshield muestra que $g(z)=\dfrac{a_{z}}{a_{z+1}}$ si $z>0$ es un bijection de $\mathbb{N} \rightarrow \mathbb{Q}^{+}$. Equivalentemente, podemos escribir esto como $g$ es un bijection de $\mathbb{Z}^ {+}$ $\mathbb{Q}^{+}$ para $z>0$. Ahora, se sigue por la simetría del problema que $g(z)=- \dfrac{a_ {z}}{a_{-(z-1)}}$ es un bijection de $\mathbb{Z}^ { -}$ $\mathbb{Q}^{-}$ si $z<0$. Es decir, $g$ es un bijection entre los enteros negativos y el negativo racionales. Así que hemos cubierto todos los aspectos positivos y negativos racionales. El único elemento en los racionales que no se explica es el elemento cero. Así que vamos a tener el entero $0$ asignación del número racional $0$. Sin embargo, $g$ es un bijection de los enteros a los racionales. Queremos encontrar un bijection de los números naturales a los racionales. Así que ahora debemos definir el conocido bijection de los números naturales a los números enteros.
$$ h(n) = \begin{casos} \dfrac{n}{2}, & \text{si }n\text{ es aún} \\ -\dfrac{n-1}{2}, & \text{si }n\text{ es impar} \end{casos} $$
Usted puede comprobar por sí mismo que $h$ es un bijection. De ello se sigue que $g~\circ~ h: \mathbb{N} \rightarrow \mathbb{Q}$ es un bijection ya que la composición de dos bijections es un bijection. Así, tenemos un explícito bijection de $\mathbb{N}$ $\mathbb{Q}$.
Sin embargo, dado un número racional, podemos encontrar lo que este número racional mapas en el conjunto de los números naturales? Aunque yo no la prueban, la respuesta es sí y es dado por la siguiente pieza de sabios función definida por el cual es una extensión de la función definida en el Paso Uno. Primero se definen $g^{-1}: \mathbb{Q} \rightarrow \mathbb{Z}$ como
$$ g^{-1}(q) = \begin{casos} 2f^{-1}(q-1)+1, & \text{si } p>1 \\ 1, & \text{si } q=1 \\ 2f^{-1} \bigg(\dfrac{p}{1-p} \bigg), & \text{si } 0<q<1 \\ 0, & \text{si } q=0 \\ -2 \Bigg(f^{-1} \bigg(\dfrac{-q}{1+q}\bigg) \Bigg), & \text{si } -1<q<0 \\ -1, & \text{si } q=-1 \\ -2(f^{-1}(-q-1)+1), & \text{si } p<-1 \end{casos} $$
Ahora podemos definir la función $h^{-1}: \mathbb{Z} \rightarrow \mathbb{N}$ como sigue:
$$ h^{-1}(z)= \begin{casos} 2z, & \text{si } z>0 \\ 1, & \text{si } z=0 \\ -2z+1, & \text{si } z<0 \\ \end{casos} $$
Entonces $h^{-1} \circ g^{-1}: \mathbb{Q} \rightarrow \mathbb{N}$ es la bijection que estamos buscando.
-Elliot Gangaram
Wikipedia contiene varios ejemplos explícitos: Cantor función de sincronización, de Stern–Brocot árbol, Calkin–Wilf árbol.
Gary Adams
Puntos
1
Phil
Puntos
1
Con el fin de crear esta función, uno debe mirar esto en varias partes y luego ensamblar las piezas juntas para producir el final de la función.
Primero usted necesitará la siguiente serie:
0,1,1,2,1,2,3,1,2,3,4,...
0,1,2,1,3,2,1,4,3,2,1,...
Una serie es el numerador y el otro el denominador. Una función explícita para generar cada una de las series será necesaria (tratar de wikipedia o de otras de matemáticas en línea de recursos para encontrar estos)
A continuación, una manera de pasar por esto una segunda vez para que todos los valores son negativos serán necesarios.
La manera más fácil de pensar en el montaje de todas estas piezas es más probable que los compuestos de funciones.
Utilizar el viejo (-1)^n truco para cambiar a los valores negativos.
Un profesor me mostró esta función una vez, he estado tratando de buscar en las notas antiguas, pero fue en vano. Si recuerdo correctamente, utiliza compuestos de funciones y de suelos/techos.
Lo siento si esto no era útil para usted en su búsqueda.
