Zeigen Sie, dass die Menge P(N) aller Teilmengen von N überabzählbar ist.

Question

Aufgabe:

Zeigen Sie, dass die Menge P(N) aller Teilmengen von N überabzählbar ist.
Hinweis: Fuhren Sie die Existenz einer surjektiven Abbildung ¨ ϕ: N → P(N) zum Widerspruch. Betrachten Sie dazu die Menge M = {n ∈ N : n /∈ ϕ(n)} ∈ P(N)

Answer 1

Du kannst einfach eine Injektion von $\{0,1\}^{\infty}$ (die Menge aller semi-unendlichen Binärsequenzen, also nach rechts unbeschränkt) nach $\mathcal{P}(\mathbb{N})$ geben durch
$f:\{0,1\}^{\infty} \rightarrow \mathcal{P}(\mathbb{N}), \quad f(x)=\left\{n \in \mathbb{N} \mid\right.$ das $n$te Bit von $x$ ist eins, i.e. $\left.x_{n}=1\right\}$
Es ist klar, dass $\{0,1\}^{\infty}$ überabzählbar ist (einfach Kantordiagonalisierung anwenden).

Answer 2

Hallo,

vielleicht noch die Antwort auf die Frage von mero im engeren Sinn:

Wir nehmen an, es gäbe eine surjektive Abbildung $f: \mathbb{N} \to \mathcal{P}(\mathbb{N})$. Im Hinweis wird eine Menge M definiert durch die Eigenschaft:

$$n \in M \iff n \notin f(n)$$.

Wenn f surjektiv ist, gibt es ein k mit $f(k)=M$. Die Definition von M führt zum Widerspruch:

$$k \in M \iff k \notin f(k)=M$$

Gruß mathhilf