Halteproblem

[Beowulf]

Floyd, dass was du da vorbringst ist der absolute Logik-GAU! Es gehört schon eine ziemlich verschrobene Sichtweise dazu, um bei einem Beweis eine falsche bzw. unbewiesene Prämisse zuzulassen, beim einem anderen aber nicht. Es gehört eben nun mal zur Natur einer Annahme, dass diese erst noch bewiesen werden muss. Auch bei meinem Komplementbeweis ist die Surjektivität von f lediglich eine Prämisse. Und verwende den Buchstaben A bitte nicht auch für deine "Aussage", damit bringst du alles nur durcheinander.

Dann erkläre bitte, welche der Umformungen, mit denen man von 2 = 0 zu 1 = 1 kommt, mathematisch ungültig ist.

Die Quadrierung ist ungültig. Jedenfalls dann, wenn man auf Gleichheit prüfen will. Daher ist es immer wichtig zu wissen, was man denn nun mit dem Beweis zeigen möchte, damit man die ungültigen Umformungen erkennen kann.

PS: Die Menge der Klassen, die keine Mengen sind, ist erstaunlich umfangreich. Da sind einige alte Bekannte dadrunter: http://de.wikipedia.org/wiki/Klasse_(Me ... te_Klassen

[Floyd]

Floyd, dass was du da vorbringst ist der absolute Logik-GAU! Es gehört schon eine ziemlich verschrobene Sichtweise dazu, um bei einem Beweis eine falsche bzw. unbewiesene Prämisse zuzulassen, beim einem anderen aber nicht.

Der Beweis auf Wikipedia zeigt, dass f nicht existiert, weil die Annahme, f gäbe es doch, zu einem Widerspruch führt. Deine Ansicht, dass meine "Sichtweise" verschroben sei, ist dem Umstand geschuldet, dass du immer noch nicht verstanden hast, was ein indirekter Beweis (=Widerspruchsbeweis) ist und wie er sich von einem direkten Beweis unterscheidet. Ich weiß ehrlich gesagt auch nicht, wie man das noch verständlicher machen soll.

Es gehört eben nun mal zur Natur einer Annahme, dass diese erst noch bewiesen werden muss. Auch bei meinem Komplementbeweis ist die Surjektivität von f lediglich eine Prämisse.

Insbesondere ist sie eine Prämisse, die du nicht bewiesen hast. Ich wiederhole mich, aber:
Es gibt zwei Möglichkeiten:
Entweder wurde bereits bewiesen, dass die Prämisse wahr ist. Dann kannst du sie im Rahmen deines Beweises verwenden.
Oder sie wurde noch nicht validiert. Dann darfst du sie in einem direkten Beweis nicht verwenden (im Sinne des Schlussfolgerns auf Basis dieser Prämisse), und in einem Widerspruchsbeweis nur dann, wenn du annimmst, dass sie falsch ist und du dies zeigen möchtest.
Deine analoge Konstruktion ist weder ein Widerspruchsbeweis, noch hast du die Prämisse zuvor überprüft.
Ich würde dich bitten, dich wirklich neutral mit diesem Absatz auseinanderzusetzen.

Die Quadrierung ist ungültig. Jedenfalls dann, wenn man auf Gleichheit prüfen will. Daher ist es immer wichtig zu wissen, was man denn nun mit dem Beweis zeigen möchte, damit man die ungültigen Umformungen erkennen kann.

Die Quadrierung einer natürlichen Zahl ist keine ungültige Operation, auch wenn du das gerne hättest.
Alles, was das Beispiel zeigt, ist, dass du aus einer falschen Prämisse eine wahre Aussage ableiten kannst. Wieso willst du das nicht akzeptieren?
Schau dir mal den Artikel Implikation an, vielleicht hilft das.

[Beowulf]

Die Quadrierung einer natürlichen Zahl ist keine ungültige Operation, auch wenn du das gerne hättest.

Natürlich ist sie das! Denn das Quadrieren einer Gleichung ist keine Äquivalenzumformung!
a = b => a² = b²
Man kann hier zwar von links nach rechts schließen, aber nicht von rechts nach links. Folgendes hingegen wäre eine Äquivalenzumformung:
|a| = |b| <=> a² = b²

Wenn man zeigen kann, dass a² != b² ist, dann man sicher daraus folgern, dass a != b ist. Aber nicht, dass |a| != |b| ist.
Und ein ähnliches Problem ergibt sich aus der Prämisse beim Wikipedia-Beweis: Wenn man x0 nicht lokalisieren kann, bedeutet dies wirklich, dass f nicht surjektiv sein kann? Schließlich geht es hier um die Widersprüchlichkeit eines Systems! Das Bilden des Komplements ist meines Erachtens nach eine Äquivalenzumformung. Und da sich der Komplementbeweis nur in diesem Punkt von dem ursprünglichen Beweis unterscheidet, muss auch das Ergebnis äquivalent sein!

