Halteproblem

[elevar]

Er hätte aber sicher eine Menge Spaß damit gehabt...

[Beowulf]

Dass dich selbst Autoritäten wie Cantor oder gar Jan nicht zum zweifeln oder auch nur grübeln bringen, zeugt von beeindruckendem Selbstvertrauen

Natürlich bringen sie mich zum Grübeln! Oder meinst du, man solle von gewissen "Autoritäten" alles unbesehen glauben? Nein, das gehört doch eher in den Religions-Thread! Auch gibt es keine Garantie, dass ein Beweis, der auf Cantor verweist, wirklich vollständig oder korrekt ist. Oft werden Dinge aus dem Zusammenhang gerissen.

Streng genommen muss das nicht bewiesen werden, das ist naemlich genau die Aussage vom Aussonderungsaxiom.

Cantor hat die naive Mengenlehre benutzt. Als die Zermelo-Fraenkel-Mengenlehre entwickelt wurde, war dieser wohl schon tot. Das Aussonderungsaxiom soll gerade die Paradoxien vermeiden, die bei der naiven Mengenlehre eben nun mal entstehen.

Aber ich will versuchen, es dir plausibel zu machen: A = {x Element von X | x kein Element von f(x)} ist eine Teilmenge von X. Vielleicht die leere, vielleicht nicht die leere. Aber es ist auf jeden Fall eine Teilmenge von X. Und weil P(X) alle Teilmengen von X enthaelt, enthaelt P(X) insbesondere auch A.

Aber meiner Meinung nach enthält die Definition von A eine "unzulässige Referenz" auf f(x). Das "Prädikat", welches bestimmt, welche x der Menge A zugehörig sind, ist zweistellig, also trifft das Aussonderungsaxiom (wenn man dieses denn nun unbedingt benutzen möchte) darüber keine Aussagen. Zusätzlich dazu ist einer der Eingabewerte des zweistelligen Prädikats die Abbildung selber, die bestimmt, ob das Prädikat denn nun zutrifft oder nicht. Wirkt auf mich wie ein Zirkelschluss.

1. Millionen von Mathestudenten, die das in ihrem Studium mal gesehen haben, und alle Mathematik-Professoren auf der Welt haben den Beweis faelschlicherweise fuer korrekt gehalten.
2. Der Beweis ist korrekt.

Gibst du wenigstens zu, das Moeglichkeit 2 die wahrscheinlichere ist?

Ich lasse mir da kein falsches Dilemma aufzwängen! Ich finde es vieeel wahrscheinlicher, dass der Beweis zwar korrekt, aber nur auszugsweise zitiert und/oder nur teilweise verstanden wird.

[DasJan]

Oder meinst du, man solle von gewissen "Autoritäten" alles unbesehen glauben?

Auch Cantor hat sich mit Sicherheit mal geirrt. In dieser Sache aber nicht, das waere inzwischen jemandem aufgefallen.

Ich lasse mir da kein falsches Dilemma aufzwängen! Ich finde es vieeel wahrscheinlicher, dass der Beweis zwar korrekt, aber nur auszugsweise zitiert und/oder nur teilweise verstanden wird.

Lass mich meine These anders formulieren. Es gibt zwei Moeglichkeiten:
1. Millionen von Mathestudenten, die das in ihrem Studium mal gesehen haben, und alle Mathematik-Professoren auf der Welt haben diese Formulierung des Beweises faelschlicherweise fuer vollstaendig gehalten.
2. Der Beweis ist so, wie er da steht, vollstaendig.

Wenn es dir lieber ist, kannst du es aber auch bei Cantor selbst nachlesen. Ich persoenlich finde den Beweis mit heutigem Vokabular und auf das Wesentliche reduziert aber griffiger.

Aber meiner Meinung nach enthält die Definition von A eine "unzulässige Referenz" auf f(x).

Wieso ist die unzulaessig? Du waehlst zuerst irgendeine surjektive Abbildung f : X -> P(X). Und dann gilt fuer jedes x in X eine der beiden Aussagen:
1. x ist Element von f(x)
2. nicht (x ist Element von f(x))

Die x, bei denen 2. zutrifft, tust du in dein A rein, die anderen nicht.

Jan

[Beowulf]

Die x, bei denen 2. zutrifft, tust du in dein A rein, die anderen nicht.

