Können wir wissen, ob die selbstreferenzielle Aussage: „Es ist nicht möglich, abzuleiten, ob P1 wahr oder falsch ist“ unentscheidbar ist?

Update: Einfache, prägnante Version

Danke an Nick R für den Hinweis in die richtige Richtung.

Die Aussage P0: „Diese Aussage ist falsch“ ist unentscheidbar.
Auch die Aussage P1: „diese Aussage ist unentscheidbar“ ist unentscheidbar.

Es kann nachgewiesen werden, dass P0 unentscheidbar ist, P1 jedoch nicht. Wie könnte man diese verschiedenen "Ebenen" der Unentscheidbarkeit kategorisieren?

Ursprüngliche Frage

Betrachten wir zunächst die grundlegende widersprüchliche Selbstreferenz:

P0 = "Aussage P0 ist falsch"

P0 kann ohne Widerspruch weder wahr noch falsch sein. Dies ist ähnlich wie NaN (Not a Number) in der Mathematik, nur mit booleschen statt numerischen Werten. Lassen Sie uns den Wahrheitswert von P0 als NaB (Not a Boolean) definieren.

Die Aussage im Titel:

P1 = "Es ist nicht möglich abzuleiten, ob P1 wahr oder falsch ist"

ist insofern ähnlich, als es auf sich selbst verweist, sich aber nicht direkt widerspricht. Ist der Wahrheitswert von P1 derselbe wie der von P0, den ich NaB definiert habe, oder etwas anderes? Eine komplexere Klasse von Instabilitäten?

  • Wenn P1 falsch ist, dann sollte es möglich sein, dies abzuleiten. Dh es muss gezeigt werden, dass die Wahrheit von P1 zu einem Widerspruch führt.
  • Wenn P1 wahr ist, dann könnte es sehr wohl so sein, wir wissen es nur nicht.

Beide Optionen sind möglich - keine kann ausgeschlossen werden, daher ist es nicht möglich, den Wahrheitswert von P1 abzuleiten.

Aber genau das sagt P1, also haben wir gerade bewiesen, dass es wahr ist! Anders als bei P0 macht es selbst die Annahme, dass es weder wahr noch falsch ist, wieder zu wahr. Fast so, als würde es zwischen nicht 2, sondern 3 Werten oszillieren (wahr, falsch, keiner von beiden).

Bedeutet dies, dass der Wahrheitswert von P1 eine Art Meta-NaB ist: "Weder ein Boolean noch ein NaB"?

EDIT: Zur Klarstellung nochmal umformuliert. Die Frage bezieht sich auf P1, nicht auf P0. P0 ist nur dort für den Vergleich ohne Bezug

Einige (wenn auch sehr wenige!) Menschen akzeptieren, dass die Aussage „Diese Aussage ist falsch“ wahr und falsch ist. Noch mehr Leute (aber immer noch wenige!) denken, dass man nicht allen Aussagen einzelne Wahrheitswerte zuweisen kann oder sollte (insbesondere: konstruktive Logik kann nicht mit einer endlichen Menge von Wahrheitswerten formalisiert werden)
@virmaior OK, diesen Teil entfernt, da er für die Frage nicht relevant ist.
Beweisbarkeit und Wahrheit sind nicht dasselbe. Die Aussage kann wahr und unbeweisbar sein. Daran ist nichts auszusetzen. (Das bezieht sich auf Ihr "Wenn es falsch ist, sollte es möglich sein, es zu beweisen.")
Auf welcher Grundlage sagen Sie? It can't be either true or false. Die Idee, dass es wahr oder falsch sein muss, ist ein Schlüsselmerkmal der Bivalenz, die die meisten Formen der Logik definiert. Auch hier wird, wie bei meinem vorherigen Kommentar, die Hauptfrage die Reihenfolge der Bewertung sein, um festzustellen, ob es wahr oder falsch ist.
Sie können Liar Paradox und Self-Reference für Diskussionen und Ansätze mit dreiwertiger Logik sehen, bei denen ein selbstreferenzieller Satz den Wert undefined erhält .
@virmaior Häh? Was meinst du mit "den meisten Formen der Logik"? Ich denke, das Gegenteil gilt: Die meisten Logiken, die Menschen interessieren, sind nicht zweiwertig.
Es scheint Verwirrung über die Frage zu geben, wie soll ich sie umformulieren? Die Frage bezieht sich auf diese Aussage: "Es ist nicht möglich abzuleiten, ob diese Aussage wahr oder falsch ist". Der einfache Widerspruch dient nur zum Vergleich und zur Definition von "NaB".
Ich kann es als Axiom akzeptieren. In diesem Fall ist es wahr, aber ich habe nicht gefolgert, dass es wahr ist, ich habe es gewählt. So braucht man nicht auf seine Wahrheit zu schließen, und es bleibt wahr.
Ich verstehe die SE-beantwortbare Frage in all dem immer noch nicht vollständig, aber es scheint sich in Richtung Klarheit zu bewegen ...

