Mächtigkeit (Mathematik)

In der Mathematik verwendet man den aus der Mengenlehre stammenden Begriff der Mächtigkeit oder Kardinalität, um den für endliche Mengen verwendeten Begriff der "Anzahl der Elemente einer Menge" auf unendliche Mengen zu verallgemeinern.

Für endliche Mengen setzt man die Mächtigkeit gleich der Anzahl der Elemente der Menge, das ist eine natürliche Zahl. Für unendliche Mengen benötigt man etwas Vorarbeit, um ihre Mächtigkeiten zu charakterisieren. Die im folgenden gemachten Definitionen und Folgerungen sind aber auch im Falle endlicher Mengen gültig.

Gleichmächtigkeit, Mächtigkeit

Man definiert zunächst den Begriff der Gleichmächtigkeit zweier Mengen A und B:

Eine Menge A heißt gleichmächtig zu einer Menge B, wenn es eine Bijektion f: A -> B gibt. Man schreibt dann |A| = |B|.

Ist A gleichmächtig zu B, dann ist auch die Umkehrfunktion von f eine Bijektion, also ist auch B gleichmächtig zu A. Endliche Mengen sind genau dann gleichmächtig, wenn sie gleich viele Elemente haben.

Man nennt eine Menge, die gleichmächtig zur unendlichen Menge N der natürlichen Zahlen ist, eine abzählbare Menge.

Kardinalzahlen

Da man leicht zeigen kann, dass die Gleichmächtigkeit von Mengen eine Äquivalenzrelation ist, macht die folgende Definition Sinn:

Die Äquivalenzklassen der Mengen bezüglich der Relation der Gleichmächtigkeit nennt man Kardinalzahlen.

Aleph ($\aleph$) ist der erste Buchstabe des hebräischen Alphabets, er wird mit einem Index verwendet, um Kardinalzahlen unendlicher Mengen zu benennen.

Liegt eine Menge A in der Äquivalenzklasse (= Kardinalzahl) aleph_i, dann sagt man, A hat die Mächtigkeit aleph_i. Man schreibt dann:

$|A|=\aleph _{i}$.

Die Kardinalzahl einer endlichen Menge mit n Elementen wird mit der natürlichen Zahl n gleichgesetzt.

Man kann sich nun fragen, ob alle unendlichen Mengen einander gleichmächtig sind - in dem Fall wären alle unendlichen Mengen abzählbar.

Es stellt sich jedoch heraus, dass es unendliche Mengen gibt, die nicht gleichmächtig zueinander sind, z.B. ist die Menge der natürlichen Zahlen nicht gleichmächtig zur Mengen der reellen Zahlen. Das kann man z.B. mit dem so genannten "Cantorschen Diagonalbeweis" zeigen.

Weiter unten wird gezeigt, dass es unendlich viele verschiedene Kardinalzahlen gibt.

Indem man zeigt, dass jede Menge gleichmächtig zu einer Ordinalzahl ist (dies ist die Aussage des Wohlordnungssatzes), kann man jede Kardinalzahl mit der kleinsten ihr gleichmächtigen Ordinalzahl gleichsetzen.

Höchstens gleichmächtig, mächtiger

Um die Mächtigkeiten ungleichmächtiger Mengen trotzdem noch vergleichen zu können, legt man fest, wann eine Menge B mächtiger als eine Menge A sein soll:

Wenn es eine Bijektion f von A auf eine Teilmenge von B gibt, dann heißt A höchstens gleichmächtig zu B. Man schreibt dann |A| <= |B|.

Wenn es eine Bijektion f von A auf eine Teilmenge von B gibt, aber keine Bijektion von A nach B existiert, dann heißt A weniger mächtig als B und B mächtiger als A. Man schreibt dann |A| < |B|.

Offenbar gilt |A| < |B| genau dann, wenn |A| <= |B| aber nicht |A| = |B| ist.

Da die natürlichen Zahlen eine Teilmenge der reellen Zahlen sind, gilt also:

R ist mächtiger als N, c := |R| > |N|.

Man kann zeigen, dass R gleichmächtig ist zur Potenzmenge von N.

Eine Menge A, die höchstens gleichmächtig zu N ist, heißt höchstens abzählbar.

Man kann zeigen, dass jede Menge, die höchstens abzählbar ist, entweder endlich oder gleichmächtig zu N ist. Außerdem kann man zeigen, dass jede unendliche Menge eine zu N gleichmächtige Teilmenge enthält.

Damit ist die Mächtigkeit von N die kleinste unendliche Kardinalzahl. Man bezeichnet sie mit aleph₀:

$\aleph _{0}:=|\mathbb {N} |$.

Die nächstgrößere Mächtigkeit wird mit aleph₁ bezeichnet.

Die Kontinuumshypothese (CH) besagt, dass es keine Menge gibt, die mächtiger ist als N, aber weniger mächtig als R. In dem Fall gilt:

$c=2^{\aleph _{0}}=\aleph _{1}$.

Totale Ordnung der Mächtigkeiten

Bei naiver Betrachtung der Schreibweise könnte man vermuten, dass für Mengen A und B mit |A| <= |B| und |B| <= |A| stets |A| = |B| gilt. Dass das tatsächlich so ist, wird vom folgenden Satz ausgesagt:

Cantor-Bernstein-Schröder-Theorem: Ist A höchstens gleichmächtig zu B und B höchstens gleichmächtig zu A, dann sind A und B gleichmächtig.

Fassen wir einige Eigenschaften der Mächtigkeiten zusammen:

• Es gilt stets |A| = |A| (nimm die Identität als Bijektion).
• Aus |A| <= |B| und |B| <= |A| folgt |A| = |B|.
• Aus |A| <= |B| und |B| <= |C| folgt |A| <= |C| (folgt sofort aus der Definition).

Damit ist gezeigt, dass die Kardinalzahlen total geordnet sind.

Größte Mächtigkeit

Wir haben die kleinste Mächtigkeit schon als die von N erkannt, gibt es nun eine größte Mächtigkeit? Das beantwortet der folgende Satz:

Für jede Menge A ist die Potenzmenge P(A) mächtiger als A.

Beweis: Dass |A| <= |P(A)| gilt, sieht man, indem man A bijektiv auf die einelementigen Teilmengen von P(A) abbildet. Der Beweis, dass keine Bijektion von A nach P(A) existiert, ist etwas trickreicher. Man betrachtet für eine widerspruchshalber angenommene Bijektion f: A -> P(A) die Menge

$M:=\{x\in A|x\not \in f(x)\}\in \mathrm {P} (A)$.

Da f als bijektiv vorausgesetzt ist, muss es ein x in A geben mit f(x) = M. Läge nun x in M, dann wäre nach Definition von M x nicht in f(x) = M. Läge x dagegen nicht in M, dann wäre x in f(x) = M, wieder nach der Definition von M. Damit haben wir einen Widerspruch erhalten, der zeigt, dass die angenommene Bijektion f nicht existieren kann.

Bestimmt man nun die Mächtigkeiten der Potenzmengen von Potenzmengen von Potenzmengen ..., dann sieht man, dass es unendlich viele Kardinalzahlen gibt, und keine mächtigste Menge existiert.