Das Problem ist, dass die ganze Beweisführung für das Komplement funktioniert, also zu keinen Widersprüchen führt. Das liegt am binären Charakter von Potenzmengen: Die Anzahl der Elemente beträgt 2^n, ist also immer durch zwei teilbar. Z.B. das Komplement der leeren Menge ist die Menge aller Zahlen. Bei einer dreielementigen Menge {1, 2, 3} wäre das Komplement von {1} die Menge {2, 3}. Und wenn z.B. f(2) = {1}, und damit 2 nicht Element von {1}, so wäre aber 2 auf jeden Fall im Komplement enthalten, und zwar in {2, 3}.

Führen wir also die Beweisführung für das Komplement durch:
Angenommen, f sei eine surjektive Abbildung f(x) -> P(X);

Angenommen, es gäbe eine Menge A: {x Element von X | x kein Element von f(x)}
so gibt es zu jedem f(x) ein Komplement f(x)´, für das gilt: A´: {x Element von X | x Element von f(x)´}

Da wir annehmen, f sei surjektiv, gibt es ein x0 Element von X mit f(x0)´ = A´.

Versuchen wir, x0 zu lokalisieren:
1) x0 Element von A´ => x0 Element von f(x)´ => x0 Element von A´
2) x0 Element von X / A´ => x0 kein Element von f(x)´ => x0 kein Element von A´

Tolle Wurst, oder nicht?

[DasJan]

Die Konstruktion von A führt bereits zum Widerspruch. Da kannst du noch so viele andere Sachen machen, die nicht zum Widerspruch führen, ein einziger reicht schon, um zu wissen: Deine Annahme ("es gibt eine Surjektion f : X -> P(X)") ist falsch.

Tolle Wurst, oder nicht?

Eigentlich nicht. Die Wurstfachverkäufer bei uns geben dafür eher wenig Punkte.

Das Jan

[Beowulf]

Deine Annahme ("es gibt eine Surjektion f : X -> P(X)") ist falsch.

Warum? Wenn diese Annahme falsch wäre, würde der Komplement-Beweis auch zu Widersprüchen führen. Denn wenn es eine Abbildung der Komplemente gibt, gibt es auch eine Abbildung der Originale. Nein, eine Annahme an sich ist nicht falsch... solange man nicht das Gegenteil beweist.
Nun ist es so, dass bei konkret eingesetzten Werten auch der Komplement-Beweis zu Widersprüchen führt. Nur sind diese nicht ganz so offensichtlich. Trotz allem müssen wir also herausfinden, wo hier der Fehler bzw. die Unvollständigkeit im Beweis liegt.

Ich habe da etwas länger drüber nachgedacht, und bin zu dem Schluss gekommen, dass der Beweis wohl die Transitivität beweisen möchte, welche aber nirgens explizit erwähnt wird.

Ein Beispiel für ein transitives Prädikat wäre kleiner (<), also z.B. 1 < 2 < 3 => 1 < 3
Ein Beispiel für ein intransitives Prädikat wäre ungleich (=/=), also z.B. 1 =/= 2 =/= 1 => 1 =/= 1 => Widerspruch!
Ähnlich gilt das für "nicht Element von" (/€), also z.B. 1 /€ {2} => 2 /€ {1} => 2 /€ {2} => Widerspruch!

Beispiel:
Angenommen, wir haben die surjektive Abbildung f(1) = {2} und f(2) = {1}.
Man bildet f(1) auf {2} ab. Man merkt, dass 1 nicht Element von {2} ist und bildet mit der 1 die Menge A = {1} mit A: {x | x kein Element von f(x)}. Da f surjektiv ist, muss(?) es eine Abbildung geben, für die f(x) = A = {1} ist. Nun, dieses Element gibt es auch, da f(2) = {1}. So weit, so gut. Jetzt möchten wir x0 (in diesem Fall 2) allgemein lokalisieren, also:
1) x0 Element von A = {1} (nicht wahr da x0 = 2) => x0 kein Element von f(x0) (aufgrund Definition von A) => x0 kein Element von A (da f(x0) = A, angeblich wegen Surjektivität) => Widerspruch!
2) x0 Element von X / A = {2} (wahr da x0 = 2) => x0 Element von f(x0) (aufgrund der negierten Definition von A) => x0 Element von A (da f(x0) = A, angeblich wegen Surjektivität) => Widerspruch!

