¿La colección de subconjuntos finitos de$\mathbb{Z}$ es contable?

Question

La colección de todos los subconjuntos de $\mathbb{Z}$ es incontable, por Teorema de Cantor

Pero, ¿cómo puedo probar que el conjunto de todos los subconjuntos finitos de $\mathbb{Z}$ es contable?

Answer 1

Hay un bonito bijection entre el $\mathbb{Z}$ y el conjunto de $\mathbb{N}$ de los números enteros no negativos. De esto podemos obtener un bijection entre el conjunto de los subconjuntos finitos de $\mathbb{Z}$ y el conjunto de los subconjuntos finitos de $\mathbb{N}$. Por lo tanto es suficiente para demostrar que el conjunto de los subconjuntos finitos de $\mathbb{N}$ es contable.

Para cualquier subconjunto finito $A$$\mathbb{N}$, vamos a $a_i=1$ si $i\in A$, y deje $a_i=0$ lo contrario. Vamos $$\psi(A)=\sum_{i=0}^\infty 2^i a_i$$ (tenga en cuenta que la suma es, efectivamente, una suma finita). El mapa de $\psi$ es un bijection desde el conjunto de los subconjuntos finitos de $\mathbb{N}$$\mathbb{N}$.

Estamos utilizando el entero con representación binaria $\dots a_na_{n-1}\dots a_2a_1a_0$ a representar a $A$.

Answer 2

Cada expresión un subconjunto finito $S \subseteq \mathbb{Z}$ es una expresión de entero de base-$14$, usando cuatro dígitos nueva: $${{} = 10, \quad {}} = 11, \quad {,} = 12, \quad {-} = 13$ $ tan por ejemplo $$ \begin{align} {1,-2,9,51} &= 11+1\cdot14+5\cdot14^2+12\cdot14^3+9\cdot14^4+12\cdot14^5+2\cdot14^6\ & \qquad +13\cdot14^7+12\cdot14^8+14^9+10\cdot14^{10}\ &= 2932309333405 \end{alinee el} $$ se puede definir así una inyección $\mathcal{P}_{\text{fin}}(\mathbb{Z}) \to \mathbb{N}$ mediante la asignación de un subconjunto finito $S \subseteq \mathbb{Z}$ al menos entero que representa el $S$ % base $14$con dígitos definidos como arriba.

Answer 3

Aviso el conjunto de todos los subconjuntos finitos de $\mathbb{Z}$ puede ser reescrita como una Unión contable. $$ \Big{\; Un \subseteq \mathbb{Z}\;:\;| A |