El subconjunto de un conjunto contable es a su vez contable

Question

¿Cómo se demuestra que si $$A \subset B\ \text{with}\ B\ \text{countable} $$ entonces $A$ es contable, finito o vacío? Creo que la prueba implica un $1-1$ correspondencia entre $\mathbb{N}$ et $A$ pero aparte de eso no sé cómo proceder.

EDIT: He comprobado la solución y me aconseja proceder de la siguiente manera. "Como inicio de una definición de $$g: \mathbb{N} \rightarrow A$$ set $$g(1)=f(n_1) $$ A continuación, muestre cómo continuar inductivamente este proceso para producir un $1-1$ función $g$ de $\mathbb{N}$ en $A$ ."

Así que la prueba según mi libro implica la inducción.

Answer 1

Cualquier subconjunto de un conjunto contable es contable.

Tome $A\subset B$ donde $B$ es contable. Entonces $|A|\leq|B|$ desde $A\subset B$ . Por definición, $|A|\leq|B|$ si existe una función uno a uno desde $A$ en $B$ . También vemos que $|B|\leq\aleph_0$ desde $B$ es contable. Por lo tanto, $|A|\leq\aleph_0$ .

Answer 2

Mediante la biyección $\Bbb N\cong B$ tenemos una inyección $i:A\to\Bbb N$ .

Definir $$f(n+1)=\min\{k∈i[A]∣k>f(n)\}$$ para $n≥1$ et $$f(1)=\min i[A]$$

Afirmamos que para cada $n$ tenemos $\{f(1)<f(2)<...<f(n)\}$ es un subconjunto de $i[A]$ y contiene cada $i(a)$ menos que $f(n)$ .
Prueba: Inducción sobre $n$ :
Para $n=1$ claramente $f(1)∈i[A]$ y como no hay $i(a)<f(1)$ La afirmación es cierta.
Supongamos que la afirmación es cierta para $n$ . Entonces, por definición de $f$ el número $f(n+1)$ es mayor que $f(n)$ por lo que el conjunto $\{f(1)<...<f(n)<f(n+1)\}$ es un subconjunto de $i[A]$ . Desde $f(n+1)$ es el elemento mínimo de $i[A]$ más grande que $f(n)$ debe contener cada $i(a)$ menos de $f(n+1)$ .

Así que hemos demostrado que $f:\Bbb N↦i[A]$ es una inyección. Ahora, para $a\in A$ tenemos el número natural $l=i(a)$ . Desde $l$ es menor que $f(n)$ para algunos $n\in\Bbb N$ , $f$ al ser estrictamente creciente, debe ser uno de $f(1),f(2),...,f(n-1)$ .

Answer 3

Sugerencia: Definir una inyección $f:B \to \mathbb{N}$ (esto es posible ya que B es contable). Definir el mapa de inclusión $I:A \to B$ . Considere $f\circ I:A \to \mathbb{N}.$ ¿Qué puede decir sobre $I$ ? ¿Qué puede decir entonces sobre $f \circ I$ ? ¿Qué puede concluir entonces sobre $A$ ?

Answer 4

Comenzamos con un mapeo biyectivo

$\tag 1 f: \Bbb N \cong B$

Utilizando $f$ definimos otra función

$\tag 2 \Phi: \mathcal P(B) \setminus \emptyset \to B$ $\quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad X \mapsto f\bigr(\,\text{min}(f^{-1}(X))\,\bigr)$

Si $A \subset B$ et $A$ no es finita, podemos construir recursivamente otra función $g: \Bbb N \to A$ al establecer

$\quad g(1) = \Phi(A)$

y con $g(1), g(2), \dots, g(n)$ conjunto, definiendo

$\quad g(n+1) = \Phi\bigr(A \setminus \{g(1), g(2), \dots, g(n)\}\bigr)$

Ejercicio 1: Demuestre que $g$ es una función bien definida (recursiva).

Ejercicio 2: Demuestre que $g$ es una correspondencia biyectiva,

$\tag 3 g: \Bbb N \cong A$

---

Aquí hay otra prueba.

Un conjunto $C$ es contable si existe una suryección $h: \Bbb N \to C$ . De hecho, una biyección explícita $\Bbb N \cong C$ puede construirse utilizando $h$ (véase, por ejemplo, este ).

Abordando la interesante situación, dejemos $B$ sea un conjunto infinito contenido en un conjunto contable $A$ . Sea $f: \Bbb N \cong A$ exhibir la $\text{1:1}$ la correspondencia. Elija cualquier elemento $b_0 \in B$ y definir

$$ F(m) = \left\{\begin{array}{lr} f(m), & \text{for } m \in f^{-1}(B) \\ b_0 , & \text{for } m \in \mathbb N \setminus f^{-1}(B) \end{array}\right\} $$

La cartografía $F: \Bbb N \to B$ es un suryecto.

Answer 5

Pista: Supongamos que $f$ es la función que mapea $B$ a $\mathbb{N}$ , ordenar cada elemento en $B$ por su $f$ valor.