Demnach wäre die Abbildung angeblich nicht surjektiv. Dies ist aber laut Definition sehr wohl der Fall. Sie ist surjektiv, aber nicht transitiv.

[elevar]

Deine Annahme ("es gibt eine Surjektion f : X -> P(X)") ist falsch.

Warum?

Jan hat den Grund doch bereits genannt:

Die Konstruktion von A führt bereits zum Widerspruch. Da kannst du noch so viele andere Sachen machen, die nicht zum Widerspruch führen, ein einziger reicht schon, um zu wissen: [...]

Wenn diese Annahme falsch wäre, würde der Komplement-Beweis auch zu Widersprüchen führen.

Nein, das ist nicht richtig.

Denn wenn es eine Abbildung der Komplemente gibt, gibt es auch eine Abbildung der Originale.

Ja, das stimmt. Aber du hast nicht gezeigt, dass es eine solche "Abbildung der Komplemente" gibt, sondern nur, dass die Annahme, es gäbe eine, auf dem von dir beschriebenen Weg nicht zum Widerspruch führt. Ein Existenzbeweis ist das aber noch lange nicht.

Nein, eine Annahme an sich ist nicht falsch... solange man nicht das Gegenteil beweist.

Wieder wahr. Deswegen haben wir ja das Gegenteil bewiesen.

Trotz allem müssen wir also herausfinden, wo hier der Fehler bzw. die Unvollständigkeit im Beweis liegt.

Nicht wir müssen das herausfinden, sondern du musst herausfinden, wo dein Denkfehler liegt. Ich würde dazu empfehlen, deine weiteren Konstruktionen und Gedanken einmal zurück zu stellen und dir noch einmal klar darüber zu werden, wo genau dein Problem mit dem Beweis liegt. Momentan schweifen wir nämlich etwas ab, da du in jedem Beitrag ein neues angebliches Problem nennst. Dein Problem, wie du es am Anfang beschrieben hast, war der Bezug auf die Potenzmenge. Vielleicht begreifst du den Beweis, wenn du an der Stelle noch einmal ansetzt.

[DasJan]

Ein Widerspruchsbeweis funktioniert so:
1. Wir treffen eine Annahme ("Es gibt eine Surjektion f: X -> P(X).")
2. Wir folgern aus dieser Annahme andere Aussagen ("Wenn es so eine Funktion gibt, dann baue ich mir damit M.")
3. Wir entdecken einen Widerspruch ("Hoppla, M kann es ja gar nicht geben.")
4. Und dann müssen wir einsehen, dass wohl schon unsere Annahme falsch war ("Es gibt also KEINE solche Surjektion.")

Mit Transitivität hat das ganze nicht das Geringste zu tun. Kann ja auch nicht, denn Transitivität ist eine Eigenschaft von Relationen, nicht wie du offenbar vermutest von Funktionen.

Noch mal, jeder Mathematiker und vermutlich auch jeder mathematisch interessierte Laie wird dir bestätigen können, dass das bei Wikipedia ein vollständiger, korrekter Beweis der Aussage "Für jede Menge X gibt es keine Surjektion X -> P(X)" ist. Um das einzusehen, musst du dich aber erst mal von deiner "Ein Geisterfahrer? Hunderte!"-Idee verabschieden.

Ich habe da etwas länger drüber nachgedacht,

Das ehrt dich, aber du hast offenbar in die falsche Richtung gedacht und niemand hat dich gebremst.

Das Jan

[Beowulf]

Ja, das stimmt. Aber du hast nicht gezeigt, dass es eine solche "Abbildung der Komplemente" gibt, sondern nur, dass die Annahme, es gäbe eine, auf dem von dir beschriebenen Weg nicht zum Widerspruch führt. Ein Existenzbeweis ist das aber noch lange nicht.

Wie bitte? Wenn ein Beweis zu keinen Widersprüchen führt, dann ist es... nun ja... ein Beweis! Oder etwa nicht? Deiner Logik zufolge wäre ja dann der Satz von Cantor auch kein Beweis für die Nicht-Existenz. Zu dumm, dass ein und dasselbe Beweiskonstrukt einmal zu Widersprüchen führt, ein anderes mal aber nicht. Daher liegt es nahe, dass der Beweis an sich nichts taugt.

Mit Transitivität hat das ganze nicht das Geringste zu tun. Kann ja auch nicht, denn Transitivität ist eine Eigenschaft von Relationen, nicht wie du offenbar vermutest von Funktionen.

