Mächtigkeit (Mathematik)

Grundidee der Mächtigkeit

Die Mächtigkeit oder Kardinalität einer Menge beschreibt, wie viele Elemente sie enthält. Bei endlichen Mengen ist sie gleich der Anzahl der Elemente und wird als natürliche Zahl n ∈ ℕ₀ angegeben; 0 ist eingeschlossen. Allgemein notiert man die Mächtigkeit einer Menge A als |A|. Der Begriff erweitert die gewöhnliche Anzahl von Elementen auf unendliche Mengen.

Beispiele sind |{1, 3, 7, 21}| = 4, die Menge der fünf platonischen Körper mit |B| = 5 und eine Menge mit sechs angegebenen Farben mit |C| = 6. Für unendliche Mengen ist zur Definition ein theoretischer Apparat der Mengenlehre erforderlich. Die folgenden Begriffe und Regeln gelten jedoch für endliche und unendliche Mengen.

Gleichmächtigkeit und Kardinalzahlen

Zwei Mengen A und B heißen gleichmächtig, wenn es eine Bijektion f: A → B gibt, also eine umkehrbar eindeutige Abbildung, die jedes Element der einen Menge genau einem Element der anderen Menge zuordnet. Man schreibt |A| = |B| oder A ∼ B. Die Umkehrfunktion einer Bijektion ist ebenfalls eine Bijektion. Daher ist die Gleichmächtigkeitsrelation symmetrisch; insgesamt ist sie eine Äquivalenzrelation.

Bei endlichen Mengen bedeutet Gleichmächtigkeit genau, dass beide Mengen gleich viele Elemente haben. Unendliche Mengen sind dadurch gekennzeichnet, dass sie gleichmächtig zu einer ihrer echten Teilmengen sein können. Eine Menge heißt abzählbar, wenn sie gleichmächtig zu ℕ oder zu einer Teilmenge von ℕ ist und somit mit natürlichen Zahlen einschließlich 0 abgezählt werden kann. Mitunter wird „abzählbar“ nur für „abzählbar unendlich“, also gleichmächtig zu ℕ, verwendet; für die weitere Bedeutung sagt man dann „höchstens abzählbar“.

Die Kardinalzahl einer Menge ist ihre Äquivalenzklasse bezüglich der Gleichmächtigkeit. Unter Annahme des Auswahlaxioms folgt aus dem Wohlordnungssatz, dass jede Menge gleichmächtig zu einer wohlgeordneten Menge ist. Ihre Kardinalzahl kann dadurch als die kleinste mit ihr gleichmächtige Ordinalzahl aufgefasst werden. Die unendlichen Kardinalzahlen werden durch die Aleph-Funktion bezeichnet: Für jede Menge A gibt es genau ein aleph 𝖭ℵᵢ mit |A| = ℵᵢ. Die Kardinalzahl einer endlichen Menge mit n Elementen wird mit n gleichgesetzt.

Wichtige Gleichmächtigkeiten sind ℕ ∼ ℤ ∼ ℚ sowie ℝ ∼ (0, 1) ∼ C ∼ 𝒫(ℕ), wobei C die Cantor-Menge ist. Dagegen ist ℝ mächtiger als ℕ; die reellen Zahlen sind also überabzählbar. Es gibt unendlich viele verschiedene Kardinalzahlen.

Vergleich und Ordnung von Mächtigkeiten

Für Mengen A und B gilt |A| ≤ |B|, wenn es eine Bijektion von A auf eine Teilmenge von B gibt. Dann heißt A höchstens gleichmächtig zu B. Gibt es diese Bijektion, aber keine Bijektion von B auf eine Teilmenge von A, so ist A weniger mächtig und B mächtiger als A. Man schreibt dann |A| < |B| beziehungsweise |B| > |A|. Dabei gilt |A| < |B| genau dann, wenn |A| ≤ |B| und |A| ≠ |B|.

Unter Annahme des Auswahlaxioms sind je zwei Mengen vergleichbar: Für alle A und B gilt |A| ≤ |B| oder |B| ≤ |A|. Außerdem ist jede abzählbare Menge entweder endlich oder gleichmächtig zu ℕ, und jede unendliche Menge enthält eine zu ℕ gleichmächtige Teilmenge. Deshalb ist |ℕ| die kleinste unendliche Kardinalzahl; sie wird mit ℵ₀ bezeichnet: ℵ₀ := |ℕ|.