Nehmen wir mal ein anderes Beispiel:
a = b => a² = b² <=> 3a² = 3b²
Sei a = -1 und b = 1, dann führt die erste Schlussfolgerung zu keinem Widerspruch. Man kann aber daraus natürlich nicht folgern, dass a = b ist. Das dumme ist nur, dass jede Äquivalenzumformung, egal ob diese nun vor oder nach der Schlussfolgerung vollzogen wird, nichts daran ändert, dass am Ende kein Widerspruch erzeugt wird. Im diesem Beispiel wurde am Ende alles mit 3 multipliziert. Aber jede andere Äquivalenzumformung wäre denkbar gewesen, es hätte am Ergebnis nichts geändert.

Versteh mich nicht falsch: Der Komplementbeweis dient nicht dazu, die Surjektivität von f zu beweisen, sondern die Widersprüchlichkeit des Beweises zu zeigen, die durch eine Äquivalenzumformung vermieden werden kann.

Ich denke du hast dir die Gödel-Nummerierung auch schon angesehen. Weil du davon gesprochen hast das ein Programm eine Riesige Nummer ist. Aber dann müsstet du doch auch verstehen wo das Problem liegt?Was soll deiner Meinung nach denn der Sinn des Halteproblems sein?Oder welchen Schwindel befürchtest du hier, vielleicht ein Formverstoß in dem Beispiel der Wikipedia?

"Schwindel" geht vielleicht etwas zu weit. "Fehlinterpretation" ist da vielleicht passender. Das Problem ist, dass die von mir angesprochenen Knilch-Programme keine eindeutige Gödelnummer besitzen. Die Gödelnummer ist abhängig von der Funktion, die diese abbilden soll (da das Knilch-Programm das Haltetestprogramm einbindet). Und diese Verschränkung führt meiner Meinung nach zu einem Paradoxon.
Wenn man eine alternative Ausgabe des Programms wie "unentscheidbar" zulassen würde, dann wäre meiner Meinung nach die Menge der Eingabewerte, für die dies zutreffen würde, nicht derart komplex, dass daraus die Überabzählbarkeit folgern müsste.
Mein Vorschlag ist einfach: Paradoxien erkennen und entsprechend behandeln, den Rest normal den Ausgabewerten "hält" und "hält nicht" zuordnen.

[Floyd]

Natürlich ist sie das! Denn das Quadrieren einer Gleichung ist keine Äquivalenzumformung!

Dein Postulat wäre demnach: Nur Äquivalenzumformungen sind mathematisch gültige Operationen. Das ist offensichtlich nicht richtig, denn die Potenzfunktion (und damit insbesondere die Quadratfunktion) ist auf reellen Zahlen definiert. Und wie du selbst sagst:

Man kann hier ... von links nach rechts schließen

Wie sollte das möglich sein, wenn die Operation nicht gültig ist?
Du hast vollkommen recht, dass das Quadrieren keine Äquivalenzumformung ist. Daraus folgt aber nicht, dass die Umformung mathematisch ungültig ist.

Und ein ähnliches Problem ergibt sich aus der Prämisse beim Wikipedia-Beweis: Wenn man x0 nicht lokalisieren kann, bedeutet dies wirklich, dass f nicht surjektiv sein kann?

Die surjektive Abbildung f existiert genau dann nicht, wenn alle anderen verwendeten Prämissen wahr sind und ich auf Basis der Annahme "die surjektive Abbildung f existiert" auf logische Widersprüche stoße. Und genau das zeigt der Beweis.

Schließlich geht es hier um die Widersprüchlichkeit eines Systems! Das Bilden des Komplements ist meines Erachtens nach eine Äquivalenzumformung. Und da sich der Komplementbeweis nur in diesem Punkt von dem ursprünglichen Beweis unterscheidet, muss auch das Ergebnis äquivalent sein!

Wieso gehst du ständig nur punktuell auf Aussagen ein? Es macht keinen Spaß, immer wieder mit denselben Argumenten anzukommen, weil du schlicht über sie hinweggehst. Dein "Komplementbeweis" unterscheidet sich nicht nur in diesem Punkt. Er ist kein Widerspruchsbeweis. Siehe meinen vorherigen Post.
Die Lokalisation von x0 ist ohne Wert, da sie dir nur auf Basis der Annahme "f existiert" gelingt. Diese ist falsch.

[Beowulf]

Dein Postulat wäre demnach: Nur Äquivalenzumformungen sind mathematisch gültige Operationen.

Jetzt dreh mir doch das Wort nicht im Munde herum! Ich meinte, dass nur Aquivalenzumformungen sicherstellen, dass zwei Aussagen auch wirklich äquivalent sind.

Die surjektive Abbildung f existiert genau dann nicht, wenn alle anderen verwendeten Prämissen wahr sind und ich auf Basis der Annahme "die surjektive Abbildung f existiert" auf logische Widersprüche stoße. Und genau das zeigt der Beweis.

Und genau da halte ich eben mit meiner Argumentation gegen. Zwei Beweise, die meiner Meinung nach äquivalent sind, aber unterschiedliche Aussagen liefern, sind in meinen Augen das Indiz für ein Paradoxon. Sie sagen deshalb nichts über die Prämisse aus.

Die Lokalisation von x0 ist ohne Wert, da sie dir nur auf Basis der Annahme "f existiert" gelingt. Diese ist falsch.

