Montre CA $ 2^{\mathbb{N}}$ est indénombrable [en double]

Question

Je veux montrer ça $\mid 2^{\mathbb{N}} \mid \neq \mid \mathbb{N} \mid$. J'ai voulu procéder par l'Absurde en supposant qu'il y a une bijection$\phi : \mathbb{N} \longrightarrow 2^{\mathbb{N}} $mais je ne trouve pas l'absurdité. L'indication nous dit de considérer l'ensemble$\{ n \in \mathbb{N} \mid n \notin \phi(n) \}$ mais je ne vois pas en quoi c'est utile.

Answer 1

En général, il n'y a pas de carte surjective $f:X\rightarrow 2^{X}$, où $2^{X}$ est l'ensemble des sous-ensembles de $X$. En effet, supposons qu'un tel$f$existe et est donc surjectif. Ensuite, il y a quelques$x\in X$ qui est mappé à $f(x)=\lbrace x\in X : x\notin f(x)\rbrace\in 2^{X}$. Maintenant, notez que$x\in f(x)$ signifie que $x\notin f(x)$ et cela $x\notin f(x)$ signifie que $x\in f(x)$ce qui est absurde. Dans ton cas,$X=\mathbb{N}$. Recherchez l'argument diagonal de Cantor.