Mengentheorie/Abzählbarkeit/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Eine Menge heißt abzählbar, wenn sie leer ist oder wenn es eine surjektive Abbildung

gibt.

Nicht abzählbare Mengen nennt man im Allgemeinen überabzählbar. Aufgrund von Fakt 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.


Definition  

Eine Menge heißt abzählbar unendlich, wenn sie abzählbar, aber nicht endlich ist.



Lemma  

Eine Menge ist genau dann abzählbar unendlich, wenn es eine Bijektion zwischen und gibt.

Beweis  

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 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.




Lemma  

Seien und abzählbare Mengen.

Dann ist auch die Produktmenge abzählbar.

Insbesondere ist das Produkt abzählbar.

Beweis  

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 Fakt 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. Seien also und nicht leer und seien und zwei surjektive Abbildungen. Dann ist auch die Produktabbildung

surjektiv. Nach der Vorüberlegung gibt es eine surjektive Abbildung

so dass es insgesamt eine surjektive Abbildung gibt.




Lemma  

Es sei eine abzählbare Indexmenge und zu jedem sei eine abzählbare Menge.

Dann ist auch die (disjunkte) Vereinigung abzählbar.

Beweis  

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 Fakt 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.


Lemma

Die Menge der ganzen Zahlen

ist abzählbar.

Beweis

Siehe Aufgabe.


Die Abzählbarkeit der positiven rationalen Zahlen.



Satz

Die Menge der rationalen Zahlen

ist abzählbar.

Beweis

Siehe Aufgabe.