Wenn du beweisen kannst, dass die Bildung des Komplements keine Aquivalenzumformung darstellt, dann darfst du du gerne sagen, dass der Komplementbeweis keine Aussagekraft bezüglich des ursprünglichen Beweises hat.

Wieso gehst du ständig nur punktuell auf Aussagen ein?

Weil du immer bestimmte Aussagen verdrehst. Ein Beispiel:
Ich sage: "Die Quadrierung ist ungültig. Jedenfalls dann, wenn man auf Gleichheit prüfen will."
Du antwortest: "Die Quadrierung einer natürlichen Zahl ist keine ungültige Operation, auch wenn du das gerne hättest."
Später veränderst und verdrehst du die Aussage: "Du hast vollkommen recht, dass das Quadrieren keine Äquivalenzumformung ist. Daraus folgt aber nicht, dass die Umformung mathematisch ungültig ist."

Du unterstellst mir, ich hätte behauptet, dass das Quadrieren keine Mathematisch korrekte Umformung ist. Aber genau dies habe ich nicht gesagt. Ich sagte, dass die Quadrierung nicht ausreicht, um die Gleichheit zu beweisen. Man kann damit zwar notwendige, aber nicht hinreichende Bedingungen basteln. Deshalb hinkt die Analogie, da ich stets von Beweisführungen ausgegangen bin, die äquivalent zueinander sind.

Daher: Wenn du mehr Sachlichkeit willst, packe dich bitte mal an die eigene Nase!

[Floyd]

Der Ausgangspunkt war folgender:

Man kann nicht mit mathematisch gültigen Umformungen eine falsche Aussage in eine wahre umwandeln.

Dann erkläre bitte, welche der Umformungen, mit denen man von 2 = 0 zu 1 = 1 kommt, mathematisch ungültig ist.

Es ging also darum, ob man mit mathematisch gültigen Umformungen aus einer falschen Aussage eine wahre ableiten kann. Es ging nicht um den Spezialfall der Äquivalenzumformung. Da hast du zwar völlig recht, das war aber nicht der Diskussionsgegenstand. Für allgemeine Umformungen ist deine obige Aussage nicht richtig, und das ist der Punkt.

Du unterstellst mir, ich hätte behauptet, dass das Quadrieren keine Mathematisch korrekte Umformung ist. Aber genau dies habe ich nicht gesagt

Doch, das hast du. Vielleicht hast du es ganz anders gemeint, aber deine Antwort auf meine Frage, welche Operation mathematisch ungültig ist, war: "Die Quadrierung ist ungültig." Und kurz darauf sprichst du noch einmal von "ungültigen Umformungen", die man erkennen muss.

Jetzt dreh mir doch das Wort nicht im Munde herum! Ich meinte, dass nur Aquivalenzumformungen sicherstellen, dass zwei Aussagen auch wirklich äquivalent sind.

Es tut mir leid, wenn wir uns missverstanden haben, aber ich kann nur auf das eingehen, was du niederschreibst, und ich bin nicht der Meinung, dass ich deine Aussagen verdreht habe. Die Intention deiner Aussagen kann natürlich eine andere gewesen sein.

Und genau da halte ich eben mit meiner Argumentation gegen. Zwei Beweise, die meiner Meinung nach äquivalent sind, aber unterschiedliche Aussagen liefern, sind in meinen Augen das Indiz für ein Paradoxon. Sie sagen deshalb nichts über die Prämisse aus.

Welche Aussage(n) liefert dein "Beweis" denn ganz konkret? Und zwar nicht in Bezug auf den Wikipedia-Beweis, sondern für sich?

[Beowulf]

Doch, das hast du. Vielleicht hast du es ganz anders gemeint, aber deine Antwort auf meine Frage, welche Operation mathematisch ungültig ist, war: "Die Quadrierung ist ungültig." Und kurz darauf sprichst du noch einmal von "ungültigen Umformungen", die man erkennen muss.

Dann solltest du mal besser nachlesen! Ich habe folgendes geschrieben: Jans Analogie taugt nichts, da sie mathematisch nicht korrekt ist. Aus a²=b² folgt eben nicht zwangsläufig, dass a=b ist. Diese Schlussfolgerung darf nicht gezogen werden.
Also bitte nicht immer alles aus dem Zusammenhang reißen. Es wäre gut, wenn wir nun diesen kindischen Hickhack, wer denn nun was genau gesagt hat, beenden könnten.

Die Intention deiner Aussagen kann natürlich eine andere gewesen sein.

Neben der Intention gibt es da noch die Interpretation, lieber Floyd!

Welche Aussage(n) liefert dein "Beweis" denn ganz konkret? Und zwar nicht in Bezug auf den Wikipedia-Beweis, sondern für sich?

Er liefert eigentlich nur eine Erkenntnis: Der Versuch, das x0 in den Komplementen zu lokalisieren, ergibt keine Widersprüche. (Ich könnte da zur Veranschaulichung wieder mit der Transitivität argumentieren, aber dann hackt ihr wieder auf "Formfehlern" rum, die im Beweis aber gar keine Rolle spielen. Aber dazu später.) Das entstehende Gleichungssystem ist derart banal, dass man sich fragt, warum man überhaupt diese Lokalisierung unbedingt vornehmen wollte. Die Aussagekraft ist nahezu gleich Null. Beim "normalen" Beweis hat man an dieser Stelle aber freudig aufgehört und den Widerspruchsbeweis als gelungen angesehen. Die Möglichkeit eines Paradoxons wurde nicht in Erwägung gezogen.

