Mostra isso $ 2^{\mathbb{N}}$ é incontável [duplicado]

Question

Eu quero mostrar isso $\mid 2^{\mathbb{N}} \mid \neq \mid \mathbb{N} \mid$. Eu queria prosseguir pelo Absurdo assumindo que há uma bijeção$\phi : \mathbb{N} \longrightarrow 2^{\mathbb{N}} $mas não consigo encontrar o absurdo. A indicação nos diz para considerar o conjunto$\{ n \in \mathbb{N} \mid n \notin \phi(n) \}$ mas não vejo como é útil.

Answer 1

Em geral, não há mapa sobrejetivo $f:X\rightarrow 2^{X}$, Onde $2^{X}$ é o conjunto de subconjuntos de $X$. Na verdade, suponha que tal$f$existe e então é sobrejetiva. Então, há alguns$x\in X$ que é mapeado para $f(x)=\lbrace x\in X : x\notin f(x)\rbrace\in 2^{X}$. Agora, observe que$x\in f(x)$ significa que $x\notin f(x)$ e essa $x\notin f(x)$ significa que $x\in f(x)$o que é um absurdo. No seu caso,$X=\mathbb{N}$. Procure o argumento diagonal de Cantor.