Natürl. Zahlen überabzählbar? < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:08 Mi 24.04.2013 | | Autor: | davux |
| Aufgabe | Es ist bekannt, dass die Menge aller natürlichen zahlen abzählbar ist. der folgende Diagonalisierungsbeweis (Cantors zweites Diagonalargument) zeigt genau das Gegenteil, nämlich dass die natürlichen Zahlen überabzählbar sind! Analysieren Sie diesen beweis und erklären Sie, wo der Fehler steckt:
Zu zeigen: Die Menge aller natürlichen Zahlen ist überabzählbar.
Annahme: Wir nehmen an, [mm] \IN [/mm] sei abzählbar (Beweis durch Widerspruch).
Dann gibt es eine Abzählung, welche alle natürlichen zahlen enthält, der Art:
[mm] n_{1,1}n_{1,2}n_{1,3}... [/mm] (erste natürliche Zahl in der Abzählung)
[mm] n_{2,1}n_{2,2}n_{2,3}... [/mm] (zweite natürliche Zahl in der Abzählung)
[mm] n_{3,1}n_{3,2}n_{3,3}... [/mm] (zweite natürliche Zahl in der Abzählung)
.
.
.
Hierbei bezeichnet [mm] $n_{i,j}$ [/mm] die $j$-te Stelle (von links) der $i$-ten Zahl (in der Abzählung), und es gibt [mm] $n_{i,j}\in\{0,1,2,...,9\}$. [/mm] Beachten Sie, dass dies eine Darstellung einer ganz beliebigen Abzählung ist (und keiner willkürlich gewählten konkreten Abzählung)!
Nun konstruieren wir eine Zahl $n$ (unser Diagonalelement) wie folgt: für alle [mm] $i\in\IN$ [/mm] ist die $i$-te Stelle unserer Zahl $n$ definiert durch [mm] $n_i=n_{i,i}+1$, [/mm] falls [mm] $n_{i,i}<9$, [/mm] und [mm] n_i=0, [/mm] falls [mm] $n_{i,i}=9$. [/mm] Wenn die $i$-te Zahl in der Abzählung zu kurz ist, es also kein [mm] n_{i,i} [/mm] gibt, dann setzen wir für [mm] n_i [/mm] eine beliebige Ziffer ein.
Damit gilt nun offensichtlich: $n$ ist verschieden von jeder in der Abzählung vorkommenden Zahl. Ergo kommt $n$ nicht in der Abzählung vor und die Abzählung ist nicht vollständig. Da wir eine ganz allgemeine Darstellung für eine beliebige Abzählung gewählt haben, kann es also keine vollständige Abzählung für [mm] $\IN$ [/mm] geben. Fazit: [mm] $\IN$ [/mm] ist überabzählbar. |
Hallo,
schau mir das schon eine Weile an, aber ich glaube, ich komme heute zu nichts mehr, weil ich meine Ansätze kaum zu Ende denken kann. Liegt der Fehler in der Abzählung, liegt er in der Konstruktion der Zahl? Warum kann man das zweite Diagonalargument nicht auf die natürlichen Zahlen anwenden?
Nun ja, ich wollte die Aufgabe auf jeden Fall schonmal stehen haben, weil ich morgen sicher noch etwas weiterkomme. Aber wer Lust hat, darf gerne selbst etwas dazu schreiben. Ich finde es ja interessant.
Gruss,
Dave
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:31 Mi 24.04.2013 | | Autor: | Marcel |
Hallo,
> Es ist bekannt, dass die Menge aller natürlichen zahlen
> abzählbar ist. der folgende Diagonalisierungsbeweis
> (Cantors zweites Diagonalargument) zeigt genau das
> Gegenteil, nämlich dass die natürlichen Zahlen
> überabzählbar sind! Analysieren Sie diesen beweis und
> erklären Sie, wo der Fehler steckt:
>
> Zu zeigen: Die Menge aller natürlichen Zahlen ist
> überabzählbar.
> Annahme: Wir nehmen an, [mm]\IN[/mm] sei abzählbar (Beweis durch
> Widerspruch).
> Dann gibt es eine Abzählung, welche alle natürlichen
> zahlen enthält, der Art:
>
> [mm]n_{1,1}n_{1,2}n_{1,3}...[/mm] (erste natürliche Zahl in der
> Abzählung)
> [mm]n_{2,1}n_{2,2}n_{2,3}...[/mm] (zweite natürliche Zahl in der
> Abzählung)
> [mm]n_{3,1}n_{3,2}n_{3,3}...[/mm] (zweite natürliche Zahl in der
> Abzählung)
> .
> .
> .
>
> Hierbei bezeichnet [mm]n_{i,j}[/mm] die [mm]j[/mm]-te Stelle (von links) der
> [mm]i[/mm]-ten Zahl (in der Abzählung), und es gibt
> [mm]n_{i,j}\in\{0,1,2,...,9\}[/mm]. Beachten Sie, dass dies eine
> Darstellung einer ganz beliebigen Abzählung ist (und
> keiner willkürlich gewählten konkreten Abzählung)!
> Nun konstruieren wir eine Zahl [mm]n[/mm] (unser Diagonalelement)
> wie folgt: für alle [mm]i\in\IN[/mm] ist die [mm]i[/mm]-te Stelle unserer
> Zahl [mm]n[/mm] definiert durch [mm]n_i=n_{i,i}+1[/mm], falls [mm]n_{i,i}<9[/mm], und
> [mm]n_i=0,[/mm] falls [mm]n_{i,i}=9[/mm]. Wenn die [mm]i[/mm]-te Zahl in der
> Abzählung zu kurz ist, es also kein [mm]n_{i,i}[/mm] gibt, dann
> setzen wir für [mm]n_i[/mm] eine beliebige Ziffer ein.
> Damit gilt nun offensichtlich: [mm]n[/mm] ist verschieden von jeder
> in der Abzählung vorkommenden Zahl. Ergo kommt [mm]n[/mm] nicht in
> der Abzählung vor und die Abzählung ist nicht
> vollständig. Da wir eine ganz allgemeine Darstellung für
> eine beliebige Abzählung gewählt haben, kann es also
> keine vollständige Abzählung für [mm]\IN[/mm] geben. Fazit: [mm]\IN[/mm]
> ist überabzählbar.
>
> Hallo,
>
> schau mir das schon eine Weile an, aber ich glaube, ich
> komme heute zu nichts mehr, weil ich meine Ansätze kaum zu
> Ende denken kann. Liegt der Fehler in der Abzählung, liegt
> er in der Konstruktion der Zahl? Warum kann man das zweite
> Diagonalargument nicht auf die natürlichen Zahlen
> anwenden?
> Nun ja, ich wollte die Aufgabe auf jeden Fall schonmal
> stehen haben, weil ich morgen sicher noch etwas
> weiterkomme. Aber wer Lust hat, darf gerne selbst etwas
> dazu schreiben. Ich finde es ja interessant.
denke mal über die Anzahl der Stellen der konstruierten Zahl [mm] $n\,$ [/mm] nach - wenn
es eine natürliche Zahl ist, also $n [mm] \in \IN$ [/mm] sein soll, muss [mm] $n\,$ [/mm] ENDLICH VIELE
Stellen haben! Folgt das aus der obigen Konstruktion?
P.S. Die natürlichen Zahlen sind übrigens abzählbar etwa deswegen, weil
es eine Surjektion [mm] $\IN \to \IN$ [/mm] gibt - nämlich einfach die Identität auf [mm] $\IN$
[/mm]
(die ist ja "sogar" bijektiv)! Denn Definition: [mm] $M\,$ [/mm] heißt abzählbar (im Sinne
von endlich oder abzählbar unendlich), wenn es eine Surjektion [mm] $\IN \to [/mm] M$
gibt! Welche Definition liegt Euch eigentlich zugrunde?
Gruß,
Marcel
|
|
|
|
