imported>InkoBot: Bot: Ersetze hartkodierte Farbangabe durch Farbklasse

2025-07-23T16:32:11Z

Bot: Ersetze hartkodierte Farbangabe durch Farbklasse

Neue Seite

In der [[Mengenlehre]] wird eine Menge <math>A</math> als '''abzählbar unendlich''' bezeichnet, wenn sie die gleiche [[Mächtigkeit (Mathematik)|Mächtigkeit]] hat wie die Menge der [[Natürliche Zahlen|natürlichen Zahlen ]]<math>\mathbb{N}.</math> Dies bedeutet, dass es eine [[Bijektion]] zwischen <math>A</math> und der Menge der natürlichen Zahlen gibt, die Elemente der Menge <math>A</math> also „durchnummeriert“ werden können.

Zu den '''höchstens abzählbaren''' Mengen zählen neben den abzählbar unendlichen Mengen auch die [[Endliche Menge|endlichen Mengen]]. Die Verwendung des Begriffes '''abzählbar''' ist nicht einheitlich. Er kann je nach Definition sowohl ''abzählbar unendlich''<ref>{{Literatur |Autor=[[I. P. Natanson]] |Titel=Theorie der Funktionen einer reellen Veränderlichen |Auflage=4. |Verlag= Harri Deutsch |Ort=Thun |Datum=1981 |ISBN=3-87144-217-8 |Fundstelle= S. 8 |Kommentar=Unveränderter Nachdruck der 4. Aufl., Akademie-Verlag, Berlin 1975}}</ref><ref>{{Literatur|Autor= A. I. Khuri |Titel= Advanced Calculus with Applications in Statistics |Auflage=2. |Reihe=Wiley Series in Probability and Statistics |Verlag= Wiley |Ort=Hoboken |Datum=2003 |ISBN=0-471-39104-2 |Fundstelle=1.4 ''Finite, Countable, and Uncountable Sets'', S. 6–9}}</ref> als auch ''höchstens abzählbar''<ref>{{Literatur |Autor=[[Otto Forster]], Florian Lindemann |Titel=Differential- und Integralrechnung einer Veränderlichen |Reihe=Grundkurs Mathematik |Auflage=13. |Verlag=Springer Spektrum |Ort=Wiesbaden |Datum=2023 |ISBN=978-3-658-40129-0 |Fundstelle= S. 129 |DOI=10.1007/978-3-658-40130-6}}</ref><ref>{{Literatur |Autor=[[Nicolas Bourbaki]] |Titel=Éléments de Mathematique – Théorie des ensembles |Verlag=Springer |Ort=Berlin / Heidelberg / New York |Datum=2006 |ISBN=978-3-540-34034-8 |DOI=10.1007/978-3-540-34035-5 |Fundstelle= S. E.R.33 |Kommentar=Nachdruck der Originalausgabe Hermann, Paris 1970 |Sprache=fr}}</ref> bedeuten.

Eine Menge, die weder endlich noch abzählbar unendlich ist, wird als [[Überabzählbarkeit|überabzählbar]] bezeichnet.

Die Mächtigkeit einer abzählbar unendlichen Menge wird – als [[Kardinalzahl (Mathematik)|Kardinalzahl]] – mit <math>\aleph_0</math> (gesprochen: alef null) bezeichnet, etwa gilt <math>\left|\N\right|=\aleph_0</math>. Zu dieser Bezeichnung siehe auch [[Aleph-Funktion]].

== Beispiele abzählbar unendlicher Mengen ==
=== Natürliche Zahlen ===
Die Menge der [[natürliche Zahl|natürlichen Zahlen]] <math>\mathbb{N}</math> ist per Definition ''abzählbar unendlich'', da sie dieselbe Mächtigkeit wie sie selbst besitzt.

=== Primzahlen ===
Die Menge der [[Primzahl]]en <math>\mathbb{P}</math> ist ebenfalls ''abzählbar unendlich'', da sie eine Teilmenge der natürlichen Zahlen und nach dem [[Satz von Euklid]] auch unendlich ist.

{| class="wikitable" style="text-align:right;"
| <math>n</math>
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| …
|-
| <math>f(n)</math>
| {{0}}2
| {{0}}3
| {{0}}5
| {{0}}7
| 11
| 13
| 17
| 19
| …
|}

