Warum ist die Logik erster Ordnung (ohne Arithmetik) VALIDITY nur rekursiv aufzählbar und nicht rekursiv?

Papadimitrious "Computational Complexity" besagt, dass VALIDITY, das Problem der Entscheidung, ob eine logische Formel erster Ordnung (ohne Arithmetik) gültig ist, rekursiv aufzählbar ist. Dies folgt aus den Vollständigkeits- und Soliditätssätzen, die GÜLTIGKEIT und THEOREMHOOD gleichsetzen, wobei letzteres das Problem ist, einen Beweis für eine Formel zu finden, von der zuvor gezeigt wurde, dass sie rekursiv aufzählbar ist.

Ich verstehe jedoch nicht, warum VALIDITY nicht auch rekursiv ist, da bei einer gegebenen Formel zwei Turing-Maschinen für THEOREMHOOD gleichzeitig ausgeführt werden können, eine auf und die andere auf . Da mindestens einer von ihnen gültig ist, kann immer entschieden werden, ob gültig ist oder nicht. Was vermisse ich? $\phi$ $\phi$ $\neg \phi$ $\phi$

Anmerkung: Diese Frage bezieht sich auf Logik erster Ordnung ohne Arithmetik, daher hat Gödels Unvollständigkeitssatz hier keine Bedeutung.

complexity-theory undecidability first-order-logic user118967
quelle

Relevant (glaube ich): en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems

Antworten:

Ich verstehe jedoch nicht, warum VALIDITY nicht auch rekursiv ist, da bei einer gegebenen Formel zwei Turing-Maschinen für THEOREMHOOD gleichzeitig ausgeführt werden können, eine auf und die andere auf . Da mindestens einer von ihnen gültig ist, kann immer entschieden werden, ob gültig ist oder nicht. Was vermisse ich? $\phi$ $\phi$ $\neg \phi$ $\phi$

Das ist falsch. Eine Formel ist gültig, wenn sie in allen Modellen gilt. $\phi$

Es ist nicht wahr, dass mindestens eines von und gültig sein muss: Beide können in einigen Modellen gelten, aber nicht in allen. $\phi$ $\lnot\phi$

Triviales Beispiel: Nehmen Sie FOL mit zwei konstanten Symbolen und der Formel . Dann gilt in einigen Modellen (diejenigen, die und mit demselben Punkt interpretieren ), aber nicht in allen (ein Modell kann sie bestimmten Punkten zuordnen). Und tatsächlich kann FOL weder noch beweisen . ${\sf a}, {\sf b}$ $\phi \equiv {\sf a}={\sf b}$ $\phi$ $\sf a$ $\sf b$ ${\sf a} = {\sf b}$ ${\sf a} \neq {\sf b}$

Chi
quelle

Vielen Dank, dass Sie herausgefunden haben, was mir gefehlt hat. Das macht Sinn. Aber dann denke ich, dass die Menge der gültigen Sätze (Formeln ohne freie Variablen) dann rekursiv ist, da in diesem Fall entweder oder gültig sein muss.

ϕ

$\phi$

\neg ϕ

$\neg \phi$

user118967

Nee. ist in Modellen mit nur einem Element wahr und in Modellen mit mehr als einem Element falsch. Es ist nicht gültig, nicht seine Negation. Und keine freien Variablen.

\forall x, y . x = y

$\forall x, y.\ x=y$

Chi

Eigentlich etwas mehr darüber nachdenken. Wenn die Menge der gültigen Sätze rekursiv ist, kann ich zeigen, dass die Menge der gültigen Formeln auch rekursiv ist, indem ich Folgendes tue: Wenn eine Formel mit den Konstanten , entscheide, ob der Satz ist gültig. Wenn ja, ist gültig; Andernfalls ist nicht gültig. In beiden Fällen kann ich entscheiden, ob es sich um gültige Formeln handelt. Was vermisse ich jetzt?

ϕ

$\phi$

a_{1}, \dots, a_{m}

$a_1,\dots,a_m$

\forall a_{1}, \dots, a_{m} ϕ

$\forall a_1,\dots,a_m \phi$

ϕ

$\phi$

ϕ

$\phi$

user118967

Betrachten Sie auch - es gilt nur in Modellen, in denen die Prädikate und geeignet interpretiert werden. In FOL haben Sie Prädikate, konstante Symbole und Funktionssymbole. Auch ohne freie Variablen können Sie Prädikate usw. verwenden, um komplexe Dinge zu schreiben, die möglicherweise wahr sind oder nicht.

\forall x . p (x) ⟹ q (x)

$\forall x. \ p(x) \implies q(x)$

p

$p$

q

$q$

Chi

