Mengenlehre und mathematische Logik

Kardinalitäten / Kardinalzahlen

Wir sagen, zwei Mengen x, y sind gleichmächtig (haben die gleiche Kardinalität) genau dann, wenn es eine Bijektion zwischen ihnen gibt ($x \thicksim y$). $\thicksim$ ist offensichtlich eine Äquivalenzrelation.

Eine Menge x ist von kleinerer oder gleicher Kardinalität als eine Menge y gdw. es eine Injektion von x nach y gibt ($card(x) \le card(y)$). Hierdurch ist offenbar eine partielle Ordnung auf obigen Äquivalenzklassen gegeben. Unter Choice ist diese Ordnung total. In diesem Fall benutzt man eine echte Teilklasse der Ordinalzahlen (die Kardinalzahlen) zur Bezeichnung der Äquivalenzklassen.

Boris 'pi' Piwinger <gro.ebeted|41.3#gro.ebeted|41.3>

Unendliche Mengen und Cantors Diagonalargumente

Wir nennen eine Menge A (Dedekind-)unendlich, wenn es eine echte Teilmenge von A gibt, die zu A gleichmächtig ist. Eine Menge heißt endlich, wenn sie nicht unendlich ist.

Die ,,kleinste" unendliche Menge ist die Menge $\mathbb{N}$ der natürlichen Zahlen. Eine Menge, die zu $\mathbb{N}$ gleichmächtig ist, heißt abzählbar unendlich. Eine unendliche Menge, die nicht zu $\mathbb{N}$ gleichmächtig ist, heißt überabzählbar.

Cantor bewies Ende des 19. Jahrhunderts, dass die Menge der rationalen Zahlen abzählbar unendlich ist. Den Kern seines Beweises nennt man seitdem Cantors Erstes Diagonalargument:

$p/q$ 1 2 3 4 5
1 1/1 1/2 1/3 1/4 1/5
2 2/1 2/2 2/3 2/4 2/5
3 3/1 3/2 3/3 3/4 3/5
4 4/1 4/2 4/3 4/4 4/5
5 5/1 5/2 5/3 5/4 5/5
.
1 2 6 7 15
3 5 8 14 17
4 9 13 18
10 12 19
11 20

Die beiden Tabellen ,,übereinandergelegt" ergeben ein Zählschema, bei dem alle positiven rationalen Zahlen in eine unendliche Folge ,,gesteckt" werden. (Dass hier einige rationale Zahlen mehrfach auftreten (1/1=2/2=3/3 usw.), ändert nichts an der Gültigkeit des Argumentes; man kann sie einfach ,,überspringen".)

Damit ist die Menge $\mathbb{Q}^+$ der positiven rationalen Zahlen abzählbar unendlich. Dass ganz $\mathbb{Q}$ abzählbar ist, kann man jetzt einfach beweisen, zum Beispiel durch ,,Basteln" einer neuen Folge, wo man die $\mathbb{Q}^+$-Folge in die geraden Folgenglieder ,,steckt", die Zahl 0 ins erste Folgenglied, und die ungeraden Folgenglieder, die jetzt noch ,,leer" sind, mit dem Negativen des unmittelbar vorhergehenden Folgengliedes ,,füllt".

Cantors Zweites Diagonalargument ist der Kern des Beweises dafür, dass die Menge der reellen Zahlen überabzählbar ist. Es beweist, dass das (reelle) offene Intervall ]0,1[ überabzählbar ist:

Jede reelle Zahl in diesem Intervall lässt sich (in Dezimaldarstellung) als $0,p_1p_2...p_n...$ schreiben (hier ist auch der Fall eingeschlossen, dass nach einer gewissen Stelle nur noch Nullen auftreten). Angenommen die Menge der Zahlen im Intervall wäre abzählbar, dann ließen sich alle diese Zahlen auf folgende Art und Weise in eine Folge ,,packen":

$\displaystyle a_1 = 0 , p_{11} p_{12} p_{13} p_{14} \ldots$

$\displaystyle a_2 = 0 , p_{21} p_{22} p_{23} p_{24} \ldots$

$\displaystyle a_3 = 0 , p_{31} p_{32} p_{33} p_{34} \ldots$

$\displaystyle a_4 = 0 , p_{41} p_{42} p_{43} p_{44} \ldots$

$\displaystyle \ldots$

Wählt man sich nun eine Zahl $d=0,d_1d_2...d_n...$ (manchmal ,,Diagonalzahl" genannt), so dass immer $d_n$ ungleich $p_{nn}$ (und ungleich 9) ist, dann ist d von allen Zahlen der Folge verschieden. Da d aber auch im Intervall ]0,1[ liegt, ist dies ein Widerspruch zur Annahme, dass wir alle Zahlen dieses Intervalls in der Folge aufgezählt hätten.

Damit ist das Intervall ]0,1[ überabzählbar. Dass es zur Menge $\mathbb{R}$ der reellen Zahlen gleichmächtig ist, beweist man dann ziemlich leicht, und damit ist $\mathbb{R}$ überabzählbar.

Ulrich Fahrenberg <kd.cua.htam|ilu#kd.cua.htam|ilu>

Notwendig, hinreichend

Was bedeutet es, wenn eine Bedingung ,,notwendig" bzw. ,,hinreichend" ist?

A $\Rightarrow$ B (A impliziert B): A heißt hinreichend für B, B heißt notwendig für A.

Wenn es regnet, sind Wolken am Himmel. Es regnet $\Rightarrow$ Wolken sind am Himmel.

Regen reicht aus, um sagen zu können, dass Wolken am Himmel sind. Wolken am Himmel sind notwendig, dass es regnen kann.

Andererseits gilt die Umkehrung nicht allgemein:

Wolken am Himmel impliziert noch lange nicht Regen. Und Regen ist daher auch nicht notwendig für Wolken, denn Wolken können auch ohne Regen am Himmel sein.

Andreas Slateff <ta.yawten|ffetals#ta.yawten|ffetals>

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-NoDerivs 3.0 License