Beweis dass R überabzählbar ist

19.05.2019, 19:43

KoenigVonAugsburg

Beweis dass R überabzählbar ist

Hallo,

seit einer Stunde versuche ich den folgenden Beweis zu verstehen, der genauso in meinem Script steht:

Beweisanfang.

Beweis durch Widerspruch: Angenommen $\begin{align*} f : N -> R \end{align*}$ wäre surjektiv (es muss ja eine Bijektion geben, also insbesondere eine Surjektion). Dann definiert man eine Intervallschachtelung die eine Zahl aus $\begin{align*} [0,1] \end{align*}$ erfasst wie folgt: $\begin{align*} I_{0} := [0,1] \end{align*}$ . Es wird nun eine Folge von Intervallen definiert, deren Länge sich in jedem Schritt drittelt, also $\begin{align*} |I_{n}| = 3^{-n} \end{align*}$ . Nun rekursiv: $\begin{align*} I_{n} = [a_{n},b_{n}] \end{align*}$ sei schon gewählt. Man teilt das Intervall in drei geleichlange Teilintervalle $\begin{align*} [a_{n},a_{n} + 3^{-n-1}], [a_{n} + 3^{-n-1}, a_{n} + 2*3^{-n-1}],[a_{n} + 2*3^{-n-1}, b_{n}]<br /> \end{align*}$ . $\begin{align*} f(n+1) \end{align*}$ kann nicht im linken und im rechten Teilintervall liegen. Wir wählen davon ein Intervall aus, indem es nicht liegt. Dadurch entsteht eine Intervallverschachtelung, die keines der $\begin{align*} f(n) \end{align*}$ enthält. Die von der Intervallschachtelung erfasste Zahl liegt als nicht im Bild.

Beweisende.

Ich weis gar nicht wo ich anfangen soll.

Also zuersteinmal verstehe ich nicht warum ich hier das Intervall in 3 Teile aufteile und warum f(n+1) nicht um linken und im rechten Intervall liegen kann(Oder ist hier gemeint, dass f(n+1) nicht gleichzeitig in beiden Intervallen liegen kann?).

Außerdem verstehe ich diesem Satz nicht: "Wir wählen davon ein Intervall aus, indem es nicht liegt". Was für ein Sinn verbirgt sich hinter dieser Wahl des Intervalls? Ich meine natürlich liegt eine Zahl die nicht im Intervall liegt nicht im Intervall. Warum wähle ich denn nicht das Intervall in der diese Zahl liegt?

Ich muss zugeben, ich habe überhaupt keine Ahnung was hier abgeht. Was würde sich am Beweis ändern, wenn ich probieren würde die rationalen Zahlen als überabzählbar zu beweisen?

Ich verzweifle.

Vielen Dank.

KVA

19.05.2019, 20:29

URL

Auf diesen Beitrag antworten »

RE: Beweis dass R überabzählbar ist
Wenn ich das recht verstehe, wird eine Intervallschachtelung mit $\begin{eqnarray*} f(n)\notin [a_n,b_n] \end{eqnarray*}$ konstruiert.
Würde man das Intervall jeweils halbieren, könnte f(n) genau an der Nahtstelle der beiden Intervalle liegen. Mit der Drittelung vermeidet man solche Pathologien. Man findet unter den drei Intervallen immer mindestens eins, das f(n) nicht enthält.
Die Intervallschachtelung enthält genau eine reelle Zahl. Würdest du dich auf die rationalen Zahlen beschränken. könnte die Intervallschachtelung leer sein. Deshalb funktioniert der Beweis nicht für die rationalen Zahlen.

19.05.2019, 20:31

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von KoenigVonAugsburg
Also zuersteinmal verstehe ich nicht warum ich hier das Intervall in 3 Teile aufteile

Das ist halt die Beweisidee. Nimm sie als gegeben hin. Man teilt ein Intervall in drei gleiche Teile. Warum auch nicht.

Zitat:

