¿Es el conjunto de todos los pares de números naturales contable?

Question

Decir que $\Bbb N \times \Bbb N$ es el conjunto de todos los pares $(n_1, n_2)$ de números naturales. ¿Es contable? Mi hipótesis es que sí es contable porque los sistemas son contables. Pero soy incapaz de llegar a una prueba. ¿Es correcta mi hipótesis? ¿Cómo es contable?

Answer 1

Considere la función $f: \mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N}$ definidas en $f(a,b)=2^a \, 3^b$. Entonces esta función es 1. Cardinalidad de $\mathbb{N} \times \mathbb{N}$ no es, en consecuencia, "más" (si puedo usar esta frase) que $\mathbb{N}$, por lo tanto, contable.

Answer 2

En primer lugar, una lista de los pares en el que la suma es $0$:

$$(0,0)$$

Entonces aquellos en que la suma es $1$:

$$(1,0),(0,1)$$

Entonces aquellos en que la suma es $2$:

$$(2,0),(1,1),(0,2)$$

Entonces aquellos en que la suma es $3$:

$$(3,0),(2,1),(1,2),(0,3)$$

Y así sucesivamente.

Answer 3

Sí, haces la diagonalización como con números racionales, que es básicamente lo mismo.

Answer 4

Otra manera fácil: tomar un par, escribir los números en cualquier base de numeración. Por ejemplo 1234 (decimal) y 987. Agregar ceros adicionales donde sea necesario para que tienen la misma longitud y mezclarlos

1 2 3 4
 0 9 8 7
--------
10293847

Invertir la operación: tomar cifras incluso posiciones de (resp. impar).

EDITO: y por supuesto hay fórmulas explícitos, aquí dadas como 3 funciones de Python recursivas

def combine(a,b):
   return 0 if a==0 and b==0 else 10*combine(b/10, a) + (b % 10)
def second(n):
   return 0 if n==0 else 10*second(n/100)+ (n%10)
def first(n):
   return second(n/10)

Answer 5

Sí, aquí es un ejemplo de biyección, donde $p_k$ es el $kth$ primer número:

• $f(x,y)=p_x^{p_y}$

• $g(x)=(x,x)$