Wenn man neben der Russelschen Antinomie nun die Cantorsche Antinomie betrachtet, dann fällt auf, dass auch A´ eine Klasse ist, die mit der Allklasse verwandt ist. Warum erzeugt diese Klasse scheinbar kein Paradoxon?
Nun, der ursprüngliche Beweis, der sich der Russelschen Antinomie bedient, läuft ja so ab:
x0 wird mit f auf A abgebildet, welches eine Menge (?) ist, für die gilt: x kein Element von f(x).
Es fällt auf, dass die Abbildung f zweimal benutzt wird, ineinander verschachtelt. Und dieser Umstand ist meiner Meinung nach für eine surjektive Abbildung nicht notwendig.

Betrachten wir nebenbei mal das Fundierungsaxiom der Zermelo-Fraenkel-Mengenlehre: "Jede nichtleere Menge A enthält ein Element B, so dass A und B disjunkt sind."
Somit entspricht in diesem Fall die Russelsche Klasse der Allklasse, da sich ja sowieso keine Menge selber enthalten darf. Aber wie gesagt, die gilt nur für die ZF-Menge, die entwickelt wurde um Widersprüche zu vermeiden.

Was bei der Russelschen Klasse einfach aussieht, ist für unser A doch etwas komplexer. Sie sieht anfangs noch harmlos aus, aber das geforderte f(x0) = A lässt sie schnell alt aussehen.
Stellt man alles etwas um, und beschränkt die Sichtweise auf das x0, so erhält man folgende Form:
x0: A: {x0 | x0 kein Element von A}
Wir ersetzen einfach f(x0) durch A und blenden alle anderen Elemente aus... diese interessieren uns erst einmal sowieso nicht. Das sieht dann verdammt nach der Russelschen Klasse aus. Das Problem ist die "Endlosschleife", die hier erzeugt wird. A enthält sich selber. Auch wenn die Relation negierend wirkt, so wird hier ein endloser Selbstbezug in Gang gebracht.

Warum erzeugt also der Komplementbeweis (mit der Allklasse) scheinbar keine Widersprüche?
x0: A': {x0 | x0 Element von A'}

Dies ist für mich der eigentliche Knackpunkt, über den ich noch etwas nachdenken muss.

[Floyd]

Dann solltest du mal besser nachlesen! Ich habe folgendes geschrieben: Jans Analogie taugt nichts, da sie mathematisch nicht korrekt ist. Aus a²=b² folgt eben nicht zwangsläufig, dass a=b ist. Diese Schlussfolgerung darf nicht gezogen werden.
Also bitte nicht immer alles aus dem Zusammenhang reißen. Es wäre gut, wenn wir nun diesen kindischen Hickhack, wer denn nun was genau gesagt hat, beenden könnten.

Jan hat nicht behauptet, dass aus a²=b² a=b folgt. Im Gegenteil, er sagt sogar:

Betrachten wir die Behauptung 0 = 2. Jetzt ziehe ich von beiden Seiten 1 ab (-1 = 1) und quadriere beide Seiten. Dann steht da 1 = 1, was offenbar richtig ist. Die Praemisse 0 = 2 ist damit aber noch laengst nicht bewiesen. Sie ist sogar falsch.

Dass deine Aussagen aus dem Zusammenhang gerissen werden, scheint deine Standardausrede zu sein. "Ist Element von" ist aber auch im Zusammenhang nicht transitiv, und die Quadrierung ist auch im Zusammenhang eine mathematisch gültige Umformung, nur eben keine Äquivalenzumformung.

Er liefert eigentlich nur eine Erkenntnis: Der Versuch, das x0 in den Komplementen zu lokalisieren, ergibt keine Widersprüche. ... Das entstehende Gleichungssystem ist derart banal, dass man sich fragt, warum man überhaupt diese Lokalisierung unbedingt vornehmen wollte. Die Aussagekraft ist nahezu gleich Null.

Exakt, das ist die "Erkenntnis", wenn du es so nennen willst. Aber wie bereits mehrmals gesagt, hat sie überhaupt keinen Wert, da hieraus - wie Jans Analogie zeigt - nicht folgt, dass f existiert. Diese Widerspruchsfreiheit deines "Komplementbeweises" steht also nicht im Widerspruch zu dem "normalen Beweis". Deine ganze analoge Konstruktion steht nicht im Widerspruch zum Wikipedia-Beweis, und dir das verständlich zu machen, ist bisher leider nicht gelungen.

Beim "normalen" Beweis hat man an dieser Stelle aber freudig aufgehört und den Widerspruchsbeweis als gelungen angesehen. Die Möglichkeit eines Paradoxons wurde nicht in Erwägung gezogen.

Man kann an dieser Stelle "aufhören", weil man in beiden Fällen der Fallunterscheidung auf einen logischen Widerspruch stößt*. Daraus folgt sofort, dass eine Prämisse falsch sein muss. Das ist in diesem Fall "f existiert".
Bei deiner Konstruktion ergeben sich hingegen keine logischen Widerspruche. Daraus folgt aber eben nicht, dass f existiert, und das ist der wesentliche Unterschied.