Natürlich ja. Dieser letzte Punkt macht wirklich alles klar. Vielen Dank.

user118967

Ein Satz erster Ordnung ist gültig, wenn er in jedem möglichen Modell wahr ist, dh wenn er für alle Entscheidungen gilt, was die Beziehungssymbole, Funktionssymbole (falls vorhanden) und konstanten Symbole bedeuten. Ein Satz ist in einem Beweissystem nachweisbar , wenn dieses Beweissystem einen Beweis des Satzes enthält.

Beachten Sie, dass Beweisbarkeit und Gültigkeit zwei getrennte Konzepte sind. Ihr Versuch, zu zeigen, dass Gültigkeit rekursiv ist, bestimmt jedoch tatsächlich die Beweisbarkeit und nicht die Gültigkeit.

Gültigkeit und Beweisbarkeit sind durch zwei weitere Begriffe miteinander verbunden:

Ein Beweissystem ist solide, wenn alles, was es beweisen kann, gültig ist, dh Sie können nur Dinge beweisen, die tatsächlich wahr sind.
Ein Beweissystem ist vollständig, wenn es alles beweisen kann, was gültig ist, dh Sie können alle Dinge beweisen, die wahr sind.

Ihre vorgeschlagene Methode wäre also in Ordnung, wenn Sie ein solides und vollständiges Beweissystem verwenden würden: Das würde bedeuten, dass Sie genau alle gültigen Sätze beweisen könnten, sodass die Entscheidung über die Beweisbarkeit dasselbe wäre wie die Entscheidung über die Gültigkeit. Leider sagen Gödels berühmte Unvollständigkeitssätze , dass es kein solides und vollständiges Beweissystem für Logik erster Ordnung gibt.

Wenn Ihr System also solide ist (es beweist nur wahre Dinge), ist es unvollständig (es beweist nicht alle wahren Dinge). Insbesondere gibt es einige Sätze so dass weder noch einen Beweis in Ihrem System haben, was bedeutet, dass Ihre Turing-Maschine bei der Eingabe nicht und daher keine Sprache entscheidet . Wenn Ihr System vollständig ist (es beweist alle wahren Dinge), dann ist es nicht in Ordnung: Es beweist mindestens eine falsche Sache, und da falsch irgendetwas impliziert, beweist es tatsächlich, dass jeder Satz gültig ist. In diesem Fall entscheidet die Turing-Maschine, von der Sie dachten, sie würde über die Gültigkeit entscheiden, tatsächlich über . $\varphi$ $\varphi$ $\neg\varphi$ $\varphi$ $\Sigma^*$

David Richerby
quelle

Ihre Verwendung des Unvollständigkeitssatzes bezieht sich auf Logik erster Ordnung mit Arithmetik, aber meine Frage bezieht sich auf reine Logik erster Ordnung, für die es ein solides und vollständiges Beweissystem gibt, gemäß dem Buch, das ich lese, und Gödels Vollständigkeitssatz. Daher denke ich, dass meine Frage an dieser Stelle unbeantwortet bleibt (ich werde es klären).

user118967

Entweder ist Ihr Beweissystem leistungsfähig genug, um Aussagen über Arithmetik erster Ordnung zu beweisen. In diesem Fall gilt Goedel oder nicht. In diesem Fall kann es offensichtlich nicht alle wahren Aussagen erster Ordnung beweisen, da es nicht beweisen kann diejenigen über Arithmetik.

David Richerby

Recht. Aber ich spreche von Logik erster Ordnung ohne Arithmetik, während Sie von FOL mit Arithmetik sprechen . Für FOL ohne Arithmetik gibt es in der Tat ein solides und vollständiges Beweissystem. Die Gesamtheit der Frage, einschließlich der Definition von GÜLTIGKEIT, bezieht sich auf FOL ohne Arithmetik. In diesem Szenario müssen daher keine Aussagen über Arithmetik nachgewiesen werden, um die Vollständigkeit festzustellen.

user118967

Gödels Vollständigkeit Satz zeigt , dass es nicht existiert ein solide und vollständige deduktives System für Logik ersten Ordnung, so dass ein erste Ordnung Satz eine Tautologie ist, wenn und nur wenn es einen endlichen Abzug hat. Der Unvollständigkeitssatz zeigt, dass es Sätze geben kann, die formal unabhängig von den Axiomen Ihrer Theorie sind: Weder der Satz noch seine Negation sind eine Tautologie. In Bezug auf die Arithmetik zeigt der Unvollständigkeitssatz, dass das PA-Axiomschema der Induktion erster Ordnung im Gegensatz zum "wahren" Induktionsaxiom (das ein Satz zweiter Ordnung ist) versagen kann.

Mike Battaglia