Toplinks zu diesem Thema:
Sprache
Der Artikel Abzählbarkeit gehört zur Kategorie: Mengenlehre
Eine Menge [Formel] bezeichnet man als abzählbar unendlich, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen [Formel]. 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 [Formel], 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 ([Formel]) ist per Definition abzählbar, da sie dieselbe Mächtigkeit wie sie selbst besitzt.Primzahlen
Die Menge der Primzahlen ist ebenfalls abzählbar, da es unendlich viele gibt und diese durchnummeriert werden können.| [Formel] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
| [Formel] | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | … |
Ganze Zahlen
Die Menge der ganzen Zahlen ([Formel]) ist abzählbar unendlich, eine Abzählung ist beispielsweise gegeben durch
| [Formel] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
| [Formel] | 0 | 1 | −1 | 2 | −2 | 3 | −3 | 4 | … |
Die Beispiele Primzahlen und ganze Zahlen zeigen, dass sowohl echte Teilmengen als auch Obermengen dieselbe Mächtigkeit besitzen können, im Gegensatz zu endlichen Mengen.
Paare natürlicher Zahlen
Auch die Menge aller Paare [Formel] ([Formel]) 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 [Formel] bijektiv eine natürliche Zahl [Formel] zuordnet. Damit kann man alle Zahlenpaare eindeutig nummerieren und somit abzählen.
| [Formel] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … |
| [Formel] | 1,1 | 1,2 | 2,1 | 1,3 | 2,2 | 3,1 | 1,4 | 2,3 | 3,2 | 4,1 | … |
[Formel]-Tupel natürlicher Zahlen
Die Menge aller [Formel]-Tupel [Formel] natürlicher Zahlen ([Formel]) ist ebenfalls abzählbar unendlich. Das zeigt man wiederum durch Anwendung der Cantorsche Paarungsfunktion.Rationale Zahlen
Georg Cantor zeigte mit der so genannten Cantor-Diagonalisierung, dass die Menge der rationalen Zahlen abzählbar ist, ebenso jede Menge der Gestalt [Formel] (Tupel ganzer Zahlen).Die Abbildung [Formel], [Formel] ist surjektiv, also ist die Mächtigkeit von [Formel] höchstens so groß wie die von [Formel]. Da es einerseits unendlich viele Brüche gibt, und andererseits die Menge [Formel] abzählbar unendlich ist, ist auch [Formel] abzählbar unendlich.
Wörter über einem Alphabet
Durch die Anwendung der sogenannten Standardnummerierung über das Alphabet [Formel] 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
Diskussion der Autoren über den Artikel: Abzählbarkeit
Ist die Menge der Primzahlen abzählbar?
--Himmelsfisch 16:42, 18. Jan 2005 (CET)
Ja, denn die Menge aller Primzahlen ist eine Untermenge der Menge der natürlichen Zahlen.
--Barbarossa | Barbarossa 17:32, 18. Jan 2005 (CET)
Aus dem Artikel entfernt (es geht um die Herstellung einer Bijektion von N auf N):
- Dafür benötigt man zwar unendlich lange und auch unendlich große Zahlen, aber es ist prinzipiell möglich.
Absatz: Die Menge aller rationalen Zahlen
Ich frage mich, warum eine rationale Zahl q durch DREI natürliche Zahlen in der genannten Form als Bruch dargestellt werden muss. Meines Erachtens genügen doch ZWEI natürliche Zahlen für diese Darstellung, z.B. q := a/b mit a,b aus IN. Wenn es aber bestimmte Gründe für die gewählte Darstellung gibt(etwa um die erforderliche Bijektivität der Abbildung zu gewähren), sollte dies erwähnt und ggf. etwas näher erläutert werden.
- Mit nur zwei natürlichen Zahlen wird die Darstellung der negativen Brüche problematisch. Natürlich könnte man es hintricksen, aber dann könnte man sich auch gleich auf eine einzige natürliche Zahl beschränken. Mit drei natürlichen Zahlen dagegen ist die Darstellung einigermaßen einfach. Bijektiv ist die Abbildung jedoch nicht, aber surjektiv reicht schon.--MKI 15:39, 1. Okt 2005 (CEST)
Absatz: Ganze Zahlen
Ich denke mal das die zweite Abbildung falsch ist. Diese sollte alle ganzen Zahlen z bijektiv auf die natürlichen Zahlen abbilden. Also sollte sie heißen: z -> -2z, wenn z < 0 und z -> 2z + 1, wenn z >= 0
anstatt wie es momentan propagiert wird:
z -> -2z, wenn z < 0 und z -> 2z - 1, wenn z >= 0
Ich hab das mal ausgebessert, falls ich doch falsch liegen sollte kann man es ja wieder rausnehmen :) --84.57.5.165 20:38, 13. Dez 2005 (CET)
Die Definition von Abzählbarkeit ist garantiert falsch (auch wenn ich kein Mathematiker bin, ist das klar), denn nach dieser Definition wäre z.B. auch die Menge der rationalen Zahlen abzählbar (da sie die gleiche Mächtigkeit wie die Menge der natürlichen Zahlen hat), was jedoch falsch ist. (Es gibt zwischen zwei rationalen Zahlen stets unendlich viele weitere rationale Zahlen. ES widerspräche daher dem Sprachgebrauch von abzählbar, wenn die Menge der rationalen Zahlen als abzählbar gelten sollte.)
- Die Definition ist korrekt, und wie auch schon im Artikel steht, ist die Menge der rationalen Zahlen in der Tat abzählbar. Mathematische Begriffe unterscheiden sich manchmal stark von ihrer Alltagsbedeutung, kaum jemand würde beispielsweise so etwas fragiles wie den Cantor-Staub oder den Menger-Schwamm im Alltagssinne als kompakt ansehen.--Gunther 13:19, 28. Sep 2006 (CEST)
@ Gunther: Deine Replik ist zwar nicht besonders informativ, aber du hast anscheinend Recht. Gibt es eigentlich auch eine Bezeichnung für die Eigenschaft von (Zahl-)Mengen, dass es zu keiner Zahl eine nächstgrößere oder -kleinere gibt?
- Was du meinst, nennt man „in sich dicht liegen“. (Die Erklärung unter Dicht (Mathematik) ist allerdings leider unverdaulich.) Das Abzählen hat dagegen nichts mit der Anordnung zu tun: Bei der Cantor-Diagonalisierung zählt man „kreuz und quer“ - aber jede Zahl kommt irgendwann mal dran. -- Peter Steinberg 19:56, 30. Sep 2006 (CEST)
