Überabzählbar unendlich

Überabzählbar unendlich

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 Menge A also „durchnummeriert“ werden kann.

Zu den höchstens abzählbaren Mengen zählen neben den abzählbar unendlichen auch kleinere, also endliche Mengen. Die Verwendung des Begriffes abzählbar ist nicht einheitlich. Er kann je nach Definition sowohl abzählbar unendlich als auch höchstens abzählbar bedeuten.

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

Inhaltsverzeichnis

Beispiele abzählbar unendlicher Mengen

Natürliche Zahlen

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

Primzahlen

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

Ganze Zahlen

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

n 1 2 3 4 5 6 7 8
f(n) 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 (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
f(n) 1,1 1,2 2,1 1,3 2,2 3,1 1,4 2,3 3,2 4,1

n-Tupel natürlicher Zahlen

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.

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 \mathbb{Z}^n (Tupel ganzer Zahlen). Darüber hinaus existiert noch die Quantoralsymmetrie.

Die Abbildung \mathbb{N}_0^3\rightarrow\mathbb{Q}, (i, j, k)\mapsto {{i-j} \over {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.

Algebraische Zahlen

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

Wörter über einem Alphabet

Durch die Anwendung der sogenannten Standardnummerierung über das Alphabet Σ 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 Cantors zweites Diagonalargument.

Eigenschaften

  • Jede Teilmenge einer (höchstens) abzählbaren Menge ist (höchstens) abzählbar.
  • Die 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 kartesische Produkt zweier (höchstens) abzählbaren Mengen ist (höchstens) abzählbar.
  • Gibt es eine Surjektion von der Menge \mathbb{N} der natürlichen Zahlen auf die Menge A, so ist A höchstens abzählbar.
  • Jede aufzählbare Menge ist auch abzählbar.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Überabzählbar — Eine Menge heißt überabzählbar, wenn sie nicht abzählbar ist. Dabei heißt eine Menge abzählbar, wenn sie entweder endlich ist oder eine Bijektion zur Menge der natürlichen Zahlen existiert. Eine Menge ist also genau dann überabzählbar, wenn ihre… …   Deutsch Wikipedia

  • Unendlich — Der Begriff Unendlichkeit bezeichnet die Negation bzw. Aufhebung von Endlichkeit, weniger präzise auch deren Gegenteil . Sein mathematisches Symbol ist ∞. Das Unendliche im Sinne von: das Nichtendliche ist der direkten menschlichen Erfahrung… …   Deutsch Wikipedia

  • Abzählbar unendlich — 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 . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Aktual unendlich — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… …   Deutsch Wikipedia

  • Aktuell unendlich — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… …   Deutsch Wikipedia

  • Potentiell unendlich — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… …   Deutsch Wikipedia

  • Potenziell unendlich — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… …   Deutsch Wikipedia

  • Löwenheim-Skolem — Das Löwenheim Skolem Theorem besagt, dass eine Menge von Aussagen der Prädikatenlogik erster Stufe, die in einem Modell mit einer überabzählbar unendlich großen Domäne erfüllt ist, immer auch in einem Modell mit einer abzählbar unendlich großen… …   Deutsch Wikipedia

  • Satz von Löwenheim-Skolem — Das Löwenheim Skolem Theorem besagt, dass eine Menge von Aussagen der Prädikatenlogik erster Stufe, die in einem Modell mit einer überabzählbar unendlich großen Domäne erfüllt ist, immer auch in einem Modell mit einer abzählbar unendlich großen… …   Deutsch Wikipedia

  • Satz von Löwenheim und Skolem — Das Löwenheim Skolem Theorem besagt, dass eine Menge von Aussagen der Prädikatenlogik erster Stufe, die in einem Modell mit einer überabzählbar unendlich großen Domäne erfüllt ist, immer auch in einem Modell mit einer abzählbar unendlich großen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”