Antworten (2)

Ich bin kein Experte auf diesem Gebiet, also möchte mich vielleicht jemand korrigieren.

Da Sie dies anscheinend formal betrachten möchten, beginnen wir mit einer formalen Betrachtung des Problems.

In einer formalen Umgebung heißt eine Aussage P nicht entscheidbar , wenn es unmöglich ist, P zu beweisen, und es unmöglich ist, nicht (P) zu beweisen.

Beachten Sie, dass Beweisbarkeit hier ein rein syntaktischer Begriff ist. Andererseits ist Wahrheit ein semantischer Begriff, und wir sagen, dass eine Aussage in einem formalen System wahr ist, wenn sie beweisbar ist; mit anderen Worten, wir sagen, eine Aussage ist wahr, wenn es sich um ein Theorem handelt.

Vor diesem Hintergrund können wir Ihre Aussage P1 wie folgt wiederholen:

P1 = Die Aussage P1 ist nicht entscheidbar.

Wenn ich mich nicht irre, ist diese Aussage das berechenbarkeitstheoretische Äquivalent des Gödel-Satzes „Diese Aussage ist nicht beweisbar“. Der Gödel-Satz eines formalen Systems ist der Satz, den Gödel in eine Aussage über Mengen natürlicher Zahlen codierte, um seinen Unvollständigkeitssatz zu beweisen. Der Beweis zeigt, dass der Gödelsatz nicht entscheidbar ist.

Durch einen analogen Beweis in der Berechenbarkeitstheorie ist Ihre Aussage P1 (in ihrer modifizierten Form) nicht entscheidbar, was bedeutet, dass es keinen Algorithmus gibt, um festzustellen, ob sie gültig oder nicht gültig ist - dh entweder wahr oder falsch.

Wenn dies richtig ist, dann ist es richtig, P1 "NaB" zu nennen. Aber wie gesagt, ich bin kein Experte auf diesem Gebiet, vielleicht kann mich jemand korrigieren.

Das wäre also eine formale Behandlung der Aussage P1. Wenn wir uns P1 informell ansehen wollen, dann ist die übliche Art, damit umzugehen, meiner Meinung nach, abzustreiten, dass P1 irgendeinen sinnvollen Inhalt hat.

