Siehe auch
Kardinalitäten
Mit Kardinalität oder Mächtigkeit einer Menge wird die „Größe“ dieser Menge gemeint, d. h. „wie viele“ Elemente sie hat.
Wann sind 2 Mengen „gleich groß“?
Bei einer endlichen Menge kann man einfach ihre Elemente zählen. Die Anzahl ihrer Elemente ist ihre Kardinalität.
Um festzustellen, welche von 2 endlichen Mengen größer ist, kann man auch Paare von Elementen aus Menge 1 und 2 bilden und diese aus den Mengen entfernen, bis eine der beiden Mengen leer ist. Jene Menge, die danach noch Elemente besitzt, ist die größere. Sind beide Mengen gleichzeitig leer geworden, sind sie gleich groß.
Die Elemente von unendlichen Mengen kann man nicht direkt zählen, aber die Paarbildung ist möglich:
2 Mengen sind „gleich groß“, wenn es eine umkehrbar eindeutige (bijektive) Funktion gibt, die jedes Element einer Menge genau einem Element der anderen Menge zuordnet, ohne dass Elemente übrig bleiben.
Diese Definition ist sowohl für endliche als auch unendliche Mengen geeignet. Statt „Die Mengen A und B sind gleich groß“ sagt man „sie haben die gleiche Kardinalität“ oder „sie sind gleich mächtig“ und schreibt
|A| = |B|.
Beispiel
Die natürlichen Zahlen sind gleich mächtig wie alle Quadratzahlen, obwohl letztere eine echte Teilmenge der ersteren sind. Die Funktion, die jeder natürlichen Zahl n die n-
Wann ist eine Menge „kleiner“ als eine andere?
Wenn bei der „Paarbildung“ (umkehrbar eindeutigen Funktion) Elemente übrig bleiben, dann können wir sicher sein, dass die Menge, deren Elemente übrig bleiben, nicht die kleinere von beiden sein kann. (Bei endlichen Mengen wissen wir, dass sie die größere ist, aber bei unendlichen Mengen kann es auch an einer schlechten Wahl der Paarbildungsfunktion liegen, wenn Elemente übrig bleiben. Z. B. im obigen Beispiel die Funktion, die jeder Quadratzahl dieselbe Zahl in der Menge aller natürlichen Zahlen zuordnet.) So wird definiert:
|A| ≤ |B|.
Das heißt also, dass es eine injektive Funktion von A nach B gibt. Oder auch: dass es eine bijektive Funktion von A auf eine Teilmenge von B gibt, nämlich die Bildmenge der injektiven Funktion, also B ohne die „übrig gebliebenen“ Elemente.
Ist sowohl |A| ≤ |B| als auch |B| ≤ |A|, dann ist |A| = |B| (Äquivalenzsatz von Cantor-
Ist |A| ≤ |B|, aber nicht |A| = |B|, dann hat A eine (echt) kleinere Kardinalität:
|A| < |B|.
(Das heißt, es gibt eine injektive, aber keine bijektive Funktion von A nach B.
Oder auch: Es gibt eine injektive Funktion von A nach B, aber keine injektive Funktion von B nach A.)
Was ist die Kardinalität?
Bisher haben wir definiert, wie man |A| und |B| vergleicht, aber was ist |A| allein? Das ist für unendliche Mengen gar nicht so leicht festzulegen. Naheliegend wäre, alle Mengen, die zu A gleich mächtig sind, in eine „Über“-
Die Lösung des Problems: Man definiert keine Äquivalenzklassen, aber für jede Kardinalität ein „Musterbeispiel“ (einen Repräsentanten). Das ist „von unten“ möglich, d. h. ohne Rückgriff auf die „Menge aller Mengen“. Diese „Musterbeispiele“ heißen Kardinale und werden durch Kardinalzahlen „nummeriert“. (Mathematisch sind Kardinale das Gleiche wie Kardinalzahlen. Man kann aber den Begriff Kardinalzahlen verwenden, wenn man nur mit der „Nummerierung“ rechnen will, und Kardinale, wenn man mit den „Beispiel-
Vorteil: Wenn man die Kardinalzahl |A| bestimmt, kann man die Mächtigkeit von A sofort mit allen anderen Mengen, deren Kardinalzahl man kennt, vergleichen. Man braucht nicht zwischen allen Mengen eine „Paarbildungs-
Andere Definition
Die Menge A ist höchstens so groß wie die Menge B, wenn es möglich ist, jedes Element von B mit einem Element von A zu paaren, ohne dass Elemente übrig bleiben, wobei Elemente von A mehrfach verwendet werden dürfen (d. h. es gibt eine surjektive Funktion von B auf A).
Wenn (wie üblich) das Auswahlaxiom angenommen wird, ist diese Definition gleichwertig zu der zuvor gegebenen (denn mit Hilfe des Auswahlaxioms kann man jede surjektive Funktion von A auf B umdrehen und eine injektive Funktion von B nach A gewinnen; eine injektive Funktion kann man sogar ohne Auswahlaxiom umdrehen).
Wenn das Auswahlaxiom nicht angenommen wird, ist das eine eigene, zusätzliche Vergleichsmöglichkeit für die Kardinalität von Mengen. Es gibt dann ein deutlich komplizierteres Bild, „was alles passieren kann“. Siehe
- Kardinalitäten wenn das Auswahlaxiom nicht gilt und als Beispiel dafür
Andere Schreibweisen
| A ≼ B | für |A| ≤ |B| |
| A ≺ B | für |A| < |B| |
| A ~ B | für |A| = |B| |
| #A | für |A| |