Neben der Intention gibt es da noch die Interpretation, lieber Floyd!

Stimmt. Die Frage ist, ob du deine Intentionen besser und präziser artikulieren kannst, als ich deine Aussagen wortgetreu auslegen.



* x0 Element von Y => x0 kein Element von Y
x0 Element von X\Y => x0 Element von Y

[Beowulf]

Dass deine Aussagen aus dem Zusammenhang gerissen werden, scheint deine Standardausrede zu sein.

Nun, dass meine Aussagen aus dem Zusammenhang gerissen werden ist ja nicht meine Schuld, oder?

"Ist Element von" ist aber auch im Zusammenhang nicht transitiv, und die Quadrierung ist auch im Zusammenhang eine mathematisch gültige Umformung, nur eben keine Äquivalenzumformung.

Da verdrehst du wieder etwas. Das ganze Brimborium mit der Äquivalenzumformung bezog sich auf das Bilden des Komplements! Und das Quadrieren war in dem Zusammenhang, den ich meinte, nicht gültig, da das Quadrieren keinen äquivalenten Beweis erzeugen kann, das Komplementieren meiner Meinung nach hingegen schon. Jan hat die Analogie gebracht, um die Aussagekraft meines Komplementbeweises in Frage zu stellen. Zugegeben, es war Jan in diesem Moment vielleicht nicht 100%ig bewusst dass ich hier gezielt einen äquivalenten Beweis konstruieren wollte. Denn meine Intention war es nicht, die Surjektivität von f zu beweisen... sondern einen analogen Beweis zu konstruieren, der keine Widersprüche erzeugt und somit das Paradoxon verdeutlicht.

Bei deiner Konstruktion ergeben sich hingegen keine logischen Widerspruche. Daraus folgt aber eben nicht, dass f existiert, und das ist der wesentliche Unterschied.

Richtig. Zu dumm nur, dass die beiden Beweise in ihrem Aufbau äquivalent erscheinen. Ihre Ergebnisse sind es jedoch nicht. Und genau dies ist die Natur einer Antinomie. Sei z.B. R die Russelsche Klasse, dann sind die Aussagen "R ist Element von R" und "R ist nicht Element von R" äquivalent.
Fakt ist, dass alle axiomatischen Mengenlehren, die nach der Entdeckung der Antinomie entwickelt wurden, einfach derart gestaltet sind, dass solche widersprüchliche Mengen (bzw. Klassen) nicht mehr gebildet werden dürfen. Somit fallen dann aber auch leider alle bisher genannten Beweise weg, weil diese dann auf inkorrekten Mengenbildungen beruhen.

Die Frage ist, ob du deine Intentionen besser und präziser artikulieren kannst, als ich deine Aussagen wortgetreu auslegen.

Die Frage ist, ob dies hier irgend jemanden interessiert. Ich behaupte mal: Nein.

[elevar]

Ich versuche die ganze Sache noch ein letztes Mal zu formulieren und würde mich freuen, wenn du es aufmerksam und vorbehaltlos liest.

Richtig. Zu dumm nur, dass die beiden Beweise in ihrem Aufbau äquivalent erscheinen. Ihre Ergebnisse sind es jedoch nicht. Und genau dies ist die Natur einer Antinomie.

Deine These, wie ich dich und deine Ausführungen zu äquivalenten Beweisen verstehe ist, dass aus einer falschen Annahme auch immer ein Widerspruch folgt. Dass ist fast richtig, aber nur fast. Richtig ist, dass man aus jeder falschen Annahme einen Widerspruch ableiten kann (Eigentlich nur aus fast jeder, aber lassen wir Gödel mal außen vor). Nur ist eben nicht jede logische Folge auch gleich ein Widerspruch. Dafür hat Jan ein Beispiel geliefert.

An dieser Stelle merkst du an, dass das Beispiel untauglich sei, da es sich nicht um Äquivalenzumformungen handle. Tatsächlich hat Jan hier lediglich Implikationen verwendet, "von links nach rechts". Die Annahme 0=2 lässt auf 1=1 schließen, umgekehrt ist das nicht richtig. Dabei ist aber festzustellen, dass eine Äquivalenz auch nicht notwendig ist, um zu zeigen, dass man aus einer falschen Annahme eine wahre folgern kann. Du verlangst also mehr, als an dieser Stelle gebraucht wird.

Richtig ist allerdings, dass eine wahre Aussage nie mit einer falschen äquivalent sein kann. Mir kommt es so vor, als hättest du diese Tatsache bei deiner Argumentation im Hinterkopf. Aber dieser Gedanke findet in der ganzen Diskussion bislang keine Anwendung und ist nicht direkt relevant für Jans Beispiel oder deinen Komplementen-Beweis.

