Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Abzählbar aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Abzählbarkeit

Eine Menge $A$ bezeichnet man als abzählbar unendlich, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen_Zahlen $\backslash mathbb\{N\}$. Zu den höchstens abzählbaren zählen auch kleinere, also endliche Mengen. Der Begriff abzählbar kann beides bedeuten und muss von Fall zu Fall definiert werden. In diesem Artikel bedeutet er abzählbar unendlich.

In diesem Sinne bedeutet die Abzählbarkeit der Menge $A$, dass es eine Bijektion von den natürlichen Zahlen auf die Menge gibt, das heißt, dass die Menge durchnummeriert werden kann.

Beispiele abzählbar unendlicher Mengen

Natürliche Zahlen

Die Menge der natürlichen_Zahlen $\backslash mathbb\{N\}$ ist per Definition abzählbar, da sie dieselbe Mächtigkeit wie sie selbst besitzt.

Primzahlen

Die Menge der Primzahlen $\backslash mathbb\{P\}$ ist ebenfalls abzählbar, da es unendlich viele gibt und diese durchnummeriert werden können.

Ganze Zahlen

Die Menge der Teilmengen_als_auch_Obermengen dieselbe Mächtigkeit besitzen können, im Gegensatz zu endlichen_Mengen.

Paare natürlicher Zahlen

Auch die Menge aller Paare $(i,j)\backslash in\backslash mathbb\{N\}\; \backslash times\; \backslash mathbb\{N\}$ von zwei natürlichen Zahlen ist abzählbar unendlich.

Die Unendlichkeit ist wiederum offensichtlich. Schwieriger ist die Frage der Abzählbarkeit. Dafür nutzt man die Cantorsche Paarungsfunktion, die jedem Zahlenpaar $(i,j)$ bijektiv eine natürliche Zahl $k$ zuordnet. Damit kann man alle Zahlenpaare eindeutig nummerieren und somit abzählen.

$n$-Tupel natürlicher Zahlen

Die Menge aller $n$-Tupel $(i\_1,\; i\_2,\; \backslash ldots,\; i\_n)$ natürlicher Zahlen $\backslash mathbb\{N\}^n$ ist ebenfalls abzählbar unendlich. Das zeigt man wiederum durch Anwendung der Cantor-Diagonalisierung, dass die Menge der rationalen_Zahlen abzählbar ist, ebenso jede Menge der Gestalt $\backslash mathbb\{Z\}^n$ (Tupel ganzer_Zahlen). Darüber hinaus existiert noch die Quantoralsymmetrie.

Die Abbildung $\backslash mathbb\{N\}\_0^3\backslash rightarrow\backslash mathbb\{Q\}$, $(i,\; j,\; k)\backslash mapsto$ ist surjektiv, also ist die Mächtigkeit von $\backslash mathbb\{Q\}$ höchstens so groß wie die von $\backslash mathbb\{N\}\_0^3$. Da es einerseits unendlich viele Brüche gibt, und andererseits die Menge $\backslash mathbb\{N\}\_0^3$ abzählbar unendlich ist, ist auch $\backslash mathbb\{Q\}$ abzählbar unendlich.

Algebraische Zahlen

Es sei $P$ sein Polynom mit ganzzahligen Koeffizienten, $P(x)=a\_0+...+a\_n\; x^n$.
Die Höhe von $P$ sei definiert als $h(P)=|a\_0|+...+|a\_n|+n$.
Zu jeder vorgegebenen Höhe $>0$ gibt es nur endlich viele Polynome, welche wiederum nur endlich viele
Nullstellen besitzen.
Die Vereinigung $\backslash bigcup\_\{n=1\}\; \backslash left\backslash \{\; x\; \backslash ,\; \backslash big|\backslash ,\; x\backslash ;\backslash right.$ ist Nullstelle eines ganzzahligen Polynoms $P$ mit $\backslash left.\; h(P)=n\backslash ,\; \backslash right\backslash \}$ ist gerade die Menge der algebraischen Zahlen $\backslash mathbb\{A\}$.
Als abzählbare Vereinigung endlicher Mengen ist $\backslash mathbb\{A\}$ daher abzählbar.

Wörter über einem Alphabet

Durch die Anwendung der sogenannten Standardnummerierung über das Alphabet $\backslash Sigma$ kann man auch die Wörter einer Sprache im Sinne der Mathematik abzählen.

Berechenbare Zahlenfunktionen

Die Menge aller berechenbaren Zahlenfunktionen ist abzählbar unendlich. Man kann eine Standardnummerierung aller denkbaren Bandprogramme angeben. Da die Menge der Bandprogramme größer als die Menge der berechenbaren Funktionen ist (es könnte ja zwei unterschiedliche Programme geben, die dieselbe Funktion berechnen), sind damit die Zahlenfunktionen abzählbar unendlich.

Beispiel einer überabzählbaren unendlichen Menge

Die Menge der reellen_Zahlen ist dagegen überabzählbar. Das bedeutet, dass es keine bijektive Abbildung gibt, die jede reelle Zahl auf je eine natürliche Zahl abbildet, siehe Kontinuumshypothese.

Eigenschaften

* Jede aufzählbare Menge ist auch abzählbar.

Siehe auch

* In der Topologie erfüllen ?kleine? topologische_Räume ein Abzählbarkeitsaxiom.
Kardinalzahl (Mathematik)
Diskretheit
Hilberts Hotel

       VIDEO-NEWS UND ANGEBOTE