Zeigen Sie, dass M abzählbar ist.

Question

Aufgabe:

Sei M ⊂ P(N0) die Menge aller endlichen Teilmengen von N0. Zeigen Sie, dass M abzählbar ist.

Problem/Ansatz:

Was bedeutet vor allem abzählbar? Wie löse ich die Aufgabe?

Answer 1

Abzählbar bedeutet, dass du eine Injektion von \( M \) nach \( \mathbb{N} \) finden kannst. Du assoziiest also mit jedem Element von \( M \) eine natürliche Zahl und kannst die Elemente von \( M \) somit nummerieren, bzw. abzählen. Es gibt natürlich unendlich viele Möglichkeiten, eine Funktion wäre z.B.
\( \begin{array}{l} f: M \subseteq \mathcal{P}(\mathbb{N}) \rightarrow \mathbb{N} \\ f(Q)=\prod \limits_{n \in Q} p_{n} \end{array} \)
wobei \( p_{n} \) die \( n \) te Primzahl bezeichnet. Die Injektivität folgt direkt aus der Eindeutigkeit der Darstellung einer Zahl als ein Produkt von Primzahlen. Das Produkt ist natürlich endlich, da wir ja nur endliche Teilmengen betrachten.

Du kannst den Injektivitätsbeweis gerne als Übung exakt aufschreiebn.