Das Cantor-Bernstein-Schröder-Theorem besagt: Sind A und B jeweils höchstens gleichmächtig zueinander, also |A| ≤ |B| und |B| ≤ |A|, dann sind sie gleichmächtig. Für Mächtigkeiten gelten außerdem Reflexivität, Transitivität und die durch das Auswahlaxiom gewährleistete Vergleichbarkeit. Damit sind die Kardinalzahlen total geordnet.

Die Kontinuumhypothese behauptet, dass es keine Menge gibt, deren Mächtigkeit zwischen der von ℕ und der von ℝ liegt. Sie besagt, dass |ℝ| = |𝒫(ℕ)| = 2^ℵ₀ die zweitkleinste unendliche Kardinalzahl ℵ₁ ist. Weder die Kontinuumhypothese noch ihre Verneinung lässt sich aus den üblichen Axiomensystemen, etwa der Zermelo-Fraenkel-Mengenlehre mit Auswahlaxiom, herleiten.

Rechenregeln für endliche Mengen

Für endliche Mengen M, N und N₁, …, Nₖ gelten folgende Regeln:

• Bijektionsregel: M ist genau dann bijektiv auf N abbildbar, wenn |M| = |N|.

• Summenregel: Sind M und N disjunkt, also M ∩ N = ∅, dann gilt |M ∪ N| = |M| + |N|. Allgemein gilt |M ∪ N| + |M ∩ N| = |M| + |N|. Für mehrere Mengen führt dies zum Prinzip von Inklusion und Exklusion.

• Differenzenregel: Aus M ⊆ N folgt |N \ M| = |N| − |M|.

• Produktregel: Für das kartesische Produkt gilt |M × N| = |M| · |N|.

• Quotientenregel: Ist M eine disjunkte Vereinigung M = N₁ ⊔ ⋯ ⊔ Nₖ und haben alle Nᵢ dieselbe positive Mächtigkeit n, dann gilt |M| = k · n beziehungsweise k = |M|/n.

• Subadditivität: Für endlich viele Mengen gilt |⋃ᵢ₌₁ᵏ Nᵢ| ≤ ∑ᵢ₌₁ᵏ |Nᵢ|. Sind die Mengen paarweise disjunkt, gilt Gleichheit.

• Inklusion und Exklusion: Die Mächtigkeit einer Vereinigung wird als alternierende Summe der Mächtigkeiten aller verschiedenstufigen Durchschnitte berechnet: |⋃ᵢ₌₁ᵏ Nᵢ| = ∑∅ ≠ I ⊆ {1,…,k} (−1)^{|I|+1} |⋂ᵢ∈I Nᵢ|.

• Potenzregel: Nᴹ bezeichnet die Menge aller Abbildungen von M nach N. Dann gilt |Nᴹ| = |N|^{|M|}.

Beispielsweise haben M = {1, 2, 3} und N = {1, 3, 5, 7} keine Bijektion, ihre Vereinigung hat aber die Mächtigkeit 5 und ihr kartesisches Produkt die Mächtigkeit 12. Für M = N = {1, 2, 3, 4} besteht eine Bijektion durch die Identität, die Differenz hat Mächtigkeit 0 und das kartesische Produkt Mächtigkeit 16. Die vier ein-elementigen, paarweise disjunkten Mengen N₁, …, N₄ vereinigen sich zu einer Menge der Mächtigkeit 4.

Potenzmenge und fehlende größte Mächtigkeit

Die Potenzmenge 𝒫(A) ist die Menge aller Teilmengen von A. Nach dem Satz von Cantor ist sie für jede Menge A echt mächtiger als A. Daher gibt es keine Menge größter Mächtigkeit.

Für jede Menge gilt |𝒫(A)| = 2^{|A|}. Hat eine endliche Menge A die Mächtigkeit n, besitzt ihre Potenzmenge genau 2ⁿ Elemente. Der Grund ist, dass für jedes der n Elemente unabhängig entschieden wird, ob es in einer ausgewählten Teilmenge enthalten ist oder nicht; es gibt jeweils zwei Möglichkeiten.

Wendet man die Potenzmengenbildung auf eine unendliche Menge wiederholt an, entstehen immer größere Mächtigkeiten. Daraus folgt, dass es unendlich viele unendliche Kardinalzahlen gibt und keine größte Kardinalität existiert.