Formelsammlung Mathematik: Kardinalzahlen

↑ Formelsammlung Mathematik

Definitionen zur Mächtigkeit

Definition. Gleichmächtigkeit, Kardinalzahl.

Gibt es zwischen zwei Mengen $A,B$ eine Bijektion, so heißen die beiden Mengen gleichmächtig und man schreibt

$|A|=|B|$.

Gleichmächtigkeit ist eine Äquivalenzrelation. Die Äquivalenzklassen (bzw. ein anschaulich gewähltes Repräsentantensystem) nennt man Kardinalzahlen. Ist $A$ eine Menge, so notiert man mit $|A|$ die Kardinalzahl von $A$.

Definition. Höchstens gleichmächtig.

Gibt es eine Injektion $f\colon A\to B$, so nennt man A höchstens gleichmächtig zu B und man schreibt:

$|A|\leq |B|$.

Definition. Weniger mächtig.

Gibt es eine Injektion $f\colon A\to B$, aber keine Bijektion $g\colon A\to B$, nennt man A weniger mächtig als B und man schreibt:

$|A|<|B|$.

Definition. Endliche Menge.

Eine Menge M heißt endlich, wenn es eine natürliche Zahl $n\in \mathbb {N} _{0}$ gibt, so dass

$n=|M|.$

Andernfalls bezeichnet man M als unendlich.

Definition. Abzählbar unendliche Menge.

Eine Menge M heißt abzählbar unendlich, wenn $|M|=|\mathbb {N} |$ gilt.

Definition. Überabzählbare Menge.

Eine Menge M heißt überabzählbar, wenn $|\mathbb {N} |<|M|$ gilt.

Sätze zur Mächtigkeit

Satz von Cantor.

Jede Menge M ist weniger mächtig als ihre Potenzmenge:

$|M|<|2^{M}|.$

Satz von Cantor-Bernstein.

Ist A höchstens gleichmächtig zu B und B höchstens gleichmächtig zu A, dann sind A und B gleichmächtig. Kurz:

$|A|\leq |B|\land |B|\leq |A|\implies |A|=|B|.$

Gemäß den Definitionen der Relationen lautet der Satz wie folgt:

Gibt es eine Injektion $f\colon A\to B$ und eine Injektion $g\colon B\to A$, dann muss auch eine Bijektion $h\colon A\to B$ existieren.

Satz. Totalordnung der Kardinalzahlen.

Die Kardinalzahlen sind total geordnet, da die folgenden vier Axiome erfüllt sind.

Reflexivität. Es gilt:

$|A|\leq |A|.$

Antisymmetrie (Satz von Cantor-Bernstein). Es gilt:

$|A|\leq |B|\land |B|\leq |A|\implies |A|=|B|.$

Transitivität. Es gilt:

$|A|\leq |B|\land |B|\leq |C|\implies |A|\leq |C|.$

Totalität (Vergleichbarkeitssatz). Es gilt:

$|A|\leq |B|\lor |B|\leq |A|.$

Bemerkung:

1. Die Reflexivität ist trivial, weil es immer $\operatorname {id} _{A}\colon A\to A$ gibt, und id immer injektiv ist.
2. Das Reflexivitätsaxiom ist redundant, weil in der Totalität enthalten.
3. Die Transitivität folgt auch sofort aus der Definition, weil die Verkettung von zwei Injektionen wieder injektiv ist.

Weitere Regeln sind:

1. $A\subseteq B\implies |A|\leq |B|.$
2. Speziell gilt: Jede Teilmenge einer höchstens abzählbaren Menge ist auch höchstens abzählbar.
3. Jede Teilmenge einer endlichen Menge ist auch endlich.
4. Wenn $f\colon A\to B$ surjektiv ist, dann gilt $|B|\leq |A|$.
5. Aus $|A|=|B|$ folgt immer $|A|\leq |B|$, denn jede Bijektion ist auch injektiv.
6. Nach Definition gilt: $|A|<|B|\iff |A|\leq |B|\land |A|\neq |B|$.
7. Infolge dessen auch: $|A|\leq |B|\iff |A|<|B|\lor |A|=|B|$.
8. Nach den Axiomen gilt: $\neg (|A|\leq |B|)\iff |B|<|A|$.
9. Nach den Axiomen gilt: $\neg (|A|<|B|)\iff |B|\leq |A|$.
10. Die Relation $|A|<|B|$ erfüllt die Axiome einer strengen Totalordnung.

Mächtigkeit spezieller Mengen

Für jede natürliche Zahl n gilt:

$n<|\mathbb {N} |.$

Für jede natürliche Zahl m gilt:

$|\mathbb {N} |=|\mathbb {N} ^{m}|.$

Es gilt:

$|\mathbb {N} |=|\mathbb {Z} |=|\mathbb {Q} |=|\mathbb {A} |<|2^{\mathbb {N} }|=|\mathbb {T} |=|\mathbb {R} |=|\mathbb {C} |,$

wobei mit $\mathbb {A}$ die Menge der algebraischen Zahlen und mit $\mathbb {T}$ die Menge der transzendenten Zahlen gemeint ist.

Kardinalzahlarithmetik

Definition. Addition, Multiplikation und Potenzierung von Kardinalzahlen.

Die Summe von zwei Kardinalzahlen ist die Kardinalität der disjunkten Vereinigung von Repräsentanten:

$|A|+|B|:=|A\sqcup B|.$

Das Produkt von zwei Kardinalzahlen ist die Kardinalität des kartesischen Produktes von Repräsentanten:

$|A|\cdot |B|:=|A\times B|.$

Die Potenz von zwei Kardinalzahlen ist die Kardinalität der Menge der Abbildungen von einem Exponent-Repräsentanten zu einem Basis-Repräsentanten:

$|B|^{|A|}:=|B^{A}|.$