Zu dumm nur, dass die Menge M, von der du sprichst, mit einer Relation gebildet wird, die nicht transitiv ist. Und einer der Eingabewerte der Relation ist die Funktion. Das ganze ist nur eine Abwandlung der Russelschen Antinomie. Auch habe ich gezeigt dass der Widerspruch für alle surjektiven Abbildungen gilt, die mindestens ein Element haben, bei denen x kein Element von f(x) ist, also z.B. f(1) = 2, f(2) = 1.
Über die Zusammenhänge zwischen der Russelschen Antinomie und dem Halteproblem kannst du dich gerne hier informieren: ftp://ftp.mi.fu-berlin.de/lwb/Halt.pdf

Das ehrt dich, aber du hast offenbar in die falsche Richtung gedacht und niemand hat dich gebremst.

Immerhin übernehme ich nicht ungefiltert irgendwelches Halbwissen. Da kannst du noch so viel über "Wahrscheinlichkeiten" reden, das gehört dann doch eher in den Religions-Thread.

[DasJan]

Zu dumm nur, dass die Menge M, von der du sprichst, mit einer Relation gebildet wird, die nicht transitiv ist. Und einer der Eingabewerte der Relation ist die Funktion.

Wieso darf ich nur transitive Relationen zum Bilden von Mengen benutzen? Der ganze Beweis hat nichts mit Transitivität zu tun. Und was du hier mit Eingabewert bezeichnest, ist nicht die Funktion, sondern ein Element im Bild der Funktion, also eine Menge.

Auch habe ich gezeigt dass der Widerspruch für alle surjektiven Abbildungen gilt, die mindestens ein Element haben, bei denen x kein Element von f(x) ist, also z.B. f(1) = 2, f(2) = 1.
Über die Zusammenhänge zwischen der Russelschen Antinomie und dem Halteproblem kannst du dich gerne hier informieren: ftp://ftp.mi.fu-berlin.de/lwb/Halt.pdf

Das hast du nicht gezeigt. Auch kann nicht f(1) = 2 gelten, da 2 kein Element der Potenzmenge von {1,2,3} ist.

Immerhin übernehme ich nicht ungefiltert irgendwelches Halbwissen. Da kannst du noch so viel über "Wahrscheinlichkeiten" reden, das gehört dann doch eher in den Religions-Thread.

Ich übernehme nicht ungefiltert Halbwissen. Ich habe das lange studiert, dabei Prüfungen sowohl über den Themenkreis russelsche Antinomie als auch über den Themenkreis Halteproblem abgelegt, und mache das jetzt beruflich. Über hundert Jahre alte, einfach zu beweisende Sätze, gegen die nie auch nur ein Mathematiker ein Wort erhoben hat, würde ich auch nicht als Halbwissen bezeichnen.

Ich sehe leider keine Möglichkeit mehr, außer aufzugeben. Mir ist bewusst, dass du das als Bestätigung deiner These sehen wirst, der Beweis sei lücken- oder fehlerhaft, aber ich sehe da leider keinen Ausweg. Elevar und ich haben uns wirklich, wirklich viel Mühe gegeben, dir deine Denkfehler aufzuzeigen, aber entweder du willst oder du kannst sie nicht einsehen. Ich wünsche dir, dass es dir irgendwann doch gelingt, vielleicht in einem direkten Gespräch mit einem Fachkundigen, das nicht über ein Internetforum geführt wird.

Das Jan

[realchris]

Hier kann nur noch einer helfen:

[elevar]

Wenn ein Beweis zu keinen Widersprüchen führt, dann ist es... nun ja... ein Beweis! Oder etwa nicht?

Nein, ein Widerspruchsbeweis ohne Widerspruch ist keiner.

Deiner Logik zufolge wäre ja dann der Satz von Cantor auch kein Beweis für die Nicht-Existenz.

Wie du auf diese falsche Schlussfolgerung kommst, ist mir nicht klar. Sie bleibt falsch.

Vielleicht solltest du noch einen Schritt früher ansetzen und dich mit der logischen Grundlage eines Widerspruchsbeweises auseinandersetzen. Offenbar hast du die noch nicht ganz durchdrungen.

