Hacer todos los infinitos subconjuntos de a $\mathbb N$ tiene un bijective función de a $\mathbb N$?

Question

¿Existe para todos los subconjuntos de los números naturales, con infinitos elementos, una función que asigna a cada elemento en el que a cada subconjunto de los números naturales, y de la otra manera?

Answer 1

Si $A\subseteq \mathbb{N}$ $A$ es infinito, ya que $\aleph _0$ es el más pequeño de cardinalidad infinita, a continuación,$\aleph_0 \leq |A|\leq |\mathbb{N}| =\aleph_0$, por lo que Un y $\mathbb{N}$ tienen la misma cardinalidad - lo que significa que hay un bijection entre los dos.

Esto también puede ser visto directamente - supongamos $A\subseteq \mathbb{N}$ $A$ es infinito, definir una función $\varphi: \mathbb{N}\rightarrow A$ como sigue: Una tiene un número mínimo $a_1 \in A$, por lo que $\varphi(1)=a_1$. $A-\{a_1\}$ tiene un mínimo de número de $a_2$, por lo definen $\varphi(2)=a_2$. y, en general, tiene una k-ésimo número mínimo $a_k$$\varphi(k)=a_k$. Esto es cierto para todos los k puesto que a es infinito.

Es fácil ver que esto es inyectiva mapa. para mostrar surjectivity aviso que si $a\in A$ entonces no sólo es finito número natural (denotaremos por k-1) menor que $a$ que están en $A$, lo $\varphi(k)=a$.

---

Para el caso de $\mathbb{Z}$ esto también es cierto, ya que la $|\mathbb{Z}|=2|\mathbb{N}|=2\aleph_0 =\aleph_0$.

Para la aproximación directa, supongamos $A\subseteq \mathbb{Z}$ es infinito. Deje $B=A\cap \mathbb{N}$ si $B$ $A-B$ (positiva y negativa de las partes de Una) son infinitas, a continuación, hay un bijection entre B y $\mathbb{N}$ y un bijection entre el $A-B$ y los enteros negativos, así que únete a los dos bijections para conseguir uno de la a a la $\mathbb{Z}$. Supongamos ahora que uno de ellos es finito, wlog $B-A$ es finito, por lo que Una tiene un número mínimo. La misma prueba como antes, muestra que hay un bijection entre Un y $\mathbb{N}$.

Hay un bijection entre el $\mathbb{N}$ $\mathbb{Z}$ al ordenar los números enteros, por ejemplo,$0,1,-1,2,-2,3,-3,...$. Ahora se acaba de tomar la composición de los mapas - de la a a la $\mathbb{N}$ y, a continuación, a $\mathbb{Z}$.