Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Kardinalzahlen und Abzählbarkeit

Wie vergleicht man die Größen von Mengen? Zwei Vorschulkinder können feststellen wer mehr Murmeln hat, indem sie versuchen Paare zu bilden. Hat A am Schluß alle verbraucht, während B noch Murmeln hat, dann hat B mehr (oder, die vorsichtige Version, die auch im Unendlichen gilt: B hat zumindest nicht weniger). Auch der elementare Aufteilalgorithmus ("Amal Dana, amal Lisa") basiert auf diesem Prinzip.

Definition: Zwei Mengen werden gleichmächtig genannt, wenn es eine bijektive Abbildung zwischen ihnen gibt.

Dies ist offenbar eine Äquivalenzrelation auf jeder gegebenen Menge von Mengen (Aufgepasst: Eine "Menge aller Mengen" gibt es nicht!), denn die Identität ist bijektiv, ist f bijektiv so existiert die Umkehrfunktion, die dann auch bijektiv ist, und die Komposition von bijektiven Abbildungen ist bijektiv.

Eine Menge enthält genau dann n N Elemente, falls sie zu der Menge {1,2,...,n} gleichmächtig ist.

Definition: Eine Menge B heißt mächtiger oder gleichmächtig als Menge A, wenn es eine injektive Abbildung von A in B gibt.
Diese Relation ist reflexiv (Identität) und transitiv (Komposition injektiver Abbildungen ist injektiv) aber nicht antisymmetrisch auf Mengen von Mengen. Aber es gilt:
Bernsteinscher Äquivalenzsatz: Gibt es eine injektive Abbildung f: A B und eine injektive Abbildung g: B A, so sind A und B gleichmächtig.
Beweis mit dem Fixpunktsatz von Knaster/Tarski:
Beweis mit dem unendlichen Heiratssatz:

Somit erhalten wir eine Ordnungsrelation, wenn wir gleichmächtige Mengen als "gleich" ansehen. Genauer:

Gegeben sei eine Menge M von Mengen.
  • Die Äquivalenzklassen bzgl. der Äquivalenzrelation "... und ... sind gleichmächtig" werden Kardinalzahlen genannt.
  • Die zur Menge M M gehörende Kardinalzahl wird mit |M| bezeichnet.
  • Für Kardinalzahlen A und B definieren wir A B falls B mächtiger oder gleichmächtiger als A ist, für ein (jedes) A A und B B
Dies ist eine Ordnungsrelation, sogar eine lineare.
Beweis: Die Ordnungseigenschaft ist klar, die Linearität etwas schwieriger zu beweisen: Seien zwei Mengen A und B gegeben, nach dem Wohlordnungssatz lassen sich beide wohlordnen. Diese beiden wohlgeordneten Mengen sind zu zwei Ordinalzahlen ordnungsisomorph (also insbesondere gleichmächtig), von denen (wegen der linearen Struktur der Ordinalzahlen) eine Teilmenge der anderen ist, also höchstens so mächtig wie die andere.

Statt mit injektiven Abbildungen hätte man auch mit surjektiven Abbildungen arbeiten können, denn es gilt:
Zu je zwei Mengen A und B gibt es genau dann eine injektive Abbildung von A in B wenn es eine surjektive Abbildung von B auf A gibt.

Aus A B folgt |A| |B|, aber falls B unendlich ist, kann durchaus |A| = |B| für echte Teilmenge A von B (d.h. A B) sein.

Man kann immer mächtigere Mengen finden:

Für jede Menge M gilt: Die Potenzmenge P(M) ist mächtiger als M. In Kardinalzahlen ausgedrückt: |M| |P(M)|, aber |M| |P(M)|.
Beweis: (1) Zuerst zeigen wir, daß beide Mengen nicht gleichmächtig sind, indem wir diese Annahme zu einem Widerspruch führen. Angenommen es gäbe also eine bijektive Abbildung f: M P(M). Die f(x) sind Teilmengen von M, die x enthalten oder nicht enthalten können. Wir versuchen eine Teilmenge A von M zu basteln, die sich von allen diesen Teilmengen f(x) unterscheidet. Wir definieren
A := {x M | x f(x) }.
Unter der Annahme der Bijektivität von f gibt es ein y M mit f(y) = A. Ist y f(y), dann gilt nach Konstruktion von A: y A. Ist y f(y), dann gilt nach Konstruktion von A: y A. Wir erhalten den Widerspruch.

(2) Andererseits gibt es eine injektive Abbildung f von M nach P(M): Wir setzen einfach f(x) = {x}. Also ist P(M) mächtiger als M.

Abzählbare Mengen

Definition: Eine Menge ist abzählbar wenn sie zur Menge N der natürlichen Zahlen gleichmächtig ist. Ist sie endlich oder abzählbar, so heisst sie höchstens abzählbar.

Disjunkte abzählbare Vereinigungen endlicher Mengen sind wieder höchstens abzählbar: Für jede natürliche Zahl n sei An eine endliche Menge An = {an,1, an,2, ... ,an,s(n)}. Diese Mengen werden künstlich disjunkt gemacht, indem wir die zu An gleichmächtige Mengen An' = {(an,1,n), (an,2,n), ... ,(an,s(n),n)} betrachten.
Dann ist nN An' höchstens abzählbar.

Denn wir definieren eine injektive Abbildung f: nN An' N durch
f((an,i,n)) := s(1)+s(2)+...+s(n-1)+i.

Unter obigen Voraussetzungen ist auch nN An höchstens abzählbar.
Denn wir definieren eine injektive Abbildung g: nN An nN An' wie folgt: Für jedes x nN An wählen wir ein n N und ein 1 i s(n) mit an,i = x. Dann definieren wir g(x) = (an,i,n). g ist offenbar injektiv.

Sind die Mengen A und B höchstens abzählbar, so ist auch A ×B höchstens abzählbar.
Insbesondere ist die Menge Q aller rationalen Zahlen abzählbar, da sie als Teilmenge von N × N aufgefasst werden kann.
Beweis: Seien f: A N und g: B N beide injektiv. Es gibt sehr viele Möglichkeiten A × B als (disjunkte) Vereinigung abzählbar vieler endlicher Mengen darzustellen. Wir können etwa definieren Cn := {(a,b) A × B/ f(a) n und g(b) n}, (oder auch Dn := {(a,b) A × B/ f(a) + g(b) = n} --- dies kommt Cantor's ursprünglich verwendeter "erster Diagonalmethode" recht nahe). Jedenfalls sind alle diese Mengen Cn (bzw. Dn) endlich, und A × B ist Vereinigung aller dieser Cn (und auch Vereinigung aller dieser Dn). Dann benutzen wir obiges Lemma.

Mit einem "2. Diagonalbeweis" ähnlich wie in obigem Potenzmengensatz beweist man:

Cantor 1874: Die Menge der reellen Zahlen ist nicht abzählbar.
Beweis

Rechnen mit Kardinalzahlen


Lesen Sie doch mal den interessanten Artikel über die Anfänge der Mengenlehre.
Erich Prisner
erstellt im Mai 2000.