Mit dieser Einsicht trägt dieser alternative "Beweis" auch nicht mehr. Es ist eben nicht so, dass du ähnlich der Russelschen Antinomie einmal die Aussage "Es gibt eine surjektive Abbildung..." und einmal "Es gibt keine surjektive Abbildung..." beweist. Damit hättest du tatsächlich eine Antinomie entdeckt. Der Komplementen-Beweis zeigt stattdessen eben eigentlich gar nichts. Die strukturelle Ähnlichkeit zum Wikipedia-Beweis hat so für sich erstmal keine logische Relevanz. Es handelt sich nicht um einen Widerspruchsbeweis (es entsteht ja gerade kein Widerspruch), aber auch nicht um einen direkten Beweis. Stattdessen nimmst du irgendwas an, und folgerst dann irgendwas anderes daraus. Über deine Annahme sagt das nichts aus. Das ausbleiben eines Widerspruchs ist eben kein Beweis für irgendwas.

Nun, dass meine Aussagen aus dem Zusammenhang gerissen werden ist ja nicht meine Schuld, oder?

Nun, du redest hier auch mit Mathematikern, die es gewohnt sind, mit klar definierten Begriffen zu arbeiten. Deine Sprache ist hingegen weniger streng. Zum Beispiel ist mir nicht klar, was genau du mit hinreichender Beweis oder äquivalenter Beweis meinst (so etwas ist nirgends definiert), außerdem fasst du den Begriff der Transitivität etwas weiter als die Definition es hergibt. Das führt dann zwangsläufig zu Missverständnissen, die für dich dann so aussehen, als würden wir Dinge aus dem Zusammenhang reißen.

[Floyd]

Jans Analogie bezog sich nicht auf den Part der Komplementbildung deines Beweises. Dass du die Diskussion um mathematisch gültige Umformungen, die von seiner Analogie ausging, nun auf deine Komplementbildung ummünzen willst... ich weiß nicht, was ich davon halten soll. Wenn du die letzten Postings noch einmal durchgehst, wirst du jedenfalls feststellen, dass ich an keiner Stelle etwas über selbige sage. Aber du hast dich mental offenbar derart auf diesen einen Punkt fokussiert, dass du Hinweise auf andere Fehler in deiner Argumentation nicht mehr zulässt. Oder sie als "Formfehler" abtust, auch wenn sie das nicht sind.

Jan hat die Analogie gebracht, um die Aussagekraft meines Komplementbeweises in Frage zu stellen. Zugegeben, es war Jan in diesem Moment vielleicht nicht 100%ig bewusst dass ich hier gezielt einen äquivalenten Beweis konstruieren wollte. Denn meine Intention war es nicht, die Surjektivität von f zu beweisen... sondern einen analogen Beweis zu konstruieren, der keine Widersprüche erzeugt und somit das Paradoxon verdeutlicht.

Deine analoge Konstruktion verdeutlicht aber kein Paradoxon. Die Tatsache, dass keine Widersprüche auftreten, sagt nichts und steht nicht im Konflikt mit dem richtigen Beweis. Ich an deiner Stelle hätte längst innegehalten, um diese Aussage mal zu überdenken. Alles, was du benötigst, um die Argumentation zu verstehen, steht in diesem und den vorangegangenen Posts. Ich habe nur leider nicht das Gefühl, dass bei dir die Bereitschaft da ist, mal einen Schritt zurückzutreten und die Aussagen objektiv zu validieren. Du hast dein Konzept, das steht, und jedes Argument, das wir dagegen vorbringen, muss falsch sein - wieso sich also noch ernsthaft damit auseinandersetzen, richtig?

Richtig. Zu dumm nur, dass die beiden Beweise in ihrem Aufbau äquivalent erscheinen. Ihre Ergebnisse sind es jedoch nicht.

Das Ergebnis des richtigen Beweises ist "Es existiert keine surjektive Abbildung f, weil die Annahme, f würde existieren, zu einem logischen Widerspruch führt".
Das Ergebnis deines Beweises ist "Wenn ich von der unbewiesenen Annahme ausgehe, dass f existiert, erhalte ich auf diesem Weg keinen Widerspruch". Wir erinnern uns: Aus falschen Annahmen kann man wahre Aussagen ableiten. Siehst du das Problem?

Langsam verliere ich auch die Lust. Wenn du der Meinung bist, dass ich ohnehin nur Unsinn rede und du einen viel klareren Blick für die Zusammenhänge hast, dann sehe ich keinen Sinn darin, die Diskussion weiterzuführen. Ich habe nur versucht, dir deinen Fehler verständlich zu machen, aber das ist mir leider nicht gelungen.

[Beowulf]

Richtig ist allerdings, dass eine wahre Aussage nie mit einer falschen äquivalent sein kann. Mir kommt es so vor, als hättest du diese Tatsache bei deiner Argumentation im Hinterkopf. Aber dieser Gedanke findet in der ganzen Diskussion bislang keine Anwendung und ist nicht direkt relevant für Jans Beispiel oder deinen Komplementen-Beweis.

Richtig, diesen Umstand hatte ich die ganze Zeit im Hinterkopf. Für meinen Komplementbeweis ist dies sehr wichtig.

Die strukturelle Ähnlichkeit zum Wikipedia-Beweis hat so für sich erstmal keine logische Relevanz.

