Zeigen Sie, dass S abzählbar ist.

Question

Aufgabe:

Sei S die Menge aller endl. Teilmengen von ℕ.

Zeigen Sie, dass S abzählbar ist, d.h es ex. eine surj. Abbildung ℕ -> T. Betrachten Sie hierzu die Binärdarstellung jeder Teilmenge.

Beweisen Sie danach, dass keine inj. Abbildung P(ℕ) -> ℕ existiert.

Problem/Ansatz:

Tue mich hier sehr schwer, das formal aufzuschreiben. Das erste verstehe ich glaube. Z.B. für 10 wäre es {2,4}, denn 10 = 1010 in binär. Aber wie man das aufschreiben würde allgemein, weiß ich nicht genau.

Bei dem zweiten hab ich gar keinen richtigen Ansatz, man könnte es vielleicht mit einem Widerspruchsbeweis versuchen, aber da kam ich auch nicht weiter.

Comments

Vom Duplikat:

Titel: Die Menge aller endlichen Teilmengen von N ist abzählbar. wie kann man das zeigen

Stichworte: mengen,abzählbar,surjektiv,teilmenge

Aufgabe:

Zeigen Sie:

(a) Die Menge T aller endlichen Teilmengen von N ist abzählbar, d.h. es gibt eine
surjektive Abbildung N → T.
Hinweis: Assoziieren Sie zu jeder endlichen Teilmenge eine Binärzahl.

(b) Es gibt keine injektive Abbildung ϕ : 2N → N

Answer 1

Die surj. Abbildung f: ℕ -> S hast du ja schon ganz gut erkannt.

Formalisiert vielleicht so:

Zu jeder Zahl x∈ℕ wird durch die Binärdarstellung der Zahl in

eindeutiger Weise eine Folge (an)n∈ℕ definiert, nämlich die

Ziffernfolge der Binärziffern ergänzt durch weitere Nullen,

damit es auch wirklich eine unendliche Folge wird.

Jeder Ziffernfolge (an)n∈ℕ und damit jedem x∈ℕ

kann man eine endliche Teilmenge von ℕ zuordnen durch

f(x) = {n∈ℕ  | a_n = 1 }.

Diese Mengen sind alle endlich, da jede Ziffernfolge nur

endlich viele 1en enthält.

Andererseits gibt es zu jeder endlichen Teilmenge M von ℕ

ein x mit f(x)=M. Denn sind in M die Elemente a_o bis a_n

dann ist x = \( \sum \limits_{k=0}^{n} 2^{a_k} \)

Comments

Das hat mir sehr geholfen, danke! Hast du bei dem anderen Teil

"Beweisen Sie danach, dass keine inj. Abbildung P(ℕ) -> ℕ existiert."

eine Idee?

Answer 2

Für die erste: Siehe https://www.mathelounge.de/886484/zeigen-sie-dass-m-abzahlbar-ist.

Für die zweite Aufgabe:

Es gibt eine Injektion zwischen der Menge aller semi-unendlichen Binärsequenzen \( \{0,1\}^{\infty} \) und \( \mathcal{P}(\mathbb{N}) \) gegeben durch

\(\begin{aligned} f:\{0,1\}^{\infty} \rightarrow \mathcal{P}(\mathbb{N}), \quad f(x)=\left\{i \mid x_{i}=1\right\}\end{aligned} \)
wobei \( x_{i} \) das \( i \) te Bit der Binärsequenz \( x \) bezeichnet. Gäbe es nun eine injektive Abbildung \( g: \mathcal{P}(\mathbb{N}) \rightarrow \mathbb{N} \), so gäbe es eine Injektive Abbildung \( g \circ f:\{0,1\}^{\infty} \rightarrow \mathbb{N} \) was aber unmöglich ist, da \( \{0,1\}^{\infty} \) überabzählbar ist (via Cantorargument).

Comments

Hast du auch eine Idee ohne Cantorargument? Weil das hatten wir nicht und dürfen wir deshalb wohl auch nicht verwenden.