Demuestra que la unión de muchos conjuntos contables es contable.

Question

Estoy haciendo algunos ejercicios de tarea y me tropecé con esta pregunta. No sé por dónde empezar.

Demuestra que la unión de muchos conjuntos contables es contable.

Sólo leerlo me confunde.

¡Cualquier sugerencia o ayuda es muy apreciada! ¡Salud!

Answer 1

Empecemos con un rápido repaso de "contable". Un conjunto es contable si podemos establecer una correspondencia 1-1 entre el conjunto y los números naturales. Como ejemplo, tomemos $\mathbb{Z}$ que consiste en todos los números enteros. Es $\mathbb Z$ ¿contable?

Puede parecer incontable si se elige una correspondencia ingenua, por ejemplo $1 \mapsto 1$ , $2 \mapsto 2 ...$ que deja todos los números negativos sin mapear. Pero si organizamos los enteros así:

$$0$$ $$1, -1$$ $$2, -2$$ $$3, -3$$ $$...$$

Rápidamente vemos que hay un mapa que funciona. Mapa 1 a 0, 2 a 1, 3 a -1, 4 a 2, 5 a -2, etc. Así que dado un elemento $x$ en $\mathbb Z$ tenemos que $1 \mapsto x$ si $x=0$ , $2x \mapsto x$ si $x > 0$ o $2|x|+1 \mapsto x$ si $x < 0$ . Así que los enteros son contables.

Lo demostramos encontrando un mapa entre los números enteros y los números naturales. Así que para demostrar que la unión de conjuntos contables es contable, necesitamos encontrar un mapa similar. En primer lugar, vamos a desempacar "la unión de conjuntos contables es contable":

1. "conjuntos contables" bastante simple. Si $S$ está en nuestro conjunto de conjuntos, hay una correspondencia 1-1 entre los elementos de $S$ y $\mathbb N$ .

2. "conjuntos contables" tenemos una correspondencia 1-1 entre $\mathbb N$ y los propios decorados. En otras palabras, podemos escribir los conjuntos como $S_1$ , $S_2$ , $S_3$ ... Llamemos al conjunto de conjuntos $\{S_n\}, n \in \mathbb N$ .

3. "La unión de un número contable de conjuntos es contable". Existe un mapeo 1-1 entre los elementos de $\mathbb N$ y los elementos en $S_1 \cup S_2 \cup S_3 ...$

¿Cómo lo demostramos? Tenemos que encontrar una correspondencia, por supuesto. Afortunadamente, hay una forma sencilla de hacerlo. Dejemos que $s_{nm}$ sea el $mth$ elemento de $S_n$ . Podemos hacerlo porque $S_n$ es por definición del problema contable. Podemos escribir los elementos de TODOS los conjuntos así:

$$s_{11}, s_{12}, s_{13} ...$$ $$s_{21}, s_{22}, s_{23} ...$$ $$s_{31}, s_{32}, s_{33} ...$$ $$...$$

Ahora dejemos que $1 \mapsto s_{11}$ , $2 \mapsto s_{12}$ , $3 \mapsto s_{21}$ , $4 \mapsto s_{13}$ etc. Puedes notar que si tachamos cada elemento que hemos mapeado, los estamos tachando en líneas diagonales. Con $1$ tachamos la primera diagonal, $2-3$ tachamos la segunda diagonal, $4-6$ la tercera diagonal, $7-10$ la cuarta diagonal, etc. El $nth$ diagonal requiere que mapeemos $n$ elementos para tacharlo. Dado que nunca "nos quedamos sin" elementos en $\mathbb N$ En definitiva, dada una diagonal cualquiera, crearemos un mapa para cada elemento de la misma. Como obviamente cada elemento en $S_1 \cup S_2 \cup S_3 ...$ está en una de las diagonales, hemos creado un mapa 1-1 entre $\mathbb N$ y el conjunto de conjuntos.

Vamos a dar un paso más. ¿Y si hacemos $s_{11} = 1/1$ , $s_{12} = 1/2$ , $s_{21} = 2/1$ ¿ etc.? Entonces $S_1 \cup S_2 \cup S_3 ... = \mathbb Q^+$ ¡! Así se demuestra que los racionales son contables. Bueno, los racionales positivos al menos. ¿Puedes extender estas pruebas para demostrar que los racionales son contables?

Answer 2

La respuesta de @Hovercouch es correcta, pero la presentación oculta un punto realmente importante que probablemente deberías conocer. Aquí está:

El argumento depende de que se acepte (una versión débil) el axioma de elección.

¿Por qué?

Sólo se le da que cada $S_i$ es contable . No se le da por adelantado una forma de contando cualquier $S_i$ por lo que hay que elegir una función suryectiva $f_i\colon \mathbb{N} \to S_i$ para hacer el recuento (en la notación de @Hovercouch, $f_m(n) = s_{mn}$ ). Y, sobre todo, hay que elegir un $f_i$ un número contable de veces (una opción para cada $i$ ).

Se trata de una secuencia infinita de elecciones: y es una versión del Axioma de Elección altamente no trivial que dice, sí, es legítimo pretender que podemos hacer eso.

Answer 3

Lema 1. La unión de dos conjuntos contables es contable.

Prueba. Dejemos que $A = \{a_n : n \in \mathbf N\}$ y $B = \{b_n : n \in \mathbf N\}$ . Entonces podemos definir la secuencia $(c_n)_{n=0}^\infty$ por $$c_{2k} = a_k \quad\text{and}\quad c_{2k+1} = b_k$$ por cada $k \in \mathbf N$ . Ahora $A \cup B = \{c_n : n \in \mathbf N\}$ y como es un conjunto infinito entonces es contable.

Por el Lemma 1 puedes demostrar tu proposición por inducción sobre el número de conjuntos de la familia

Corolario. La unión de una familia finita de conjuntos contables es un conjunto contable.

Para probar para una familia infinita se necesita el Axioma de elección.

Answer 4

Dejemos que $\{A_n\}$ sea una colección contable de conjuntos de colecciones. Denotemos, $A=\cup_{n\in I} A_n$ . Ahora, para cada $A_n$ definir una inyección $f_n:A_n\to \mathbb{N}$ . Ahora defina una función $f:A\to \mathbb{N}$ de la siguiente manera, tome $x\in A$ . Supongamos que $i$ sea la primera tal que $x\in A_i$ . Ahora defina $f(x)=2^i3^{f_i(x)}$ . Claramente esto es una inyección. Ahora bien, si $A$ es finito entonces hecho, si no entonces $im(f)$ es un subconjunto infinito de $\mathbb{N}$ . Y de nuevo es contable, por lo que es biyectiva a $\mathbb{N}$ . También, $A$ es biyectiva a $im(f)$ Así que.., $A$ es biyectiva a $\mathbb{N}$ Hecho.

Answer 5

Bien, la afirmación es que, si tienes una colección contable de conjuntos que son contables ellos mismos, entonces la unión de todos los elementos de la colección también es contable. Para demostrar esto, intente escribir el conjunto de los números naturales como la unión de infinitos subconjuntos disjuntos de $\mathbb{N}$ (y, para ello, considere la descomposición de cada número natural en su única factorización prima)