La unión de una secuencia de conjuntos contables es contable.

Question

Mientras trabajaba en el teorema siguiente, construí la siguiente demostración:

Teorema. Si $\left\langle E_{n}\right\rangle_{n\in\mathbb{N}}$ es una secuencia de conjuntos contables, entonces

$$ \bigcup_{n\in\mathbb N}E_{n} $$

es contable.

Prueba. Sea $S=\left\langle E_{n}\right\rangle_{n\in\mathbb{N}}$ sea una secuencia de conjuntos contables. Además, sea $x_{n,m}$ sea el $m$ ésimo elemento del $n$ ª serie en $S$ . Construir una secuencia de secuencias

$$ \mathcal S=\left\langle\left\langle x_{n-m+1,m}\right\rangle_{m\in\mathcal N_n}\right\rangle_{n\in\mathbb N}, $$

donde $\mathcal N_{n}=\left\{k\in\mathbb N:k\leqslant n\right\}$ . Entonces $\mathcal S$ contiene todos los elementos de

$$ T=\bigcup_{n\in\mathbb N}E_{n}. $$

Observe que $\mathcal S$ es un suryecto $\mathbb N\to T$ porque para cada $n\in\mathbb N$ , $\mathcal S$ da lugar a una subsecuencia finita y, por tanto, contable. Además, como $\mathcal S$ puede contener elementos duplicados, un $U\subseteq\mathbb N$ de forma que $\mathcal S$ es una inyección $U\to T$ . Hemos encontrado entonces una biyección $\mathcal S:U\to T$ . Por lo tanto, $T$ es contable. $\blacksquare$

¿Le parece convincente?

Edita: Acabo de darme cuenta de que no puedo localizar duplicados debido a cómo $\mathcal S$ se construye, ¿puedo? :-(

Answer 1

Estás intentando hacer una lista $T$ como $$\langle x_{1,1},x_{2,1},x_{1,2},x_{3,1},x_{2,2},x_{1,3},\ldots\rangle\;,\tag{1}$$ pero en su lugar has construido la secuencia

$$\Big\langle\langle x_{1,1}\rangle,\langle x_{2,1},x_{1,2}\rangle,\langle x_{3,1},x_{2,2},x_{1,3}\rangle,\ldots\Big\rangle\;,$$

un animal relacionado pero definitivamente diferente. En realidad es más fácil decir qué $n\in\Bbb N$ corresponde a $x_{k,\ell}$ en la lista $(1)$ que ir hacia delante. Cuente los elementos de $(1)$ que preceden $x_{k,\ell}$ . Ciertamente incluyen todos $x_{i,j}$ tal que $i+j<k+\ell$ y hay

$$\sum_{n=2}^{k+\ell-1}n=\frac{(k+\ell-1)(k+\ell)}2-1$$

de esos. (La suma comienza en $2$ porque siempre tenemos $i+j\ge 2$ .)

Sea $m=k+\ell$ También incluye todos los $x_{m-i,i}$ tal que $1\le i\le\ell$ y hay $\ell-1$ de esos. Así,

$$\frac{(k+\ell-1)(k+\ell)}2-1+\ell-1=\frac{(k+\ell-1)(k+\ell)}2+\ell-2$$

términos de $(1)$ precede a $x_{k,\ell}$ y $x_{k,\ell}$ es, por tanto, el término número

$$\frac{(k+\ell-1)(k+\ell)}2+\ell-1$$

de la secuencia $(1)$ .

Answer 2

Quizá se pueda ser más concreto. Supongamos que la indexación de su $x_{n,m}$ comienza en $1$ . Sea $p_n$ sea el $n$ - primo. Mapa $p_n^m$ à $x_{n,m}$ y los números que no sean de la forma $p_n^m$ a cualquier objeto fijo. Esto da una proyección desde los números naturales a nuestra unión.

Answer 3

Proposición 1: Un conjunto $X$ es contable si y sólo si existe una suryección $\tau: \mathbb N \to X$ .
Pruebas: Véase enlace .

Para cada conjunto contable en $\left\langle E_{n}\right\rangle_{n\in\mathbb{N}}$ seleccione un suryecto $\tau_n: \mathbb N \to E_{n}$ y que $X$ sea la unión de los $E_n$ .

Proposición 2: Existe una suryección $\gamma: \mathbb N \times \mathbb N \to X$ .
Prueba
Defina $\gamma$ por $(n,m) \mapsto \tau_n(m)$ .

El argumento diagonal de Cantor nos da

Proposición 3: Existe una biyección desde $\mathbb N$ à $\mathbb N \times \mathbb N$ .

Dado que la composición de dos mapas suryectivos es también suryectiva, hemos demostrado que la unión de los mapas $E_n$ es un conjunto contable.