Es el poder conjunto de los números naturales contables?

Question

Algunas explicaciones: Un conjunto S es contable si existe una función inyectiva $f$ $S$ a los números naturales ($f:S \rightarrow \mathbb{N}$).

$\{1,2,3,4\}, \mathbb{N},\mathbb{Z}, \mathbb{Q}$ son todos contables.

$\mathbb{R}$ no es contable.

El juego de poder $\mathcal P(A)$ se define como un conjunto de todos los posibles subconjuntos de A, incluyendo el conjunto vacío y el conjunto.

$\mathcal P (\{\}) = \{\{\}\}, \mathcal P ( \mathcal P (\{\})) = \{\{\}, \{\{\}\}\}$

$\mathcal P({1,2}) = \{\{\}, \{1\},\{2\},\{1,2\}\}$

Mi pregunta es:

Es $\mathcal P (\mathbb{N})$ contables? ¿Cómo sería una función inyectiva $f:S \rightarrow \mathbb{N}$?

Answer 1

El Cantor del Teorema establece que para cualquier conjunto a $A$ no hay surjective función de $A\to\mathcal P(A)$. Con $A=\mathbb N$ esto implica que $\mathcal P(\mathbb N)$ no es contable.

(Pero en la tierra donde encontraste esas buenas explicaciones de countability y conjuntos de poder que no diga esto?)

Answer 2

El poder conjunto de los números naturales tiene la misma cardinalidad con los números reales. Así, es incontable.

Para ser rigurosos, he aquí una prueba de ello.