• Home
• Theorie
  • Potenzmenge
  • Unendlichkeit der Primzahlen
  • Euler-Formel
  • Diagonalsprache
  • O-Kalkül
  • wp-Kalkül
  • Informationstheorie
  • Schnelle Fourier Transformation
  • Diskrete Kosinus Transformation
• Praxis
  • Huffman Kodierung
  • Primzahlen TM
• Aufschriebe
  • Papers
  • Mathematik
• Tutorien
  • Info III WS05/06
  • Info IV SS06
  • Info III WS06/07
  • Info IV SS07

Die Mächtigkeit der Potenzmenge

Mengen spielen in der Mathematik eine sehr grundlegende Rolle. Das Konzept der Potenzmenge ist daher auch von großer Bedeutung. Sei also $M$ eine Menge. Dann ist die Potenzmenge von $M$ wie folgt definiert:

$$\mathcal{P}(M) := \{ N \;|\; N \subseteq M \}$$

Sie enthält also alle möglichen Teilmengen von $M$, insbesondere auch die leere Menge und $M$ selbst.

Ein kleines Beispiel: Ist $M := \{1,2,3\}$, so enthält $\mathcal{P}(M)$ die folgende Elemente:

$$\mathcal{P}(M) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$$

Wir können hier nachzählen, dass gilt $|\mathcal{P}(M)| = 2^{|M|}$. Tatsächlich gilt diese Beziehung für alle endlichen Mengen. Das lässt sich beispielsweise durch vollständige Induktion leicht beweisen.

Viel spannender ist jedoch die Frage, wie es um unendliche Mengen steht. Nehmen wir beispielsweise $\mathbb{N}$. Wir wissen, dass $\mathbb{N}$ abzählbar unendlich ist. Welche Mächtigkeit hat nun $\mathcal{P}(\mathbb{N})$? Ist diese Menge immernoch abzählbar?

Der folgende Satz beantwortet diese Fragen. Der Beweis dazu (zumindest für den unendlichen Teil, den ich hier vorstellen möchte) besitzt eine gewisse Eleganz und wäre meiner Meinung nach fast ein Kandidat für einen BUCH Beweis.

Satz.

Sei $M$ eine beliebige Menge, dann gilt $|\mathcal{P}(M)| > |M|$. Man beachte, dass es echt größer heißt.

Beweis.

Dass $|\mathcal{P}(M)| \geq |M|$ gilt, sollte ziemlich klar sein. Jedes Element aus $M$ ist als Einermenge natürlich in $\mathcal{P}(M)$ enthalten. Damit enthält $\mathcal{P}(M)$ mindestens so viele Elemente wie $M$. Konzentrieren wir uns also auf den Beweis, dass die Potenzmenge echt mächtiger ist.

Für endliche Mengen ist das uninteressant. Eine einfache Induktion zeigt die Aussage.

Sei $M$ also eine Menge, für die gilt $|M| = \infty$. Nehmen wir an, dass die Potenzmenge gleichmächtig ist, will heißen $|M| = |\mathcal{P}(M)|$. Das heißt also, dass es eine bijektive Abbildung $\Phi: M \to \mathcal{P}(M)$ geben muss, die jedem Element aus $M$ eineindeutig ein Element aus $\mathcal{P}(M)$ zuordnet. Über das genaue Aussehen der Abbildung wollen wir garkeine Aussagen machen, wir wissen nur dass eine existiert.

Jetzt kommt der Trick: Wir definieren uns geschickt eine neue Menge $A \subset M$, und zwar wie folgt:

$$A := \{ m \in M \;|\; m \notin \Phi(m) \}$$

Machen wir uns zunächst klar, dass $A$ wohldefiniert ist. $A$ soll alle Elemente $m \in M$ enthalten, für die gilt, dass $m$ nicht in der Menge $\Phi(m)$ ist. Da $\Phi$ in die Potenzmenge von $M$ abbildet, lässt sich das tatsächlich überprüfen. Des Weiteren ist $A$ selbst wieder ein Element der Potenzmenge $\mathcal{P}(M)$, da $A$ nach Definition eine Teilmenge von $M$ ist.

So, da wir nach Voraussetzung wissen dass $\Phi$ bijektiv ist, muss es nun ein Element $\xi \in M$ geben, so dass $\Phi(\xi) = A$ gilt. Jetzt kommt die Frage: Ist $\xi \in A$? Es gibt dafür nur die zwei folgenden Möglichkeiten:

• Nehmen wir an $\xi \notin A$. Nach Definition von $A$ enthält $A$ aber gerade die Elemente $m \in M$ für die $m \notin \Phi(m) = A$ gilt. Wähle $m = \xi$, damit ist $\xi \in A$. Das ist ein Widerspruch!
• Nehmen wir also an $\xi \in A$. Das heißt aber nach Definition von $A$ dass $\xi \notin \Phi(\xi) = A$. Das ist offensichtlich ebenfalls ein Widerspruch!

Zusammengefasst konnten wir den Widerspruch herleiten, dass $\xi$ genau dann in $A$ enthalten ist, wenn es nicht in $A$ enthalten ist. Somit ist unsere Prämisse falsch, und es existiert keine solche bijektive Abbildung $\Phi: M \to \mathcal{P}(M)$. Also folgt $|\mathcal{P}(M)| > |M|$. $\square$

Schlussfolgerungen

Das Resultat ist nun vielleicht nicht so ganz das was der Intuition entspricht. Für die natürlichen Zahlen beispielsweise bedeutet das, dass ihre Potenzmenge echt mächtiger sein muss. Glaubt man an die Kontinuumshypothese, so bedeutet das, dass sie (mindestens) überabzählbar unendlich ist. Somit ist sie mindestens so mächtig wie $\mathbb{R}$, was ich doch recht faszinierend finde.