Abzählbarkeit der Potenzmenge der natürlichen Zahlen

02.03.2016, 20:47

123markus123

Abzählbarkeit der Potenzmenge der natürlichen Zahlen

Die Potenzmenge der natürlichen Zahlen ist nicht abzählbar, allerdings verstehe ich nicht, warum man sie nicht nach dem folgenden Algorithmus abzählen kann:

Definiere $\begin{eqnarray*} M_i:= \left\{ M \subset \mathbb{N} \mid \vert M \vert \leq i \wedge \forall x \in M \colon x \leq i \right\} \end{eqnarray*}$

code:
1: 2:	for i = 0 to infinity print M[i]

Die Menge $\begin{eqnarray*} M_i \end{eqnarray*}$ ist trivialerweise endlich und berechenbar. Demnach wird die Schleife immer wieder ausgeführt. Nacheinander müssten so alle Teilmengen von $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ ausgegeben werden. Damit wäre die Menge abzählbar, da ich alle Elemente nacheinander ausgeben kann.

Mal ein paar Schritte zum Verständnis.

n=0: $\begin{eqnarray*} M_0 = \left\{ \left\{ \right\} \right\} \end{eqnarray*}$
n=1: $\begin{eqnarray*} M_1 = \left\{ \left\{ \right\},\left\{ 0\right\}, \left\{ 1\right\} \right\} \end{eqnarray*}$
n=2: $\begin{eqnarray*} M_2 = \left\{ \left\{ \right\},\left\{ 0\right\}, \left\{ 1\right\},\left\{ 2\right\},\left\{ 0,1\right\},\left\{ 0,2\right\}, \left\{ 1,2\right\}\right\} \end{eqnarray*}$
n=3: $\begin{eqnarray*} M_3 = \left\{ \left\{ \right\},\left\{ 0\right\}, \left\{ 1\right\},\left\{ 2\right\},\left\{ 3\right\} ,\left\{ 0,1\right\},\left\{ 0,2\right\},\left\{ 0,3\right\} , \left\{ 1,2\right\},\left\{ 1,3\right\},\left\{ 2,3\right\},\left\{ 0,1,2\right\},\left\{ 0,1,3\right\},\left\{ 0,2,3\right\},\left\{ 1,2,3\right\}\right\} \end{eqnarray*}$

Wo ist der Denkfehler in dem Algorithmus?

02.03.2016, 20:54

tatmas

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Die Menge $\begin{eqnarray*} M_i \end{eqnarray*}$ ist trivialerweise endlich

Du summierst aber bis unendlich auf, und die $\begin{eqnarray*} M_\infty \end{eqnarray*}$ enthält unendliche Mengen, wie z.B. IN.

03.03.2016, 08:05

HAL 9000

Auf diesen Beitrag antworten »

Die Vereinigung aller $\begin{align*} M_i \end{align*}$ enthält alle endlichen Teilmengen von $\begin{align*} \mathbb{N} \end{align*}$ , und diese Vereinigungsmenge ist tatsächlich abzählbar.

Es fehlt aber eine "Kleinigkeit", nämlich alle unendlichen Teilmengen - und das sind nicht nur $\begin{align*} \mathbb{N} \end{align*}$ selbst, sondern eine ganze Vielfalt anderer Mengen wie etwa die Menge der geraden Zahlen, die Menge der ungeraden Zahlen usw. insgesamt überabzählbar viele. smile

@tatmas

Ich kenne die Symbolik $\begin{align*} \bigcup_{i=1}^{\infty} M_i \end{align*}$ als synonym zu $\begin{align*} \bigcup_{i\in\mathbb{N}} M_i \end{align*}$ , d.h., ein $\begin{align*} M_{\infty} \end{align*}$ (wie immer das auch definiert sein möge) gehört nicht zu dieser Vereinigung - ist genau wie bei Reihen $\begin{align*} \sum_{i=1}^{\infty} a_i \end{align*}$ , wo auch kein Element $\begin{align*} a_{\infty} \end{align*}$ mit summiert wird. Augenzwinkern

Neue Frage »

Antworten »

Abzählbarkeit der Potenzmenge der natürlichen Zahlen

Verwandte Themen