abzählbar oder nicht?

28.04.2005, 10:21

ellocko

abzählbar oder nicht?

Hi, ich sitze an folgender Aufgabe:
Zeigen Sie, dass
$\begin{eqnarray*} \{X \in P(\mathbb N )|~~|X|<\infty \} \end{eqnarray*}$ abzählbar ist.

Kann mir jemand helfen?

28.04.2005, 16:53

Tobias

Auf diesen Beitrag antworten »

Ich hätte evt. eine Idee, bin mir aber nicht wirklich sicher.

Deine Menge nenne ich mal $\begin{eqnarray*} P_{fin}(\mathbb{N}) \end{eqnarray*}$ . Um zu zeigen, dass diese Menge abzählbar ist, reicht es, zwei injektive Abbildungen anzugeben (Cantor-Schröder-Bernstein-Theorem):

$\begin{eqnarray*} \varphi : \mathbb{N} \to P_{fin}(\mathbb{N}) \end{eqnarray*}$
$\begin{eqnarray*} \psi : P_{fin}(\mathbb{N}) \to \mathbb{N} \end{eqnarray*}$

$\begin{eqnarray*} \varphi \end{eqnarray*}$ ist einfach: Man bildet einfach $\begin{eqnarray*} n \end{eqnarray*}$ auf $\begin{eqnarray*} \{n\} \end{eqnarray*}$ ab.

Für $\begin{eqnarray*} \psi \end{eqnarray*}$ hab ich diese Idee:

Sei $\begin{eqnarray*} p_1, p_2, \ldots \end{eqnarray*}$ die der Größe nach geordnete Liste der Primzahlen.

Die Elemente einer Menge $\begin{eqnarray*} M \in P_{fin}(\mathbb{N}) \end{eqnarray*}$ lassen sich der Größe nach ordnen: $\begin{eqnarray*} x_1 < x_2 < \ldots < x_n \end{eqnarray*}$ .

Dann bildet $\begin{eqnarray*} \psi \end{eqnarray*}$ die Menge M auf das Produkt
$\begin{eqnarray*} p_1^{x_1} \cdot p_2^{x_2} \cdot \ldots \cdot p_n^{x_n} \end{eqnarray*}$ ab. Da die Primfaktorzerlegung eindeutig ist, ist $\begin{eqnarray*} \psi \end{eqnarray*}$ injektiv.

Damit ist $\begin{eqnarray*} P_{fin}(\mathbb{N}) \end{eqnarray*}$ abzählbar.

28.04.2005, 17:22

Auf diesen Beitrag antworten »

@Tobias

Netter Beweis. Augenzwinkern

@ellocko

Etwas volkstümlicher ist die folgende direkte Angabe einer Abzählung:

0 --> {}

1 --> {0}

2 --> {1}
3 --> {0,1}

4 --> {2}
5 --> {0,2}
6 --> {1,2}
7 --> {0,1,2}

8 --> {3}
...

Allgemein werden $\begin{eqnarray*} 2^n,\ldots,2^{n+1}-1 \end{eqnarray*}$ genau diejenigen endlichen Teilmengen zugeordnet, die n als maximales Element enthalten - die Anzahl derartiger Teilmengen ist ja gerade $\begin{eqnarray*} 2^n \end{eqnarray*}$ .

EDIT: Kürzer formuliert: Der Zahl n mit Binärdarstellung

$\begin{eqnarray*} n=\sum\limits_{k=0}^{\infty}b_k2^k,\qquad b_k\in\{0,1\} \end{eqnarray*}$

wird die endliche Teilmenge $\begin{eqnarray*} \left\{ k \bigm| b_k=1 \right\}\subset\mathbb{N} \end{eqnarray*}$ zugeordnet.

28.04.2005, 19:08

martins1

Auf diesen Beitrag antworten »

Ein "Beweis":
Alle einelementigen Teilmengen von $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ lassen sich abzählen. Die zweielementigen Teilmengen lassen sich ebenso wie die rationalen Zahlen abzählen (Alle Paare natürlicher Zahlen in ein Quadrat schreiben, diagonalweise abzählen). Induktiv zeigt man, dass für jedes $\begin{eqnarray*} n \end{eqnarray*}$ , die $\begin{eqnarray*} n \end{eqnarray*}$ -elementigen Teilmengen abzählbar sind.

Nun schreibst du in eine "Tabelle" in die erste Zeile die einelementigen, in die zweite Zeile die zweielementigen, ..., in die $\begin{eqnarray*} n \end{eqnarray*}$ -te Zeile die $\begin{eqnarray*} n \end{eqnarray*}$ -elementigen Teilmengen der natürlichen Zahlen und zählst sie erneut diagonal ab.

Ist nicht formal, dafür aber anschaulich. (Korrigiert mich, wenn ich in diesem Punkt irre)

28.04.2005, 21:24

Tobias

Auf diesen Beitrag antworten »

Das Problem ist hier die nach oben unbeschränkte Größe der Mengen.

Du argumentierst nach dem Satz:

Sind A und B abzählbar, dann auch $\begin{eqnarray*} A \cup B \end{eqnarray*}$ . Dies ist natürlich richtig und lässt sich auf beliebig lange (aber endliche) Vereinigungen erweitern. In diesem Fall brauchen wir aber eine Vereinigung von unendlich vielen Mengen:

$\begin{eqnarray*} \bigcup_{k \in \mathbb{N}} A_k \end{eqnarray*}$

Wir wissen aber, dass eine Vereinigung von unendlich vielen abzählbaren Mengen auch überabzählbar sein kann.

28.04.2005, 22:49

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von Tobias
Wir wissen aber, dass eine Vereinigung von unendlich vielen abzählbaren Mengen auch überabzählbar sein kann.

Das stimmt. Aber auch nur, wenn wir die Vereinigung überabzählbar vieler abzählbarer Mengen betrachten. Es gilt nämlich:
Die Vereinigung abzählbar vieler abzählbarer Mengen ist wieder abzählbar. Und das ist hier der Fall, denn die Anzahl der Mengen kannst du ja abzählen, du hast ja selbst schon unter das Vereinigungszeichen k aus N geschrieben!
Und der Beweis des obigen Satzes verläuft genau so, wie martins1 es in diesem speziellen Fall gemacht hat!

Neue Frage »

Antworten »

abzählbar oder nicht?

Verwandte Themen