Más bonito que la prueba de que el conjunto de subconjuntos finitos es contable?

Question

Estoy buscando una hermosa manera de mostrar el siguiente resultado básico en la escuela primaria de teoría de conjuntos:

Si $A$ es una contables se establece a continuación el conjunto de los subconjuntos finitos de $A$ es contables.

He demostrado de la siguiente manera, pero mi prueba es algo fugly así que me preguntaba si hay una buena manera de mostrar que:

Deje $|A| \le \aleph_0$. Si $A$ es finito, a continuación, $P(A)$ es finito y por lo tanto contables. Si $|A| = \aleph_0$, entonces hay un bijection $A \to \omega$, de modo que podemos suponer que estamos hablando de subconjuntos finitos de $\omega$ a partir de ahora. Definir un mapa de $\varphi: [A]^{<\aleph_0} \to (0,1) \cap \mathbb Q$$B \mapsto \sum_{n \in \omega} \frac{\chi_B (n)}{2^n}$. A continuación, $\varphi$ es inyectiva de ahí el reclamo de la siguiente manera. (La prueba de que es lo que es el núcleo de fugly parte de la prueba y omito.).

Answer 1

Si $A$ es un infinito contables conjunto, $S$ es el conjunto de subconjuntos finitos de $A$ $S_k$ es el conjunto de $k$-elemento de subconjuntos de a $A$, luego

$$ |S| = \sum_{k \in \mathbb{N}} |S_k| \leq \sum_{k \in \mathbb{N}} ||^k \leq \sum_{k \in \mathbb{N}} \aleph_0 = |\mathbb{N}| \cdot \aleph_0 = \aleph_0 $$

Answer 2

Los subconjuntos de a $A$ están en bijection con los subconjuntos de a$\mathbb{N}$, por lo que es suficiente para enumerar el último. Cualquier subconjunto de a $\mathbb{N}$ puede ser escrito como una cadena finita utilizando los siguientes trece caracteres $$0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ \{\ \}\ ,$$ Mediante el establecimiento de $${\{}=10 \qquad {\}}=11 \qquad {,}=12$$ la escritura de un subconjunto de a $\mathbb{N}$ es un base-$13$ expresión de un número entero. Por ejemplo $$\{ 0,1 \}_{13} = 10 \cdot 13^4 + 0 \cdot 13^3 + 12 \cdot 13^2 + 1 \cdot 13 + 11 = 287662$$

El mapa de envío $$S \mapsto \text{the least}\ n\ \text{represented by}\ S$$ define una inyección en $\mathbb{N}$.

Answer 3

Es suficiente para demostrar que el reclamo por $A=\mathbb{N}$. Denotar por $\operatorname{Fin}(\mathbb{N})$ el conjunto de todos los subconjuntos finitos de $\mathbb N$. Tenemos $$\operatorname{Fin}(\mathbb{N}) = \bigcup_{n\in\mathbb{N}}\left\{ A\subseteq\mathbb{N}: \max(A) = n \right\},$$ que es una contables de la unión finita de conjuntos como para cada una de las $n\in\mathbb{N}$ ciertamente hay menos de $2^n = \left|\mathcal{P}(\{1,\ldots,n \})\right|$ subconjuntos de a $\mathbb{N}$ cuyo elemento más grande es $n$. Por lo tanto, $\operatorname{Fin}(\mathbb{N})$ contables de sí mismo.

Answer 4

Clive la respuesta de obras (por supuesto)! O usted podría ir así, aprovechando el conocido truco de la codificación de una secuencia mediante el uso de potencias de números primos.

Índice de los miembros de $A$ $a_1$, $a_2$, $a_3$ $\ldots$ (sabemos que podemos, porque es contable).

Dado un número finito no vacío subconjunto $F \subset A$, vamos a $a_f$ es la más alta de indexado miembro de $F$, y para $1 \leq j \leq f$, puesto $c_j = 1$ fib $a_j \in F$ $c_j = 0$ lo contrario. Forma del producto $n_F = 2^{c_1} \cdot 3^{c_2} \cdot 5^{c_3} \cdot \ldots \cdot \pi_f^{c_f}$ donde $\pi_j$ $j$- ésimo primo. De una manera obvia, $n_F$ únicamente los códigos para $F$.

El mapa de $F \mapsto n_F$ es claramente una inyección de la no vacía de subconjuntos finitos de $A$ a los números naturales (distintos subconjuntos de ir a distintos números), por lo que los subconjuntos finitos son contables.

Answer 5

Tal vez usted encontrará la siguiente más a su gusto. Deje $S$ ser una contables conjunto y deje $F$ ser el conjunto de todos los subconjuntos finitos de $S$. Deje $E$ ser el conjunto de todas las secuencias finitas de elementos de $S$. Claramente $|F|\le |E|$. Ahora, para cada número natural $n$, vamos a $E_n=S^n$ ser el conjunto de todas las secuencias de $S$ de la longitud de la $n$. A continuación,$E=\bigcup _n E_n$. Ahora, un contable de la unión de conjuntos contables es contable, por lo $E$ es contable, y por lo tanto también se $F$ es contable.

Por supuesto, este argumento se basa en el hecho de que una contables de la unión de conjuntos contables es contable y que por una contables set $S$, los conjuntos de $S^n$ son todos contables, que han elegante pruebas.