Cómo obtener todos los números racionales sin repeticiones?

Question

Hace unos días he visto Cantor diagonal del argumento, y presentó una tabla similar a la siguiente:

$$\begin{matrix} {\frac{1}{1}}&{\frac{1}{2}}&{\frac{1}{3}}&{\frac{1}{4}}&{\cdots}\\ {\frac{2}{1}}&{\frac{2}{2}}&{\frac{2}{3}}&{\frac{2}{4}}&{\cdots}\\ {\frac{3}{1}}&{\frac{3}{2}}&{\frac{3}{3}}&{\frac{3}{4}}&{\cdots}\\ {\vdots}&{\vdots}&{\vdots}&{\vdots}&{\ddots} \end{de la matriz}$$

Si seguimos algunas de las diagonales, que vamos a cumplir con números repetidos como $1/1,\; 2/2,\; \cdots$ ¿cuáles son las condiciones para encontrar que no sólo repite los números? Tuve la sensación de que el establecido para dicha tarea es la siguiente:

$$\{0,1\}\cup \{a/b: \, a,b\in\mathbb{Z}, \;b\neq 0, \; b \in primes, \; a\neq b \}\tag{1.0}$$

La primera idea que yo tenía era sólo para los positivos racionales:

$$\{0,1\}\cup \{a/b: \, a,b\in\mathbb{N}, \;b\neq 0, \; b \in primes, \; a\neq b \}\tag{1.1}$$

Pero realmente no estoy seguro de lo que estoy haciendo yo tampoco tengo las herramientas mentales para demostrar que, simplemente, tenía un sentimiento. Yo estaba bastante seguro de que (con algunas mágico misterio en mi cabeza) que $(1.1)$ estaba en lo correcto, pero me extendió también a la negativa racionales en $(1.0)$ y estoy un poco menos seguro de que iba a funcionar para este caso específico.

Me acaba de caer algunas etiquetas que creo que están relacionados de alguna manera, pero no estoy seguro de lo que las etiquetas sean adecuados, si usted lo sabe, por favor, edite.

Answer 1

Idealmente, esto debe ser un comentario pero no puedo comentar aún.

El Wilf-Calkin árbol también enumera los racionales positivos.

Wikipedia: Calkin-Wilf árbol

Answer 2

Recuerde que cada número racional admitir una única forma reducida con denominador positivo. Así que todo lo que necesitas hacer es enumerar todos ellos. $\frac{a}{b}$ está en forma reducida con denominador positivo si $\gcd(a,b)=1$$b>0$.

Así que hay un montón de manera de ir sobre esto realmente. De una manera, que es llenar la tabla con cada fila corresponde a un $b\in\mathbb{Z}^{+}$ $b$ aumentando. El 0 fila contiene sólo $0$. Después de que para cada fila, de izquierda a derecha se tiene un bloque para cada valor de $a$ donde$\gcd(a,b)=1$$0<a\leq b$; cada bloque contendrá $\frac{a}{b},-\frac{a}{b},\frac{b}{a},-\frac{b}{a}$. Cada fila es finito, y usted puede enumerar ellos fila por fila, en lugar de en diagonal.

Sólo a elaborar, la fila 6, tenemos $b=6$, por lo que la fila tener este aspecto:

$\frac{1}{6},-\frac{1}{6},\frac{6}{1},-\frac{6}{1},\frac{5}{6},-\frac{5}{6},\frac{6}{5},-\frac{6}{5}$

Answer 3

Hay un método fácil: simplemente tome la reducción de fracciones.

Otro método sencillo es tener en cuenta la diagonal argumento ya te ha dado un orden en todas las fracciones positivas. Así que a tomar cada uno positivo racional exactamente una vez, todo lo que tienes que hacer es tomar sólo aquellas fracciones que no tienen un valor igual a la que aparece antes en la secuencia.

Hay más elegante esquemas demasiado: por ejemplo, Farey secuencias puede dar racionales de 0 a 1, y los relacionados con Stern-Brocot árbol para todos los racionales positivos.

Answer 4

Aparte de la bijections dado por el Cantor de Vinculación de la Función, la de Stern-Brocot árbol o la Calkin-Wilf árbol mencionado en otra parte, me gustaría presentar una agradable bijection entre los números naturales $\mathbb{N}$ y los racionales $\mathbb{Q}$ que hace uso del hecho de que tanto los números naturales y los racionales positivos tienen una única factorización prima.

Deje $\rho$ ser un bijection entre los números naturales y los enteros no negativos $\mathbb{N}_0:=\mathbb{N}\cup\{0\}$, por ejemplo, $$\rho:n\mapsto n-1.$$

Deje $\sigma$ ser un bijection entre el $\mathbb{N}_0$ $\mathbb{Z}$ que corrige $0$, por ejemplo, $$\sigma:n\mapsto\left\{\begin{matrix}{n/2}&{n\text{ even}}\\{-(n+1)/2}&{n\text{ odd}}\end{matrix}\right.$$

A continuación, vamos a $\mathbb{P}=\{p_1, p_2, p_3, \ldots\}$ el conjunto de los números primos.

Deje $n$ ser un entero positivo. Ya en $\mathbb{N}$, la factorización en factores primos es única, existen determinada únicamente exponentes $e_1, e_2, e_3, \ldots$ tal que $$n=\prod_{i=1}^\infty p_i^{e_i}.$$

(Tenga en cuenta que infinidad de $e_i$ son cero, de modo que el lado derecho es un bien definida la expresión.)

Ahora, definir $$\tau^*(n):=\prod_{i=1}^\infty p_i^{\sigma(e_i)}.$$

Entonces, es fácil ver que

• $\tau^*(n)$ está bien definida (es decir, el producto en la mano derecha converge),
• $\tau^*(n)$ es un racional positivo,
• la construcción de los rendimientos de los diferentes valores $\tau^*(m)$, $\tau^*(n)$ para los diferentes argumentos $m$, $n$.

Por lo tanto, $\tau^*$ de los rendimientos de un bijection entre el $\mathbb{N}$ positivos y racionales $\mathbb{Q}^+$ que puede ser extendido a un bijection $\tau$ $\mathbb{Z}$ y todos los de $\mathbb{Q}$: $$\tau:z\mapsto\left\{\begin{matrix}{\tau^*(z)}&{z>0}\\{0}&{z=0}\\{-\tau^*(-z)}&{z<0}\end{matrix}\right.$$

Finalmente, la composición de $\rho$, $\sigma$ y $\tau$ da un bijection $\tau\circ\sigma\circ\rho:\mathbb{N}\to\mathbb{Q}$.