Wie beweist man Beweisbarkeit?
Hallo liebe Mathefans und Logikisten ;)
Ich bin in letzter Zeit häufig bei meinen Recherchen über mathematische Themen auf diesen Satz gestoßen: "Mathematiker X hat bewiesen, dass man das Problem nicht beweisen kann"
Die Frage die ich mir jetzt stelle, wie funktioniert das? Wie zeigt man, dass sich ein Problem lösen lässt, oder eben nicht? Ist das Problemspezifisch oder kann man ähnliche Methoden auf alle Probleme anwenden? Bei welchen Problemen findet man sowas?
6 Antworten
Die Frage die ich mir jetzt stelle, wie funktioniert das?
Das ist generell ein Problem der mathematischen Logik. Bei der "intuitiven" Anwendung der Logik, wie sie in den ersten Semestern und auch in einem großen Teil des Mathematikstudiums verwendet wird kommt so etwas überhaupt nicht vor.
Um überhaupt über "Beweisbar" oder "nicht beweisbar" zu reden, muß man zunächst eine grundlegende Axiomatisierung nicht nur der "Rechenoperationen" (wie dies z.B. bei der Axiomatisierung der reellen Zahlen geleistet wird), sondern auch der logischen Schlußfolgerungen einführen. Ein Beispiel dafür ist die
https://de.wikipedia.org/wiki/Pr%C3%A4dikatenlogik
Innerhalb dieses Logiksystems gilt dann eine Aussage als "beweisbar" wenn sie über die logischen Operationen auf ein oder mehrere Axiome zurückgeführt werden kann.
Ein klassisches Beispiel dafür ist das sogenannte Halteproblem. Es ist nicht durch eine endliche Kette von logischen Schlußfolgerungen entscheidbar, ob ein beliebiger in einem formalen System beschriebener Algorithmus für eine Eingabe irgendwann anhalten wird oder nicht.
Kurt Gödel, der hier schon von vielen erwähnt wurde, hat das Thema der Beweisbarkeit von Aussagen in Axiomensystemen auf eine höhere Stufe gehoben, indem er gezeigt hat das solche Probleme wie das Halteproblem in jedem formalen System entsteht, das mindestens die Arithmetik der natürlichen Zahlen beschreiben kann. Damit hat er dem sogenannten
https://de.wikipedia.org/wiki/Hilbertprogramm
nämlich der vollständigen und widerspruchsfreien Beschreibung der Mathematik, einen schweren Schlag versetzt.
Danke für die Blumen, aber es gibt da sicher qualifizierte als mich :-). Ich habe noch vergessen zu erwähnen das sowohl formale Logik wie auch Mengenlehre im Mathematikstudium klassisch zu kurz kommen und eben eher intuitiv verwendet werden. Mengenlehre ist ein Wahlfach in höheren Semestern und formale Logik wird eher im Informatikstudium (theoretische Informatik) oder im Philosophiestudium gelehrt. Um diese Themen als Mathematiker zu erlernen muß man schon Eigeninitiative zeigen.
Gödel hat sich in seinem Unvollständigkeitssatz mit solchen Fragen sehr eingehend beschäftigt. Es kann in einem Kontext Aussagen geben, die sich mit den Mitteln der im Kontext anzuwendenden Regeln weder beweisen noch widerlegen lassen.
Ein schönes Beispiel ist hier ebenfalls angegeben.
Der Beweis ist hier zu finden:
Die Berechenbarkeit bzw. Das Fehlen davon wurde dadurch bewiesen, dass man erst eine Codierung definiert, die beliebige Programme in eine Zahl umsetzt und umgekehrt. Damit sind alle berechenbaren Programme natürliche Zahlen.
Dann konstruierst Du eine Funktion F die für x terminiert wenn das zugehörige Programm x selbst nicht terminiert und terminiert wenn das Programm x terminiert. F(x) ist nicht berechenbar, da wenn es ein Programm y gäbe, das F(x) umsetzt, y unmöglich wäre. Es müsste, um alle Bedingungen zu erfüllen, gleichzeitig terminieren und nicht terminieren.
Die ersten Beweise dieser Art hat Georg Cantor gemacht, um die Überabzählbarkeit von Mengen zu beweisen. Wer das Ganze auf Betechenbarkeit angewendet hat, weiß ich nicht
Es gibt philosophisch gesehen garkeine Beweise für irgendwas.
Du könntest immer noch das Gehirn im Tank sein und Die Welt dir nur vorgegaukelt.
Ich weiß dass ich nichts weiß.
Es gibt viele bewiesene Dinge. Fangen wir mal an mit der fundamentalsten Sache an:
Es gibt das nichts. Denn: Es gibt das Bewusstsein, und es gibt das Denken. Das heißt, dass es das nichts gibt, was nämlich die Abwesenheit dieser existenten Sachen ist. Mit der leeren Menge kann man dann die gesamten Zahlen definieren. Philosophische Sicht muss immer hinterfragt werden, eben, weil es so einfach fällt, falsche Schlüsse zu ziehen, oder sogar, wie du selber, falsch zu zitieren.
Es heißt nicht "Ich weiß, dass ich nichts weiß", sondern das Zitat war: "Ich weiß, dass ich nicht weiß". Der Unterschied sollte deutlich sein.
Nur weil es das Denken gibt heißt das nicht dass es das Nichts gibt, vielleicht gibt es ja auch nur das Alles. Es ist nicht überprüfbar genauso wenig was deine Gedanken sind, wo sie herkommen und ob es eine Welt gibt zu der sie passen. Vielleicht bist du ja auch nur ein Gedanke den ein anderes Wesen aus einer anderen Dimension hat.
Zitiert habe ich auch garnicht das war dann wohl meine eigene Feststellung.
Das gibt es sogar für die gesamte Mathematik an sich
https://de.m.wikipedia.org/wiki/G%C3%B6delscher_Unvollst%C3%A4ndigkeitssatz
Im wesentlichen beweist dieser, dass es Probleme in der Mathematik gibt welche nicht lösbar sind und das ganz allgemein.
Die spezifischen Beweise für einzelne Dinge sind aber oftmals auf das Problem angepasst folgen aber im wesentlichen des Strukturen des direkten und indirekten Beweises auf einer etwas abstrakterem Ebene. Ein Beweis der Unbeweisbarkeit einer These kann zB durch Widerspruch erfolgen, also man überlegt sich was bedeutet die Beweisbarkeit und versucht nun einen Widerspruch daraus herzuleiten wordurch bewiesen ist, dass das Problem selbst nicht Beweisbar ist.
Danke :) Du bringst immer verlässliche, gestütze Antworten! :)