Entscheidbarkeit und „Wahrheitswert“

Es ist wahr, dass, wenn eine Aussage unentscheidbar ist (dh in einem bestimmten deduktiven System nicht auf die eine oder andere Weise beweisbar ist), es Modelle gibt, in denen sie wahr ist, und Modelle, in denen sie falsch ist. Dies ist jedoch nicht die einzige Möglichkeit zu interpretieren, „ob der Wahrheitswert der Aussage wohldefiniert ist“ . Im Fall von$\mathbb{N}$, insbesondere ist es üblich zu glauben, dass es die "tatsächlichen" natürlichen Zahlen gibt$0, 1, 2, 3, \ldots$, und alle anderen Modelle der Arithmetik sind gefälschte oder nicht standardisierte Modelle. In diesem Sinne glauben wir Folgendes: Jede Aussage über die natürlichen Zahlen ist entweder wahr oder falsch. (Dies gilt sogar in der mathematischen Logik, wo wir beispielsweise über Eigenschaften der „Standard“- und „Nichtstandard“-Modelle sprechen$\mathbb{N}$.)

Der Satz von Gödel kann jedoch so interpretiert werden, dass er genau diese Behauptung in Frage stellt! Schließlich können wir die Menge der natürlichen Zahlen nie genau beschreiben$\mathbb{N}$– weder in PA, noch in ZFC, noch in irgendeiner anderen (rekursiv axiomatisierbaren) Theorie – dann gibt es wirklich nur eine$\mathbb{N}$das existiert? Macht es wirklich Sinn zu sagen, dass jede Aussage über die natürlichen Zahlen entweder wahr oder falsch ist?

Manche würden ja sagen, manche nein. Es ist eine philosophische Angelegenheit, denn die Frage ist, ob Sie glauben, dass es da draußen ein ideales mathematisches Universum jenseits dessen gibt, was wir jemals formalisieren können. Das ist die Kontroverse, über die Wikipedia in diesem Absatz spricht.

Nehmen wir als Beispiel den Gödel-Satz G für PA (erster Ordnung), der in PA unentscheidbar ist. Es ist auch wahr, denn es behauptet, dass ein (Gödelzahl von a) Beweis für sich selbst nicht existiert, und tatsächlich existiert diese Zahl/Beweis nicht.

Und doch sagt das der Vollständigkeitssatz seit PA+$\lnot$G ist konsistent, es hat ein Modell, dh einige Interpretationen der Arithmetik erster Ordnung haben G falsch.

Ist G also wahr oder falsch oder keines von beiden? Es ist wahr als wörtliche Aussage über Zahlen, und doch ist klar, dass es PA-Modelle gibt, die in beide Richtungen gehen. Alles, was dieser zweite Teil uns wirklich sagt, ist, dass es PA-Modelle gibt, in denen einige falsche Aussagen über Zahlen wahr sind. Die Axiome von PA reichen nicht aus, um ein Modell der Arithmetik eindeutig zu spezifizieren. Diese anderen Modelle existieren tatsächlich und werden als Nicht-Standard-Modelle von PA bezeichnet . Das Modell von PA kennen wir in der Liebe – wo das Universum ist$\mathbb N$und die Symbole$0,$ $S,$ $+$in der Sprache der Arithmetik haben ihre üblichen Interpretationen - wird das Standardmodell von PA genannt.

Der Schlüssel hier ist, dass wir uns auf ein bestimmtes Modell beziehen, wenn wir sagen, dass etwas wahr ist. Etwas heikler wird es zum Beispiel in der ZFC-Mengentheorie, wo es kein vereinbartes „korrektes“ Modell gibt, das die „mengentheoretische Wahrheit“ definiert.

Ich denke, dieser Satz ist nicht 100% genau, sollte aber bedeuten:

Die Unentscheidbarkeit eines Satzes gegenüber einem deduktiven System besteht lediglich darin, ob dieses System den Satz beweist oder widerlegt, und ist eine rein syntaktische Angelegenheit (zumindest wenn Sie an die klassischen Eigenschaften endlicher Zeichenketten aus einem endlichen Alphabet glauben). Das hat nichts mit semantischer Wahrheit des Satzes unabhängig vom deduktiven System zu tun. Im Fall der natürlichen Zahlen glauben wir vielleicht, dass sie durch Codierung als endliche Zeichenfolgen in die physikalische Welt eingebettet werden können, wobei in diesem Fall jeder arithmetische Satz einen wohldefinierten Wahrheitswert hat. In anderen Fällen, wie z. B. der ZFC-Mengentheorie, ist keine physische Einbettung bekannt, und daher gibt es Grund zu der Annahme, dass jeder Satz über ZFC einen genau definierten Wahrheitswert hat, und ist daher umstrittener.

Auch wenn jeder Satz über einem System einen wohldefinierten Wahrheitswert hat (nicht schlecht spezifiziert), bedeutet dies nicht, dass wir diesen Wahrheitswert jemals auch nur im Prinzip kennen können. Selbst wenn zum Beispiel „wahre natürliche Zahlen“ eine physikalische Einbettung haben, ist es uns möglicherweise nicht möglich, den Wahrheitswert eines arithmetischen Satzes zu bestimmen.

Außerdem würde ich folgendes hinzufügen.

Erstens, wenn wir glauben, dass der Begriff der Beweisbarkeit wohldefiniert ist, müssen wir auch glauben, dass jeder$Σ_1$-Satz hat einen wohldefinierten Wahrheitswert. Aber dann ist es natürlich zu glauben, dass jeder arithmetische Satz auch einen wohldefinierten Wahrheitswert hat, wie folgt. A$Π_2$-Satz behauptet die Wahrheit von$P(n)$für jeden Naturmenschen$n$, Wo$P$ist etwas$Σ_1$-Satz. Seit$P(n)$hat für jeden Natural einen wohldefinierten Wahrheitswert$n$(beim Ersetzen des Begriffs darstellen$n$für den Parameter in$P$), haben wir, dass entweder alle wahr sind oder mindestens eine falsch ist, also das Original$Π_2$-Satz hat auch einen genau definierten Wahrheitswert. Natürlich ist dies ein philosophisches Argument, also kann man es bestreiten, aber die anfängliche Annahme, dass jeder$Σ_1$-Satz einen wohldefinierten Wahrheitswert hat, ist ein weitaus größerer Sprung als von diesem zu allen arithmetischen Sätzen. Weitere Informationen finden Sie in diesem Beitrag zu Bausteinen .

Zweitens gibt es keinen rein mathematischen Weg, um die natürlichen Zahlen festzulegen, wie aus der Existenz von Nicht-Standardmodellen eines rekursiven deduktiven Systems für sie ersichtlich ist. Es ist auch unmöglich, PA zweiter Ordnung zu verwenden, um sie festzulegen, da die Kategorisierung relativ zum Metasystem ist. Wie in diesem Beitrag weiter erläutert, ist jede mathematische Begründung für die natürlichen Zahlen zwangsläufig zirkulär, und es scheint, dass es nicht einmal eine physikalische Begründung dafür gibt, dass es eine exakte reale Einbettung eines PA-Modells gibt, trotz seiner unglaublichen Genauigkeit beim Menschen Waage.

Drittens, selbst wenn wir von der Existenz des „wahren Modells“ ausgehen,$N$von PA, es hilft uns nicht einmal, "die wahren Untersammlungen" von zu bestimmen$N$. Beachten Sie, dass jede Theorie erster Ordnung (einschließlich ZFC) ein zählbares Modell haben wird, wenn sie konsistent ist. Also irgendeine Theorie erster Ordnung$T$das axiomatisiert die Untersammlungen von$N$wird ein zählbares Modell haben, aber sehr schwache Annahmen zwingen uns dazu, dies auch innerhalb eines beliebigen Modells von zu akzeptieren$T$die Untersammlungen von$N$sind unzählbar. Dies lässt sich sehr konkret per Pair-Encoding ausdrücken als „$\neg \exists X ⊆ N\ \forall Y ⊆ N\ \exists c \in N\ \forall k \in N\ ( k \in Y ⇔ pair(c,k) \in X )$", Wo$pair$ist irgendeine sinnvolle Verschlüsselungsfunktion an$N$. Wenn so$X$existierte, lassen Sie$Z = \{ k : k \in N \land pair(k,k) \notin X \}$, welche Konstruktion in fast jedem Fundamentsystem erlaubt ist, also für jeden$c \in N$wir haben$c \in Z ⇔ pair(c,c) \in X$durch die definierende Eigenschaft von$X$Aber$c \in Z ⇔ pair(c,c) \notin X$per Definition von$Z$, und damit Widerspruch.

