Thema: Aufgabe: Überabzählbarkeit (Menge/Obermenge) |
|
Stimmt Du hast Recht! Ich habe zu kompliziert nachgedacht, die Lösung ist ja viel einfacher...
Jedenfalls möchte ich mich für Deine Unterstützung bedanken! Dadurch konnte ich mein Verständnis verbessern.
Mit freundlichen Grüßen,
cyberjohn
|
|
Thema: Aufgabe: Überabzählbarkeit (Menge/Obermenge) |
|
Dennoch würde der Widerspruchsbeweis für diese Aufgabe nicht ausreichen... D,h. die Aufgabe ist nicht ganz erfüllt. Wie kann man nun beweisen, dass jede Obermenge einer überabzählbaren Menge überabzählbar ist?
Mein Vorschlag:
Die Menge aller Abbildungen f: X*->X* ist überabzählbar und kann nicht durch einen Algorithmus berechnet werden.
Mit freundlichen Grüßen,
cyberjohn
|
|
Thema: Aufgabe: Grundlagen der Programmierung |
|
Hallo Karlito,
Ich bin mir nicht sicher, aber man müsste die Funktionen g0, g1, g2,... und ihre Argumente w0, w1, w2,... in einer Tabelle anordnen (Prinzip der Diagonalisierung) und erhält die Dialogelemente gk(wk). g weicht dann von jeder beliebigen Funktion fi, ieN, an der Stelle wi ab und kann daher nicht in der Abzählung f0,f1,f2,... vorkommen.
Ist das korrekt?
Mit freundlichen Grüßen,
cyberjohn
|
|
Thema: Aufgabe: Überabzählbarkeit (Menge/Obermenge) |
|
Hallo Karlito,
Beim indirekten Beweis (Widerspruchsbeweis) wird eine Aussage (A -> B) dadurch bewie-
sen, dass man zeigt: "Aus B folgt A , also ein Widerspruch zu A".
Beispiel: Beweisen Sie das Schubfachprinzip für neN:
Hat man n+1 Objekte in n Schubfächer verteilt, so gibt es mindestens ein Schubfach,
in dem zwei (oder mehr) Objekte liegen.
Lösung: Der Satz hat die Form "A -> B" mit:
A: n+1 Objekte sind in n Schubfächer verteilt.
B: Es gibt mindestens ein Schubfach mit 2 (oder mehr) Objekten.
Angenommen, es gälte B : Jedes Schubfach enthält höchstens 1 Objekt. Dann wären in al-
len Schubladen zusammen n mal höchstens 1 Objekt, also höchstens n Objekte. Dies ist ein
Widerspruch zu A, dass n+1 Objekte in den Schubfächern liegen. Also gilt nicht B -> nicht A ,ist (A -> B) richtig. .
Wenn die Obermenge abzählbar wäre, dann wären die Mengen ebenso abzählbar.
Ist das richtig?
Mit freundlichen Grüßen,
cyberjohn
|
|
Thema: Aufgabe: Algorithmen |
|
Hallo Karlito,
vielen Dank für Deine schnelle Antwort! Ich habe das Halteproblem von Turingmaschinen bei Wikipedia durchgelesen. Da ich erst im 2. Semester Theoretische Informatik belegen werde, ist es für mich schwierig die Aufgaben im Bereich Programmierung zu verstehen.
Nochmals Dankeschön für Deine Unterstützung!
Mit freundlichen Grüßen,
cyberjohn
|
|
Thema: Aufgabe: Algorithmen |
|
Meine Frage:
Hallo,
ich habe eine Aufgabe zu Algorithmen erhalten, weiß aber nicht wie man diese lösen kann. Die Aufgabe befindet sich im Anhang.
Meine Ideen:
a) Man kann X* nicht lösen, weil "*" überabzählbar ist und somit kann kein Algorithmus für beliebige Algorithmen gelten bzw. terminieren.
b) Könnte berechenbar sein f(alpha)=(w), aber aeX* ist überabzählbar und dadurch kann man die Aufgabe nicht terminieren.
Sei E eine beliebige Eigenschaft, die von mind. einer, aber nicht von allen berechenbaren Funktionen f: X*->X* erfüllt wird, dann gibt es keinen Algorithmus, der für beliebige Algorithmen (alpha)eX* ausgibt, ob f(alpha) die Eigenschaft erfüllt oder nicht. Das bedeutet, dass die Aufgabe, einem Algorithmus "anzusehen", ob die durch ihn berechenbare Funktion eine bestimmte Eigenschaft besitzt, nicht algorithmisch gelöst werden kann.
Sind meine Ideen schon auf den richtigen Weg oder ist mein Ansatz komplett falsch?
Mit freundlichen Grüßen,
cyberjohn
|
|
Thema: Aufgabe: Überabzählbarkeit (Menge/Obermenge) |
|
Meine Frage:
Hallo,
ich habe eine Aufgabe erhalten und muss beweisen, dass "Jede Obermenge einer überabzählbaren Menge überabzählbar ist."
Meine Ideen:
Beispiel: Die Menge der rationalen Zahlen Q ist abzählbar.
Mit freundlichen Grüßen,
cyberjohn
|
|
Thema: Aufgabe: Grundlagen der Programmierung |
|
Meine Frage:
Hallo,
ich habe eine Aufgabe im Bereich Programmierung erhalten, bin mir aber nicht sicher, wie man diese lösen kann. Die Aufgabe befindet sich im Anhang.
Mit freundlichen Grüßen,
cyberjohn
Meine Ideen:
a) Das Cantor'sche Diagonalverfahren:
1/1->1/2->1/3->1/4 ...
2/1->2/2->2/3->2/4 ...
3/1->3/2->3/3 ... ...
4/1->4/2 ... ... ...
... ... ... ... ...
b) M ist abzählbar und f ist total
|
|
|