de.wikipedia.org

Abzählbare Menge – Wikipedia

In der Mengenlehre wird eine Menge $A$ als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen $\mathbb {N} .$ Dies bedeutet, dass es eine Bijektion zwischen $A$ und der Menge der natürlichen Zahlen gibt, die Elemente der Menge $A$ also „durchnummeriert“ werden können.

Zu den höchstens abzählbaren Mengen zählen neben den abzählbar unendlichen Mengen auch die endlichen Mengen. Die Verwendung des Begriffes abzählbar ist nicht einheitlich. Er kann je nach Definition sowohl abzählbar unendlich^[1]^[2] als auch höchstens abzählbar^[3]^[4] bedeuten.

Eine Menge, die weder endlich noch abzählbar unendlich ist, wird als überabzählbar bezeichnet.

Die Mächtigkeit einer abzählbar unendlichen Menge wird – als Kardinalzahl – mit $\aleph _{0}$ (gesprochen: alef null) bezeichnet, etwa gilt $\left|\mathbb {N} \right|=\aleph _{0}$ . Zu dieser Bezeichnung siehe auch Aleph-Funktion.

Die Menge der natürlichen Zahlen $\mathbb {N}$ ist per definitionem abzählbar unendlich, da sie dieselbe Mächtigkeit wie sie selbst besitzt.

Die Menge der Primzahlen $\mathbb {P}$ ist ebenfalls abzählbar unendlich, da sie eine Teilmenge der natürlichen Zahlen und nach dem Satz von Euklid auch unendlich ist.

$n$	1	2	3	4	5	6	7	8	…
$f(n)$	2	3	5	7	11	13	17	19	…

Die Menge der ganzen Zahlen $\mathbb {Z}$ ist abzählbar unendlich, eine Abzählung ist beispielsweise durch die Funktion

$f\colon {\begin{cases}\mathbb {N} _{0}\to \mathbb {Z} \\n\mapsto {\frac {1-(-1)^{n}\,(2\,n+1)}{4}}\end{cases}}$

gegeben mit der Wertetabelle:

$n$	0	1	2	3	4	5	6	7	8	…
$f(n)$	0	+1	−1	+2	−2	+3	−3	+4	−4	…

Die Beispiele Primzahlen und ganze Zahlen zeigen, dass bei einer unendlichen Grundmenge sowohl echte Teilmengen als auch Obermengen dieselbe Mächtigkeit besitzen können wie die Grundmenge, im Gegensatz zu den Verhältnissen bei endlichen Mengen.

Auch die Menge aller Paare $(i,j)\in \mathbb {N} \times \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$		1		2	3		4	5	6		7	8	9	10	11	12	…
$f(n)$	1,1	1,2	2,1	1,3	2,2	3,1	1,4	2,3	3,2	4,1	1,5	2,4	…
	i+j=2	i+j=3	i+j=4	i+j=5	i+j=6

Die Menge aller $n$ -Tupel $(i_{1},i_{2},\ldots ,i_{n})$ natürlicher Zahlen $\mathbb {N} ^{n}$ ist ebenfalls abzählbar unendlich. Das zeigt man wiederum durch $(n-1)$ -malige Anwendung der Cantorschen Paarungsfunktion.

Georg Cantor zeigte mit dem so genannten ersten Diagonalargument, dass die Menge der rationalen Zahlen abzählbar ist, ebenso jede Menge der Gestalt $\mathbb {Z} ^{n}$ (Tupel ganzer Zahlen).

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

Mit der Stern-Brocot-Folge kann in einfacher Weise eine Bijektion zwischen ℕ und ℚ angegeben werden, was die Abzählbarkeit der rationalen Zahlen ebenfalls beweist.^[5]^[6]

Eine algebraische Zahl ist Nullstelle eines Polynoms $P(x)=a_{0}+\dots +a_{n}x^{n}$ mit ganzzahligen Koeffizienten. Die Höhe von $P$ sei definiert als $h(P)=|a_{0}|+\dots +|a_{n}|+n$ .

Zu jeder vorgegebenen Höhe $k>0$ gibt es nur endlich viele Polynome, welche wiederum nur endlich viele Nullstellen besitzen; für jedes dieser k hat mit $a_{0}=k-1$ das Polynom $P(x)=-a_{0}+x^{1}$ die Nullstelle $x=a_{0}\in \mathbb {N}$ . Wird $Q(k)$ als die Menge aller dieser Nullstellen gesetzt, dann ist die Menge $\mathbb {A}$ der algebraischen Zahlen die Vereinigung $\bigcup _{k\in \mathbb {N} \setminus \{0\}}{Q(k)}$ .

Als abzählbare Vereinigung endlicher Mengen ist $\mathbb {A}$ daher abzählbar. Da $\mathbb {A}$ andererseits $\mathbb {N}$ enthält, ist $\mathbb {A}$ abzählbar unendlich.

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

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.

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 Cantors zweites Diagonalargument.

In der Topologie erfüllen „kleine“ topologische Räume ein Abzählbarkeitsaxiom.
Kardinalzahl (Mathematik)

Nicolas Bourbaki: Éléments de Mathematique – Théorie des ensembles. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34034-8, § 7. Puissanses. Ensembles dénomerables, S. E.R.32–37, doi:10.1007/978-3-540-34035-5 (französisch, Nachdruck der Originalausgabe Hermann, Paris 1970).

↑ I. P. Natanson: Theorie der Funktionen einer reellen Veränderlichen. 4. Auflage. Harri Deutsch, Thun 1981, ISBN 3-87144-217-8, S. 8 (Unveränderter Nachdruck der 4. Aufl., Akademie-Verlag, Berlin 1975).
↑ A. I. Khuri: Advanced Calculus with Applications in Statistics (= Wiley Series in Probability and Statistics). 2. Auflage. Wiley, Hoboken 2003, ISBN 0-471-39104-2, 1.4 Finite, Countable, and Uncountable Sets, S. 6–9.
↑ Otto Forster, Florian Lindemann: Differential- und Integralrechnung einer Veränderlichen (= Grundkurs Mathematik). 13. Auflage. Springer Spektrum, Wiesbaden 2023, ISBN 978-3-658-40129-0, S. 129, doi:10.1007/978-3-658-40130-6.
↑ Nicolas Bourbaki: Éléments de Mathematique – Théorie des ensembles. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34034-8, S. E.R.33, doi:10.1007/978-3-540-34035-5 (französisch, Nachdruck der Originalausgabe Hermann, Paris 1970).
↑ Stephen P. Glasby: Enumerating the rationals from left to right. In: American Mathematical Monthly. Band 118, Nr. 9, 2011, S. 830–835, doi:10.4169/amer.math.monthly.118.09.830, arxiv:1011.2823 (englisch).
↑ Neil Calkin, Herbert Wilf: Recounting the rationals. In: The American Mathematical Monthly. Band 107, Nr. 4, 2000, S. 360–363, doi:10.1080/00029890.2000.12005205 (englisch, math.upenn.edu [PDF; abgerufen am 12. Januar 2022]).