¿Cuántos subconjuntos de a $\mathbb{N}$ tienen la misma cardinalidad como $\mathbb{N}$?

Question

¿Cuántos subconjuntos de a $\mathbb{N}$ tienen la misma cardinalidad como $\mathbb{N}$?

Me doy cuenta de que cualquiera de la clase de funciones $f:x\to (n\cdot x)$ da un bijection entre el $\mathbb{N}$ y el subconjunto de $\mathbb{N}$ cuyos miembros la igualdad de los múltiplos de n. Así, tenemos al menos un infinito contable de conjuntos que tienen la misma cardinalidad de a $\mathbb{N}$. Pero, se podría eliminar un elemento único de cualquier countably infinito subconjunto de los números naturales y que todavía va a terminar con un countably infinito subconjunto de $\mathbb{N}$. Así que (el razonamiento aquí, no parece muy correcto para mí), ¿ existe una cantidad no numerable de infinitos subconjuntos de a $\mathbb{N}$ con la misma cardinalidad de a $\mathbb{N}$?

También, es la clase de todos los bijections $f: \mathbb{N} \to \mathbb{N}$ y un dado countably infinito subconjunto uncountably infinito o countably infinito?

Answer 1

Uno puede escribir un bijection entre el$\mathrm{Fin}(\mathbb N)$$\mathbb N$, es decir, entre el conjunto de los subconjuntos finitos de $\mathbb N$$\mathbb N$. Por ejemplo: $$f(A)=\sum_{i\in A}2^i$$

Tenga en cuenta que $A$ es finito por lo que esta es una bien definida la función. Resulta que este es un bijection así.

Entonces uno puede mostrar que $\mathcal P(\mathbb N)\setminus\mathrm{Fin}(\mathbb N)$ es incontable, y de hecho equipotente a $\mathcal P(\mathbb N)$. Esto es debido a que $k+\aleph_0=2^{\aleph_0}$ implica que el $k=2^{\aleph_0}$. Así que si $k=|\mathcal P(\mathbb N)\setminus\mathrm{Fin}(\mathbb N)|$$k=2^{\aleph_0}=|\mathcal P(\mathbb N)|$.

---

A la segunda pregunta, uno puede demostrar que no se $2^{\aleph_0}$ permutaciones de $\mathbb N$. Por lo tanto, si $f\colon A\to\mathbb N$ es un bijection a componer con una permutación de $\mathbb N$ resultará en otro bijection. No es difícil mostrar que si queremos componer permutaciones diferentes que tienen diferentes bijections (es decir, que no están de acuerdo sobre el valor de algún punto en $A$). Por lo tanto, no se $2^{\aleph_0}$ muchos bijections entre dos conjuntos contables.

(También me comentó que ninguno de los puntos en esta respuesta requiere el axioma de elección).

Answer 2

$\Bbb N$ tiene sólo countably muchos subconjuntos finitos, pero tiene una cantidad no numerable de subconjuntos en total, por lo que debe tener una cantidad no numerable de countably infinitos subconjuntos (es decir, subconjuntos con la misma cardinalidad como $\Bbb N$ sí).

Si $A$ es cualquier countably conjunto infinito, hay una cantidad no numerable de bijections entre el$\Bbb N$$A$.

Answer 3

Algunas respuestas:

Hay una cantidad no numerable de conjuntos de números impares, y al lado de los números pares a cada uno de estos rendimientos de un juego con la misma cardinalidad como $\mathbb N$.

Dado cualquier número real $x$, podemos formar el conjunto $S(x)=\{\lfloor x \rfloor,\lfloor 10x \rfloor,\lfloor 100x\rfloor,\dots\}$ (por ejemplo, $S(\pi)=\{3,31,314,3141,31415,\dots\}$), que claramente tiene la misma cardinalidad como $\mathbb N$, y el mapa de $S$ es un bijection, por lo que este proceso se obtiene una cantidad no numerable de conjuntos.

(En realidad el mismo que el último) Dado cualquier secuencia infinita $(a_n)$ de los números naturales, podemos formar el conjunto $\{2^{a_1},3^{a_2},5^{a_3},\dots\}$ que tiene la misma cardinalidad como $\mathbb N$.

Answer 4

Como grandes respuestas ya se han dado, me gustaría simplemente agregue una manera fácil de mostrar que el conjunto de los subconjuntos finitos de $\mathbb{N}$ contables:

Observar que $$\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.

A partir de aquí, usted puede utilizar Asaf del argumento para demostrar que el conjunto de los infinitos subconjuntos de a $\mathbb{N}$ (que son precisamente los conjuntos con la misma cardinalidad como $\mathbb{N}$) deben ser incontables.