Original von KoenigVonAugsburg
warum f(n+1) nicht um linken und im rechten Intervall liegen kann(Oder ist hier gemeint, dass f(n+1) nicht gleichzeitig in beiden Intervallen liegen kann?).

Das ist in der Tat unglücklich ausgedrückt. Ich glaube, das Letzte ist gemeint: "nicht gleichzeitig".

Zitat:

Original von KoenigVonAugsburg
Außerdem verstehe ich diesem Satz nicht: "Wir wählen davon ein Intervall aus, indem es nicht liegt". Was für ein Sinn verbirgt sich hinter dieser Wahl des Intervalls?

Der Sinn dahinter ist, daß man später damit einen Widerspruch erhält. Die Intervallschachtelung definiert eine reelle Zahl $\begin{align*} \xi \end{align*}$ . Da $\begin{align*} f \end{align*}$ als surjektiv angenommen ist, muß es daher ein $\begin{align*} n_0 \end{align*}$ geben mit $\begin{align*} f(n_0) = \xi \end{align*}$ . Da $\begin{align*} \xi \end{align*}$ in allen Intervallen der Intervallschachtelung liegt, muß es auch in $\begin{align*} I_{n_0} \end{align*}$ liegen. Aber $\begin{align*} f(n_0) = \xi \end{align*}$ liegt nach Konstruktion gerade nicht in $\begin{align*} I_{n_0} \end{align*}$ . Ja was nun? Liegt nun $\begin{align*} \xi \end{align*}$ in $\begin{align*} I_{n_0} \end{align*}$ oder nicht? Aus diesem Widerspruch schließt man, daß die Annahme der Surjektivität falsch gewesen sein muß.

Zitat:

Original von KoenigVonAugsburg
Ich meine natürlich liegt eine Zahl die nicht im Intervall liegt nicht im Intervall. Warum wähle ich denn nicht das Intervall in der diese Zahl liegt?

Man weiß nur, daß $\begin{align*} f(n+1) \end{align*}$ nicht gleichzeitig im linken und rechten Drittel liegen kann. Wenn es nun zufällig im linken Drittel liegt, dann wählt man das rechte. Wenn es zufällig im rechten Drittel liegt, wählt man das linke. Und wenn es irgendwo ganz anders liegt, dann wählt man eines der beiden Randdrittel, das linke oder das rechte.

Interessant finde ich die Frage, warum bei diesem Beweis gedrittelt und nicht halbiert wird.

20.05.2019, 02:18

KoenigVonAugsburg

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Der Sinn dahinter ist, daß man später damit einen Widerspruch erhält. Die Intervallschachtelung definiert eine reelle Zahl $\begin{align*} \xi \end{align*}$ . Da $\begin{align*} f \end{align*}$ als surjektiv angenommen ist, muß es daher ein $\begin{align*} n_0 \end{align*}$ geben mit $\begin{align*} f(n_0) = \xi \end{align*}$ . Da $\begin{align*} \xi \end{align*}$ in allen Intervallen der Intervallschachtelung liegt, muß es auch in $\begin{align*} I_{n_0} \end{align*}$ liegen. Aber $\begin{align*} f(n_0) = \xi \end{align*}$ liegt nach Konstruktion gerade nicht in $\begin{align*} I_{n_0} \end{align*}$ . Ja was nun? Liegt nun $\begin{align*} \xi \end{align*}$ in $\begin{align*} I_{n_0} \end{align*}$ oder nicht? Aus diesem Widerspruch schließt man, daß die Annahme der Surjektivität falsch gewesen sein muß.

Wenn ich das doch richtig verstanden habe dann bilde ich alle natürlichen zahlen n auf die reellen Zahlen ab. Die Funktion der Abbildung ist dann mit f(n) definiert oder? Bei der Wahl des ersten und somit längsten Intervalls $\begin{align*} I_{n_{0}} \end{align*}$ wähle ich dann das Drittel in dem meine reelle Zahl nicht vorhanden ist, und sage am Schluss dass diese Zahl nicht abgebildet wurde, weil es nicht in Intervall enthalten ist oder wie? Ich kann doch genauso eine Intervallverschachtelung wählen, in der meine Zahl enthalten ist. Dann würde es heisen $\begin{align*} f(n_0) = \xi \end{align*}$ und $\begin{align*} \xi \end{align*}$ liegt in $\begin{align*} I_{n_0} \end{align*}$ .