Dies ist sicherlich eine bessere Formulierung und Gödels Satz ist eng verwandt. Trotzdem zögere ich zu akzeptieren. Ich habe die Frage mit einer treffenderen Zusammenfassung aktualisiert.
Sie unterscheiden zu Recht zwischen Beweisbarkeit als syntaktischem Begriff und Wahrheit als semantischem Begriff. Aber dann sagen Sie weiter, dass eine Aussage wahr ist, wenn sie beweisbar ist. Meinen Sie das als Ergebnis des Korrektheitssatzes oder als Definitionssache? Die Umkehrung gilt natürlich nicht immer (dh einige wahre Aussagen sind nicht beweisbar).
Also ist P1 nicht entscheidbar. Aber P1 besagt, dass P1 nicht entscheidbar ist, also ist P1 wahr. Kann eine Aussage sowohl unentscheidbar als auch wahr sein?
@EliranH Nach meinem „hauchdünnen“ Verständnis des Themas sagen wir, dass eine Aussage in Bezug auf die Theorie wahr ist, wenn sie beweisbar ist - dh die wahren Aussagen einer Theorie sind genau die Theoreme der Theorie. Vielleicht hätte ich das Wort gültig statt wahr verwenden sollen . Die durch Gödels Theorem identifizierten unbeweisbaren Wahrheiten sind keine Theoreme, also sind sie keine Wahrheiten in Bezug auf die Theorie. (Fortsetzung...)
(... Fortsetzung) Ich würde sagen, dass die Beschreibung unbeweisbarer Wahrheiten als wahr die Erweiterung der semantischen Komponente der Theorie über die Theorie selbst hinaus erfordern würde, um „metatheoretische“ Argumente einzubeziehen. Wahrscheinlich bin ich hier falsch. Ich bin mir nicht sicher, was Sie mit dem „Korrektheitssatz“ meinen. Ich glaube, dass eine Theorie solide ist, wenn ihre Theoreme in Bezug auf ihre Semantik und tatsächlich alle Interpretationen der Semantik der Theorie gültig / wahr sind. (Ich habe den letzten Teil – „alle Interpretationen …“ – aus dem Wiki genommen, falls Sie es nicht sagen konnten.) Es ist ein faszinierendes Thema und ich hoffe, es eines Tages besser zu verstehen.
@LuísHenrique Wenn P1 nachweislich wahr ist, scheint es semantisch falsch zu sein. Wenn P1 beweisbar falsch ist, dann scheint die Aussage nicht(P1) semantisch wahr zu sein. In beiden Fällen ist P1 semantisch falsch. Sicherlich kann eine Aussage sowohl unentscheidbar als auch wahr sein. Dies ist genau die Situation, die von Gödels Unvollständigkeitssatz identifiziert wird.
Vielleicht müssen wir den Unterschied zwischen "unentscheidbar" und "nicht nachweisbar" diskutieren? Wenn wir mit Sicherheit sagen können, dass S eine unentscheidbare Aussage ist, dann ist sie „nachweislich unentscheidbar“? Wenn jedoch eine Aussage unentscheidbar ist, wir sie aber nicht beweisen können (dh S1 = „ S ist unentscheidbar“ ist ebenso unentscheidbar), ist dies ein anderer Status, nicht wahr?
@LuísHenrique Ja und nein - zumindest nach meinem Verständnis. Die Unentscheidbarkeit von P1 impliziert, dass Entscheidbarkeit nicht entscheidbar ist, also ist "ja", Entscheidbarkeit nicht "demonstrierbar", wobei "demonstrierbar" = "entscheidbar". In Bezug auf S1 ist "nein", S1 jedoch nicht unentscheidbar. Wenn wir wissen, dass S unentscheidbar ist, dann können wir definitionsgemäß S nicht beweisen und wir können nicht nicht (S) beweisen, also ist die Aussage S1 = „ S ist unentscheidbar“ entscheidbar, nicht unentscheidbar. Wir haben es bewiesen und daher ist es ein Theorem, also ist sein semantischer Wahrheitsstatus "wahr".
Ich bin mir ziemlich sicher, dass P0 nicht unentscheidbar ist, aber einfach keine Aussage. Die ganze Logik davon baut darauf auf, dass Aussagen tatsächlich wahr oder falsch sind (und weder beides noch dazwischen). P0 ist selbstwidersprüchlich und somit (iirc) nicht einmal eine Aussage . P1 ist jedoch unentscheidbar: Angenommen, P1 wäre richtig, könnten wir es nicht ableiten; vorausgesetzt, es ist nicht, könnten wir. Aber bis eine Turing-Maschine, die diese Frage beantwortet (die nur stoppen würde, wenn P1 falsch ist), tatsächlich stoppt, können wir jetzt nicht. Ich denke, das nennt man semi-entscheidbar

„Diese Aussage ist falsch“

Dies impliziert zwei unterschiedliche Aussagen:

  1. Dies ist eine Aussage; und
  2. Die Aussage in 1. ist falsch.

Aber ich bin mir nicht sicher, ob 1. trivial ist. Dies ist eine "Aussage über Aussagen" oder eine Meta-Aussage (genauer gesagt eine Meta-Aussage der Stufe 1), daher bin ich mir nicht sicher, ob es zulässig ist, sie eine "Aussage" zu nennen. Wenn nicht, dann ist es falsch, weil 1. oben falsch ist.

Darüber kann man natürlich streiten

"Diese Meta-Aussage ist falsch"

entsteht in den Problemen, die Sie zeigen. Aber dann ist dies eine Meta-Aussage Ebene 2, dh eine Meta-Aussage über eine Meta-Aussage, und jeder Versuch, eine Ebene für eine Meta-Aussage zu behaupten, führt zu einer Meta-Aussage höherer Ebene; „Diese Meta-Aussage der Stufe 546 ist falsch“ ist eine Meta-Aussage der Stufe 547.

Bitte beachten Sie die geklärte Frage. Ich denke nicht, dass es eine "Aussage über Aussagen" ist, sondern eher eine "Aussage über Logik bezüglich Aussagen"
P1 ist eine Aussage über P0. Wenn P0 eine Meta-Aussage ist und Meta-Aussagen keine Aussagen sind, dann ist P0 falsch, ebenso wie P1, weil es behauptet, es sei unmöglich abzuleiten, ob P0 wahr oder falsch ist, und P0 falsch ist.
P1 verweist nur auf P1 selbst. P0 ist separat und wird nur zum Vergleich im selben Beitrag erwähnt.
Ah ja. Entschuldigung, ich habe P1 falsch verstanden.
Können wir wissen, ob die selbstreferenzielle Aussage: „Es ist nicht möglich, abzuleiten, ob P1 wahr oder falsch ist“ unentscheidbar ist?
AntwortenHierDatenschutz-Bestimmungen1y, 0v