Ich sehe leider keine Möglichkeit mehr, außer aufzugeben. Mir ist bewusst, dass du das als Bestätigung deiner These sehen wirst, der Beweis sei lücken- oder fehlerhaft, aber ich sehe da leider keinen Ausweg. Elevar und ich haben uns wirklich, wirklich viel Mühe gegeben, dir deine Denkfehler aufzuzeigen, aber entweder du willst oder du kannst sie nicht einsehen.

Dem muss ich mich anschließen.

[Beowulf]

Wieso darf ich nur transitive Relationen zum Bilden von Mengen benutzen? Der ganze Beweis hat nichts mit Transitivität zu tun. Und was du hier mit Eingabewert bezeichnest, ist nicht die Funktion, sondern ein Element im Bild der Funktion, also eine Menge.

Du reißt das aus dem Zusammenhang. Anhand der Abbildungswerte (x kein Element von f(x)) bildet man eine Menge, bei der man voraussetzt, dass diese wieder abgebildet werden kann. Und das ganze wird mit einer intransitiven Relation verknüpft. Klingelts jetzt bei dir?

Ich sehe leider keine Möglichkeit mehr, außer aufzugeben. Mir ist bewusst, dass du das als Bestätigung deiner These sehen wirst, der Beweis sei lücken- oder fehlerhaft, aber ich sehe da leider keinen Ausweg.

Aber sonst gehts dir noch gut? Du machst sowas beruflich und bildest dir ein alles korrekt verstanden zu haben, willst jetzt jedoch das Handtuch werfen? Vielleicht solltest du dir ein anderes Betätigungsfeld suchen und lieber Pastor werden. Wenn dir wirklich bewusst ist, was die Russelsche Antinomie bedeutet, dann weißt du auch, dass der Beweis nur auf der Formulierung einer solchen beruht. Die Beweise, die über Pseudocode funktionieren (wie das Knilch-Programm im anderen Thread) haben ja schließlich auch nichts anderes gemacht. Und du müsstest auch wissen, das die Erkenntnisse, die man daraus ableiten kann, sehr gering sind, da es sich schließlich um ein gezielt konstruiertes Paradoxon handelt.

@realchris: Schizophrenie ist keine Lösung!

Nein, ein Widerspruchsbeweis ohne Widerspruch ist keiner.

Nein, es gibt zwei Arten von Beweise: Welche die zu Widersprüchen führen, und welche die es nicht tun. Die erste Art zeigt dass die Annahme falsch war, die zweite zeigt dass die Annahme richtig war.

[elevar]

Du hast kein grundlegendes Problem herausgearbeitet, sondern machst einfach dauernd neue Fässer auf, sobald wir das alte wieder geschlossen haben. Da fällt es schwer daran zu glauben, dass diese Endlosschleife irgendwann abbricht. Gut gemeinte Ratschläge übergehst du, gehst in Opposition zu nahezu allem was wir sagen, jetzt paulst du sogar noch hier rum. Es muss dir doch klar sein, dass dir unter diesen Umständen nicht geholfen werden kann.

[DasJan]

Du reißt das aus dem Zusammenhang. Anhand der Abbildungswerte (x kein Element von f(x)) bildet man eine Menge, bei der man voraussetzt, dass diese wieder abgebildet werden kann. Und das ganze wird mit einer intransitiven Relation verknüpft. Klingelts jetzt bei dir?

Nein. Du hast recht damit, dass die "ist Element von"-Relation nicht transitiv ist. Aber das ist kein Problem, nicht-transitive Relationen sind nicht boese oder verboten oder so.

Du machst sowas beruflich und bildest dir ein alles korrekt verstanden zu haben, willst jetzt jedoch das Handtuch werfen?

Ja, ja und ja.

Vielleicht solltest du dir ein anderes Betätigungsfeld suchen und lieber Pastor werden.

Wieso sollte ich mir ein anderes Betätigungsfeld suchen? Wie gesagt: Jeder hier versteht den Beweis und wuerde mir recht geben, wenn ich sage, dass er so stimmt und vollstaendig ist. Da bin ich doch in guter Gesellschaft. Die Pastoren-Community wuerde mich dagegen wohl viel weniger haben wollen.

Und du müsstest auch wissen, das die Erkenntnisse, die man daraus ableiten kann, sehr gering sind, da es sich schließlich um ein gezielt konstruiertes Paradoxon handelt.

Die Erkenntnisse, die aus der Antinomie, dem Halteproblem und dem Satz von Cantor erwachsen sind, sind ziemlich gewaltig.

Das Jan