Für $\begin{align*} \xi \end{align*}$ ist rational könnte ich doch genauso sagen:

Es muss ein $\begin{align*} n_{0} \end{align*}$ geben mit $\begin{align*} f(n_0) = \xi \end{align*}$ . Da $\begin{align*} \xi \end{align*}$ in allen Intervallen der Intervallschachtelung liegt, muß es auch in $\begin{align*} I_{n_0} \end{align*}$ liegen. Aber $\begin{align*} f(n_0) = \xi \end{align*}$ liegt nach Konstruktion gerade nicht in $\begin{align*} I_{n_0} \end{align*}$ . Wo ist hier der unterschied zu den reellen Zahlen?

Vergesse ich etwas, oder denke ich einfach zu unmathematisch?

Irgendwie verstehe ich gerade mein Problem nicht. Das Prinzip der Verschachtelung und Surjektivität habe ich verstanden. Ich nicht mal mehr was ich fragen soll um mein Logikproblem zu lösen verwirrt

20.05.2019, 14:37

URL

Auf diesen Beitrag antworten »

Zitat:

wähle ich dann das Drittel in dem meine reelle Zahl nicht vorhanden ist

Nein, die reelle Zahl wird erst durch die Intervallschachtelung bestimmt.

Du startest mit $\begin{eqnarray*} I_0=[0,1] \end{eqnarray*}$ , drittelst das Intervall und wählst aus den drei Intervallen eines aus, das $\begin{eqnarray*} f(1) \end{eqnarray*}$ nicht enthält. Das nennst du $\begin{eqnarray*} I_1 \end{eqnarray*}$ und damit ist dann $\begin{eqnarray*} f(1)\notin I_1 \end{eqnarray*}$ . Dann drittelst du $\begin{eqnarray*} I_1 \end{eqnarray*}$ , wählst ein Teilintervall, das $\begin{eqnarray*} f(2) \end{eqnarray*}$ nicht enthält und nennst das $\begin{eqnarray*} I_2 \end{eqnarray*}$ . So fortfahrend bekommst du eine Intervallschachtelung mit Intervallen $\begin{eqnarray*} I_n \end{eqnarray*}$ und für jedes $\begin{eqnarray*} n\in\mathbb{N} \end{eqnarray*}$ ist $\begin{eqnarray*} f(n)\notin I_n \end{eqnarray*}$ .
Die Intervallschachtelung erfasst genau eine reelle Zahl $\begin{eqnarray*} \xi \end{eqnarray*}$ . Für diese Zahl gilt also $\begin{eqnarray*} \xi\in I_n \end{eqnarray*}$ für jedes $\begin{eqnarray*} n\in\mathbb{N} \end{eqnarray*}$ . Weil andererseits $\begin{eqnarray*} f(n)\notin I_n \end{eqnarray*}$ ist, folgt $\begin{eqnarray*} \xi \neq f(n) \end{eqnarray*}$ und damit der gesuchte Widerspruch.

20.05.2019, 15:14

Leopold

Auf diesen Beitrag antworten »

Während ich meinen Beitrag schrieb, hat URL schon geantwortet. Ich veröffentliche ihn hier doch, weil er sehr ausführlich das ganze Vorgehen durchleuchtet.

Allein schon die Konstruktion von $\begin{align*} \xi \end{align*}$ ist in $\begin{align*} \mathbb{Q} \end{align*}$ gar nicht möglich. Denn $\begin{align*} \mathbb{Q} \end{align*}$ ist nicht vollständig. Nicht jede Intervallschachtelung besitzt dort ein Zentrum.