=== Ganze Zahlen ===
Die Menge der [[Ganze Zahl|ganzen Zahlen]] <math>\mathbb{Z}</math> ist abzählbar unendlich, eine Abzählung ist beispielsweise durch die Funktion

<math>f\colon\begin{cases}
\mathbb{N}_0 \to \mathbb{Z} \\
n\mapsto \frac {1-(-1)^n\,(2\,n+1)} 4
\end{cases} </math>

gegeben mit der [[Wertetabelle]]:
{| class="wikitable" style="text-align:right;"
| <math>n</math>
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| …
|-
| <math>f(n)</math>
| 0
| +1  
|   −1
| +2  
|   −2
| +3  
|   −3
| +4  
|   −4
| …
|}

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

=== Paare natürlicher Zahlen ===
Auch die Menge aller Paare <math>(i,j)\in\mathbb{N} \times \mathbb{N}</math> 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 <math>(i,j)</math> bijektiv eine natürliche Zahl <math>k</math> zuordnet. Damit kann man alle Zahlenpaare eindeutig nummerieren und somit abzählen.

{| class="wikitable" style="border:0; text-align:center;"
| <math>n</math>
| rowspan="3" class="hintergrundfarbe-basis" style="border:0; padding:2px;" |
| 1
| rowspan="3" class="hintergrundfarbe-basis" style="border:0; padding:2px;" |
| 2
| 3
| rowspan="3" class="hintergrundfarbe-basis" style="border:0; padding:2px;" |
| 4
| 5
| 6
| rowspan="3" class="hintergrundfarbe-basis" style="border:0; padding:2px;" |
| 7
| 8
| 9
| 10
| rowspan="3" class="hintergrundfarbe-basis" style="border:0; padding:1px;" |
| 11
| 12
| …
|-
| <math>f(n)</math>
| 1,1
| 1,2
| 2,1
| 1,3
| 2,2
| 3,1
| 1,4
| 2,3
| 3,2
| 4,1
| 1,5
| 2,4
| …
|-
| class="hintergrundfarbe-basis" style="border:0; font-size:70%;" colspan="1" |
| class="hintergrundfarbe-basis" style="border:0; font-size:70%;" colspan="1" | ''i+j=2''
| class="hintergrundfarbe-basis" style="border:0; font-size:70%;" colspan="2" | ''i+j=3''
| class="hintergrundfarbe-basis" style="border:0; font-size:70%;" colspan="3" | ''i+j=4''
| class="hintergrundfarbe-basis" style="border:0; font-size:70%;" colspan="4" | ''i+j=5''
| class="hintergrundfarbe-basis" style="border:0; font-size:70%;" colspan="3" | ''i+j=6''
|}

=== ''n''-Tupel natürlicher Zahlen ===
Die Menge aller <math>n</math>-Tupel <math>(i_1, i_2, \ldots, i_n)</math> natürlicher Zahlen <math>\mathbb{N}^n</math> ist ebenfalls abzählbar unendlich. Das zeigt man wiederum durch <math>(n-1)</math>-malige Anwendung der [[Cantorsche Paarungsfunktion|Cantorschen Paarungsfunktion]].

=== Rationale Zahlen ===
[[Georg Cantor]] zeigte mit dem so genannten [[Cantors erstes Diagonalargument|ersten Diagonalargument]], dass die Menge der [[Rationale Zahlen|rationalen Zahlen]] abzählbar ist, ebenso jede Menge der Gestalt <math>\mathbb{Z}^n</math> ([[Tupel]] [[Ganze Zahlen|ganzer Zahlen]]).

