Überabzählbarkeit von Funktion < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:12 Mi 20.06.2007 | | Autor: | Marujah |
Hallo,
Ich habe ein kleines Problem bei einer Aufgabe der Theoretischen Informatik. Ich soll zeigen dass | IN --> {0,1} | > | IN |. Ich komm gar nicht voran :(. Hat jemand 'ne Idee.
gruss Marujah
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Hallo,
> Ich habe ein kleines Problem bei einer Aufgabe der
> Theoretischen Informatik. Ich soll zeigen dass | IN -->
> {0,1} | > | IN |.
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Wenn ich mir das, was Du schreibst, mal übersetze, heißt das ja, daß Du zeigen sollst, daß die Anzahl der Folgen in [mm] \{0,1\} [/mm] nicht abzählbar ist.
(Die Folgen sind ja gerade Abbildungen von [mm] \IN [/mm] in eine andere Menge, hier in [mm] \{0,1\}.)
[/mm]
Für den Beweis kannst Du davon ausgehen, daß es eine Bijektion [mm] \phi [/mm] der natürlichen Zahlen auf die Menge F der Folgen in [mm] \{0,1\} [/mm] gibt, daß man die genannten Folgen also abzählen kann. Dieses führe dann zum Widerspruch.
Ich gehe davon aus, daß Ihr in der Vorlesung gezeigt habt, daß die reellen Zahlen oder [0,1] nicht abzählbar sind.
An diesem Beweis kannst Du Dich orientieren.
Statt daß Du Dezimalzahlen [mm] 0,x_1x_2x_3x_4 [/mm] betrachtest,
hast Du es nun mit einer Aufreihung von Folgengliedern zu tun:
[mm] \phi(1)=Folge1: f_1(1), f_1(2), f_1(3), f_1(4)...
[/mm]
[mm] \phi(2)=Folge2: f_2(1), f_2(2), f_2(3), f_2(4)...
[/mm]
[mm] \phi(3)=Folge3: f_3(1), f_3(2), f_3(3), f_3(4)... [/mm]
[mm] \vdots
[/mm]
Betrachten tust Du dann die neue Folge [mm] f:\overline{f_1(1)} [/mm] , [mm] \overline{f_2(2)}, \overline{f_3(3)},...
[/mm]
mit [mm] \overline{f_i(i)}=\begin{cases} 0, & \mbox{für } f_i(i)=1 \mbox{ } \\ 1, & \mbox{für } f_i(i)=0 \mbox{ } \end{cases}
[/mm]
Sie unterscheidet sich von allen vorhergehenden Folgen, denn sie hat jeweils an der i-ten Stelle einen anderen Wert als [mm] f_i. [/mm]
Und sie ist nicht [mm] \in \phi(\IN).
[/mm]
Schau Dir, wie gesagt den Beweis für die reellen Zahlen an, wenn Du noch Fragen hast, kannst Du Dich ja melden.
Gruß v. Angela
|
|
|
|
