Mächtigkeit (Mathematik)

Aus AnthroWiki
Wechseln zu: Navigation, Suche

In der Mathematik verwendet man den aus der Mengenlehre von Georg Cantor 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 ist die Mächtigkeit gleich der Anzahl der Elemente der Menge, das ist eine natürliche Zahl einschließlich der Null. 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.

Mächtigkeit bei endlichen Mengen

Bei einer endlichen Menge LaTeX: X bezeichnet die Mächtigkeit die Anzahl der Elemente von LaTeX: X. Man notiert die Mächtigkeit von LaTeX: X durch LaTeX: |X| oder alternativ mit voranstehendem Doppelkreuz: LaTeX: \#X.

Beispiele:

LaTeX: A = \{1, 3, 7, 21\}\Rightarrow |A| = 4
LaTeX: B = \{\mbox{Tetraeder, Hexaeder, Oktaeder, Dodekaeder, Ikosaeder}\} \Rightarrow |B| = 5
LaTeX: C = \{\mbox{rot, gelb, blau, orange, violett, schwarz}\} \Rightarrow |C| = 6

Die Potenzmenge LaTeX: \mathcal P(X) einer endlichen Menge LaTeX: X hat genau LaTeX: 2^{|X|} Elemente: Die Wahl einer Teilmenge entspricht den LaTeX: |X| unabhängigen Wahlen zwischen den zwei Möglichkeiten, ob ein bestimmtes Element von LaTeX: X in der Teilmenge liegen soll oder nicht.

Gleichmächtigkeit, Mächtigkeit

Der Vergleich der Mächtigkeit zweier Mengen

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

Eine Menge LaTeX: A heißt gleichmächtig (bei Cantor: äquivalent) zu einer Menge LaTeX: B, wenn es eine Bijektion LaTeX: f\colon A \to B gibt. Man schreibt dann LaTeX: |A| = |B| oder LaTeX: A \;\tilde{}\; B.[1][2][3] Die Gleichmächtigkeit LaTeX: \tilde{} ist eine Äquivalenzrelation auf der Klasse aller Mengen, deren Äquivalenzklassen (bis auf die der Leermenge) echte Klassen sind. Näheres siehe unten (§Kardinalzahlen) und Kardinalzahlen §Definition.

Ist LaTeX: A gleichmächtig zu LaTeX: B und LaTeX: f eine Bijektion zwischen LaTeX: A und LaTeX: B, dann ist auch die Umkehrfunktion von LaTeX: f eine Bijektion, also ist auch LaTeX: B gleichmächtig zu LaTeX: A. Endliche Mengen sind genau dann gleichmächtig, wenn sie gleich viele Elemente haben. Unendliche Mengen sind Mengen, die zu sich gleichmächtige echte Teilmengen besitzen.

Man nennt eine Menge, die gleichmächtig zur unendlichen Menge LaTeX: \Bbb N der natürlichen Zahlen oder einer Teilmenge von ihr ist, die also mit natürlichen Zahlen (einschließlich 0) „abgezählt“ werden kann, eine abzählbare Menge.

Bisweilen versteht man auch abzählbar nur im Sinne von abzählbar unendlich (= gleichmächtig zu LaTeX: \Bbb N), und spricht dann an Stelle von abzählbar im Sinne der oben zuerst eingeführten Definition von höchstens abzählbar, die die Formulierung vieler Beweise etwas einfacher macht, und eher dem deutschen Sprachgebrauch entspricht.