Das Wichtigste zum Verständnis scheint mir zu sein, daß du dich an die Reihenfolge hältst. Wenn deine Gedanken kreuz und quer durch die Konstruktion irren, wirst du das nicht verstehen. Ich versuche einmal, Ordnung in den Laden zu bringen.

Eigentlich wollen wir zeigen, daß es keine surjektive Abbildung von $\begin{align*} \mathbb{N} \end{align*}$ nach $\begin{align*} \mathbb{R} \end{align*}$ gibt. Um das zu tun, nehmen wir das Gegenteil an, wir hätten eine solche surjektive Abbildung. Und von deren Existenz ausgehend, basteln wir uns einen Widerspruch.

Sei also $\begin{align*} f \end{align*}$ unterstelltermaßen surjektiv. Für irgendein $\begin{align*} n \end{align*}$ wird zum Beispiel $\begin{align*} 4001 \end{align*}$ getroffen, vielleicht

$\begin{align*} f(37379574974875910) = 4001 \end{align*}$

Für ein anderes $\begin{align*} n \end{align*}$ wird $\begin{align*} \frac{7}{6} = 1{,}1666 \ldots \end{align*}$ getroffen, vielleicht

$\begin{align*} f(357897902343624687687656186350065974754877544121236967495) = \frac{7}{6} \end{align*}$

Mit wieder einem anderen $\begin{align*} n \end{align*}$ erreicht man $\begin{align*} - \pi = -3{,}14159 \ldots \end{align*}$ , vielleicht

$\begin{align*} f(600003458902224593849029345457979767306754740807345067070675) = - \pi \end{align*}$

Und so kann man, wie wir unterstellen, zu jeder reellen Zahl $\begin{align*} t \end{align*}$ ein $\begin{align*} n \end{align*}$ finden mit $\begin{align*} f(n) = t \end{align*}$ .

Dieses $\begin{align*} f \end{align*}$ ist nun da. Wie es genau aussehen könnte, weiß kein Mensch. (Wir wollen ja sogar zeigen, daß es gar kein solches $\begin{align*} f \end{align*}$ geben kann.) Was wir nur wissen: Jede reelle Zahl $\begin{align*} t \end{align*}$ wird über $\begin{align*} f \end{align*}$ durch ein gewisses $\begin{align*} n \end{align*}$ erfaßt: $\begin{align*} f(n) = t \end{align*}$ .

Nun beginnen wir mit dem Intervall $\begin{align*} I_0 = [0,1] \end{align*}$ und teilen es in drei gleiche Teile auf:

$\begin{align*} I_0 = \left[ 0 , \frac{1}{3} \right] \cup \left[ \frac{1}{3} , \frac{2}{3} \right] \cup \left[ \frac{2}{3} , 1 \right] \end{align*}$

Jetzt kommt unser $\begin{align*} f \end{align*}$ ins Spiel. Wir schauen uns $\begin{align*} f(1) \end{align*}$ an. Vielleicht ist $\begin{align*} f(1) = - \sqrt{2} = - 1{,}414 \ldots \end{align*}$ . Diese Zahl liegt weder im linken noch im rechten Drittel, also sind wir frei in der Drittelwahl. Wir nehmen

$\begin{align*} I_1 = \left[ \frac{2}{3} , 1 \right] \end{align*}$

und teilen dieses Intervall in drei gleichgroße Drittel auf:

$\begin{align*} I_1 = \left[ \frac{2}{3} , \frac{7}{9} \right] \cup \left[ \frac{7}{9} , \frac{8}{9} \right] \cup \left[ \frac{8}{9} , 1 \right] \end{align*}$

Jetzt kommt $\begin{align*} f(2) \end{align*}$ an die Reihe. Keine Ahnung, was das für ein Wert ist, vielleicht $\begin{align*} f(2) = \sqrt{0{,}9} = 0{,}948 \ldots \end{align*}$ . Diese Zahl liegt nun im rechten Drittel. Das können wir daher nicht nehmen. Wir wählen daher

