Cantors erster Überabzählbarkeitsbeweis

Cantors erster Überabzählbarkeitsbeweis ist Georg Cantors erster Beweis, dass die reellen Zahlen eine überabzählbare Menge bilden. Er kommt ohne das Dezimalsystem oder irgendein anderes Zahlensystem aus. Die Behauptung und der erste Beweis wurden von Cantor im Dezember 1873 entdeckt, und 1874 in Crelles Journal (Journal für die Reine und Angewandte Mathematik, Bd. 77, 1874) veröffentlicht. Viel bekannter wurde sein 1877 gefundener zweiter Beweis dafür, Cantors zweites Diagonalargument.

Der Satz

Sei $\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 $\mathbf {R}$ in zwei nichtleere Teilmengen $A$ und $B$ partitioniert ist, so dass jedes Element von $A$ kleiner als jedes Element von $B$ ist, dann gibt es ein Element $c$, so dass jedes Element, das kleiner als $c$ ist, in $A$ und jedes Element, das größer als $c$ ist, in $B$ liegt. Dabei ist $c$ entweder aus $A$ oder aus $B$ (vergleiche Dedekindscher Schnitt).

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

Die genannten Eigenschaften treffen insbesondere auf $\mathbb {R}$ sowie bereits auf jedes beliebig gewählte Intervall (z. B. Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\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 $a,b$ von $\mathbf {R}$ mit $a<b$ sogar unendlich viele Elemente von $\mathbf {R}$ liegen müssen. Gäbe es nämlich nur endlich viele, so gäbe es hierunter ein größtes, etwa $x$. Zwischen $x$ und $b$ müsste dann ein weiteres Element liegen, $x<y<b$. Aber dies stünde im Widerspruch zur Maximalität von $x$.

Zum Beweis der Überabzählbarkeit nehmen wir an, dass es eine Folge Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (x_{1},x_{2},\ldots )} in $\mathbf {R}$ gibt, die ganz $\mathbf {R}$ als Folgeglieder hat. Wir dürfen o. B. d. A. voraussetzen, dass Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle x_{1}<x_{2}} gilt (sonst vertausche man diese beiden Folgenglieder). Nun definieren wir zwei weitere Folgen Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (a_{1},a_{2},\ldots )} und $(b_{1},b_{2},\ldots )$:

$a_{1}=x_{1}$ sowie Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle b_{1}=x_{2}} . Laut Voraussetzung gilt also Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle a_{1}<b_{1}} .

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

$b_{n+1}=x_{i}$, wobei $i$ der kleinste Index ist, der größer ist als der zuvor für $a_{n+1}$ ausgewählte Index und für den Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle a_{n+1}<x_{i}<b_{n}} gilt. Wieder geht dies, weil $\mathbf {R}$ dicht ist.

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

Da $c$ wie jedes Element von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf{R}} in der Folge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x_i)} auftritt, gibt es einen Index Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} , so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c = x_j} ist. Hierbei ist gewiss Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j>2} , denn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} ist von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1} und $b_{1}$ verschieden. Sei $n$ die kleinste natürliche Zahl mit der Eigenschaft, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{n+1} = x_i} für ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i>j} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{n+1} = x_i} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i>j} gilt. In beiden Fällen ergibt sich ein Widerspruch zur Wahl von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} , da ja bereits Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_n < x_j < b_n} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{n+1} < x_j < b_n} gilt.

Dieser Widerspruch kann nur aufgehoben werden, indem man die Existenz der Folge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x_1,x_2,\ldots)} verneint, d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbf{R}} ist überabzählbar.

Reelle algebraische und transzendente Zahlen

Im gleichen Werk von 1874 bewies Cantor, dass die Menge der reellen algebraischen Zahlen abzählbar ist, woraus sofort die Existenz von überabzählbar vielen transzendenten Zahlen folgt. Die Existenzaussage an sich war nicht neu: Joseph Liouville hatte bereits 1844 einige transzendente Zahlen explizit angegeben.