Nachlesen

Mächtigkeit einer Menge

Bei der Mächtigkeit einer Menge (auch Kardinalität einer Menge) handelt es sich um eine Verallgemeinerung des für endliche Mengen verwendeten Begriffs Anzahl der Elemente einer Menge auf unendliche Mengen. Für endliche Mengen entspricht die Mächtigkeit der Anzahl der Elemente, also einer natürlichen Zahl inklusive Null.

Inhalt

Definition
Beispiele
Vergleich der Mächtigkeiten von Mengen
Ordnung der Mächtigkeiten
Größte Mächtigkeit

Definition

Mächtigkeit einer endlichen Menge

Gegeben sei eine endliche Menge $A$. Bei der Mächtigkeit (auch Kardinalität) der Menge $A$ handelt es sich um die Anzahl der Elemente der Menge $A$. Die Mächtigkeit von $A$ wird typischerweise als $|A|$ geschrieben.

Besitzt die Menge $A$ insgesamt $n \in \N_0$ Elemente, wobei $n$ eine natürliche Zahl inklusive Null ist, so gilt:

\[ |A| = n. \]

Mächtigkeit einer unendlichen Menge

Gegeben sei eine unendliche Menge $A$. Die Mächtigkeit (auch Kardinalität) der Menge $A$ wird dann mithilfe von Kardinalzahlen angegeben, die sich aus den Äquivalenzklassen der Gleichmächtigkeitsrelation ergeben.

Gleichmächtigkeit von Mengen

Eine Menge $A$ heißt gleichmächtig zu einer Menge $B$, wenn es eine Bijektion $f: A \rightarrow B$ gibt. In diesem Fall gilt $|A| = |B|$ bzw. $A \sim B$. Bei der Gleichmächtigkeitsrelation bzw. Gleichmächtigkeit $\sim$ handelt es sich um eine Äquivalenzrelation, aus deren Äquivalenzklassen sich die Kardinalzahlen ergeben, die die Größe der Repräsentanten der jeweiligen Klasse beschreiben.

Ist eine Menge $A$ gleichmächtig zu einer Menge $B$, so existiert eine Bijektion $f: A \rightarrow B$. Hieraus folgt unmittelbar die Existenz der (ebenfalls bijektiven) Umkehrfunktion $f^{-1}: B \rightarrow A$ und somit die Gleichmächtigkeit von $B$ und $A$. Es gilt:

Endliche Mengen sind genau dann gleichmächtig, wenn sie dieselbe (endliche) Anzahl an Elementen besitzen.
Unendliche Mengen sind genau dann gleichmächtig, wenn sie in derselben Äquivalenzklasse der Gleichmächtigkeitsrelation liegen.

Abzählbare Menge

Eine Menge, die gleichmächtig zur Menge $\N_0$ der natürlichen Zahlen inklusive Null oder gleichmächtig zu einer Teilmenge von $\N_0$ ist, wird abzählbare Menge genannt.

Teilweise wird unter abzählbar lediglich abzählbar unendlich verstanden – also gleichmächtig zu den natürlichen Zahlen $\N_0$. Die Gleichmächtigkeit zu einer endlichen Teilmenge der natürlichen Zahlen wird dann als höchstens abzählbar bezeichnet.

Ist eine Menge mächtiger als die natürlichen Zahlen, so heißt sie überabzählbar.

Beispiele

Bei den folgenden Beispielen handelt es sich exemplarisch um die Mächtigkeiten einiger (endlicher) Mengen:

Für die leere Menge $\emptyset$ gilt $|\emptyset| = 0$.
Für die Menge $A = \bigl\{ 1,2,3 \bigr\}$ gilt $|A| = 3$.
Für die Menge $B = \bigl\{ 0,2,4,6,8 \bigr\}$ gilt $|B| = 5$.
Für die Menge $C = \bigl\{ x \in \N \mid 23 \leq x \leq 42 \bigr\}$ gilt $|C| = 20$.

Für die folgenden (unendlichen) Mengen gilt exemplarisch:

Die natürlichen Zahlen $\N$, die ganzen Zahlen $\Z$ und die rationalen Zahlen $\Q$ sind gleichmächtig.
Die reellen Zahlen $\R$, die komplexen Zahlen $\C$ und die Potenzmenge $\mathcal{P}(\N)$ der natürlichen Zahlen sind gleichmächtig.
Die Menge der reellen Zahlen ist mächtiger als die Menge der natürlichen Zahlen.

Vergleich der Mächtigkeiten von Mengen

Für Mengen $A$ und $B$ gilt:

Die Menge $A$ heißt höchstens gleichmächtig zu $B$, falls es eine bijektive Abbildung von $A$ auf eine Teilmenge von $B$ gibt. Es gilt $|A| \leq |B|$.
Die Menge $A$ heißt weniger mächtig als $B$, falls es eine bijektive Abbildung von $A$ auf eine (echte) Teilmenge von $B$ gibt, aber keine bijektive Abbildung von $A$ auf die Menge $B$ selbst. Die Menge $B$ heißt entsprechend mächtiger als $A$. Es gilt $|A| \lt |B|$ – und somit $|A| \leq |B|$, aber nicht $|A|=|B|$.
Für beliebige Mengen $A$ und $B$ gilt stets $|A| \leq |B|$ oder $|B| \leq |A|$.

Jede abzählbare Menge ist entweder endlich oder gleichmächtig zu den natürlichen Zahlen $\N$. Zudem enthält jede unendliche Menge eine Teilmenge, die gleichmächtig zu den natürlichen Zahlen ist. Die Mächtigkeit von $\N$ ist somit die kleinste Kardinalzahl und es gilt:

|\N| = \aleph_0.

Gemäß Kontinuumshypothese existiert keine Menge, die mächtiger als die natürlichen Zahlen $\N$, aber weniger mächtig als die reellen Zahlen $\R$ ist. Es gilt:

|\R| = |\mathcal{P}(\N)| = 2^{|\N|} = 2^{\aleph_0} = \aleph_1.

Ordnung der Mächtigkeiten

Die Kardinalzahlen sind total geordnet:

Es gilt stets $|A| = |A|$.
(Dies kann unmittelbar mithilfe der identischen Abbildung $\id_A$ gezeigt werden, bei der es sich um eine Bijektion der Menge $A$ auf sich selbst handelt.)
Aus $|A| \leq |B|$ und $|B| \leq |A|$ folgt stets $|A| = |B|$.
(Dies besagt das Cantor-Bernstein-Schröder-Theorem.)
Aus $|A| \leq |B|$ und $|B| \leq |C|$ folgt stets $|A| \leq |C|$.
(Dies folgt unmittelbar aus der Definition der Relation $\leq$ und der Eigenschaft, dass die Komposition der bijektiven Abbildungen $A \rightarrow B$ und $B \rightarrow C$ eine Bijektion $A \rightarrow C$ ergibt.)
Für beliebige Mengen $A$ und $B$ gilt stets $|A| \leq |B|$ oder $|B| \leq |A|$.
(Dies ist äquivalent zum Auswahlaxiom.)

Größte Mächtigkeit

Der Satz von Cantor besagt, dass eine beliebige Menge $A$ stets weniger mächtig ist als ihre Potenzmenge $\mathcal{P}(A)$:

Für die Mächtigkeit der Potenzmenge $\mathcal{P}(A)$ einer endlichen Menge $A$ mit $|A| = n$ gilt: $|\mathcal{P}(A)| = 2^{|A|} = 2^n.$
Für die Mächtigkeit der Potenzmenge $\mathcal{P}(A)$ einer unendlichen Menge $A$ mit $|A| = \aleph_i$ (mit $i \in \N_0$) gilt analog: $|\mathcal{P}(A)| = 2^{|A|} = 2^{\aleph_i} = \aleph_{i+1}.$

Werden die Potenzmengen von Potenzmengen von Potenzmengen usw. betrachtet, so folgt hieraus unmittelbar, dass keine mächtigste Menge existieren kann – und somit unendlich viele Kardinalzahlen existieren.