Die Abbildung <math>\mathbb{N}_0^3\rightarrow\mathbb{Q}</math>, <math>(i, j, k)\mapsto \frac{i-j}{1 + k}</math> ist [[Surjektivität|surjektiv]], also ist die Mächtigkeit von <math>\mathbb{Q}</math> höchstens so groß wie die von <math>\mathbb{N}_0^3</math>. Da es einerseits unendlich viele Brüche gibt und andererseits die Menge <math>\mathbb{N}_0^3</math> abzählbar unendlich ist, ist auch <math>\mathbb{Q}</math> 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.<ref>{{Literatur |Autor=Stephen P. Glasby |Titel=Enumerating the rationals from left to right |Sammelwerk=[[American Mathematical Monthly]] |Band=118 |Nummer=9 |Datum=2011 |Seiten=830–835 |Sprache=en |arXiv=1011.2823 |DOI=10.4169/amer.math.monthly.118.09.830}}</ref><ref>{{Literatur |Autor=Neil Calkin, [[Herbert Wilf]] |Titel=Recounting the rationals |Sammelwerk=[[The American Mathematical Monthly]] |Band=107 |Nummer=4 |Datum=2000 |Seiten=360–363 |Sprache=en |Online=[https://www2.math.upenn.edu/~wilf/website/recounting.pdf math.upenn.edu] |Abruf=2022-01-12 |DOI=10.1080/00029890.2000.12005205}}</ref>

=== Algebraische Zahlen ===
Eine [[algebraische Zahl]] ist [[Nullstelle]] eines [[Polynom]]s <math>P(x)=a_0 + \dots + a_n x^n</math> mit ganzzahligen [[Koeffizient]]en. Die Höhe von <math>P</math> sei definiert als <math>h(P)=|a_0|+ \dots +|a_n|+n</math>.

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

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

=== Wörter über einem Alphabet ===
Durch die Anwendung der sogenannten [[Standardnummerierung]] über das Alphabet <math>\Sigma</math> kann man auch die Wörter einer [[Formale Sprache|Sprache]] im Sinne der Mathematik abzählen.

=== Berechenbare Zahlenfunktionen ===
Die Menge aller [[Berechenbarkeit|berechenbaren]] [[Zahlenfunktion]]en ist abzählbar unendlich. Man kann eine Standardnummerierung aller denkbaren [[Turingmaschine|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 [[Reelle Zahlen|reellen Zahlen]] ist dagegen [[Überabzählbarkeit|ü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]].

== Eigenschaften ==
* Jede [[Teilmenge]] einer (höchstens) abzählbaren Menge ist (höchstens) abzählbar.
* Die [[Vereinigungsmenge|Vereinigung]] zweier (höchstens) abzählbarer Mengen ist (höchstens) abzählbar.
* Allgemeiner ist jede Vereinigung einer abzählbaren Anzahl von (höchstens) abzählbaren Mengen wieder (höchstens) abzählbar.
* Das [[Kartesisches Produkt|kartesische Produkt]] zweier (höchstens) abzählbaren Mengen ist (höchstens) abzählbar.
* Gibt es eine [[Surjektion]] von der Menge <math>\mathbb{N}</math> der natürlichen Zahlen auf die Menge <math>A</math>, so ist <math>A</math> höchstens abzählbar.
* Eine Menge <math>A</math> ist höchstens abzählbar gdw. es eine [[partielle Funktion|partielle]] Surjektion <math>\N \to A</math> gibt.
* Eine Menge <math>A</math> ist höchstens abzählbar gdw. es eine [[Injektivität|injektive]] Multifunktion <math>A \to \N</math> gibt.
* Jede [[Rekursive Aufzählbarkeit|aufzählbare Menge]] ist höchstens abzählbar.

== Siehe auch ==
* In der [[Topologie (Mathematik)|Topologie]] erfüllen „kleine“ [[Topologischer Raum|topologische Räume]] ein [[Abzählbarkeitsaxiom]].
* [[Kardinalzahl (Mathematik)]]
== Literatur ==
* {{Literatur |Autor=[[Nicolas Bourbaki]] |Titel=Éléments de Mathematique – Théorie des ensembles |Verlag=Springer |Ort=Berlin / Heidelberg / New York |Datum=2006 |ISBN=978-3-540-34034-8 |DOI=10.1007/978-3-540-34035-5 |Fundstelle= § 7. ''Puissanses. Ensembles dénomerables'', S. E.R.32–37 |Kommentar=Nachdruck der Originalausgabe Hermann, Paris 1970 |Sprache=fr}}

== Einzelnachweise ==
<references />

{{SORTIERUNG:Abzahlbare Menge}}
[[Kategorie:Mengenlehre]]

Abzählbare Menge - Versionsgeschichte

imported>InkoBot: Bot: Ersetze hartkodierte Farbangabe durch Farbklasse