Viertens, selbst wenn wir die Existenz des „wahren Modells“ von ZFC annehmen, kann es aufgrund des Gründungsaxioms selbst kein Objekt (Set) im Modell selbst sein, obwohl es wie ein Set ist. Genauer gesagt, wenn wir „Modell“ innerhalb von ZFC definieren, können wir zeigen, dass jedes (Mengen-)Modell von ZFC sich selbst nicht als Element hat. Dieses Problem verschwindet nicht, wenn wir 'Klassen'-Modelle von ZFC betrachten, weil solche Modelle nur Mengen als Elemente haben. Dies ist ein möglicher Grund, warum es sehr umstritten ist anzunehmen, dass es sinnvoll ist, von der Existenz eines „echten Modells“ von ZFC auszugehen.

Fünftens kann bezüglich der Bestimmung des Wahrheitswertes von arithmetischen Sätzen argumentiert werden, dass wir im Prinzip den Wahrheitswert von wahr bestimmen können, selbst wenn es eine reale Einbettung von Naturalien gibt$Σ_1$-Sätze, denn schließlich werden wir einen Zeugen finden. Aber wir können den Wahrheitswert von falsch nicht rechnerisch verifizieren$Σ_1$-Sätze, sonst können wir das Halteproblem lösen. Schlimmer noch, auch wenn wir irgendwie den Wahrheitswert von allem bestimmen können$Σ_n$-Sätze bedeutet dies nicht, dass wir dasselbe tun können$Σ_{n+1}$-Sätze, da sich das Halteproblem auf die relativiert$n$-ten Turing-Sprung lässt sich nicht lösen, indem man ein Wahrheitsorakel für alle hat$Σ_n$-Sätze. Dies wird in diesem verwandten Beitrag kurz skizziert .

Unentscheidbar ist unter bestimmten deduktiven Systemen unentscheidbar. Entscheidbar bedeutet, dass es sich um ein Theorem handelt oder seine Negation ein Theorem ist, in einem ganz bestimmten Sinne verstanden. Ein Theorem ist hier die letzte Zeile einer Liste von Aussagen, so dass jede von ihnen ist

• ein Axiom
• ein Satz bereits bewiesen (ich weiß, das klingt irgendwie kreisförmig, versuche nur, eine Idee zu geben)
• das Ergebnis der Anwendung von Modus Ponens oder einiger anderer logischer Regeln auf vorherige Zeilen der Liste.

Wenn die Anzahl der Axiome endlich oder aufzählbar ist, ist es "einfach", über alle derartigen möglichen Listen nachzudenken. Die Frage ist: Jedes mögliche Prädikat wird ein Theorem sein oder seine Negation wird ein Theorem sein? Oder gibt es Eigenschaften, die Sie aussprechen können, die aber keine Theoreme sind, und ihre Negationen sind auch keine Theoreme? Das ist alles, was Unvollständigkeit zumindest aus rein syntaktischer Sicht bedeutet.

In Bezug auf Ihre Beobachtung würde ich nicht sagen, dass die Formulierung des von Ihnen zitierten Absatzes falsch ist, aber es wird ein wenig verwirrend, da es Ergebnisse zur Unentscheidbarkeit (wie Gödels Unvollständigkeitssatz) gibt, die das Problem des Wahrheitswerts ansprechen: es präsentiert uns mit ein Satz, der im vorigen Sinne unentscheidbar, aber dennoch wahr ist (und daher einen wohldefinierten Wahrheitswert hat).

Das Zitat sagt so etwas wie "Unentscheidbarkeit spricht nicht die Frage an, ob der Wahrheitswert wohldefiniert ist", und nun ja ... Nein: "Unentscheidbarkeit" nicht; Gödel vielleicht. =S

Sicherlich kann und sollte dieser Absatz verbessert werden. Sie können die Genauigkeit Ihrer Sprache niemals übertreiben, wenn Sie über diese Themen schreiben.