Zeigen Sie, dass P(N) für endliche Teilmengen von N anzählbar unendlich ist.

Question

Aufgabe: Abzählbar unendliche Potenzmenge von N

Mir stellt sich folgendes Problem:

6. Wir betrachten die Menge \( \mathcal{P}_{\mathrm{f}}(\mathbb{N}):=\{Y \in \mathcal{P}(\mathbb{N})|| Y \mid<\infty\} \) aller endlichen Teilmengen von \( \mathbb{N} \). Zeigen Sie, dass \( \mathcal{P}_{\mathrm{f}}(\mathbb{N}) \) abzählbar unendlich ist. Sie dürfen die eindeutige Binärdarstellung oder die eindeutige Primfaktorzerlegung natürlicher Zahlen verwenden.

Bisher habe ich mir folgendes überlegt: Damit eine Menge abzählbar unendlich ist, muss es eine Bijektion von N nach P(N) geben.
Die Potenzmenge enthält in diesem Fall nur endliche Teilmengen von N. Das heisst, jede Teilmenge hat eine eindeutige charakteristische Funktion und lässt sich sozusagen als Binärcode darstellen. Ich habe mir dann überlegt, dass es möglich wäre, jede Teilmenge eben aufgrund ihrer charakteristischen Funktion als Binärcode darzustellen und sie dann der Zahl in N zuzuordnen, welche im Binärsystem so ausgedrückt wird.

Nun glaube ich einerseits, dass diese hier nicht ausreicht und andererseits wüsste ich auch nicht, wie man das aufzeigen sollte. Ich wäre froh um ein paar Inputs:)

Answer 1

Deine Idee ist vollkommen richtig!

Sei \(\chi_M:\mathbb{N}\rightarrow \{0,1\}\) die charakteristische Funktion

der Teilmenge \(M \in P_f(\mathbb{N})\), dann definieren wir

\(f(M)=\sum_{n\in\mathbb{N}}\chi_M(n)2^n\). Es ist dann

\(f:\;P_f(\mathbb{N})\rightarrow \mathbb{N}\) wegen der eindeutigen

Binärdarstellung der natürlichen Zahlen eine Bijektion.

Answer 2

Ich habe mir dann überlegt, dass es möglich wäre, jede Teilmenge eben aufgrund ihrer charakteristischen Funktion als Binärcode darzustellen und sie dann der Zahl in N zuzuordnen, welche im Binärsystem so ausgedrückt wird.

Das geht doch: Durch die char. Funktion der jeweiligen Teilmenge bekommst du doch eine

Folge von 0en und 1en, wobei sowas wie  01100... etwa bedeuten würde:

Die 1 ist nicht in der Teilmenge , 2 und 3 aber schon und 4 und 5 nicht etc.

Dann betrachtest du die Abbildung, die jeder endlichen Teilmenge von N die nat. Zahl zu,

die bei diesem Beispiel als Einerziffer die 0 und als 10er und 100er - Ziffer die 1  etc. hat.

Also quasi die Ziffernfolge umgekehrt.

Da in der Folge nur endlich viele 1en sind, hat man irgendwo die letzte

Ziffer der Folge und damit die erste Ziffer der zugeordneten Zahl.

Auf diese Weise erhält man jede binär dargestellten nat. Zahl

( denn jede hat ja nur endlich viele Ziffern)

als Bild bei dieser Abbildung.  Und für verschiedene Mengen sind die Bilder

auch verschieden.