Todo subconjunto infinito de un conjunto contable es contable.

Question

Aquí está la prueba que intenté tejer al tratar de demostrar este teorema:

Teorema. Todo subconjunto infinito de un conjunto contable es contable.

Prueba. Dejemos que $A$ sea un conjunto contable y $E\subset A$ sea infinito. Entonces $A\thicksim\mathbb{N}$ . Esto implica que existe una secuencia $\left\{x_{n}\right\}_{n\in\mathbb{N}}$ donde $x_{n}\in A$ . Construir una secuencia $\left\{n_{k}\right\}_{k\in\mathbb{N}}$ donde $x_{n_{k}}\in A$ , $n_{1}$ es el menor número entero positivo tal que $x_{n_{1}}\in A$ y $n_{k+1}>n_{k}$ . Entonces

$$ E=\bigcup_{k=1}^{\infty}x_{n_{k}}, $$

y $E$ es contable, porque $E\thicksim\mathbb{N}$ . $\blacksquare$

¿Es convincente?

Answer 1

Creo que algunas cosas se pueden escribir de forma más clara. En primer lugar, yo cambiaría

Esto implica que existe una secuencia $\left\{x_{n}\right\}_{n\in\mathbb{N}}$ donde $x_{n}\in A$ .

Para

Esto implica que podemos escribir $A=\{x_n:n\geqslant 1\}$

o

Dejemos que $\{x_n:n\geqslant 1\}$ sea una enumeración de $A$ .

Entonces, diría

Si $S$ es un subconjunto de los números naturales, sea $\min S$ denotan el menor elemento de $S$ . Definir $S_1=\{k:x_k\in E\}$ . $S_2=S_1\setminus \{\min S_1\}$ y en general $$S_{n+1}=S_{n}\setminus\{\min S_1,\ldots,\min S_{n}\}$$ Entonces defina $n_k=\mathscr \min S_k$

Supongo que la idea es clara: considerar el conjunto de subíndices tal que $x_k\in E$ . Por la buena ordenación de los números naturales, podemos extraer una secuencia $n_k$ tal que $$n_1<n_2<\cdots\\E=\{x_{n_k}:k\geqslant 1\}$$

considerando el primer subíndice con $x_k\in E$ eliminando éste de la lista y observando el nuevo primer subíndice (nuestro segundo en la lista) y así sucesivamente. Hay que atender a algunos detalles

$(1)$ El conjunto $S_{n}$ nunca está vacío. Razón: Desde $E\subseteq A$ ; $S_1$ no está vacío. Además, $E$ es, por supuesto, infinito, por lo que eliminar un elemento cada vez no puede agotarlo.

$(2)$ La construcción agota los elementos de $E$ -- es decir, se trata de una suryección. Razón: Escoge $m$ tal que $x_m\in E$ . Tenemos que encontrar $k$ tal que $n_k=m$ . Consideremos el conjunto finito $\{x_1,\dots,x_m\}$ . Manteniendo el orden, eliminar todos los elementos tales que $x_i\notin E$ . Nos queda un conjunto finito, y debe ser el caso $\{x_{n_1},\dots,x_{n_k}\}$ para algunos $k$ y $n_k=m$ por definición de la $n_k$ .

$(3)$ La construcción es una inyección. Razón: Por construcción, $n_k\neq n_j$ si $j\neq k$ ya que si $j>k$ entonces $n_k\notin S_{j}$ .

Conclusión: Obtenemos una biyección de $E$ con un subconjunto infinito $F$ de $\Bbb N$ . Así, $E\simeq F\simeq \Bbb N$ Es decir $E\simeq \Bbb N$ .

Answer 2

Parece correcto, hasta un error tipográfico entre $A$ y $E$ y los corchetes que faltan en la unión al final (en $\bigcup\{x_{n_k}\}$ Además, es posible que desee definir $n_{k+1}$ como $$n_{k+1} = \inf\{ i > n_k \mid x_i \in E \}$$

Utilizando la definición (equivalente, y bastante idéntica hasta las notaciones secuencia/función) de un conjunto contable:

Un conjunto $A$ se llama contable si existe una función inyectiva $f$ de $A$ a $\mathbb{N}$

también se puede decir que si $f\colon A \to \mathbb{N}$ es una función inyectiva de este tipo, entonces en particular cualquier restricción $f_{|_E}$ (para $E\subseteq A$ ) también es una inyección, y por tanto $E$ es contable.