Cantors erster Überabzählbarkeitsbeweis

Cantors erster Überabzählbarkeitsbeweis i​st Georg Cantors erster Beweis, d​ass die reellen Zahlen e​ine überabzählbare Menge bilden. Er k​ommt ohne d​as Dezimalsystem o​der irgendein anderes Zahlensystem aus. Die Behauptung u​nd der e​rste Beweis wurden v​on Cantor i​m Dezember 1873 entdeckt, u​nd 1874 i​n Crelles Journal (Journal für d​ie Reine u​nd Angewandte Mathematik, Bd. 77, 1874) veröffentlicht.[1] Viel bekannter w​urde sein 1877 gefundener zweiter Beweis dafür, Cantors zweites Diagonalargument.

Der Satz

Sei ${\displaystyle \mathbf {R} }$ eine Menge, die

• mindestens zwei Elemente enthält,
• total geordnet ist,
• dicht geordnet ist, d. h. zwischen je zwei Elementen befindet sich stets ein weiteres,
• keine Lücken hat, d. h., wenn ${\displaystyle \mathbf {R} }$ in zwei nichtleere Teilmengen ${\displaystyle A}$ und ${\displaystyle B}$ partitioniert ist, so dass jedes Element von ${\displaystyle A}$ kleiner als jedes Element von ${\displaystyle B}$ ist, dann gibt es ein Element ${\displaystyle c}$, so dass jedes Element, das kleiner als ${\displaystyle c}$ ist, in ${\displaystyle A}$ und jedes Element, das größer als ${\displaystyle c}$ ist, in ${\displaystyle B}$ liegt. Dabei ist ${\displaystyle c}$ entweder aus ${\displaystyle A}$ oder aus ${\displaystyle B}$ (vergleiche Dedekindscher Schnitt).

Dann ist ${\displaystyle \mathbf {R} }$ überabzählbar.

Die genannten Eigenschaften treffen insbesondere auf ${\displaystyle \mathbb {R} }$ sowie bereits auf jedes beliebig gewählte Intervall (z. B. ${\displaystyle [0,1]}$) zu, so dass insbesondere diese Mengen überabzählbar sind.

Der Beweis

Zunächst sei bemerkt, dass aus der Eigenschaft, dicht und total geordnet zu sein, bereits folgt, dass zwischen zwei Elementen ${\displaystyle a,b}$ von ${\displaystyle \mathbf {R} }$ mit ${\displaystyle a<b}$ sogar unendlich viele Elemente von ${\displaystyle \mathbf {R} }$ liegen müssen. Gäbe es nämlich nur endlich viele, so gäbe es hierunter ein größtes, etwa ${\displaystyle x}$. Zwischen ${\displaystyle x}$ und ${\displaystyle b}$ müsste dann ein weiteres Element liegen, ${\displaystyle x<y<b}$. Aber dies stünde im Widerspruch zur Maximalität von ${\displaystyle x}$.

Zum Beweis der Überabzählbarkeit nehmen wir an, dass es eine Folge ${\displaystyle (x_{1},x_{2},\ldots )}$ in ${\displaystyle \mathbf {R} }$ gibt, die ganz ${\displaystyle \mathbf {R} }$ als Folgeglieder hat. Wir dürfen o. B. d. A. voraussetzen, dass ${\displaystyle x_{1}<x_{2}}$ gilt (sonst vertausche man diese beiden Folgenglieder). Nun definieren wir zwei weitere Folgen ${\displaystyle (a_{1},a_{2},\ldots )}$ und ${\displaystyle (b_{1},b_{2},\ldots )}$:

${\displaystyle a_{1}=x_{1}}$ sowie ${\displaystyle b_{1}=x_{2}}$. Laut Voraussetzung gilt also ${\displaystyle a_{1}<b_{1}}$.

${\displaystyle a_{n+1}=x_{i}}$, wobei ${\displaystyle i}$ der kleinste Index ist, der größer ist als der zuvor für ${\displaystyle b_{n}}$ ausgewählte Index und für den ${\displaystyle a_{n}<x_{i}<b_{n}}$ gilt. Dies geht, weil ${\displaystyle \mathbf {R} }$ dicht geordnet ist. Es gibt ja laut Vorbemerkung unendlich viele ${\displaystyle i}$ mit ${\displaystyle a_{n}<x_{i}<b_{n}}$ und höchstens endlich viele dieser Kandidaten werden durch den Vergleich mit dem zu ${\displaystyle b_{n}}$ gehörigen Index ausgeschlossen.

