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. |
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.
|
|
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
(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. |
| 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 È
nÎN An'
höchstens abzählbar.
|
Denn wir definieren eine injektive Abbildung
f: È
nÎN An'
® N durch
f((an,i,n)) := s(1)+s(2)+...+s(n-1)+i. |
Unter obigen Voraussetzungen ist auch
È
nÎN An
höchstens abzählbar.
| Denn wir definieren eine injektive Abbildung g: È nÎN An ® È nÎN An' wie folgt: Für jedes x Î È nÎN 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 |