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