¿Por qué es $\mathbb Q $ (números racionales) contable?

Question

Por definición, un conjunto $S$ se llama contable si existe una función biyectiva $f$ de $S$ a los números naturales $N$.

Si tomamos una función $g\colon\mathbb{Z\times N\to Q}$ dada por $g(m, n) = \frac{m}{ n} $ para "construir" números racionales, $g$ sería solamente una sobreyección del conjunto contable $\mathbb{Z\times N}$ a $\mathbb Q. No es inyectiva, ¿o sí?

Answer 1

Las biyecciones explícitas están sobrevaloradas.

Podemos probar lo siguiente tres cosas (sin el axioma de elección, que ha sido mencionado en los comentarios):

1. Si $A\subseteq\Bbb N$ entonces es finito o contablemente infinito.
2. Si $f\colon\Bbb N\to X$ es sobreyectiva, entonces $X$ es finito o contablemente infinito.
3. Existe una sobreyección de $\Bbb N$ en $\Bbb Q$.

La primera demostración es bastante fácil, simplemente empezamos a enumerar $A$ de acuerdo con el orden inducido por el orden habitual de los números naturales. O bien "terminamos" el conjunto, en cuyo caso es finito, o la enumeración produce una biyección de $A$ con $\Bbb N.

La segunda demostración también es fácil, ya que la función es una sobreyección, cada $x\in X$ tiene un mínimo $n\in\Bbb N$ tal que $f(n)=x$. Este $n$ mínimo es único, por lo que hemos definido una inyección de $X$ en $\Bbb N$, que es una biyección con un subconjunto de $Bbb N$. Por la primera afirmación, $X$ es finito o contablemente infinito.

La última demostración tampoco es difícil. Primero escribe una sobreyección de $\Bbb N$ en $\Bbb{N\times N}$ y una sobreyección de $\Bbb N$ en $\Bbb Z\setminus\{0\}$, compónlos en una sobreyección de $\Bbb N$ en $\Bbb{N\times (Z\setminus\{0\})}$. Luego usas la sobreyección que has definido, $(n,m)\mapsto\frac nm$.

Ahora podemos concluir la cuarta afirmación:

4. $\Bbb Q$ es contablemente infinito.

Por supuesto, $\Bbb Q$ no es finito, y dado que hay una sobreyección de $\Bbb N$ en $\Bbb Q$, la afirmación está demostrada.

Answer 2

Aquí hay una imagen intuitiva pero muy útil para entender.

Answer 3

Estás correcto. De hecho, esta no es la función utilizada para contar números racionales.

Imagina listar todos esos números excluyendo aquellos en los que la fracción se puede simplificar.

Una posible biyección podría ser esa función que da la posición del número racional en esa lista. Dado que la lista contiene cada número racional, la función es sobreyectiva. Pero cada número tiene una posición diferente en la lista: por lo tanto, la función es sobreyectiva.

Este es un punto de vista "intuitivo". Si deseas una demostración más formal, aquí está:

Define el mapeo $\psi: \mathbb Q \rightarrow \mathbb Z \times \mathbb N$ tal que para cada $\frac{m}{n} \in \mathbb Q$ en forma canónica $\psi(\frac{m}{n})=(m,n)$

Luego, $\psi$ es claramente inyectiva. A partir del hecho de que el producto cartesiano de conjuntos infinitos contables es infinito contable, $\mathbb Z \times \mathbb N$ es contable. Debido a que el dominio de la inyección a un conjunto contable es contable, $\mathbb Q$ es contable.

Answer 4

Considera el plano $\mathbb Z\times\mathbb Z$. Claramente puedes llenarlo espiralándolo desde el origen. Evita contar las fracciones indefinidas y las que ya hayas visto antes (después de simplificar).

Answer 5

La secuencia de Farey establece una biyección entre los racionales no negativos y $\mathbb{N}$.
Paso 0: Comienza con dos números $\frac01,\frac10$ ($\frac10$ es solo un marcador de posición.) $\frac01$ es el número racional $1$.
Paso N: entre los números consecutivos $\frac{a}{b},\frac{c}{d}$, escribe $\frac{a+c}{b+d}$ Estos son números racionales del número $2^{N-1}+1$ al número $2^N$
La secuencia comienza
$$\frac01,\frac10\\ \frac01,\frac11,\frac10\\ \frac01,\frac12,\frac11,\frac21,\frac10\\ \frac01,\frac13,\frac12,\frac23,\frac11,\frac32,\frac21,\frac31,\frac10$$
Para incluir los negativos, coloca los números negativos en las posiciones pares y los números positivos en las posiciones impares.