Doch, natürlich. Wenn aus einem Beweis ein Widerspruch folgt, dann muss aus einem äquivalenten Beweis auch ein Widerspruch folgen.
Um auf mein vorheriges Beispiel zurückzukommen:
a = b => a² = b²
Wenn man die Gleichheit der rechten Gleichung beweisen kann, dann hat man eine notwendige Bedingung für die Gleichheit von a und b erfüllt. Selbiges gilt für folgende Beweisführung, die äquivalent ist:
a = b => 3a² = 3b²
Auch folgende ist äquivalent:
a = b => -a² = -b²
Oder diese:
a = b => a² + 3 = b² + 3

Ihr könnt ja auch mal andere äquivalente "Beweisführungen" testen und Werte einsetzen. Wenn eine einen Widerspruch erzeugt, erzeugen alle einen Widerspruch.

außerdem fasst du den Begriff der Transitivität etwas weiter als die Definition es hergibt.

Nicht wirklich. Wie ich schon erwähnte, sind irgendwelche Mengenklammern für diesen Beweis nicht von Belang. Dies ist durch die Rekursion bedingt. Um mal auf die in meinem vorletzten Beitrag genannte Form zurückzukommen:
x0: A: {x0 | x0 ∉ A}
Ersetzen wir rechts das A durch seine Definition, kommt folgendes heraus:
x0: A: {x0 | x0 ∉ {x0 | x0 ∉ A}}
Dieses Spielchen kann man beliebig oft fortführen. Das Ergebnis ist arg "instabil". Einerseits ist x0 Teil einer Menge, die x0 nicht enthalten darf. Andererseits ist x0 kein Teil einer Menge, die ihr Element x0 nicht als Element enthält.
Für mehr Verschachtelungen reichen meine Gehirnwindungen nicht aus...
Schöner verhält sich da der Komplementbeweis:
x0: A´: {x0 | x0 ∈ A´}
Nach der ersten Ersetzung kommt folgendes raus:
x0: A´: {x0 | x0 ∈ {x0 | x0 ∈ A´}}
Das bestätigt eigentlich nur das, was wir sowieso schon wussten: A´ ist eine Menge mit Elementen, die Element von A´ sind. Hier haben wir zwar eine triviale, aber sehr "stabile" Klasse.

Dass du die Diskussion um mathematisch gültige Umformungen, die von seiner Analogie ausging, nun auf deine Komplementbildung ummünzen willst... ich weiß nicht, was ich davon halten soll.

Ich weiß auch nicht, was ich von deinem Verhalten denken soll. Wenn du weiterhin auf diesen dümmlichen Konfrontationskurs bestehst, werde ich deine Beiträge einfach ignorieren. Ich denke, ich habe zu genüge erklärt, was ich denn nun gemeint habe.

[Floyd]

Ich weiß auch nicht, was ich von deinem Verhalten denken soll. Wenn du weiterhin auf diesen dümmlichen Konfrontationskurs bestehst, werde ich deine Beiträge einfach ignorieren.

Warum habe ich das Gefühl, dass Futur I hier nicht angebracht ist?
Gut, lass dich nicht länger von mir belästigen, ich habe jetzt eingesehen, dass ich dir meinen Standpunkt nicht verständlich machen kann und wir daher nicht auf einen Nenner kommen werden.

Konfrontationskurs sieht in meinen Augen allerdings eher so aus:

...Vielleicht solltest du dir ein anderes Betätigungsfeld suchen und lieber Pastor werden....
...es grenzt schon an Autismus...
...Möchtegern-Wissenschaftler...
...der ist in meinen Augen nicht mehr ganz dicht....
...Ich brauche deine Ratschläge nicht....
...Es gehört schon eine ziemlich verschrobene Sichtweise dazu...
...dümmlichen Konfrontationskurs...

Wenn du derart davon überzeugt bist, dass du richtig liegst, wozu dann diese Polemik?
Naja, was mache ich mir die Mühe...

[interrozitor]

Habe gerade mit Interesse diesen Thread quergelesen. Auch wenn ich nicht 100%ig nachvollziehen kann, wo genau das Problem liegt, glaube ich daß ganz fundamental ein Missverständnis bezüglich des Aufbaus eines Beweises vorliegt, zumindestens verstehe ich daß so in den Ausführungen zu den "äquivalenten Beweisen" und der daraus gefolgerten "Antinomie" bzw. "Paradox".

Ganz grundsätzlich ist ein Beweis durch Widerspruch in der Mathematik folgendermaßen aufgebaut (und ja, es gibt den Zweig der konstruktiven Mathematik, daß spielt hier aber keine Rolle):

Man nehme an, man will "A" beweisen. Stattdessen beweist man aber

"not A => False"

Warum ist das äquivalent zu "A" ist wahr? Kann einfach mit logisch (äquivalenten!) Umformungen herleiten:

"not A => False"
gdw. (not (not A)) OR False
gdw. A or False
gdw. A or (not (not False))
gdw. A or (not True)
gdw. A <= True

True => A ist offensichtlich daß gleiche wie A, denn True => A gdw. (not True) or A gdw. False or A gdw. A.

Doch, natürlich. Wenn aus einem Beweis ein Widerspruch folgt, dann muss aus einem äquivalenten Beweis auch ein Widerspruch folgen.