${\displaystyle b_{n+1}=x_{i}}$, wobei ${\displaystyle i}$ der kleinste Index ist, der größer ist als der zuvor für ${\displaystyle a_{n+1}}$ ausgewählte Index und für den ${\displaystyle a_{n+1}<x_{i}<b_{n}}$ gilt. Wieder geht dies, weil ${\displaystyle \mathbf {R} }$ dicht ist.

Die Folge ${\displaystyle (a_{n})}$ ist streng monoton wachsend, die Folge ${\displaystyle (b_{n})}$ ist streng monoton fallend, und die beiden Folgen beschränken sich gegenseitig, da ${\displaystyle a_{n}<b_{n}}$ ist für jedes ${\displaystyle n}$. Sei ${\displaystyle A}$ die Menge derjenigen Elemente von ${\displaystyle \mathbf {R} }$, die kleiner als sämtliche ${\displaystyle b_{n}}$ sind und sei ${\displaystyle B}$ das Komplement. Dann enthält ${\displaystyle A}$ unter anderem alle ${\displaystyle a_{n}}$ und ${\displaystyle B}$ alle ${\displaystyle b_{n}}$, die beiden Mengen sind also nicht leer. Außerdem ist jedes Element von ${\displaystyle B}$ größer als jedes Element von ${\displaystyle A}$: Ist ${\displaystyle x\in A}$ und ${\displaystyle y\in B}$, so gibt es ein ${\displaystyle n}$ mit ${\displaystyle b_{n}\leq y}$ nach Definition von ${\displaystyle B}$; dann folgt aber ${\displaystyle x<b_{n}\leq y}$ nach Definition von ${\displaystyle A}$. Es handelt sich also bei ${\displaystyle (A,B)}$ um einen Dedekind-Schnitt, so dass es wegen der Lückenlosigkeit von ${\displaystyle \mathbf {R} }$ ein Element ${\displaystyle c}$ geben muss, für welches insbesondere ${\displaystyle a_{n}<c<b_{n}}$ für jedes ${\displaystyle n}$ gilt.

Da ${\displaystyle c}$ wie jedes Element von ${\displaystyle \mathbf {R} }$ in der Folge ${\displaystyle (x_{i})}$ auftritt, gibt es einen Index ${\displaystyle j}$, so dass ${\displaystyle c=x_{j}}$ ist. Hierbei ist gewiss ${\displaystyle j>2}$, denn ${\displaystyle c}$ ist von ${\displaystyle a_{1}}$ und ${\displaystyle b_{1}}$ verschieden. Sei ${\displaystyle n}$ die kleinste natürliche Zahl mit der Eigenschaft, dass ${\displaystyle a_{n+1}=x_{i}}$ für ein ${\displaystyle i>j}$ oder ${\displaystyle b_{n+1}=x_{i}}$ mit ${\displaystyle i>j}$ gilt. In beiden Fällen ergibt sich ein Widerspruch zur Wahl von ${\displaystyle i}$, da ja bereits ${\displaystyle a_{n}<x_{j}<b_{n}}$ bzw. ${\displaystyle a_{n+1}<x_{j}<b_{n}}$ gilt.

Dieser Widerspruch kann nur aufgehoben werden, indem man die Existenz der Folge ${\displaystyle (x_{1},x_{2},\ldots )}$ verneint, d. h. ${\displaystyle \mathbf {R} }$ ist überabzählbar.

Reelle algebraische und transzendente Zahlen

Im gleichen Werk v​on 1874 bewies Cantor, d​ass die Menge d​er reellen algebraischen Zahlen abzählbar ist, woraus sofort d​ie Existenz v​on überabzählbar vielen transzendenten Zahlen folgt. Die Existenzaussage a​n sich w​ar nicht neu: Joseph Liouville h​atte bereits 1844 einige transzendente Zahlen explizit angegeben.

Einzelnachweise

1. Georg Cantor: Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen. Journal für die Reine und Angewandte Mathematik 77: S. 258–262.