Überabzählbarkeit und Diagonal < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | [Externes Bild http:///www.dropbox.com/s/js55cthg2kf2q46/Theoretische%20Informatik.PNG] |
Hallo,
Ich bin Informatik Student und bräuchte eine kurze Hilfestellung zu der Aufgabe in der Bilddatei. Tut mir leid das ich auf eine Bilddatei zurückgreifen musste, aber ich habe es mit LaTex versucht, ohne Erfolg.
Zunächt erstmal zu meinen jetzigen Wissensstand:
Mir ist das Prinzip des Diagonalisierbarkeitverfahrens teilweise bekannt: Man bildet eine Tabelle oder eine Matrix aus allen X und Y Werten, betrachtet dann die Diagonale und erhöht sie dann um 1 (Richtig so?). Aber wie man jetzt aus dem Ergebnis herausleiten kann ob eine Menge unendlich viele Reele Zahlen enthält ist mir nicht bewusst.
Wenn ihr mir einpaar Tipps bieten könntet wäre ich euch dankbar.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo KingTomaHawk, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> [Externes Bild http:///www.dropbox.com/s/js55cthg2kf2q46/Theoretische%20Informatik.PNG]
> Hallo,
>
> Ich bin Informatik Student und bräuchte eine kurze
> Hilfestellung zu der Aufgabe in der Bilddatei. Tut mir leid
> das ich auf eine Bilddatei zurückgreifen musste, aber ich
> habe es mit LaTex versucht, ohne Erfolg.
Hm. Das wäre auch Arbeit. Wir kennen den Diagonalisierungsbeweis aber auch so...
> Zunächt erstmal zu meinen jetzigen Wissensstand:
> Mir ist das Prinzip des Diagonalisierbarkeitverfahrens
> teilweise bekannt: Man bildet eine Tabelle oder eine Matrix
> aus allen X und Y Werten, betrachtet dann die Diagonale und
> erhöht sie dann um 1 (Richtig so?).
Du sollst dezimal arbeiten. Da brauchst Du noch die Zusatzregel, dass aus der Ziffer 9 dann eine Null wird.
> Aber wie man jetzt aus
> dem Ergebnis herausleiten kann ob eine Menge unendlich
> viele Reele Zahlen enthält ist mir nicht bewusst.
Wenn man die Diagonale wiederum als Dezimalzahl liest, dann ist diese Zahl doch mit keiner der bisherigen identisch, sondern unterscheidet sich garantiert in mindestens einer Ziffer.
Also war die Liste vorher nicht vollständig. Widerspruch.
> Wenn ihr mir einpaar Tipps bieten könntet wäre ich euch
> dankbar.
Reicht das?
Sonst findest Du zum Thema "Cantors Diagonalbeweis" leicht Unmengen lange Erklärungen im Netz, manche davon auch hübsch aufbereitet.
Grüße
reverend
|
|
|
| |
|
> Hallo KingTomaHawk,
>
> >
> [Externes Bild http:///www.dropbox.com/s/js55cthg2kf2q46/Theoretische%20Informatik.PNG]
> > Hallo,
> >
> > Ich bin Informatik Student und bräuchte eine kurze
> > Hilfestellung zu der Aufgabe in der Bilddatei. Tut mir leid
> > das ich auf eine Bilddatei zurückgreifen musste, aber ich
> > habe es mit LaTex versucht, ohne Erfolg.
>
> Hm. Das wäre auch Arbeit. Wir kennen den
> Diagonalisierungsbeweis aber auch so...
>
> > Zunächt erstmal zu meinen jetzigen Wissensstand:
> > Mir ist das Prinzip des Diagonalisierbarkeitverfahrens
> > teilweise bekannt: Man bildet eine Tabelle oder eine Matrix
> > aus allen X und Y Werten, betrachtet dann die Diagonale und
> > erhöht sie dann um 1 (Richtig so?).
>
> Du sollst dezimal arbeiten. Da brauchst Du noch die
> Zusatzregel, dass aus der Ziffer 9 dann eine Null wird.
>
> > Aber wie man jetzt aus
> > dem Ergebnis herausleiten kann ob eine Menge unendlich
> > viele Reele Zahlen enthält ist mir nicht bewusst.
Weil du im Intervall ]0|1[ bist, ist dies ganz einfach: Betrachte nur die Zahlenfolge
0,1 | 0,11 | 0,111 | 0,1111 | 0,11111 ...
Allein das sind schon unendlich viele reelle Zahlen.
Es ist noch viel schlimmer: Du sollst nicht nur zeigen, dass die Menge unendlich viele reelle Zahlen enthält, sondern überabzählbar viele. Das bedeutet: Man findet keine "Kette", in der alle Zahlen hintereinander aufgereiht sind und in der dann keine Zahl fehlt.
Deshalb:
>
> Wenn man die Diagonale wiederum als Dezimalzahl liest, dann
> ist diese Zahl doch mit keiner der bisherigen identisch,
> sondern unterscheidet sich garantiert in mindestens einer
> Ziffer.
> Also war die Liste vorher nicht vollständig.
> Widerspruch.
>
> > Wenn ihr mir einpaar Tipps bieten könntet wäre ich euch
> > dankbar.
>
> Reicht das?
> Sonst findest Du zum Thema "Cantors Diagonalbeweis" leicht
> Unmengen lange Erklärungen im Netz, manche davon auch
> hübsch aufbereitet.
>
> Grüße
> reverend
Tipp zu b) Multipliziere mal alle Zahlen aus ]0|1[ mit einem festen Faktor r.
|
|
|
| |
|
Also, deine Begründung warum es unendlich viele Zahlen seien sollen kling für mich logisch, aber ich muss es ja mit dem Diagonalisierbarkeits-Verfahren zeigen und das Verstehe ich noch nicht so ganz.
Ich habe es eine Tabelle angelegt die so ähnlich ausssieht:
[mm] \vmat{ - & -2/3 \\ -1/2 & -1/3 \\ 1/2 & 1/3 \\ - & 2/3 } [/mm] usw...
Theoretisch müsste ich jetzt die Diagonale nehmen und auf alle Werte dort (+1) rechnen:
[mm] \vmat{ - & (-2/3)+1 \\ (-1/2)+1 & -1/3 \\ 1/2 & 1/3 \\ - & 2/3 }
[/mm]
Aber in meinen Augen beweißt das gar nichts :/
Ist das denn richtig?
Und deinen anderen Tipp habe ich ganz ehrlich nicht verstanden.
|
|
|
| |
|
Hallo nochmal,
ah, da ist der Fehler... 
> Also, deine Begründung warum es unendlich viele Zahlen
> seien sollen kling für mich logisch, aber ich muss es ja
> mit dem Diagonalisierbarkeits-Verfahren zeigen und das
> Verstehe ich noch nicht so ganz.
>
> Ich habe es eine Tabelle angelegt die so ähnlich
> ausssieht:
> [mm]\vmat{ - & -2/3 \\ -1/2 & -1/3 \\ 1/2 & 1/3 \\ - & 2/3 }[/mm]
> usw...
Aha! Und die nächste Spalte enthält dann alle "Viertelbrüche" mit Betrag <1, ja?
Genau darum geht es beim Diagonalbeweis nicht.
Die rationalen Zahlen sind nämlich abzählbar und können tatsächlich alle in eine Reihenfolge gebracht werden, sogar incl. der unechten und der ungekürzten Brüche.
Hattet Ihr schon das kartesische Produkt von Mengen? Dann ist die Abzählbarkeit von [mm] \IQ [/mm] nämlich ziemlich offensichtlich.
> Theoretisch müsste ich jetzt die Diagonale nehmen und auf
> alle Werte dort (+1) rechnen:
> [mm]\vmat{ - & (-2/3)+1 \\ (-1/2)+1 & -1/3 \\ 1/2 & 1/3 \\ - & 2/3 }[/mm]
Nein, wie gesagt, darum geht es nicht.
> Aber in meinen Augen beweißt das gar nichts :/
Stimmt, es beweist überhaupt nichts.
> Ist das denn richtig?
Nein.
> Und deinen anderen Tipp habe ich ganz ehrlich nicht
> verstanden.
Welchen? Den von HJKweseleit, oder meinen Tipp, mal das Internet zu bemühen? 
Schau ![[]](/images/popup.gif) hier, da spare ich mir viel Schreibarbeit.
Dort ist allerdings eine andere Ersetzungsregel für die Diagonale definiert, die aber das Hauptargument nicht verändert.
Grüße
reverend
|
|
|
| |
|
Erstmal Danke, für die ganzen infos.
>Schau hier, da spare ich mir viel Schreibarbeit.
Die Wikipedia Seite hatte ich schon gefunden, nur kam bei mir das Problem, dass ich Irgendwie kein Schema zur errechnung von a11 a12 etc finde, oder besser gesagt woher Stammen die Werte?
Ich weiß vorrechenen ist hier nicht erlaubt, aber ein Beispiel mit anderen Werten wäre auch super hilfreich.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:51 Mo 11.11.2013 | | Autor: | leduart |
Hallo
erstmal stell dir alle Zalen als Dezimalzahlen vor.
Nimm an man kann sie durchzählen mit z1,z2,z3.....
Nachdem alle Zahlen eine Nummer haben, wird jetzt gesagt, ich finde eine die noch nicht nummeriert ist, dann habe ich einen Widerspruch und ich kann sie nicht nummerieren abzählen
jetz die Schilderung, wie die neue Zahl entsteht: ich nehme als erste Ziffer die 1, wenn z1 nicht mit 1 anfängt, sonst die 0. als 2 te Ziffer nehm ich wieder 1 wenn z2 an 2 ter Stelle keine 1 hat sonst 0
meine nte Ziffer schau ich auf die nte Stelle von [mm] z_n [/mm] und mache die zu 1 (oder 0
Jetzt ist sicher, dass meine neue Zahl sicher nicht in z1 bis zn vorkommt, denn von all denen unterscheidet sie sich an mindestens einer Stelle.
so kann ich bis zu jedem N, beliebig groß weitermachen, meine neue Zahl ist nicht unter ihnen. es gibt also garantiert keine Zahl n mit der sie nummeriert ist. Damit hab ich einen Widerspruchsbeweis, zu der anfänglichen Aussage, dass die zahlen alle eine nummer haben, also abzählbar sind
Widerspruchsbeweise sind oft schwer zu verstehen, weil sie nicht wirklich "konstruktiv" sind, also am Ende des Beweises kennst du weder einen echten Versuch der Nummerierung, (der ist ja im nachhinen auch unmöglich) noch die unnummerierte Zahl.
Gruss leduart
|
|
|
|
