$A_1 \times ... \times A_n$ es contable si $A_1, ..., A_n$ son contables

Question

Supongamos que $A_1, ..., A_n$ son conjuntos contables. Demuestre que el producto cartesiano $A := A_1 \times ... \times A_n$ es contable.

Mi intento:

Se dice que los conjuntos son contables si son finitos o si tienen la misma cardinalidad que algún subconjunto de $\mathbb{N}$ (es decir, podemos encontrar alguna biyección $f: A \rightarrow S$ o $f: S \rightarrow A$ donde $S \subset \mathbb{N}$ ).

Supongamos que $A_1, ..., A_n$ son conjuntos contables. Entonces, existen biyecciones $fi: \mathbb{N} \rightarrow A_i$ para $i = 1, ..., n$ .

Definir $g: \mathbb{N} \rightarrow A$ como sigue

Mi problema es encontrar esa función biyectiva sin que sea demasiado complicada. ¿Cómo puedo encontrarla? También estoy abierto a cualquier sugerencia. Cualquier ayuda es bienvenida.

Answer 1

Basta con demostrarlo en el caso de que $A_i=\mathbb{N}$ para todos $i$ . Así que tenemos que demostrar que $\mathbb{N^n}$ es un conjunto contable. Sea $p_1,p_2,...,p_n$ ser el primero $n$ números primos, y definir un mapa $f:\mathbb{N^n}\to\mathbb{N}$ por:

$f(m_1,m_2,...,m_n)=p_1^{m_1}p_2^{m_2}...p_n^{m_n}$

Es bien sabido que la descomposición en primos es única, por lo que $f$ es inyectiva. Así que demostramos que hay una inyección de $\mathbb{N^n}$ a $\mathbb{N}$ y así $\mathbb{N^n}$ es contable. (está en biyección con la imagen de $f$ que es un subconjunto de $\mathbb{N}$ )

Answer 2

Hazlo por inducción.

Demostrar que si $A,B$ son contables entonces $A\times B$ son contables (utilice el argumento de la "línea diagonal").

$1\mapsto (a_1,b_1); 2 \mapsto (a_2,b_1); 3\mapsto (a_1, b_2); 4\mapsto (a_3, b_1); 5\mapsto (a_2,b_2); 6\mapsto (a_1,b_3);7\mapsto (a_4, b_1).... etc. $

Entonces, si asumimos $A_1 \times A_2..... \times A_k$ es contable entonces $A_1\times A_2\times..... \times A_k \times A_{k+1} = (A_1\times A_2\times..... \times A_k) \times A_{k+1}$ es el producto de DOS conjuntos contables y, por tanto, es contable.

Así que por indcucción $A_1 \times A_2..... \times A_n$ es contable para todo $n$ .

Answer 3

Basta con demostrar que el producto cartesiano de dos conjuntos contables es contable, porque un argumento inductivo dará el resultado general.

Según su definición de conjuntos contables, si al menos un conjunto es finito, el resultado es inmediato. Así que el único caso interesante es cuando ambos conjuntos son contablemente infinitos.

En particular, basta con demostrar que $\mathbb{N}\times\mathbb{N}$ es contable. Definir una función $f:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ de la siguiente manera. Si $n\in\mathbb{N}$ entonces $n$ puede escribirse de forma única como $2^{m-1}\cdot(2k-1)$ , donde $m,k\in\mathbb{N}$ . Definir $f(n)=(m,k)$ . Por la unicidad de tales expresiones, vemos que $f$ es uno a uno. Por otro lado, si $(m,k)$ es cualquier par de $\mathbb{N}\times\mathbb{N}$ y luego establecer $n=2^{m-1}\cdot(2k-1)$ da un número entero para que $f(n)=(m,k)$ Así que $f$ es en. Así, $f$ es una biyección, y esto demuestra que $\mathbb{N}\times\mathbb{N}$ tiene la misma cardinalidad que $\mathbb{N}$ es decir, es contable.

Answer 4

Se podría utilizar un enfoque similar a la prueba de Cantor de que los números algebraicos son contables. Ordena los $A_k=(a_k(j))$ Para un elemento de $A$ dejemos $B=(a_1(j_1),....a_n(j_n))$ . Definir $b=\sum_{k=1}^n j_k$ . Para cada $b$ sólo hay un número finito de $B's$ con $b$ como la suma. Estos pueden ser ordenados de cualquier manera. La totalidad para todos los valores (enteros) de $b$ es contable e incluye todos los miembros de $A$ .