Besondere Ergebnisse:

  1. Gleichmächtig sind: LaTeX: \Bbb N, LaTeX: \Bbb Z und LaTeX: \Bbb Q (also die Mengen der natürlichen, der ganzen und der rationalen Zahlen).
  2. Gleichmächtig sind: LaTeX: \Bbb R, LaTeX: \left]0,1\right[, LaTeX: C und LaTeX: \mathcal P(\Bbb N), wobei LaTeX: C die Cantor-Menge ist.
  3. Die Menge LaTeX: \Bbb R der reellen Zahlen ist mächtiger als LaTeX: \Bbb N (also überabzählbar).

Kardinalzahlen

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

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

Aus technischen Gründen muss man aber ein geeignetes Repräsentantensystem finden: Indem man zeigt, dass jede Menge gleichmächtig zu einer wohlgeordneten Menge ist (dies ist die Aussage des Wohlordnungssatzes), kann man jede Kardinalzahl mit der kleinsten ihr gleichmächtigen Ordinalzahl gleichsetzen.

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

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

LaTeX: |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, so ist etwa die Menge der natürlichen Zahlen nicht gleichmächtig zur Menge der reellen Zahlen. Das kann man zum Beispiel mit dem so genannten „Cantorschen Diagonalbeweis“ zeigen, siehe dazu den Artikel überabzählbar.

Weiter unten wird gezeigt, dass es unendlich viele verschiedene Kardinalzahlen gibt. Cantor selbst zeigte mit der ersten Cantorschen Antinomie, dass die Kardinalzahlen eine echte Klasse bilden.

Vergleich der Mächtigkeit

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

  • Wenn es eine Bijektion LaTeX: f von LaTeX: A auf eine Teilmenge von LaTeX: B gibt, dann heißt LaTeX: A höchstens gleichmächtig zu LaTeX: B. Man schreibt dann LaTeX: |A| \leq |B|.
  • Wenn es eine Bijektion LaTeX: f von LaTeX: A auf eine Teilmenge von LaTeX: B gibt, aber keine Bijektion von LaTeX: A nach LaTeX: B existiert, dann heißt LaTeX: A weniger mächtig als LaTeX: B und LaTeX: B mächtiger als LaTeX: A. Man schreibt dann LaTeX: |A| < |B|. Offenbar gilt LaTeX: |A| < |B| genau dann, wenn LaTeX: |A| \leq |B|, aber nicht LaTeX: |A| = |B| ist.

Nun stellt sich aber die Frage nach der Vergleichbarkeit zweier beliebiger Mengen, ob also die bloße Eigenschaft, eine Menge zu sein, eine solche Vergleichsmöglichkeit impliziert. Und tatsächlich kann man für zwei beliebige Mengen im Allgemeinen zeigen (unter Verwendung des Auswahlaxioms):

Des Weiteren kann man zeigen, dass jede abzählbare Menge entweder endlich oder gleichmächtig zu LaTeX: \Bbb N ist. Außerdem kann man zeigen, dass jede unendliche Menge eine zu LaTeX: \Bbb N gleichmächtige Teilmenge enthält.

Damit ist die Mächtigkeit von LaTeX: \Bbb N die kleinste unendliche Kardinalzahl. Man bezeichnet sie mit LaTeX: \aleph_0:

LaTeX: \aleph_0 := |\Bbb N|.

Die Kontinuumhypothese (CH) besagt, dass es keine Menge gibt, die mächtiger ist als LaTeX: \Bbb N, aber weniger mächtig als LaTeX: \R . Wie der Name jedoch schon vermuten lässt, ist dies kein Satz in dem Sinne, dass er sich beweisen lässt. Weder die Kontinuumhypothese noch ihre Verneinung lässt sich aus den üblichen Axiomensystemen herleiten, zum Beispiel der Zermelo-Fraenkel-Mengenlehre mit Auswahlaxiom. Die Kontinuumhypothese besagt also, dass LaTeX: |\Bbb R| = |\mathcal P(\Bbb N)| = 2^{\aleph_0} die zweitkleinste unendliche Kardinalzahl LaTeX: \aleph_1 ist.

Totale Ordnung der Mächtigkeiten

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

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

Fassen wir einige Eigenschaften der Mächtigkeiten zusammen:

  • Es gilt stets LaTeX: |A| = |A| (man nehme die Identität als Bijektion).
  • Aus LaTeX: |A| \leq |B| und LaTeX: |B| \leq |A| folgt LaTeX: |A| = |B|.
  • Aus LaTeX: |A| \leq |B| und LaTeX: |B| \leq |C| folgt LaTeX: |A| \leq |C| (folgt sofort aus der Definition).
  • Für zwei Mengen LaTeX: A und LaTeX: B gilt stets LaTeX: |A| \leq |B| oder LaTeX: |B| \leq |A| (das ist äquivalent zum Auswahlaxiom).

Damit ist gezeigt, dass die Kardinalzahlen total geordnet sind.

Rechenregeln bei endlichen Kardinalitäten

Es seien LaTeX: M , N sowie LaTeX: N_1, \ldots, N_k endliche Mengen. Dann gelten folgende Regeln:

  • Bijektions- oder Isomorphieregel
    LaTeX: M ist bijektiv auf LaTeX: N abbildbar LaTeX: \Leftrightarrow LaTeX: |M| = |N|.
  • Summenregel
    LaTeX: M \cap N = \emptyset \Leftrightarrow |M \cup N| = |M| + |N|
    Allgemein gilt LaTeX: |M \cup N| + |M \cap N| = |M| + |N|.
    Eine weitere Verallgemeinerung der Summenregel auf endlich viele endliche Menge ist das Prinzip von Inklusion und Exklusion.
  • Differenzenregel
    LaTeX: M \subseteq N \Leftrightarrow |N \setminus M| = |N| - |M|
  • Produktregel
    LaTeX: |M \times N| = |M| \cdot |N|
  • Quotientenregel
    Ist LaTeX: M = N_1 \dot\cup \ldots \dot\cup N_k und gilt LaTeX: \forall i : |N_i| = n > 0, so folgt LaTeX: k = \tfrac{|M|}{n} bzw. LaTeX: |M| = k \cdot n
  • Subadditivität von Mengen
    LaTeX: \Big|\bigcup_{i=1}^{k} N_i\Big| \leq \sum_{i=1}^{k}|N_i|
    Falls die LaTeX: N_i paarweise disjunkt sind, so gilt die Gleichheit: LaTeX: \textstyle |\bigcup_{i=1}^k N_i| = \sum_{i=1}^k|N_i|.
    Das heißt also, dass bei disjunkten Mengen die Anzahl der Elemente in der Vereinigung der Mengen LaTeX: N_i gleich der Summe der einzelnen Anzahlen von Elementen in jeder dieser Mengen ist.
  • Potenzregel
    Bezeichnet LaTeX: N^M die Menge aller Abbildungen LaTeX: f \colon M \to N, dann gilt LaTeX: |N^M| = |N|^{|M|}.

Beispiele

LaTeX: M = \{1,2,3\} und LaTeX: N = \{1,3,5,7\}. Dann

  • existiert keine bijektive Abbildung zwischen LaTeX: M und LaTeX: N,
  • ist LaTeX: |M \cup N| = |\{1,2,3,5,7\}| = 5,
  • lässt sich die Mächtigkeit der Differenz nicht mit obigem Satz bestimmen,
  • beträgt die Mächtigkeit des kartesischen Produkts LaTeX: |M| \cdot |N| = |\{(1,1); (1,3); \ldots\}| = 12.

In einem weiteren Beispiel sei LaTeX: M = \{1,2,3,4\} und LaTeX: N_1 = \{1\}, N_2 = \{2\}, N_3 = \{3\}, N_4 = \{4\}, N = \{1,2,3,4\}. Dann

  • existieren bijektive Abbildungen (identische Abbildung) zwischen den beiden Mengen LaTeX: M und LaTeX: N,
  • ist LaTeX: |M \cup N| = |N| = 4, da die beiden Mengen identisch sind,
  • ist LaTeX: M eine Teilmenge von LaTeX: N und somit gilt: LaTeX: |N \setminus M| = |N| - |M| = 0,
  • die Mächtigkeit des kartesischen Produkts beträgt LaTeX: 16 und
  • da LaTeX: n = |N_1| = \ldots = |N_4| = 1 erhalten wir LaTeX: k = 4 bzw. LaTeX: |M| = 4 \cdot 1 = 4

Mächtigkeit der Potenzmenge, größte Mächtigkeit

Die Frage nach der größten Mächtigkeit einer Menge beantwortet der Satz von Cantor:

Für jede Menge LaTeX: A ist die Potenzmenge LaTeX: \mathcal{P}(A) mächtiger als LaTeX: A.

Für die Mächtigkeit von LaTeX: \mathcal{P}(A) gibt es auch folgende Schreibweise:

LaTeX: |\mathcal{P}(A)| = 2^{|A|}

Zu beachten ist, dass der entsprechende Ausdruck für unendliche Ordinalzahlen einen anderen Wert liefert, und z. B. LaTeX: 2^{|\N|} nicht als ein „Grenzwert“ einer Folge LaTeX: (2^n) angesehen werden kann.

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

Siehe auch

Literatur

  •  Erich Kamke: Mengenlehre (= Sammlung Göschen). De Gruyter, Berlin 1928.
  •  Oliver Deiser: Einführung in die Mengenlehre: Die Mengenlehre Georg Cantors und ihre Axiomatisierung durch Ernst Zermelo. 3. Auflage. Springer, Berlin/Heidelberg 2010, ISBN 978-3-642-01444-4, doi:10.1007/978-3-642-01445-1.
  • Heinz-Dieter Ebbinghaus: Einführung in die Mengenlehre. Mit Aufgaben und Lösungshinweisen. 4. Auflage. Spektrum Akademischer Verlag, Heidelberg 2003, ISBN 3-8274-1411-3.
  • Andreas Bartholomé, Josef Rung, Hans Kern: Zahlentheorie für Einsteiger: Eine Einführung für Schüler, Lehrer, Studierende und andere Interessierte. 7., aktualisierte Auflage. Vieweg+Teubner, Wiesbaden 2010, ISBN 978-3-8348-9650-6.

Weblinks

Einzelnachweise

  1.  Dieter Klaua: Mengenlehre. De-Gruyter-Lehrbuch. de Gruyter, Berlin, New York 1. Oktober 1979, ISBN 3-11-007726-4. Hier S. 75, Definition 16, Teil1 Definition 16, Teil2
  2.  H. König: Entwurf und Strukturtheorie von Steuerungen für Fertigungseinrichtungen (= ISW Forschung und Praxis). Springer-Verlag, Berlin / Heidelberg 1976, ISBN 3-540-07669-7, S. 15–17, doi:10.1007/978-3-642-81027-5_1. Hier: Seite 21
  3. Тhοmas Stеιnfеld: Gleichmächtigkeit auf Mathpedia


Dieser Artikel basiert (teilweise) auf dem Artikel Mächtigkeit (Mathematik) aus der freien Enzyklopädie Wikipedia und steht unter der Lizenz Creative Commons Attribution/Share Alike. In der Wikipedia ist eine Liste der Autoren verfügbar.