$\begin{align*} I_2 = \left[ \frac{2}{3} , \frac{7}{9} \right] \end{align*}$

Und so machen wir das immer weiter.

Die Intervalle liegen ineinander drin: $\begin{align*} I_0 \supset I_1 \supset I_2 \supset \ldots \end{align*}$ , und ziehen sich zusammen: $\begin{align*} I_0 \end{align*}$ hat Länge 1, $\begin{align*} I_1 \end{align*}$ hat Länge $\begin{align*} \frac{1}{3} \end{align*}$ , $\begin{align*} I_2 \end{align*}$ hat Länge $\begin{align*} \frac{1}{3^2} = \frac{1}{9} \end{align*}$ und so weiter. Alles vorhanden, was man zu einer anständigen Intervallschachtelung braucht. Nach dem Vollständigkeitsaxiom existiert eine eindeutig bestimmte reelle Zahl $\begin{align*} \xi \end{align*}$ , welche in allen Intervallen der Intervallschachtelung liegt.

Wegen der Surjektivität von $\begin{align*} f \end{align*}$ muß auch dieses $\begin{align*} \xi \end{align*}$ von $\begin{align*} f \end{align*}$ getroffen werden, vielleicht $\begin{align*} f(20052019) = \xi \end{align*}$ . Jetzt sind wir neugierig und schauen uns einmal genau das Intervall $\begin{align*} I_{20052019} \end{align*}$ an. Da es zur Intervallschachtelung gehört:

$\begin{align*} I_0 \supset I_1 \supset I_2 \supset \ldots \supset I_{20052018} \supset I_{20052019} \supset I_{20052020} \supset \ldots \end{align*}$

aber $\begin{align*} \xi \end{align*}$ in allen Intervallen der Intervallschachtelung liegt (Vollständigkeitsaxiom), muß es auch speziell in diesem Intervall liegen: $\begin{align*} \xi \in I_{20052019} \end{align*}$ . Bei der Wahl von $\begin{align*} I_{20052019} \end{align*}$ waren wir aber doch gerade so vorgegangen, daß $\begin{align*} f(20052019) \not \in I_{20052019} \end{align*}$ . Und $\begin{align*} f(20052019) \end{align*}$ ist ja gerade $\begin{align*} \xi \end{align*}$ , also $\begin{align*} \xi \not \in I_{20052019} \end{align*}$ .

Und jetzt stecken wir in der Klemme. Das logische Attentat auf unseren Verstand ist, einzugestehen, daß $\begin{align*} \xi \end{align*}$ sowohl in $\begin{align*} I_{20052019} \end{align*}$ liegt als auch nicht in $\begin{align*} I_{20052019} \end{align*}$ liegt. Das macht uns richtig fertig. Und wir können nicht zulassen, daß so etwas möglich ist, wenn wir einigermaßen bei Verstand sind. Was hat uns aber in diese Bredouille gebracht, wir haben uns bei der Konstruktion von $\begin{align*} \xi \end{align*}$ doch an alle Spielregeln gehalten? Der ganze Schlamassel muß ganz vorne angefangen haben, als wir von der Existenz einer surjektiven Abbildung $\begin{align*} f: \, \mathbb{N} \to \mathbb{R} \end{align*}$ ausgegangen sind. Wenn es sie gäbe, könnten wir diese Konstruktion machen und würden uns in Widersprüchen verheddern. Als kann es diese Funktion nicht geben.

Es gibt keine surjektive und damit keine bijektive Abbildung $\begin{align*} f: \, \mathbb{N} \to \mathbb{R} \end{align*}$ .

20.05.2019, 17:44

KoenigVonAugsburg

Auf diesen Beitrag antworten »

Ach, jetzt hats Klick gemacht. Habs verstanden! Vielen Dank euch allen!

Neue Frage »

Antworten »

Beweis dass R überabzählbar ist

Verwandte Themen