Dimostralo $ 2^{\mathbb{N}}$ è innumerevole [duplicato]

Question

Lo voglio dimostrare $\mid 2^{\mathbb{N}} \mid \neq \mid \mathbb{N} \mid$. Volevo procedere per Assurdo assumendo che ci fosse una biiezione$\phi : \mathbb{N} \longrightarrow 2^{\mathbb{N}} $ma non riesco a trovare l'assurdità. L'indicazione ci dice di considerare l'insieme$\{ n \in \mathbb{N} \mid n \notin \phi(n) \}$ ma non vedo come sia utile.

Answer 1

In generale, non esiste una mappa suriettiva $f:X\rightarrow 2^{X}$, dove $2^{X}$ è l'insieme dei sottoinsiemi di $X$. Supponiamo infatti che tale$f$esiste e quindi è suriettivo. Poi, ce ne sono alcuni$x\in X$ su cui è mappato $f(x)=\lbrace x\in X : x\notin f(x)\rbrace\in 2^{X}$. Ora, notalo$x\in f(x)$ significa che $x\notin f(x)$ e quello $x\notin f(x)$ significa che $x\in f(x)$il che è assurdo. Nel tuo caso,$X=\mathbb{N}$. Cerca l'argomento diagonale di Cantor.