Kurs:Analysis (Osnabrück 2014-2016)/Teil I/Vorlesung 10
- Mächtigkeiten
Zwei Kinder, die noch nicht zählen können, sitzen im Sandkasten und wollen wissen, wer von ihnen mehr Buddelsachen dabei hat. Sie lösen das Problem, indem beide gleichzeitig je eine Sache aus ihrem Besitz aus dem Sandkasten hinauswerfen, und dies so lange wiederholen, bis ein Kind keine Sachen mehr im Sandkasten hat. Wenn das andere Kind noch Sachen übrig hat, so hat dieses insgesamt mehr Buddelsachen, andernfalls haben sie gleichviel. Dies ist die Grundidee für den Begriff der gleichmächtigen Menge.
Zwei Mengen und heißen gleichmächtig, wenn es eine bijektive Abbildung
Es seien und zwei Mengen. Dann sind die folgenden Aussagen äquivalent.
- ist leer oder es gibt eine
surjektive Abbildung
- Es gibt eine
injektive Abbildung
. Wenn leer ist, so kann man die leere Abbildung nehmen. Es sei also und sei
surjektiv. Zu jedem gibt es ein mit . Wir wählen für jedes ein solches aus und definieren durch
Wegen
ist
injektiv.
. Es sei nun eine injektive Abbildung
gegeben. Diese induziert eine Bijektion zwischen und dem Bild von , sei diese Abbildung. Wenn leer ist, so sind wir fertig. Es sei also und sei ein fixiertes Element. Wir definieren
durch
Diese Abbildung ist wegen
surjektiv.
- Endliche Mengen
Die natürliche Zahl ist dabei nach Aufgabe 2.5 eindeutig bestimmt und heißt die Anzahl (oder die Kardinalität) der Menge. Sie wird mit oder mit bezeichnet. Die bijektive Abbildung
kann man eine Nummerierung der Menge nennen. Eine Menge besitzt also Elemente, wenn man sie mit den natürlichen Zahlen von bis durchnummerieren kann. Zwei endliche Mengen und , für die es eine Bijektion
gibt, besitzen die gleiche Anzahl. Dies beruht einfach darauf, dass diese Bijektion verknüpft mit der bijektiven Nummerierung wieder eine Bijektion ist. Eine Menge, die nicht endlich ist, für die es also keine Bijektion mit für kein gibt, heißt unendlich.
Es sei eine endliche Menge mit Elementen und eine endliche Menge mit Elementen. Es sei .
Dann gibt es keine injektive Abbildung
Wir nehmen an, dass es eine injektive Abbildung
gibt. Es sei das Bild von unter der Abbildung . Dann ergibt sich eine Bijektion
da sich die Injektivität überträgt und da eine Abbildung immer surjektiv auf ihr Bild ist. Daher haben und gleich viele Elemente. Nach Aufgabe 10.1 ist die Anzahl einer Teilmenge stets kleiner oder gleich der Anzahl der Menge. Also ist im Widerspruch zur Voraussetzung.
Die vorstehende Aussage heißt Schubfachprinzip (oder Taubenschlagprinzip). Es besagt, dass wenn man Tauben auf Plätze verteilt mit , dass dann in mindestens einem Platz mindestens zwei Tauben landen.
- Abzählbare Mengen
Durch den Mächtigkeitsbegriff wird eine Hierarchie auch in die Welt der unendlichen Mengen gebracht. Die zu den natürlichen Zahlen gleichmächtigen Mengen sind die „kleinsten“ unendlichen Mengen. Dies sind die sogenannten „abzählbar unendlichen“ Mengen.
Nicht abzählbare Mengen nennt man im Allgemeinen überabzählbar. Aufgrund von Lemma 10.2 ist die Abzählbarkeit von gleichbedeutend damit, dass es eine injektive Abbildung gibt. Beim Nachweis der Abzählbarkeit arbeitet man aber meistens mit der oben angegebenen Definition.
Endliche Mengen sind natürlich abzählbar. Die natürlichen Zahlen sind abzählbar unendlich.
Eine Menge ist genau dann abzählbar unendlich, wenn es eine Bijektion zwischen und gibt.
Es sei
eine surjektive Abbildung. Wir definieren induktiv eine streng wachsende Abbildung
derart, dass bijektiv ist. Wir setzen und konstruieren induktiv über die Eigenschaft, dass die kleinste natürliche Zahl ist, für die nicht zu
gehört. Eine solche Zahl gibt es immer, da andernfalls endlich wäre; also gibt es auch eine kleinste solche Zahl. Nach Konstruktion ist , d.h. ist streng wachsend. Da jedes die Eigenschaft
erfüllt, ist die Gesamtabbildung
injektiv.
Zum Nachweis der Surjektivität sei
.
Wegen der Surjektivität von ist die
Faser (also die Urbildmenge zu diesem Element)
nicht leer und daher gibt es auch ein kleinstes Element
mit
.
Da streng wachsend ist, gibt es nur endlich viele Zahlen
mit
.
Daher ist
und
.
D.h. insbesondere, dass alle abzählbar unendlichen Mengen gleichmächtig sind.
Seien und abzählbare Mengen.
Dann ist auch die Produktmenge abzählbar.
Insbesondere ist das Produkt abzählbar.
Wir beweisen zuerst den Zusatz. Die Abbildung
ist
injektiv,
da für jede positive natürliche Zahl die Zweierpotenz , die sie teilt, und der ungerade komplementäre Teiler eindeutig bestimmt sind
(das
Bild
der Abbildung ist ).
Daher ist die Produktmenge nach
Lemma 10.2
abzählbar.
Für den allgemeinen Fall seien abzählbare Mengen
und
gegeben.
Wenn eine davon leer ist, so ist auch die Produktmenge leer und somit abzählbar. Es seien also
und
nicht leer und seien
und
surjektive
Abbildungen. Dann ist auch die
Produktabbildung
surjektiv. Nach der Vorüberlegung gibt es eine surjektive Abbildung
sodass es insgesamt eine surjektive Abbildung
gibt.
Es sei eine abzählbare Indexmenge und zu jedem sei eine abzählbare Menge.
Dann ist auch die (disjunkte) Vereinigung[1] abzählbar.
Wir können annehmen, dass sämtliche nicht leer sind. Es gibt dann surjektive Abbildungen
Daraus konstruieren wir die Abbildung
die offensichtlich surjektiv ist. Nach Lemma 10.9 ist die Produktmenge abzählbar, also gilt das auch für das Bild unter , und dieses ist die Vereinigung.
Wir ziehen einige wichtige Konsequenzen über die Abzählbarkeit von Zahlenbereichen. Man beachte, dass die natürlichen Inklusionen
nicht bijektiv sind. Die Bijektionen, die es zwischen einerseits und
bzw.
andererseits aufgrund der folgenden Aussagen gibt, respektieren nicht die Rechenoperationen.
- Die Überabzählbarkeit der reellen Zahlen
Die Menge der reellen Zahlen
ist nicht abzählbar.
Nehmen wir an, die Menge der reellen Zahlen sei abzählbar, dann ist insbesondere auch das Einheitsintervall abzählbar. Es sei also
eine surjektive Abbildung. Wir betrachten die reellen Zahlen als Ziffernfolgen im Dreiersystem: Jede reelle Zahl besitzt eine eindeutig bestimmte Darstellung als Reihe
wobei die -te Nachkommaziffer ist und wobei nicht fast alle (das bedeutet alle bis auf endlich viele) Ziffern gleich sind (sonst hätte man keine Eindeutigkeit). Wir definieren nun eine reelle Zahl durch mit
Wir behaupten, dass diese Zahl nicht in der Aufzählung vorkommt. Für jedes ist nämlich
da sich nach Konstruktion von an der -ten Nachkommastelle unterscheidet. Also ist doch nicht surjektiv.
Ist jede überabzählbare Menge gleichmächtig zu ? Die Kontinuumshypothese behauptet, dass dies gilt. Diese Frage berührt die mengentheoretischen Grundlagen der Mathematik; es hängt nämlich von der gewählten Mengenlehre ab, ob dies gilt oder nicht, man kann es sich also aussuchen. Anders als beim Auswahlaxiom, ohne dessen Akzeptanz eine Vielzahl von mathematischen Schlüssen nicht möglich wäre und die Mathematik ziemlich anders aussehen wüde, ist es für praktische Zwecke unerheblich, wofür man sich entscheidet.
Mit einem ähnlichen (Diagonal)-Argument wie im Beweis zu Satz 10.13 kann man zeigen, dass die Potenzmenge einer Menge stets eine größere Mächtigkeit als die Menge besitzt.
Es sei eine Menge und ihre Potenzmenge.
Dann besitzt eine größere Mächtigkeit als .
Wir nehmen an, dass es eine surjektive Abbildung
gibt, und müssen dies zu einem Widerspruch führen. Dazu betrachten wir
Da dies eine Teilmenge von ist, muss es wegen der Surjektivität ein geben mit
Es gibt nun zwei Fälle, nämlich oder . Im ersten Fall ist also , und damit, nach der Definition von , auch , Widerspruch. Im zweiten Fall ist, wieder aufgrund der Definition von , , und das ist ebenfalls ein Widerspruch.
- Fußnoten
- ↑ Wenn die Teilmengen einer festen Obermenge sind, so ist die Vereinigung in dieser Menge zu nehmen und im Allgemeinen nicht disjunkt. Wenn es sich um Mengen handelt, die nichts miteinander zu tun haben, so ist mit Vereinigung die disjunkte Vereinigung gemeint.
<< | Kurs:Analysis (Osnabrück 2014-2016)/Teil I | >> |
---|