Zeigen, dass die Menge aller endlichen Teilmengen von N abzählbar unendlich ist.

29.10.2017, 13:55

David976

Zeigen, dass die Menge aller endlichen Teilmengen von N abzählbar unendlich ist.

Meine Frage:
Hallo,

Aufgabe:P(N) ist überabzählbar. Zeigen Sie, dass die Menge aller endlichen Teilmengen von N hingegen abzählbar unendlich ist.

Satz von Cantor-Bernstein-Schröder.Seien A und B Mengen. Dann gilt:
A bijektiv B $\begin{eqnarray*} <=> A\leq B\wedge B\leq A \end{eqnarray*}$

Abzählbarkeit:
Eine Menge M ist genau dann abzählbar, wenn sie gleichmächtig zu den natürlichen Zahlen ist. Das ist insofern offensichtlich, da jede Bijektion M bijektiv N quasi als Durchnummerierung verstanden werden kann und umgekehrt.

Unendlich/ endlich :
Eine Menge A ist unendlich , wenn $\begin{eqnarray*} \exists A'\subset A. A' bijektiv A \end{eqnarray*}$ .
Sonst ist A endlich.

Meine Ideen:
Meine Idee war mit $\begin{eqnarray*} i\in \mathbb N -> M \subseteq \mathbb N .|M|=i \end{eqnarray*}$ jede Teilmenge Mi mit ihrer Mächtigkeit= i aufzuzählen.

Dazu habe ich diese Funktion definiert:
$\begin{eqnarray*} f:N -> N^{M} \end{eqnarray*}$

also so:
0-> M0
1-> M1
2-> M2
.
.
.

Mein Problem ist, dass mir
1.) nicht klar ist, wie ich beweise, dass die Menge aller endlichen Teilmengen von N abzählbar unendlich ist und
2.)inwieweit die Elemente der einzelnen Teilmengen dabei zu berücksichtigen sind.

29.10.2017, 14:00

bijektion

Auf diesen Beitrag antworten »

Zitat:

Meine Idee war mit $\begin{eqnarray*} i\in \mathbb N -> M \subseteq \mathbb N .|M|=i \end{eqnarray*}$ jede Teilmenge Mi mit ihrer Mächtigkeit= i aufzuzählen.

Das geht so nicht, da dadurch natürlich keine bijektive Abbildung definiert wird.

Hast du noch eine andere Idee?

29.10.2017, 15:21

David976

Auf diesen Beitrag antworten »

Meine Idee wäre $\begin{eqnarray*} i+b*2-> m_{i} i \in M \in \mathbb N .|M|=b \end{eqnarray*}$

d.h. so als Beispiel
$\begin{eqnarray*} 0-> m0\in M0, (da 0+0*2=0); 1-> m1 \in M0; 2-> m0 \in M1; 3-> m1 \in M1; 4-> m0 \in M2; 5-> m1\in M2; . . . \end{eqnarray*}$
verwirrt

29.10.2017, 16:01

Leopold

Auf diesen Beitrag antworten »

In $\begin{align*} \mathbb{N} = \{ 0,1,2,3,\ldots \} \end{align*}$ würde ich die Menge $\begin{align*} A_n = \{ 0,1,2,\ldots,n \} \end{align*}$ mit $\begin{align*} n \in \mathbb{N} \end{align*}$ betrachten. Jede endliche Teilmenge von $\begin{align*} \mathbb{N} \end{align*}$ liegt in einem geeigneten $\begin{align*} A_n \end{align*}$ . Auf der anderen Seite besitzt $\begin{align*} A_n \end{align*}$ nur endlich viele Teilmengen. Für jedes $\begin{align*} n=0,1,2,\ldots \end{align*}$ würde ich die Teilmengen von $\begin{align*} A_n \end{align*}$ jetzt der Reihe nach aufschreiben. Die leere Menge wird vorangestellt:

leere Menge

leere Menge
0

leere Menge
0
1
0,1

leere Menge
0
1
2
0,1
0,2
1,2
0,1,2

leere Menge
0
1
2
3
0,1
0,2
0,3
1,2
1,3
2,3
0,1,2
0,1,3
0,2,3
1,2,3
0,1,2,3

...

Jetzt geht man die Liste von vorne durch. Was man schon hat, wird gestrichen. Übrig bleiben jeweils die Teilmengen, die das neue Element enthalten:

leere Menge
0
1
0,1
2
0,2
1,2
0,1,2
3
0,3
1,3
2,3
0,1,3
0,2,3
1,2,3
0,1,2,3

...

Das ist ein konstruktives Verfahren, um die endlichen Teilmengen von $\begin{align*} \mathbb{N} \end{align*}$ abzuzählen. Man kann es auch so sehen: Wenn man bis zu einer Stufe alle Teilmengen hat, nimmt man zu jeder bisher gewonnenen Teilmenge das neue Element hinzu. Mit jeder Stufe verdoppelt sich daher die Anzahl der Teilmengen. Dann sähe das so aus:

0. Stufe:
leere Menge

1. Stufe: 0 hinzunehmen zu den Mengen der 0. Stufe
0

2. Stufe: 1 hinzunehmen zu den Mengen der 0. und 1. Stufe
1
0,1

3. Stufe: 2 hinzunehmen zu den Mengen der 0., 1. und 2. Stufe
2
0,2
1,2
0,1,2

4. Stufe: 3 hinzunehmen zu den Mengen der 0., 1., 2. und 3. Stufe
3
0,3
1,3
0,1,3
2,3
0,2,3
1,2,3
0,1,2,3

Bis zur $\begin{align*} n \end{align*}$ -ten Stufe hat man dann $\begin{align*} 2^n \end{align*}$ Teilmengen erhalten.

30.10.2017, 13:52

David976

Auf diesen Beitrag antworten »

Danke, ich denke ich habe es jetzt verstanden also zeigt einfach n auf das jeweilige An, so dass N bijektiv zu der Menge A^N aller An ist oder ?

Neue Frage »

Antworten »

Zeigen, dass die Menge aller endlichen Teilmengen von N abzählbar unendlich ist.

Verwandte Themen