Aus Deinem "Beweis", oder aus Deinen Aussagen dazu lese ich, daß Du meinst, daß man aus "not A" zwangsläufig immer einen Widerspruch herleiten (also False herleiten) muss. Und wenn man aus "not A" dann "true" herleitet, dann hat man zwei unterschiedliche Beweise die unterschiedliches aussagen und daher so eine "Antinomie", also ist die Theorie widersprüchlich. Schauen wir mal, was also "not A => True" tatsächlich bedeutet:

"not A => True"
gdw. (not (not A)) or True
gdw. A or True
gdw. A or (not (not True)
gdw. A or (not False)
gdw. False => A

Aber wie schon DasJan erwähnte, kann man aus False alles folgern. Das ist also natürlich eine wahre Aussage. Also kann man natürlich aus "not A" auch True herleiten. Das sagt dann aber nun mal gar nichts darüber aus, ob A stimmt oder nicht. Es ist ein kein Beweis, für A, aber es ist auch kein Beweis für nicht A. Was hier mit "äquivalenter Beweis" bezeichnet wurde, ist also Nonsens. Also z.B. ein Satz a la aus "0 = 1" folgt X. Ob X dann stimmt oder nicht, kann man nicht sagen. Denn aus "0=1" kann man halt z.B. mit Multiplikation von 0 die Aussage "0 = 0" (stimmt) herleiten, aber gleichzeitig auch z.B. mit Addition von 1 die Aussage "1 = 2" herleiten (stimmt nicht).

Wenn Du wirklich einen Widerspruch (also einen Widerspruch in der Theorie selbst, eine Antinomie) zeigen möchtest, müsstest Du zeigen, daß gleichzeitig A bewiesen und nicht A bewiesen werden kann. Das also gleichzeitig A und nicht A gelten. Was müsste man dazu zusätzlich beweisen? Nun nicht A. Das ist das gleiche wie "True => not A".

Das ist aber etwas völlig anderes als "not A => True", auf das Du in deinem Beweis anspielst.

Man kann "True => not A" auch wieder umformen:
True => not A
gdw. (not True) or (not A)
gdw. False or (not A)
gdw. A => False

d.h. man müsste aus A einen Widerspruch ableiten.

Jetzt bezüglich Widerspruchlichkeit diverser Mengenlehren: Das hat zunächst mal damit nichts zu tun. Denn setzt man die Axiome der üblichen naiven Mengenlehre (ZFC) voraus, dann gilt der Satz. Und zwar definitiv, und erzeugt keinen Widerspruch.

Natürlich kann man die Axiome ändern. Und vielleicht gibt es irgendeine bizarre Axiomatisierung einer Mengenlehre (z.B. eine Axiomatisierung, die die Unendlichkeit von Mengen ausschließt, aber dort hätte man dann entweder eine sehr sehr komische Vorstellung von "allen Programmen", denn das könnten dann ja nur endlich viele sein, oder man könnte das Halteproblem nicht ausdrücken), in der das Halteproblem lösbar ist.

Und interessanterweise gilt die Unentscheidbarkeit des Halteproblem nun mal auch in den bekannten Alternativen zur Mengenlehre, also z.B. type theory.

Also es ist zu unterscheiden: Akzeptiert man Mengenlehre grundsätzlich nicht und damit auch keine Sätze die widerspruchsfrei(!) anhand der Axiome hergeleitet werden können (ok, ist ein, wenn auch etwas komischer Standpunkt) oder akzeptiert man die Axiome aber ist sich über entstehende Widersprüche nicht im Klaren (für ZFC: bisher keine gefunden). Aus Deinem "äquivalenten" Beweis läßt sich aber kein Widerspruch herleiten.

[Beowulf]

Danke interrozitor für deine ausführliche Antwort.

Was die logischen Schlussfolgerungen angeht, ist folgendes sehr wichtig: Ein Paradoxon bedeutet, dass eine wahre Aussage äquivalent zu einer falschen Aussage ist. Und solange ein logisches System solche Paradoxien zulässt, kann man theoretisch auch beweisen, dass 1 + 1 = 3 ist.
Da helfen auch die kompliziert hergeleiteten Logikkonstruktionen nichts, da du immer von der Kernaussage ausgehst, über die man aber keine Aussage treffen kann.
Das ganze ist ja so konstruiert:
A => B <=> C
Sei A die Aussage "f ist surjektiv", und B der Wikipedia-Beweis. Dann sei C der äquivalente Komplementbeweis. Denn wenn man Teilmengen einer Potenzmenge abbilden kann, kann man auch ihre Komplemente abbilden... und umgekehrt. Daher: Wenn man Komplemente abbilden kann, was spricht dann dagegen, auch die "ursprünglichen" Mengen abzubilden? Richtig, gar nichts. Denn was das Komplement ist und was das Original, das ist ja auch nur eine Sache des Standpunktes.
Und genau dies ist der Knackpunkt: Ist B <=> C, aber B = false und C = true, dann haben wir ein Paradoxon. Und dies kann keine notwendige Bedingung für A verifizieren. Ich versuche nicht, wie du vielleicht vermutest, aus C etwas für A zu folgern, sondern von C auf B.